We review existing approaches to mathematical modeling and analysis of multi-agent systems in which complex collective behavior arises out of local interactions between many simple agents. Though the behavior of an individual agent can be considered to be stochastic and unpredictable, the collective behavior of such systems can have a simple probabilistic description. We show that a class of mathematical models that describe the dynamics of collective behavior of multi-agent systems can be written down from the details of the individual agent controller. The models are valid for Markov or memoryless agents, in which each agents future state depends only on its present state and not any of the past states. We illustrate the approach by analyzing in detail applications from the robotics domain: collaboration and foraging in groups of robots.
With the exceptions noted below, there has been very little prior work on mathematical analysis of multi-agent systems. The closest in spirit to our paper is the work by Huberman, Hogg and coworkers on computational ecologies @cite_5 @cite_73 . These authors mathematically studied collective behavior in a system of agents, each choosing between two alternative strategies. They derived a rate equation for the average number of agents using each strategy from the underlying probability distributions. Our approach is consistent with theirs --- in fact, we can easily write down the same rate equations from the macroscopic state diagram of the system, without having to derive them from the underlying probability distributions. Computational ecologies can, therefore, be considered an application of the methodology described in this paper. Yet another application of the approach presented here is the author's work on coalition formation in electronic marketplaces @cite_71 .
@cite_5 @cite_73 @cite_71
2145374086 2761043131 2084044206 2617547828
In this paper, we formulate and solve a randomized optimal consensus problem for multi-agent systems with stochastically time-varying interconnection topology. The considered multi-agent system with a simple randomized iterating rule achieves an almost sure consensus meanwhile solving the optimization problem min"z"@?"R"^"[email protected]?"i"="1^nf"i(z), in which the optimal solution set of objective function f"i can only be observed by agent i itself. At each time step, simply determined by a Bernoulli trial, each agent independently and randomly chooses either taking an average among its neighbor set, or projecting onto the optimal solution set of its own optimization component. Both directed and bidirectional communication graphs are studied. Connectivity conditions are proposed to guarantee an optimal consensus almost surely with proper convexity and intersection assumptions. The convergence analysis is carried out using convex analysis. We compare the randomized algorithm with the deterministic one via a numerical example. The results illustrate that a group of autonomous agents can reach an optimal opinion by each node simply making a randomized trade-off between following its neighbors or sticking to its own opinion at each time step. Agent-based modeling of zapping behavior of viewers, television commercial allocation, and advertisement markets by Hiroyuki Kyan and Jun-ichi Inoue.- Agent based modeling of Housing asset bubble: A simple utility function based investigation by Kausik Gangopadhyay and Kousik Guhathakurta.- Urn model-based adaptive Multi-arm clinical trials: A stochastic approximation approach by Sophie Laruelle and Gilles Pages.- Logistic modeling of a Religious Sect features by Marcel Ausloos.- Characterizing financial crisis by means of the three states random field Ising model by Mitsuaki Murota and Jun-ichi Inoue.- Themes and applications of kinetic exchange models: Redux by Asim Ghosh, Anindya S. Chakrabarti, Anjan Kumar Chandra and Anirban Chakraborti.- Kinetic exchange opinion model: solution in the single parameter map limit by Krishanu Roy Chowdhury, Asim Ghosh, Soumyajyoti Biswas and Bikas K. Chakrabarti.- An overview of the new frontiers of Economic Complexity by Matthieu Cristelli, Andrea Tacchella, Luciano Pietronero.- Jan Tinbergen's legacy for economic networks: from the gravity model to quantum statistics by Tiziano Squartini and Diego Garlaschelli.- A macroscopic order of consumer demand due to heterogenous consumer behaviors on Japanese household demand tested by the random matrix theory by Yuji Aruka,Yuichi Kichikawa and Hiroshi Iyetomi.- Uncovering the network structure of the world currency market: Cross-correlations in the fluctuations of daily exchange rates by Sitabhra Sinha and Uday Kovur.- Systemic risk in Japanese credit network by Hideaki Aoyama.- Pricing of goods with Bandwagon properties: The curse of coordination by Mirta B. Gordon, Jean-Pierre Nadal, Denis Phan and Viktoriya Semeshenko.- Evolution of Econophysics by Kishore C. Dash.- Econophysics and sociophysics: Problems and prospects by Asim Ghosh and Anindya S. Chakrabarti.- A discussion on Econophysics by Hideaki Aoyama. We study the average consensus problem of multi-agent systems for general network topologies with unidirectional information flow. We propose two linear distributed algorithms, deterministic and gossip, respectively for the cases where the inter-agent communication is synchronous and asynchronous. In both cases, the developed algorithms guarantee state averaging on arbitrary strongly connected digraphs; in particular, this graphical condition does not require that the network be balanced or symmetric, thereby extending previous results in the literature. The key novelty of our approach is to augment an additional variable for each agent, called "surplus", whose function is to locally record individual state updates. For convergence analysis, we employ graph-theoretic and nonnegative matrix tools, plus the eigenvalue perturbation theory playing a crucial role. Cooperative multi-agent systems can be naturally used to model many real world problems, such as network packet routing and the coordination of autonomous vehicles. There is a great need for new reinforcement learning methods that can efficiently learn decentralised policies for such systems. To this end, we propose a new multi-agent actor-critic method called counterfactual multi-agent (COMA) policy gradients. COMA uses a centralised critic to estimate the Q-function and decentralised actors to optimise the agents' policies. In addition, to address the challenges of multi-agent credit assignment, it uses a counterfactual baseline that marginalises out a single agent's action, while keeping the other agents' actions fixed. COMA also uses a critic representation that allows the counterfactual baseline to be computed efficiently in a single forward pass. We evaluate COMA in the testbed of StarCraft unit micromanagement, using a decentralised variant with significant partial observability. COMA significantly improves average performance over other multi-agent actor-critic methods in this setting, and the best performing agents are competitive with state-of-the-art centralised controllers that get access to the full state.