Consider the problem of a group of agents trying to find a stable strategy
profile for a joint interaction. A standard approach is to describe the
situation as a single multi-player game and find an equilibrium strategy
profile of that game. However, most algorithms for finding equilibria are
computationally expensive; they are also centralized, requiring that all
relevant payoff information be available to a single agent (or computer) who
must determine the entire equilibrium profile. In this paper, we exploit two
ideas to address these problems. We consider structured game
representations, where the interaction between the agents is sparse, an
assumption that holds in many real-world situations. We also consider the
slightly relaxed task of finding an approximate equilibrium. We present two
algorithms for finding approximate equilibria in these games, one based on a
hill-climbing approach and one on constraint satisfaction. We show that
these algorithms exploit the game structure to achieve faster
computation. They are also inherently local, requiring only limited
communication between directly interacting agents. They can thus be scaled
to games involving large numbers of agents, provided the interaction between
the agents is not too dense.