Local Algorithms for Finding Equilibria in Structured Games

Collaborative Learning Agents

Volume

Papers from the 2002 AAAI Spring Symposium

Contents

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 consider the slightly relaxed task of finding an approximate equilibrium. We consider structured game representations, where the interaction between the agents is sparse, an assumption that holds in many real-world situations. 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 are inherently local, requiring only limited communication between directly interacting agents. The algorithms can thus be scaled to games involving large numbers of players provided the interaction between the players is not too dense.