Graphical potential games

Abstract

We study the class of potential games that are also graphical games with respect to a given graph $G$ of connections between the players. We show that, up to strategic equivalence, this class of games can be identified with the set of Markov random fields on $G$. From this characterization, and from the Hammersley-Clifford theorem, it follows that the potentials of such games can be decomposed to local potentials. We use this decomposition to strongly bound the number of strategy changes of a single player along a better response path. This result extends to generalized graphical potential games, which are played on infinite graphs.

Accepted to the Journal of Economic Theory

References in corpus (4)

• Graphical Models for Game Theory
• Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (2001)
• Graphical potential games
• Graphical Potential Games

Cited by in corpus (3)

• Graphical potential games
• Graphical Games and Decomposition
• Distributed Planning for Serving Cooperative Tasks with Time Windows: A Game Theoretic Approach