# Multiagent Systems (cs.MA)

• We introduce an axiomatic approach to group recommendations, in line of previous work on the axiomatic treatment of trust-based recommendation systems, ranking systems, and other foundational work on the axiomatic approach to internet mechanisms in social choice settings. In group recommendations we wish to recommend to a group of agents, consisting of both opinionated and undecided members, a joint choice that would be acceptable to them. Such a system has many applications, such as choosing a movie or a restaurant to go to with a group of friends, recommending games for online game players, & other communal activities. Our method utilizes a given social graph to extract information on the undecided, relying on the agents influencing them. We first show that a set of fairly natural desired requirements (a.k.a axioms) leads to an impossibility, rendering mutual satisfaction of them unreachable. However, we also show a modified set of axioms that fully axiomatize a group variant of the random-walk recommendation system, expanding a previous result from the individual recommendation case.
• Many important stable matching problems are known to be NP-hard, even when strong restrictions are placed on the input. In this paper we seek to identify simple structural properties of instances of stable matching problems which will allow the design of efficient algorithms. We focus on the setting in which all agents involved in some matching problem can be partitioned into k different types, where the type of an agent determines his or her preferences, and agents have preferences over types (which may be refined by more detailed preferences within a single type). This situation could arise in practice if agents form preferences based on some small collection of agents' attributes. The notion of types could also be used if we are interested in a relaxation of stability, in which agents will only form a private arrangement if it allows them to be matched with a partner who differs from the current partner in some particularly important characteristic. We show that in this setting several well-studied NP-hard stable matching problems (such as MAX SMTI, MAX SRTI, and MAX SIZE MIN BP SMTI) belong to the parameterised complexity class FPT when parameterised by the number of different types of agents, and so admit efficient algorithms when this number of types is small.
• Rear end collisions are deadliest in nature and cause most of traffic casualties and injuries. In the existing research, many rear end collision avoidance solutions have been proposed. However, the problem with these proposed solutions is that they are highly dependent on precise mathematical models. Whereas, the real road driving is influenced by non-linear factors such as road surface situations, driver reaction time, pedestrian flow and vehicle dynamics, hence obtaining the accurate mathematical model of the vehicle control system is challenging. This problem with precise control based rear end collision avoidance schemes has been addressed using fuzzy logic, but the excessive number of fuzzy rules straightforwardly prejudice their efficiency. Furthermore, these fuzzy logic based controllers have been proposed without using proper agent based modeling that helps in mimicking the functions of an artificial human driver executing these fuzzy rules. Keeping in view these limitations, we have proposed an Enhanced Emotion Enabled Cognitive Agent (EEEC_Agent) based controller that helps the Autonomous Vehicles (AVs) to perform rear end collision avoidance with less number of rules, designed after fear emotion, and high efficiency. To introduce a fear emotion generation mechanism in EEEC_Agent, Orton, Clore & Collins (OCC) model has been employed. The fear generation mechanism of EEEC_Agent has been verified using NetLogo simulation. Furthermore, practical validation of EEEC_Agent functions has been performed using specially built prototype AV platform. Eventually, the qualitative comparative study with existing state of the art research works reflect that proposed model outperforms recent research.
• Blind spots are one of the causes of road accidents in the hilly and flat areas. These blind spot accidents can be decreased by establishing an Internet of Vehicles (IoV) using Vehicle-2-Vehicle (V2V) and Vehicle-2-Infrastrtructure (V2I) communication systems. But the problem with these IoV is that most of them are using DSRC or single Radio Access Technology (RAT) as a wireless technology, which has been proven to be failed for efficient communication between vehicles. Recently, Cognitive Radio (CR) based IoV have to be proven best wireless communication systems for vehicular networks. However, the spectrum mobility is a challenging task to keep CR based vehicular networks interoperable and has not been addressed sufficiently in existing research. In our previous research work, the Cognitive Radio Site (CR-Site) has been proposed as in-vehicle CR-device, which can be utilized to establish efficient IoV systems. H In this paper, we have introduced the Emotions Inspired Cognitive Agent (EIC_Agent) based spectrum mobility mechanism in CR-Site and proposed a novel emotions controlled spectrum mobility scheme for efficient syntactic interoperability between vehicles. For this purpose, a probabilistic deterministic finite automaton using fear factor is proposed to perform efficient spectrum mobility using fuzzy logic. In addition, the quantitative computation of different fear intensity levels has been performed with the help of fuzzy logic. The system has been tested using active data from different GSM service providers on Mangla-Mirpur road. This is supplemented by extensive simulation experiments which validate the proposed scheme for CR based high-speed vehicular networks. The qualitative comparison with the existing-state-of the-art has proven the superiority of the proposed emotions controlled syntactic interoperable spectrum mobility scheme within cognitive radio based IoV systems.
• Humans are going to delegate the rights of driving to the autonomous vehicles in near future. However, to fulfill this complicated task, there is a need for a mechanism, which enforces the autonomous vehicles to obey the road and social rules that have been practiced by well-behaved drivers. This task can be achieved by introducing social norms compliance mechanism in the autonomous vehicles. This research paper is proposing an artificial society of autonomous vehicles as an analogy of human social society. Each AV has been assigned a social personality having different social influence. Social norms have been introduced which help the AVs in making the decisions, influenced by emotions, regarding road collision avoidance. Furthermore, social norms compliance mechanism, by artificial social AVs, has been proposed using prospect based emotion i.e. fear, which is conceived from OCC model. Fuzzy logic has been employed to compute the emotions quantitatively. Then, using SimConnect approach, fuzzy values of fear has been provided to the Netlogo simulation environment to simulate artificial society of AVs. Extensive testing has been performed using the behavior space tool to find out the performance of the proposed approach in terms of the number of collisions. For comparison, the random-walk model based artificial society of AVs has been proposed as well. A comparative study with a random walk, prove that proposed approach provides a better option to tailor the autopilots of future AVS, Which will be more socially acceptable and trustworthy by their riders in terms of safe road travel.
• Making roads safer by avoiding road collisions is one of the main reasons for inventing Autonomous vehicles (AVs). In this context, designing agent-based collision avoidance components of AVs which truly represent human cognition and emotions look is a more feasible approach as agents can replace human drivers. However, to the best of our knowledge, very few human emotion and cognition-inspired agent-based studies have previously been conducted in this domain. Furthermore, these agent-based solutions have not been validated using any key validation technique. Keeping in view this lack of validation practices, we have selected state-of-the-art Emotion Enabled Cognitive Agent (EEC_Agent), which was proposed to avoid lateral collisions between semi-AVs. The architecture of EEC_Agent has been revised using Exploratory Agent Based Modeling (EABM) level of the Cognitive Agent Based Computing (CABC) framework and real-time fear emotion generation mechanism using the Ortony, Clore & Collins (OCC) model has also been introduced. Then the proposed fear generation mechanism has been validated using the Validated Agent Based Modeling level of CABC framework using a Virtual Overlay MultiAgent System (VOMAS). Extensive simulation and practical experiments demonstrate that the Enhanced EEC_Agent exhibits the capability to feel different levels of fear, according to different traffic situations and also needs a smaller Stopping Sight Distance (SSD) and Overtaking Sight Distance (OSD) as compared to human drivers.
• Agent-based modeling and simulation tools provide a mature platform for development of complex simulations. They however, have not been applied much in the domain of mainstream modeling and simulation of computer networks. In this article, we evaluate how and if these tools can offer any value-addition in the modeling & simulation of complex networks such as pervasive computing, large-scale peer-to-peer systems, and networks involving considerable environment and human/animal/habitat interaction. Specifically, we demonstrate the effectiveness of NetLogo - a tool that has been widely used in the area of agent-based social simulation.
• Threshold models and their dynamics may be used to model the spread of `behaviors' in social networks. Regarding such from a modal logical perspective, it is shown how standard update mechanisms may be emulated using action models -- graphs encoding agents' decision rules. A small class of action models capturing the possible sets of decision rules suitable for threshold models is identified, and shown to include models characterizing best-response dynamics of both coordination and anti-coordination games played on graphs.
• The 9th Semantic Ambient Media Experience (SAME) proceedings where based on the academic contributions to a two day workshop that was held at Curtin University, Perth, WA, Australia. The symposium was held to discuss visualisation, emerging media, and user-experience from various angles. The papers of this workshop are freely available through http://www.ambientmediaassociation.org/Journal under open access as provided by the International Ambient Media Association (iAMEA) Ry. iAMEA is hosting the international open access journal entitled "International Journal on Information Systems and Management in Creative eMedia", and the series entitled "International Series on Information Systems and Management in Creative eMedia". For any further information, please visit the website of the Association: http://www.ambientmediaassociation.org.
• Multi-sensor state space models underpin fusion applications in networks of sensors. Estimation of latent parameters in these models has the potential to provide highly desirable capabilities such as network self-calibration. Conventional solutions to the problem pose difficulties in scaling with the number of sensors due to the joint multi-sensor filtering involved when evaluating the parameter likelihood. In this article, we propose a separable pseudo-likelihood which is a more accurate approximation compared to a previously proposed alternative under typical operating conditions. In addition, we consider using separable likelihoods in the presence of many objects and ambiguity in associating measurements with objects that originated them. To this end, we use a state space model with a hypothesis based parameterisation, and, develop an empirical Bayesian perspective in order to evaluate separable likelihoods on this model using local filtering. Bayesian inference with this likelihood is carried out using belief propagation on the associated pairwise Markov random field. We specify a particle algorithm for latent parameter estimation in a linear Gaussian state space model and demonstrate its efficacy for network self-calibration using measurements from non-cooperative targets in comparison with alternatives.
• The key challenge in multiagent learning is learning a best response to the behaviour of other agents, which may be non-stationary: if the other agents adapt their strategy as well, the learning target moves. Disparate streams of research have approached non-stationarity from several angles, which make a variety of implicit assumptions that make it hard to keep an overview of the state of the art and to validate the innovation and significance of new works. This survey presents a coherent overview of work that addresses opponent-induced non-stationarity with tools from game theory, reinforcement learning and multi-armed bandits. Further, we reflect on the principle approaches how algorithms model and cope with this non-stationarity, arriving at a new framework and five categories (in increasing order of sophistication): ignore, forget, respond to target models, learn models, and theory of mind. A wide range of state-of-the-art algorithms is classified into a taxonomy, using these categories and key characteristics of the environment (e.g., observability) and adaptation behaviour of the opponents (e.g., smooth, abrupt). To clarify even further we present illustrative variations of one domain, contrasting the strengths and limitations of each category. Finally, we discuss in which environments the different approaches yield most merit, and point to promising avenues of future research.
• We propose a novel computational method to extract information about interactions among individuals with different behavioral states in a biological collective from ordinary video recordings. Assuming that individuals are acting as finite state machines, our method first detects discrete behavioral states of those individuals and then constructs a model of their state transitions, taking into account the positions and states of other individuals in the vicinity. We have tested the proposed method through applications to two real-world biological collectives, termites in an experimental setting and human pedestrians in an open space. For each application, a robust tracking system was developed in-house, utilizing interactive human intervention (for termite tracking) or online agent-based simulation (for pedestrian tracking). In both cases, significant interactions were detected between nearby individuals with different states, demonstrating the effectiveness of the proposed method.
• Humanity faces numerous problems of common-pool resource appropriation. This class of multi-agent social dilemma includes the problems of ensuring sustainable use of fresh water, common fisheries, grazing pastures, and irrigation systems. Abstract models of common-pool resource appropriation based on non-cooperative game theory predict that self-interested agents will generally fail to find socially positive equilibria---a phenomenon called the tragedy of the commons. However, in reality, human societies are sometimes able to discover and implement stable cooperative solutions. Decades of behavioral game theory research have sought to uncover aspects of human behavior that make this possible. Most of that work was based on laboratory experiments where participants only make a single choice: how much to appropriate. Recognizing the importance of spatial and temporal resource dynamics, a recent trend has been toward experiments in more complex real-time video game-like environments. However, standard methods of non-cooperative game theory can no longer be used to generate predictions for this case. Here we show that deep reinforcement learning can be used instead. To that end, we study the emergent behavior of groups of independently learning agents in a partially observed Markov game modeling common-pool resource appropriation. Our experiments highlight the importance of trial-and-error learning in common-pool resource appropriation and shed light on the relationship between exclusion, sustainability, and inequality.
• In this paper, we model a Stackelberg game in a simple Gaussian test channel where a human transmitter (leader) communicates a source message to a human receiver (follower). We model human decision making using prospect theory models proposed for continuous decision spaces. Assuming that the value function is the squared distortion at both the transmitter and the receiver, we analyze the effects of the weight functions at both the transmitter and the receiver on optimal communication strategies, namely encoding at the transmitter and decoding at the receiver, in the Stackelberg sense. We show that the optimal strategies for the behavioral agents in the Stackelberg sense are identical to those designed for unbiased agents. At the same time, we also show that the prospect theoretic distortions at both the transmitter and the receiver are both smaller than the expected distortion, thus making behavioral agents more contended than unbiased agents. Consequently, the presence of cognitive biases reduces the need for transmission power in order to achieve a given distortion at both transmitter and receiver.
• Aug 16 2017 cs.MA arXiv:1708.04513v1
The concept of emergence is a powerful concept to explain very complex behaviour by simple underling rules. Existing approaches of producing emergent collective behaviour have many limitations making them unable to account for the complexity we see in the real world. In this paper we propose a new dynamic, non-local, and time independent approach that uses a network like structure to implement the laws or the rules, where the mathematical equations representing the rules are converted to a series of switching decisions carried out by the network on the particles moving in the network. The proposed approach is used to generate patterns with different types of symmetry.
• We consider the optimal coverage problem where a multi-agent network is deployed in an environment with obstacles to maximize a joint event detection probability. The objective function of this problem is non-convex and no global optimum is guaranteed by gradient-based algorithms developed to date. We first show that the objective function is monotone submodular, a class of functions for which a simple greedy algorithm is known to be within 0.63 of the optimal solution. We then derive two tighter lower bounds by exploiting the curvature information (total curvature and elemental curvature) of the objective function. We further show that the tightness of these lower bounds is complementary with respect to the sensing capabilities of the agents. The greedy algorithm solution can be subsequently used as an initial point for a gradient-based algorithm to obtain solutions even closer to the global optimum. Simulation results show that this approach leads to significantly better performance relative to previously used algorithms.
• In the multi-agent systems setting, this paper addresses continuous-time distributed synchronization of columns of rotation matrices. More precisely, k specific columns shall be synchronized and only the corresponding k columns of the relative rotations between the agents are assumed to be available for the control design. When one specific column is considered, the problem is equivalent to synchronization on the (d-1)-dimensional unit sphere and when all the columns are considered the problem is equivalent to synchronization on SO(d). We design dynamic control laws that solve these synchronization problems. The control laws are based on the introduction of auxiliary variables in combination with a QR-factorization approach. The benefit of this QR-factorization approach is that we can decouple the dynamics of the k columns from the remaining d-k ones. Under the control scheme, the closed loop system achieves almost global convergence to synchronization for quasi-strong graph interaction topologies.
• Rubenstein et al. present an interesting system of programmable self-assembled structure formation using 1000 Kilobot robots. The paper claims to advance work in artificial swarms similar to capabilities of natural systems besides being highly robust. However, the system lacks in terms of matching motility and complex shapes with holes, thereby limiting practical similarity to self-assembly in living systems.
• In this paper, we propose a novel distributed formation control strategy, which is based on the measurements of relative position of neighbors, with global orientation estimation in 3-dimensional space. Since agents do not share a common reference frame, orientations of the local reference frame are not aligned with each other. Under the orientation estimation law, a rotation matrix that identifies orientation of local frame with respect to a common frame is obtained by auxiliary variables. The proposed strategy includes a combination of global orientation estimation and formation control law. Since orientation of each agent is estimated in the global sense, formation control strategy ensures that the formation globally exponentially converges to the desired formation in 3-dimensional space.
• The simulation of pedestrian crowd that reflects reality is a major challenge for researches. Several crowd simulation models have been proposed such as cellular automata model, agent-based model, fluid dynamic model, etc. It is important to note that agent-based model is able, over others approaches, to provide a natural description of the system and then to capture complex human behaviors. In this paper, we propose a multi-agent simulation model in which pedestrian positions are updated at discrete time intervals. It takes into account the major normal conditions of a simple pedestrian situated in a crowd such as preferences, realistic perception of environment, etc. Our objective is to simulate the pedestrian crowd realistically towards a simulation of believable pedestrian behaviors. Typical pedestrian phenomena, including the unidirectional and bidirectional movement in a corridor as well as the flow through bottleneck, are simulated. The conducted simulations show that our model is able to produce realistic pedestrian behaviors. The obtained fundamental diagram and flow rate at bottleneck agree very well with classic conclusions and empirical study results. It is hoped that the idea of this study may be helpful in promoting the modeling and simulation of pedestrian crowd in a simple way.
• HIV/AIDS spread depends upon complex patterns of interaction among various sub-sets emerging at population level. This added complexity makes it difficult to study and model AIDS and its dynamics. AIDS is therefore a natural candidate to be modeled using agent-based modeling, a paradigm well-known for modeling Complex Adaptive Systems (CAS). While agent-based models are also well-known to effectively model CAS, often times models can tend to be ambiguous and the use of purely text-based specifications (such as ODD) can make models difficult to be replicated. Previous work has shown how formal specification may be used in conjunction with agent-based modeling to develop models of various CAS. However, to the best of our knowledge, no such model has been developed in conjunction with AIDS. In this paper, we present a Formal Agent-Based Simulation modeling framework (FABS-AIDS) for an AIDS-based CAS. FABS-AIDS employs the use of a formal specification model in conjunction with an agent-based model to reduce ambiguity as well as improve clarity in the model definition. The proposed model demonstrates the effectiveness of using formal specification in conjunction with agent-based simulation for developing models of CAS in general and, social network-based agent-based models, in particular.
• The increasing use of private vehicles for transportation in cities results in a growing demand for parking space and road network capacity. In many densely populated urban areas, however, the capacity of existing infrastructure is insufficient and extremely difficult to expand. Mobility-on-demand systems have been proposed as a remedy to the problem of limited parking space because they are able to satisfy the existing transportation demand with fewer shared vehicles and consequently require less parking space. Yet, the impact of large-scale vehicle sharing on traffic patterns is not well understood. In this work, we perform a simulation-based analysis of consequences of a hypothetical deployment of a large-scale station-based mobility-on-demand system in Prague and measure the traffic intensity generated by the system and its effects on the formation of congestion. We find that such a mobility-on-demand system would lead to significantly increased total driven distance and it would also increase levels of congestion due to extra trips without passengers. In fact, 38% kilometers traveled in such an MoD system would be driven empty.
• Agent Based Models are very popular in a number of different areas. For example, they have been used in a range of domains ranging from modeling of tumor growth, immune systems, molecules to models of social networks, crowds and computer and mobile self-organizing networks. One reason for their success is their intuitiveness and similarity to human cognition. However, with this power of abstraction, in spite of being easily applicable to such a wide number of domains, it is hard to validate agent-based models. In addition, building valid and credible simulations is not just a challenging task but also a crucial exercise to ensure that what we are modeling is, at some level of abstraction, a model of our conceptual system; the system that we have in mind. In this paper, we address this important area of validation of agent based models by presenting a novel technique which has broad applicability and can be applied to all kinds of agent-based models. We present a framework, where a virtual overlay multi-agent system can be used to validate simulation models. In addition, since agent-based models have been typically growing, in parallel, in multiple domains, to cater for all of these, we present a new single validation technique applicable to all agent based models. Our technique, which allows for the validation of agent based simulations uses VOMAS: a Virtual Overlay Multi-agent System. This overlay multi-agent system can comprise various types of agents, which form an overlay on top of the agent based simulation model that needs to be validated. Other than being able to watch and log, each of these agents contains clearly defined constraints, which, if violated, can be logged in real time. To demonstrate its effectiveness, we show its broad applicability in a wide variety of simulation models ranging from social sciences to computer networks in spatial and non-spatial conceptual models.
• Literature on the modeling and simulation of complex adaptive systems (cas) has primarily advanced vertically in different scientific domains with scientists developing a variety of domain-specific approaches and applications. However, while cas researchers are inher-ently interested in an interdisciplinary comparison of models, to the best of our knowledge, there is currently no single unified framework for facilitating the development, comparison, communication and validation of models across different scientific domains. In this thesis, we propose first steps towards such a unified framework using a combination of agent-based and complex network-based modeling approaches and guidelines formulated in the form of a set of four levels of usage, which allow multidisciplinary researchers to adopt a suitable framework level on the basis of available data types, their research study objectives and expected outcomes, thus allowing them to better plan and conduct their respective re-search case studies.
• Urban rail transit often operates with high service frequencies to serve heavy passenger demand during rush hours. Such operations can be delayed by train congestion, passenger congestion, and the interaction of the two. Delays are problematic for many transit systems, as they become amplified by this interactive feedback. However, there are no tractable models to describe transit systems with dynamical delays, making it difficult to analyze the management strategies of congested transit systems in general, solvable ways. To fill this gap, this article proposes simple yet physical and dynamic models of urban rail transit. First, a fundamental diagram of a transit system (3-dimensional relation among train-flow, train-density, and passenger-flow) is analytically derived by considering the physical interactions in delays and congestion based on microscopic operation principles. Then, a macroscopic model of a transit system with time-varying demand and supply is developed as a continuous approximation based on the fundamental diagram. Finally, the accuracy of the macroscopic model is investigated using a microscopic simulation, and applicable range of the model is confirmed.
• Background Road collisions and casualties pose a serious threat to commuters around the globe. Autonomous Vehicles (AVs) aim to make the use of technology to reduce the road accidents. However, the most of research work in the context of collision avoidance has been performed to address, separately, the rear end, front end and lateral collisions in less congested and with high inter-vehicular distances. Purpose The goal of this paper is to introduce the concept of a social agent, which interact with other AVs in social manners like humans are social having the capability of predicting intentions, i.e. mentalizing and copying the actions of each other, i.e. mirroring. The proposed social agent is based on a human-brain inspired mentalizing and mirroring capabilities and has been modelled for collision detection and avoidance under congested urban road traffic. Method We designed our social agent having the capabilities of mentalizing and mirroring and for this purpose we utilized Exploratory Agent Based Modeling (EABM) level of Cognitive Agent Based Computing (CABC) framework proposed by Niazi and Hussain. Results Our simulation and practical experiments reveal that by embedding Richardson's arms race model within AVs, collisions can be avoided while travelling on congested urban roads in a flock like topologies. The performance of the proposed social agent has been compared at two different levels.
• In the real world, agents or entities are in a continuous state of interactions. These inter- actions lead to various types of complexity dynamics. One key difficulty in the study of complex agent interactions is the difficulty of modeling agent communication on the basis of rewards. Game theory offers a perspective of analysis and modeling these interactions. Previously, while a large amount of literature is available on game theory, most of it is from specific domains and does not cater for the concepts from an agent- based perspective. Here in this paper, we present a comprehensive multidisciplinary state-of-the-art review and taxonomy of game theory models of complex interactions between agents.
• We consider the problem of distributedly estimating Gaussian random fields in multi-agent frameworks. Each sensor collects few measurements and aims to collaboratively reconstruct a common estimate based on all data. Agents are assumed to have limited computational and communication capabilities and to gather $M$ noisy measurements in total on input locations independently drawn from a known common probability density. The optimal solution would require agents to exchange all the $M$ input locations and measurements and then invert an $M\times M$ matrix, a non-scalable task. Differently, we propose two suboptimal approaches using the first $E$ orthonormal eigenfunctions obtained from the KL expansion of the chosen kernel, where typically $E\ll M$. The benefit is twofold: first, the computation and communication complexities scale with $E$ and not with $M$. Second, computing the required sufficient statistics can be performed via standard average consensus algorithms. We obtain probabilistic non-asymptotic bounds for both approaches, useful to determine a priori the desired level of estimation accuracy. Furthermore, we also derive new distributed strategies to tune the regularization parameter which rely on the Stein's unbiased risk estimate (SURE) paradigm and can again be implemented via standard average consensus algorithms. The proposed estimators and bounds are finally tested on both synthetic and real field data.
• In multi-sensor data fusion (or sensor fusion), sensor biases (or offsets) often affect the accuracy of the correlation and integration results of the tracking targets. Therefore, to estimate and compensate the bias, several methods are proposed. However, most methods involve bias estimation and sensor fusion simultaneously by using Kalman filter after collecting the plot data together. Hence, these methods cannot support to fuse the track data prepared by tracking filter at each sensor node. This report proposes the new bias estimation method based on multi-agent model, in order to estimate and compensate the bias for decentralized sensor fusion.
• Equilibrium notions for games with unawareness in the literature cannot be interpreted as steady-states of a learning process because players may discover novel actions during play. In this sense, many games with unawareness are "self-destroying" as a player's representation of the game must change after playing it once. We define discovery processes where at each state there is an extensive-form game with unawareness that together with the players' play determines the transition to possibly another extensive-form games with unawareness in which players are now aware of actions that they have previously discovered. A discovery process is rationalizable if players play extensive-form rationalizable strategies in each game with unawareness. We show that for any game with unawareness there is a rationalizable discovery process that leads to a self-confirming game that possesses an extensive-form rationalizable self-confirming equilibrium. This notion of equilibrium can be interpreted as steady-state of a learning and discovery process.
• While there have been many attempts, going back to BAN logic, to base reasoning about security protocols on epistemic notions, they have not been all that successful. Arguably, this has been due to the particular logics chosen. We present a simple logic based on the well-understood modal operators of knowledge, time, and probability, and show that it is able to handle issues that have often been swept under the rug by other approaches, while being flexible enough to capture all the higher- level security notions that appear in BAN logic. Moreover, while still assuming that the knowledge operator allows for unbounded computation, it can handle the fact that a computationally bounded agent cannot decrypt messages in a natural way, by distinguishing strings and message terms. We demonstrate that our logic can capture BAN logic notions by providing a translation of the BAN operators into our logic, capturing belief by a form of probabilistic knowledge.
• The paper provides an analysis of the voting method known as delegable proxy voting, or liquid democracy. The analysis first positions liquid democracy within the theory of binary aggregation. It then focuses on two issues of the system: the occurrence of delegation cycles; and the effect of delegations on individual rationality when voting on logically interdependent propositions. It finally points to proposals on how the system may be modified in order to address the above issues.
• Supply Shortage Outages are a major concern during peak demand for developing countries. In the Philippines, commercial loads have unused backup generation of up to 3000 MW, at the same time there are shortages of as much as 700 MW during peak demand. This gives utilities the incentive to implement Demand Response programs to minimize this shortage. But when considering Demand Response from a modeling perspective, social welfare through profit is always the major objective for program implementation. That isn't always the case during an emergency situation as there can be a trade-off between grid resilience and cost of electricity. The question is how the Distribution Utility (DU) shall optimally allocate the unused generation to meet the shortage when this trade-off exists. We formulate a combined multi-objective optimal dispatch model where we can make a direct comparison between the least-cost and resilience objectives. We find that this trade-off is due to the monotonically increasing nature of energy cost functions. If the supply is larger than the demand, the DU can perform a least-cost approach in the optimal dispatch since maximizing the energy generated in this case can lead to multiple solutions. We also find in our simulation that in cases where the supply of energy from the customers is less than shortage quantity, the DU must prioritize maximizing the generated energy rather than minimizing cost.
• Sensing in complex systems requires large-scale information exchange and on-the-go communications over heterogeneous networks and integrated processing platforms. Many networked cyber-physical systems exhibit hierarchical infrastructures of information flows, which naturally leads to a multi-level tree-like information structure in which each level corresponds to a particular scale of representation. This work focuses on the multiscale fusion of data collected at multiple levels of the system. We propose a multiscale state-space model to represent multi-resolution data over the hierarchical information system and formulate a multi-stage dynamic zero-sum game to design a multi-scale $H_{\infty}$ robust filter. We present numerical experiments for one and two-dimensional signals and provide a comparative analysis of the minimax filter with the standard Kalman filter to show the improvement in signal-to-noise ratio (SNR).
• This paper presents a data-driven approach for multi-robot coordination in partially-observable domains based on Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) and macro-actions (MAs). Dec-POMDPs provide a general framework for cooperative sequential decision making under uncertainty and MAs allow temporally extended and asynchronous action execution. To date, most methods assume the underlying Dec-POMDP model is known a priori or a full simulator is available during planning time. Previous methods which aim to address these issues suffer from local optimality and sensitivity to initial conditions. Additionally, few hardware demonstrations involving a large team of heterogeneous robots and with long planning horizons exist. This work addresses these gaps by proposing an iterative sampling based Expectation-Maximization algorithm (iSEM) to learn polices using only trajectory data containing observations, MAs, and rewards. Our experiments show the algorithm is able to achieve better solution quality than the state-of-the-art learning-based methods. We implement two variants of multi-robot Search and Rescue (SAR) domains (with and without obstacles) on hardware to demonstrate the learned policies can effectively control a team of distributed robots to cooperate in a partially observable stochastic environment.
• In the article I study the evolutionary adaptivity of two simple population models, based on either altruistic or egoistic law of energy exchange. The computational experiments show the convincing advantage of the altruists, which brings us to a small discussion about genetic algorithms and extraterrestrial life.
• The paper considers the problem of planning a set of non-conflict trajectories for the coalition of intelligent agents (mobile robots). Two divergent approaches, e.g. centralized and decentralized, are surveyed and analyzed. Decentralized planner - MAPP is described and applied to the task of finding trajectories for dozens UAVs performing nap-of-the-earth flight in urban environments. Results of the experimental studies provide an opportunity to claim that MAPP is a highly efficient planner for solving considered types of tasks.
• We propose a minority route choice game to investigate the effect of the network structure on traffic network performance under the assumption of drivers' bounded rationality. We investigate ring-and-hub topologies to capture the nature of traffic networks in cities, and employ a minority game-based inductive learning process to model the characteristic behavior under the route choice scenario. Through numerical experiments, we find that topological changes in traffic networks induce a phase transition from an uncongested phase to a congested phase. Understanding this phase transition is helpful in planning new traffic networks.
• This work studies the problem of inferring whether an agent is directly influenced by another agent over an adaptive diffusion network. Agent i influences agent j if they are connected (according to the network topology), and if agent j uses the data from agent i to update its online statistic. The solution of this inference task is challenging for two main reasons. First, only the output of the diffusion learning algorithm is available to the external observer that must perform the inference based on these indirect measurements. Second, only output measurements from a fraction of the network agents is available, with the total number of agents itself being also unknown. The main focus of this article is ascertaining under these demanding conditions whether consistent tomography is possible, namely, whether it is possible to reconstruct the interaction profile of the observable portion of the network, with negligible error as the network size increases. We establish a critical achievability result, namely, that for symmetric combination policies and for any given fraction of observable agents, the interacting and non-interacting agent pairs split into two separate clusters as the network size increases. This remarkable property then enables the application of clustering algorithms to identify the interacting agents influencing the observations. We provide a set of numerical experiments that verify the results for finite network sizes and time horizons. The numerical experiments show that the results hold for asymmetric combination policies as well, which is particularly relevant in the context of causation.
• Jul 21 2017 math.OC cs.MA arXiv:1707.06465v1
This work studies the convergence properties of continuous-time fictitious play in potential games. It is shown that in almost every potential game and for almost every initial condition, fictitious play converges to a pure-strategy Nash equilibrium. We focus our study on the class of regular potential games; i.e., the set of potential games in which all Nash equilibria are regular. As byproducts of the proof of our main result we show that (i) a regular mixed-strategy equilibrium of a potential game can only be reached by a fictitious play process from a set of initial conditions with Lebesgue measure zero, and (ii) in regular potential games, solutions of fictitious play are unique for almost all initial conditions.
• Jul 21 2017 math.OC cs.MA arXiv:1707.06466v1
A fundamental problem with the Nash equilibrium concept is the existence of certain "structurally deficient" equilibria that (i) lack fundamental robustness properties, and (ii) are difficult to analyze. The notion of a "regular" Nash equilibrium was introduced by Harsanyi. Such equilibria are highly robust and relatively simple to analyze. A game is said to be regular if all equilibria in the game are regular. In this paper it is shown that almost all potential games are regular. That is, except for a closed subset of potential games with Lebesgue measure zero, all potential games are regular. As an immediate consequence of this, the paper also proves an oddness result for potential games: In almost all potential games, the number of Nash equilibrium strategies is finite and odd.
• A novel distributed energy allocation mechanism for Distribution System Operator (DSO) market through a bi-level iterative auction is proposed. With the locational marginal price at the substation node known, the DSO runs an upper level auction with aggregators as intermediate agents competing for energy. This DSO level auction takes into account physical grid constraints such as line flows, transformer capacities and node voltage limits. This auction mechanism is a straightforward implementation of projected gradient descent on the social welfare (SW) of all home level agents. Aggregators, which serve home level agents - both buyers and sellers, implement lower level auctions in parallel, through proportional allocation and without asking for utility functions and generation capacities that are considered private information. The overall bi-level auction is shown to be efficient and weakly budget balanced.