TR06-005 Authors: Edith Elkind, Leslie Ann Goldberg, Paul Goldberg

Publication: 14th January 2006 07:42

Downloads: 995

Keywords:

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).