skip to main content
10.5555/1496770.1496848guideproceedingsArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article
Free access

On the complexity of Nash equilibria of action-graph games

Published: 04 January 2009 Publication History

Abstract

In light of much recent interest in finding a model of multi-player multi-action games that allows for efficient computation of Nash equilibria yet remains as expressive as possible, we investigate the computational complexity of Nash equilibria in the recently proposed model of action-graph games (AGGs). AGGs, introduced by Bhat and Leyton-Brown, are succinct representations of games that encapsulate both local dependencies as in graphical games, and partial indifference to other agents' identities as in anonymous games, which occur in many natural settings such as financial markets. This is achieved by specifying a graph on the set of actions, so that the payoff of an agent for selecting a strategy depends only on the number of agents playing each of the neighboring strategies in the action graph. We present a simple Fully Polynomial Time Approximation Scheme for computing mixed Nash equilibria of AGGs with constant degree, constant treewidth and a constant number of agent types (but an arbitrary number of strategies), and extend this algorithm to a broader set of instances. However, the main results of this paper are negative, showing that when either of the latter conditions are relaxed the problem becomes intractable. In particular, we show that even if the action graph is a tree but the number of agent-types is unconstrained, it is NP- complete to decide the existence of a pure-strategy Nash equilibrium and PPAD-complete to compute a mixed Nash equilibrium (even an approximate one). Similarly for AGGs with a constant number of agent types but unconstrained treewidth. These hardness results suggest that, in some sense, our FPTAS is as strong a positive result as one can expect. In the broader context of trying to pin down the boundary where the equilibria of multi-player games can be computed efficiently, these results complement recent hardness results for graphical games and algorithmic results for anonymous games.

References

[1]
Timothy Abbot, Daniel Kane, and Paul Valiant. On the complexity of two-player win-lose games. In Proceedings of the 46th FOCS, pages 113--122, 2005.
[2]
Navin A. R. Bhat and Kevin Leyton-Brown. Computing nash equilibria of action-graph games. In UAI, pages 35--42, 2004.
[3]
Matthias Blonski. Anonymous games with binary actions. Games and Economic Behavior, 28(2):171--180, August 1999.
[4]
Xi Chen and Xiaotie Deng. Settling the complexity of two-player nash equilibrium. In FOCS, pages 261--272, Washington, DC, USA, 2006. IEEE Computer Society.
[5]
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Computing nash equilibria: Approximation and smoothed complexity. In FOCS, pages 603--612, 2006.
[6]
Xi Chen, Shang-Hua Teng, and Paul Valiant. The approximation complexity of win-lose games. In Proceedings of SODA, 2007.
[7]
Steve Chien and Alistair Sinclair. Convergence to approximate nash equilibria in congestion games. In SODA, pages 169--178, 2007.
[8]
Bruno Codenotti and Daniel Štefankovič. On the computational complexity of nash equilibria for (0, 1) bimatrix games. Inf. Process. Lett., 94(3):145--150, 2005.
[9]
Constantinos Daskalakis, Alex Fabrikant, and Christos H. Papadimitriou. The game world is flat: The complexity of nash equilibria in succinct games. In ICALP (1), pages 513--524, 2006.
[10]
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a nash equilibrium. In STOC, 2006.
[11]
Constantinos Daskalakis and Christos H. Papadimitriou. Computing pure nash equilibria in graphical games via markov random fields. In ACM Conference on Electronic Commerce, pages 91--99, 2006.
[12]
Constantinos Daskalakis and Christos H. Papadimitriou. Computing equilibria in anonymous games. In FOCS, 2007.
[13]
Constantinos Daskalakis and Christos H. Papadimitriou. Discretized multinomial distributions and nash equilibria in anonymous games. FOCS, 2008.
[14]
Constantinos Daskalakis and Christos H. Papadimitriou. Three-player games are hard. Technical Report TR05-139, Electronic Colloquium on Computational Complexity (ECCC), November 2005.
[15]
Juliane Dunkel and Andreas S. Schulz. On the complexity of pure-strategy nash equilibria in congestion and local-effect games. In WINE, pages 62--73, 2006.
[16]
F. Fischer F. Brandt and M. Holzer. Equilibria of graphical games with symmetries. Technical Report TR07-136, Electronic Colloquium on Computational Complexity (ECCC), December 2007.
[17]
Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar. The complexity of pure nash equilibria. In STOC, pages 604--612, 2004.
[18]
D Gale, HW Kuhn, and AW Tucker. On symmetric games. Contributions to the Theory Games, Annals of Mathematics Studies, 24, 1950.
[19]
Paul W. Goldberg and Christos H. Papadimitriou. Reducibility among equilibrium problems. In STOC, 2006.
[20]
Albert Xin Jiang and Kevin Leyton-Brown. A polynomial-time algorithm for Action-Graph Games. In AAAI, pages 679--684, 2006.
[21]
Albert Xin Jiang and Kevin Leyton-Brown. Computing pure nash equilibria in symmetric action graph games. In AAAI, pages 79--85. AAAI Press, 2007.
[22]
Albert Xin Jiang, Kevin Leyton-Brown, and Navin Bhat. Action-graph games. 2007. Working paper, available at: www.cs.ubc.ca/~jiang/papers/AGG.pdf.
[23]
Ravi Kannan and Thorsten Theobald. Games of fixed rank: a hierarchy of bimatrix games. In SODA, pages 1124--1132, 2007.
[24]
Michael Kearns, Michael L. Littman, and Satinder Singh. Graphical models for game theory. In UAI, pages 253--260, 2001.
[25]
C. E. Lemke and Jr J. T. Howson. Equilibrium points of bimatrix games. SIAM Journal of Applied Mathematics, 12:413--423, 1964.
[26]
John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286--295, 1951.
[27]
Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498--532, 1994.
[28]
Christos H. Papadimitriou and Tim Roughgarden. Computing equilibria in multi-player games. In SODA '05, pages 82--91, 2005.
[29]
J. Rosenmuller. On a generalization of the lemke-howson algorithm to noncooperative n-person games. SIAM Journal of Applied Mathematics, 21:73--79, 1971.
[30]
H. E. Scarf. The approximation of fixed points of a continuous mapping. SIAM Journal of Applied Mathematics, 15:1328--1343, 1967.
[31]
Grant Schoenebeck and Salil Vadhan. The computational complexity of nash equilibria in concisely represented games. In EC '06: Proceedings of the 7th ACM conference on Electronic commerce, pages 270--279, New York, NY, USA, 2006. ACM.
[32]
G. van der Laan and A. J. J. Talman. On the computation of fixed points in the product space of unit simplices and an application to noncooperative n person games. Mathematics of Operations Research, 7, 1982.
[33]
J. von Neumann and O. Morgenstern. On the computation of fixed points in the product space of unit simplices and an application to noncooperative n person games. Theory of Games and Economic Behavior, 1944.
[34]
R. Wilson. Computing equilibria of n-person games. SIAM Journal of Applied Mathematics, 21:80--87, 1971.

Cited By

View all
  • (2022)Pure Nash Equilibria in Resource Graph GamesJournal of Artificial Intelligence Research10.1613/jair.1.1266872(185-213)Online publication date: 4-Jan-2022
  • (2016)Congestion games with polytopal strategy spacesProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060645(165-171)Online publication date: 9-Jul-2016
  • (2016)An Empirical Study on Computing Equilibria in Polymatrix GamesProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2936955(186-195)Online publication date: 9-May-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms
January 2009
1297 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 04 January 2009

Qualifiers

  • Research-article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)58
  • Downloads (Last 6 weeks)12
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Pure Nash Equilibria in Resource Graph GamesJournal of Artificial Intelligence Research10.1613/jair.1.1266872(185-213)Online publication date: 4-Jan-2022
  • (2016)Congestion games with polytopal strategy spacesProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060645(165-171)Online publication date: 9-Jul-2016
  • (2016)An Empirical Study on Computing Equilibria in Polymatrix GamesProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2936955(186-195)Online publication date: 9-May-2016
  • (2013)Empirical analysis of plurality election equilibriaProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2484983(391-398)Online publication date: 6-May-2013
  • (2012)Nash equilibrium in weighted concurrent timed games with reachability objectivesProceedings of the 8th international conference on Distributed Computing and Internet Technology10.1007/978-3-642-28073-3_11(117-128)Online publication date: 2-Feb-2012
  • (2010)Computing pure strategy nash equilibria in compact symmetric gamesProceedings of the 11th ACM conference on Electronic commerce10.1145/1807342.1807352(63-72)Online publication date: 7-Jun-2010

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media