Nash equilibria in graphical games on trees revisited

ABSTRACT

Graphical games have been proposed as a game-theoretic model of large-scale distributed networks of non-cooperative agents. When the number of players is large, and the underlying graph has low degree, they provide a concise way to represent the players' payoffs. It has recently been shown that the problem of finding Nash equilibria in a general degree-3 graphical game with two actions per player is complete for the complexity class PPAD, indicating that it is unlikely that there is any polynomial-time algorithm for this problem. In this paper, we study the complexity of graphical games with two actions per player on bounded-degree trees. This setting was first considered by Kearns, Littman and Singh, who proposed a dynamic programming-based algorithm that computes all Nash equilibria of such games. The running time of their algorithm is exponential, though approximate equilibria can be computed efficiently. Later, Littman, Kearns and Singh proposed a modification to this algorithm that can find a single Nash equilibrium in polynomial time. We show that this modified algorithm is incorrect-the output is not always a Nash equilibrium. We then propose a new algorithm that is based on the ideas of Kearns et al. and computes all Nash equilibria in quadratic time if the input graph is a path, and in polynomial time if it is an arbitrary graph of maximum degree 2. Moreover, our algorithm can be used to compute Nash equilibria of graphical games on arbitrary trees, but the running time can be exponential, even when the tree has bounded degree. We show that this is inevitable -- any algorithm of this type will take exponential time, even on bounded-degree trees with pathwidth 2. It is an open question whether our algorithm runs in polynomial time on graphs with pathwidth 1, but we show that finding a Nash equilibrium for a 2-action graphical game in which the underlying graph has maximum degree 3 and constant pathwidth is PPAD-complete (so is unlikely to be tractable).

REFERENCES

• 1: Hans L. Bodlaender , Ton Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, v.21 n.2, p.358-402, Sept. 1996 [doi>10.1006/jagm.1996.0049]
• 2: X. Chen and X. Deng. 3-NASH is PPAD-complete. Technical Report TR-05-134, Electronic Colloquium in Computational Complexity, 2005.
• 3: X. Chen and X. Deng. Settling the complexity of 2-player Nash equilibrium. Technical Report TR-05-140, Electronic Colloquium in Computational Complexity, 2005.
• 4: 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]
• 5: C. Daskalakis and C. Papadimitriou. Three-player games are hard. Technical Report TR-05-139, Electronic Colloquium in Computational Complexity, 2005.
• 6: E. Elkind, L. Goldberg, and P. Goldberg. Nash equilibria in graphical games on trees revisited. Technical Report TR-06-005, Electronic Colloquium in Computational Complexity, 2006.
• 7: 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]
• 8: 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
• 9: M. Littman, M. Kearns, and S. Singh. An efficient exact algorithm for singly connected graphical games. In Proceedings of the 15th Annual Conference on Neural Information Processing Systems, 2001.
• 10: L. Ortiz and M. Kearns. Nash propagation for loopy graphical games. In Proceedings of the 17th Annual Conference on Neural Information Processing Systems, 2003.
• 11: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
PPAD-completeness, graphical games, nash equilibrium