  In this work, we introduce graphical modelsfor multi-player game theory, and
give powerful algorithms for computing their Nash equilibria in certain cases.
An n-player game is given by an undirected graph on n nodes and a set of n
local matrices. The interpretation is that the payoff to player i is determined
entirely by the actions of player i and his neighbors in the graph, and thus
the payoff matrix to player i is indexed only by these players. We thus view
the global n-player game as being composed of interacting local games, each
involving many fewer players. Each player's action may have global impact, but
it occurs through the propagation of local influences.Our main technical result
is an efficient algorithm for computing Nash equilibria when the underlying
graph is a tree (or can be turned into a tree with few node mergings). The
algorithm runs in time polynomial in the size of the representation (the graph
and theassociated local game matrices), and comes in two related but distinct
flavors. The first version involves an approximation step, and computes a
representation of all approximate Nash equilibria (of which there may be an
exponential number in general). The second version allows the exact computation
of Nash equilibria at the expense of weakened complexity bounds. The algorithm
requires only local message-passing between nodes (and thus can be implemented
by the players themselves in a distributed manner). Despite an analogy to
inference in Bayes nets that we develop, the analysis of our algorithm is more
involved than that for the polytree algorithm in, owing partially to the fact
that we must either compute, or select from, an exponential number of potential
solutions. We discuss a number of extensions, such as the computation of
equilibria with desirable global properties (e.g. maximizing global return),
and directions for further research.
