  Graphical games are a useful framework for modeling the interactions of
(selfish) agents who are connected via an underlying topology and whose
behaviors influence each other. They have wide applications ranging from
computer science to economics and biology. Yet, even though a player's payoff
only depends on the actions of their direct neighbors in graphical games,
computing the Nash equilibria and making statements about the convergence time
of "natural" local dynamics in particular can be highly challenging. In this
work, we present a novel approach for classifying complexity of Nash equilibria
in graphical games by establishing a connection to local graph algorithms, a
subfield of distributed computing. In particular, we make the observation that
the equilibria of graphical games are equivalent to locally verifiable
labelings (LVL) in graphs; vertex labelings which are verifiable with a
constant-round local algorithm. This connection allows us to derive novel lower
bounds on the convergence time to equilibrium of best-response dynamics in
graphical games. Since we establish that distributed convergence can sometimes
be provably slow, we also introduce and give bounds on an intuitive notion of
"time-constrained" inefficiency of best responses. We exemplify how our results
can be used in the implementation of mechanisms that ensure convergence of best
responses to a Nash equilibrium. Our results thus also give insight into the
convergence of strategy-proof algorithms for graphical games, which is still
not well understood.
