skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


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.  more » « less
Award ID(s):
1905558
PAR ID:
10213629
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Proceedings of the AAAI Conference on Artificial Intelligence
ISSN:
2159-5399
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton))
    Network games have provided a framework to study strategic decision making processes that are governed by an underlying network of interdependencies among agents. However, existing models do not account for environments in which agents simultaneously interact over multiple networks. In this paper, we propose a model of multiplex network games to capture the different modalities of interactions among strategic agents. We then explore how the properties of the constituent networks of a multiplex network can undermine or support the uniqueness of its Nash equilibria. We first show that in general, even if the constituent networks are guaranteed to have unique Nash equi- libria in isolation, the resulting multiplex need not have a unique equilibrium. We then identify certain subclasses of networks wherein guarantees on the uniqueness of Nash equilibria on the isolated networks lead to the same guarantees on the multiplex network game. We further highlight that both the largest and smallest eigenvalues of the constituent networks (reflecting their connectivity and two-sidedness, respectively) are instrumental in determining the uniqueness of the multiplex network equilibrium. Together, our findings shed light on the reasons for the fragility of the uniqueness of equilibria in multiplex networks, and potential interventions to alleviate them. 
    more » « less
  2. ; ; (, American Control Conference (ACC))
    null (Ed.)
    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 order 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. 
    more » « less
  3. ; ; ; ; ; ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    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
  4. ; ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    We characterize offline data poisoning attacks on Multi-Agent Reinforcement Learning (MARL), where an attacker may change a data set in an attempt to install a (potentially fictitious) unique Markov-perfect Nash equilibrium for a two-player zero-sum Markov game. We propose the unique Nash set, namely the set of games, specified by their Q functions, with a specific joint policy being the unique Nash equilibrium. The unique Nash set is central to poisoning attacks because the attack is successful if and only if data poisoning pushes all plausible games inside it. The unique Nash set generalizes the reward polytope commonly used in inverse reinforcement learning to MARL. For zero-sum Markov games, both the inverse Nash set and the set of plausible games induced by data are polytopes in the Q function space. We exhibit a linear program to efficiently compute the optimal poisoning attack. Our work sheds light on the structure of data poisoning attacks on offline MARL, a necessary step before one can design more robust MARL algorithms. 
    more » « less
  5. ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    Coalitions naturally exist in many real-world systems involving multiple decision makers such as ridesharing, security, and online ad auctions, but the coalition structure among the agents is often unknown. We propose and study an important yet previously overseen problem -- Coalition Structure Learning (CSL), where we aim to carefully design a series of games for the agents and infer the underlying coalition structure by observing their interactions in those games. We establish a lower bound on the sample complexity -- defined as the number of games needed to learn the structure -- of any algorithms for CSL and propose the Iterative Grouping (IG) algorithm for designing normal-form games to achieve the lower bound. We show that IG can be extended to other succinct games such as congestion games and graphical games. Moreover, we solve CSL in a more restrictive and practical setting: auctions. We show a variant of IG to solve CSL in the auction setting even if we cannot design the bidder valuations. Finally, we conduct experiments to evaluate IG in the auction setting and the results align with our theoretical analysis. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email