Statistical physics approach to graphical games: local and global interactions

Abstract

In a graphical game agents play with their neighbors on a graph to achieve an appropriate state of equilibrium. Here relevant problems are characterizing the equilibrium set and discovering efficient algorithms to find such an equilibrium (solution). We consider a representation of games that extends over graphical games to deal conveniently with both local a global interactions and use the cavity method of statistical physics to study the geometrical structure of the equilibria space. The method also provides a distributive and local algorithm to find an equilibrium. For simplicity we consider only pure Nash equilibria but the methods can as well be extended to deal with (approximated) mixed Nash equilirbia.

32 pages, 11 figures, to be published in Eur. Phys. J. B

References in corpus (4)

• Evolutionary games on graphs
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical Mechanics of maximal independent sets
• Belief propagation for graph partitioning

Cited by in corpus (8)

• Sign problem in the Bethe approximation
• The Futility of Being Selfish -- The Impact of Selfish Routing on Uncoordinated and Optimized Transportation Networks
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Next nearest neighbour Ising models on random graphs
• Statics and dynamics of selfish interactions in distributed service systems
• Computing loop corrections by message passing
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Statistical physics of loopy interactions: Independent-loop approximation and beyond