Local-Effect Games

Kevin Leyton-Brown, Moshe TennenholtzIJCAI 2003 · OpenReview

Abstract

We present a new class of games, local-effect games (LEGs), which exploit structure in a different way from other compact game representations studied in AI. We show both theoretically and empirically that these games often (but not always) have pure-strategy Nash equilibria. Finding a potential function is a good technique for finding such equilibria. We give a complete characterization of which LEGs have potential functions and provide the functions in each case; we also show a general case where pure-strategy equilibria exist in the absence of potential functions. In experiments, we show that myopic best-response dynamics converge quickly to pure strategy equilibria in games not covered by our positive theoretical results.

Introduction

In game theory, identifying a Nash equilibrium—a state where no player can improve their outcome by unilaterally changing their strategy—is a fundamental challenge. As the number of agents increases, the computational complexity of finding these equilibria often becomes prohibitive. To address this, researchers utilize compact representations that exploit structural properties of the game, such as unconditional independence (Graphical Games) or symmetry (Congestion Games).

However, many real-world interactions exhibit "context-specific independence." For instance, a vendor's profit is heavily influenced by nearby competitors but unaffected by those far away. This paper introduces Local-Effect Games (LEGs) to formalize this middle ground, where the impact of an agent's choice depends on the "locality" of that action relative to others.

Modeling Local Effects

LEGs are defined using a graph-based framework where:

  • Nodes represent the set of possible actions available to agents.
  • Edges represent local effects between actions. If an edge exists between action A and action B, the number of agents choosing A influences the utility of agents choosing B.
  • Cost Functions are decomposed into node functions (inherent cost of an action) and edge functions (costs imposed by agents choosing neighboring actions).
An arbitrary graph structure used to evaluate the performance of LEGs in complex, non-symmetric scenarios.

This structure allows for the modeling of asymmetric interactions, where the effect of A on B may differ from the effect of B on A. This flexibility distinguishes LEGs from standard congestion games, which typically assume symmetric effects.

Theoretical Foundations: Potential Functions

To prove the existence of pure-strategy Nash equilibria, the authors employ Potential Functions. A game is a "potential game" if there exists a function that tracks the changes in individual payoffs. If an agent moves to a better strategy, the potential function increases. Since the state space is finite, the function must eventually reach a maximum, corresponding to a stable equilibrium.

The research provides a complete characterization of LEGs that possess potential functions. Key findings include:

  1. Linear Bidirectional LEGs: If local effects are linear and mutual, a potential function always exists.
  2. Uniform LEGs on a Clique: Games where all actions affect each other equally also guarantee stability.
  3. Independent Set Strategy: In certain cases, equilibria exist where agents distribute themselves such that no two agents occupy adjacent nodes.

Empirical Evaluation

The authors tested the scalability and convergence of LEGs using several synthetic topologies, including T-structures, binary trees, grids, and arbitrary graphs. They utilized a "myopic best-response" algorithm, where agents sequentially move to their current best action.

Comparison of steps to convergence across various graph topologies as the number of agents increases.

The experiments revealed that even in games where potential functions are not theoretically guaranteed (e.g., non-linear effects), the myopic best-response dynamics converge to a pure-strategy Nash equilibrium remarkably quickly. For an arbitrary graph with 200 agents, convergence was achieved in approximately 40 steps, demonstrating that the number of steps scales linearly with the number of agents.

Conclusion

Local-Effect Games offer a powerful framework for modeling multiagent systems with localized interactions. By exploiting context-specific independence, LEGs provide both theoretical guarantees for stability in many cases and high empirical efficiency in reaching equilibria. Future work will extend these findings to purely directed graphs and dynamic environments where the action space may change over time.

Summary updated

Abstract

We present a new class of games, local-effect games (LEGs), which exploit structure in a different way from other compact game representations studied in AI. We show both theoretically and empirically that these games often (but not always) have pure-strategy Nash equilibria. Finding a potential function is a good technique for finding such equilibria. We give a complete characterization of which LEGs have potential functions and provide the functions in each case; we also show a general case where pure-strategy equilibria exist in the absence of potential functions. In experiments, we show that myopic best-response dynamics converge quickly to pure strategy equilibria in games not covered by our positive theoretical results.
BibTeX
@inproceedings{leytonbrown2003local,
  author = {Kevin Leyton-Brown and Moshe Tennenholtz},
  title = {{Local-Effect Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
  url = {https://openreview.net/forum?id=rJW8xHMOZr},
}
Figure