Public Goods in Networks: A Statistical Mechanics Approach

The problem of multiple Nash equilibria in games of strategic substitutes on networks is studied. We consider a general model of public goods provision on network, and analyze in detail the properties of Nash equilibria with particular attention for the subset of equilibria that optimize some global quantities (optimal equilibria) and to those that are robust to small perturbations (stable equilibria). We conclude that finding good approximate optimal equilibria is not that difficult, and we describe the performances of different algorithms. On the other hand, finding stable equilibria is extremely difficult, by means of naive best-response dynamics as well as using advanced messagepassing algorithms. This is a consequence of the intrinsically different spatial organization of the two sets of equilibria