On the complexity of Nash equilibria of action-graph games

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: Tim Abbott , Daniel Kane , Paul Valiant, On the Complexity of Two-PlayerWin-Lose Games, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.113-122, October 23-25, 2005 [doi>10.1109/SFCS.2005.59]
• 2: Navin A. R. Bhat , Kevin Leyton-Brown, Computing Nash equilibria of action-graph games, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.35-42, July 07-11, 2004, Banff, Canada
• 3: Matthias Blonski. Anonymous games with binary actions. Games and Economic Behavior, 28(2):171--180, August 1999.
• 4: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 5: Xi Chen , Xiaotie Deng , Shang-Hua Teng, Computing Nash Equilibria: Approximation and Smoothed Complexity, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.603-612, October 21-24, 2006 [doi>10.1109/FOCS.2006.20]
• 6: Xi Chen , Shang-Hua Teng , Paul Valiant, The approximation complexity of win-lose games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.159-168, January 07-09, 2007, New Orleans, Louisiana
• 7: Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
• 8: Bruno Codenotti , Daniel Štefankovič, On the computational complexity of Nash equilibria for (0, 1) bimatrix games, Information Processing Letters, v.94 n.3, p.145-150, 16 May 2005 [doi>10.1016/j.ipl.2005.01.010]
• 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 , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 11: Constantinos Daskalakis , Christos H. Papadimitriou, Computing pure nash equilibria in graphical games via markov random fields, Proceedings of the 7th ACM conference on Electronic commerce, p.91-99, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134718]
• 12: Constantinos Daskalakis , Christos Papadimitriou, Computing Equilibria in Anonymous Games, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.83-93, October 21-23, 2007 [doi>10.1109/FOCS.2007.19]
• 13: Constantinos Daskalakis , Christos H. Papadimitriou, Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.25-34, October 25-28, 2008 [doi>10.1109/FOCS.2008.84]
• 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 Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 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 , Christos H. Papadimitriou, Reducibility among equilibrium problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132526]
• 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 , Thorsten Theobald, Games of fixed rank: a hierarchy of bimatrix games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1124-1132, January 07-09, 2007, New Orleans, Louisiana
• 24: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 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, Journal of Computer and System Sciences, v.48 n.3, p.498-532, June 1994 [doi>10.1016/S0022-0000(05)80063-7]
• 28: Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 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 , Salil Vadhan, The computational complexity of nash equilibria in concisely represented games, Proceedings of the 7th ACM conference on Electronic commerce, p.270-279, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134737]
• 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.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games