skip to main content

Title: Multi-scale games: Representing and solving games on networks with group structure
Network games provide a natural machinery to compactly represent strategic interactions among agents whose payoffs exhibit sparsity in their dependence on the actions of others. Besides encoding interaction sparsity, however, real networks often exhibit a multi-scale structure, in which agents can be grouped into communities, those communities further grouped, and so on, and where interactions among such groups may also exhibit sparsity. We present a general model of multi-scale network games that encodes such multi-level structure. We then develop several algorithmic approaches that leverage this multi-scale structure, and derive sufficient conditions for convergence of these to a Nash equilibrium. Our numerical experiments demonstrate that the proposed approaches enable orders of magnitude improvements in scalability when computing Nash equilibria in such games. For example, we can solve previously intractable instances involving up to 1 million agents in under 15 minutes.
Authors:
; ;
Award ID(s):
1905558
Publication Date:
NSF-PAR ID:
10213629
Journal Name:
Proceedings of the AAAI Conference on Artificial Intelligence
ISSN:
2159-5399
Sponsoring Org:
National Science Foundation
More Like this
  1. We analyze a class of stochastic dynamic games among teams with asymmetric information, where members of a team share their observations internally with a delay of d. Each team is associated with a controlled Markov Chain, whose dynamics are coupled through the players’ actions. These games exhibit challenges in both theory and practice due to the presence of signaling and the increasing domain of information over time. We develop a general approach to characterize a subset of Nash equilibria where the agents can use a compressed version of their information, instead of the full information, to choose their actions. Wemore »identify two subclasses of strategies: sufficient private information-Based (SPIB) strategies, which only compress private information, and compressed information-based (CIB) strategies, which compress both common and private information. We show that SPIB-strategy-based equilibria exist and the set of payoff profiles of such equilibria is the same as that of all Nash equilibria. On the other hand, we show that CIB-strategy-based equilibria may not exist. We develop a backward inductive sequential procedure, whose solution (if it exists) provides a CIB strategy-based equilibrium. We identify some instances where we can guarantee the existence of a solution to the above procedure. Our results highlight the tension among compression of information, ability of compression-based strategies to sustain all or some of the equilibrium payoff profiles, and backward inductive sequential computation of equilibria in stochastic dynamic games with asymmetric information.« less
  2. 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 utilitymore »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.« less
  3. We study games with nonlinear best response functions played on a network consisting of disjoint communities. Prior works on network games have identified conditions to guarantee the uniqueness and stability of Nash equilibria in a network without any community structure. In this paper we are interested in accomplishing the same for networks with a community structure; it turns out that these conditions are much easier to verify with certain community structures. Specifically, we consider multipartite graphs and show that the uniqueness and stability of Nash equilibria are related to matrices which are potentially much lower in dimension, on the ordermore »of the number of communities, compared to same-size networks without a multipartite structure, in which case such matrices have a dimension the size of the network. We further introduce a new notion of degree centrality to measure the importance and influence of a community in such a network. We show that this notion enables us to find new conditions for uniqueness and stability of Nash equilibria.« less
  4. Abstract Modern control systems are featured by their hierarchical structure composed of cyber, physical and human layers. The intricate dependencies among multiple layers and units of modern control systems require an integrated framework to address cross-layer design issues related to security and resilience challenges. To this end, game theory provides a bottom-up modeling paradigm to capture the strategic interactions among multiple components of the complex system and enables a holistic view to understand and design cyber-physical-human control systems. In this review, we first provide a multi-layer perspective toward increasingly complex and integrated control systems and then introduce several variants ofmore »dynamic games for modeling different layers of control systems. We present game-theoretic methods for understanding the fundamental tradeoffs of robustness, security and resilience and developing a cross-layer approach to enhance the system performance in various adversarial environments. This review also includes three quintessential research problems that represent three research directions where dynamic game approaches can bridge between multiple research areas and make significant contributions to the design of modern control systems. The paper is concluded with a discussion on emerging areas of research that crosscut dynamic games and control systems.« less
  5. We propose a deep neural network-based algorithm to identify the Markovian Nash equilibrium of general large 𝑁-player stochastic differential games. Following the idea of fictitious play, we recast the 𝑁-player game into 𝑁 decoupled decision problems (one for each player) and solve them iteratively. The individual decision problem is characterized by a semilinear Hamilton-Jacobi-Bellman equation, to solve which we employ the recently developed deep BSDE method. The resulted algorithm can solve large 𝑁-player games for which conventional numerical methods would suffer from the curse of dimensionality. Multiple numerical examples involving identical or heterogeneous agents, with risk-neutral or risk-sensitive objectives, aremore »tested to validate the accuracy of the proposed algorithm in large group games. Even for a fifty-player game with the presence of common noise, the proposed algorithm still finds the approximate Nash equilibrium accurately, which, to our best knowledge, is difficult to achieve by other numerical algorithms.« less