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