CoSy Zoom seminar

Link for application

Abstract: 

Many social and economic systems can be modelled as network games whereby players are represented as nodes and influences as links of an interaction graph and graph-theoretic notions of centrality, connectivity, and conductance often recur in characterising emerging behaviours in these games. 

In this talk, we first discuss some results on the separability structure of network games, refining and generalizing the notion of graphical games. We show that every strategic equivalence class contains a game with minimal separability properties. We prove a symmetry property of the minimal splitting of potential games and we describe how this property reflects to a decomposition of the potential function and generalize this analysis to arbitrary network games showing how their potential-harmonic decomposition relates to their separability properties. 

We then study a targeting problem in network games: the selection of the smallest control set of players capable of driving the system, globally, from one Nash equilibrium to another one. We prove that while the problem is NP-complete even in the special case of the network coordination games. For the class super modular network games, we introduce a randomized algorithm based on a time-reversible Markov chain with provable convergence guarantees.

Finally, we present a network formation game where the nodes choose strategically whom to link to and discuss the structure of Nash equilibria and the behaviour of asynchronous best response dynamics in such a game. 

Joint work with Laura Arditti, Costanza Catalano, Stephane Durand, and Fabio Fagnani at Politecnico di Torino.