Statistical physics approach to graphical games: local and global interactions
arXiv:1104.1929 · doi:10.1140/epjb/e2011-10963-x
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.
arXiv comment32 pages, 11 figures, to be published in Eur. Phys. J. B
References in corpus (9)
- Evolutionary games on graphs
- The Bethe lattice spin glass revisited
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Learning by message-passing in networks of discrete synapses
- Survey-propagation decimation through distributed local computations
- Matrix Games, Mixed Strategies, and Statistical Mechanics
- Geometrical organization of solutions to random linear Boolean equations
- 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