An official website of the United States government
We provide a polynomial-time, scalable algorithm for equilibrium computation in multi-agent influence games on networks, extending work of Bindel, Kleinberg, and Oren (2015) from the single-agent to the multi-agent setting. In games of influence, agents have limited advertising budget to influence the initial predisposition of nodes in some network towards their products, but the eventual decisions of the nodes are determined by the stationary state of DeGroot opinion dynamics on the network, which takes over after the seeding (Ahmadinejad et al. 2014, 2015). In multi-agent systems, how should agents spend their budgets to seed the network to maximize their utility in anticipation of other advertising agents and the network dynamics? We show that Nash equilibria of this game are pure and (under weak assumptions) unique, and can be computed in polynomial time; we test our model by computing equilibria using mirror descent for the two-agent case on random graphs.
more »
« less
Mean‐field limit of non‐exchangeable systems
Abstract This paper deals with the derivation of the mean‐field limit for multi‐agent systems on a large class of sparse graphs. More specifically, the case of non‐exchangeable multi‐agent systems consisting of non‐identical agents is addressed. The analysis does not only involve PDEs and stochastic analysis but also graph theory through a new concept of limits of sparse graphs (extended graphons) that reflect the structure of the connectivities in the network and has critical effects on the collective dynamics. In this article some of the main restrictive hypothesis in the previous literature on the connectivities between the agents (dense graphs) and the cooperation between them (symmetric interactions) are removed.
more »
« less
- PAR ID:
- 10571507
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Communications on Pure and Applied Mathematics
- Volume:
- 78
- Issue:
- 4
- ISSN:
- 0010-3640
- Format(s):
- Medium: X Size: p. 651-741
- Size(s):
- p. 651-741
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Particle dynamics and multi-agent systems provide accurate dynamical models for studying and forecasting the behaviour of complex interacting systems. They often take the form of a high-dimensional system of differential equations parameterized by an interaction kernel that models the underlying attractive or repulsive forces between agents. We consider the problem of constructing a data-based approximation of the interacting forces directly from noisy observations of the paths of the agents in time. The learned interaction kernels are then used to predict the agents’ behaviour over a longer time interval. The approximation developed in this work uses a randomized feature algorithm and a sparse randomized feature approach. Sparsity-promoting regression provides a mechanism for pruning the randomly generated features which was observed to be beneficial when one has limited data, in particular, leading to less overfitting than other approaches. In addition, imposing sparsity reduces the kernel evaluation cost which significantly lowers the simulation cost for forecasting the multi-agent systems. Our method is applied to various examples, including first-order systems with homogeneous and heterogeneous interactions, second-order homogeneous systems, and a new sheep swarming system.more » « less
-
Chenyang Lu (Ed.)The design and analysis of multi-agent human cyber-physical systems in safety-critical or industry-critical domains calls for an adequate semantic foundation capable of exhaustively and rigorously describing all emergent effects in the joint dynamic behavior of the agents that are relevant to their safety and well-behavior. We present such a semantic foundation. This framework extends beyond previous approaches by extending the agent-local dynamic state beyond state components under direct control of the agent and belief about other agents (as previously suggested for understanding cooperative as well as rational behavior) to agent-local evidence and belief about the overall cooperative, competitive, or coopetitive game structure. We argue that this extension is necessary for rigorously analyzing systems of human cyber-physical systems because humans are known to employ cognitive replacement models of system dynamics that are both non-stationary and potentially incongruent. These replacement models induce visible and potentially harmful effects on their joint emergent behavior and the interaction with cyber-physical system components.more » « less
-
Sample efficiency and scalability to a large number of agents are two important goals for multi-agent reinforcement learning systems. Recent works got us closer to those goals, addressing non-stationarity of the environment from a single agent’s perspective by utilizing a deep net critic which depends on all observations and actions. The critic input concatenates agent observations and actions in a user-specified order. However, since deep nets aren’t permutation invariant, a permuted input changes the critic output despite the environment remaining identical. To avoid this inefficiency, we propose a ‘permutation invariant critic’ (PIC), which yields identical output irrespective of the agent permutation. This consistent representation enables our model to scale to 30 times more agents and to achieve improvements of test episode reward between 15% to 50% on the challenging multi-agent particle environment (MPE).more » « less
-
Summary This paper introduces a new class of feedback‐based data‐driven extremum seeking algorithms for the solution of model‐free optimization problems in smooth continuous‐time dynamical systems. The novelty of the algorithms lies on the incorporation of memory to store recorded data that enables the use of information‐rich datasets during the optimization process, and allows to dispense with the time‐varying dither excitation signal needed by standard extremum seeking algorithms that rely on a persistence of excitation (PE) condition. The model‐free optimization dynamics are developed for single‐agent systems, as well as for multi‐agent systems with communication graphs that allow agents to share their state information while preserving the privacy of their individual data. In both cases, sufficient richness conditions on the recorded data, as well as suitable optimization dynamics modeled by ordinary differential equations are characterized in order to guarantee convergence to a neighborhood of the solution of the extremum seeking problems. The performance of the algorithms is illustrated via different numerical examples in the context of source‐seeking problems in multivehicle systems.more » « less
