Eur. Phys. J. B 81, 327-339 (2011)
https://doi.org/10.1140/epjb/e2011-10963-x

Statistical physics approach to graphical games: local and global interactions

¹ Theoretical Physics, Politecnico di Torino, Third School of Engineering – Information Technologies orso, Duca degli Abruzzi 24, 10129 Torino, Italy
² Collegio Carlo Alberto, Via Real Collegio 30, 10024 Moncalieri, Italy

Corresponding author: ^a riccardo.zecchina@polito.it

Received: 8 December 2010
Revised: 7 March 2011
Published online: 8 April 2011

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.