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
2 Collegio Carlo Alberto, Via Real Collegio 30, 10024 Moncalieri, Italy
Corresponding author: a firstname.lastname@example.org
Revised: 7 March 2011
Published online: 8 April 2011
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.
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2011