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 on a general degree-3 graphical game is complete for the complexity class PPAD, indicating that it is unlikely that there is any polynomial-time algorithm for this problem. We show here that in contrast, degree-2 graphical games are tractable. Our algorithm uses a dynamic-programming approach, which was introduced by Kearns, Littman and Singh in the context of graphical games on trees. The algorithm of Kearns et al. is a generic algorithm which can be used to compute all Nash equilibria. The running time is exponential, though approximate equilibria can be computed efficiently. Littman, Kearns and Singh proposed a modification to the generic algorithm in order to find a Nash equilibrium in polynomial time, provided that the underlying graph is a bounded-degree tree. We show that this modified algorithm is incorrect --- the output is not always a Nash equilibrium. In this paper, we focus on graphical games in which the underlying graph is a path or ``path-like''. First, we show that Nash equilibria can be computed in quadratic time if the underlying graph is a path, and therefore in polynomial time if the underlying graph has maximum degree~$2$. Our algorithm, which is based on the approach of Kearns et al., 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 two-pass 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 graphical game in which the underlying graph has maximum degree~$3$ and constant pathwidth is PPAD-complete (so is unlikely to be tractable).