Structure and control of network games

February 19, 2021, Zoom

Giacomo Como

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.

Speaker's Bio

Giacomo Como is an Associate Professor at the Department of Mathematical Sciences, Politecnico di Torino, Italy, and at the Automatic Control Department of Lund University, Sweden. He received the B.Sc., M.S., and Ph.D. degrees in Applied Mathematics from Politecnico di Torino, in 2002, 2004, and 2008, respectively. He was a Visiting Assistant in Research at Yale University in 2006-2007 and a Postdoctoral Associate at the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, from 2008 to 2011.

He currently serves as Associate Editor of the IEEE Transactions on Network Science and Engineering and of the IEEE Transactions on Control of Network Systems, and as chair of the IEEE-CSS Technical Committee on Networks and Communication Systems. He was the IPC chair of the IFAC Workshop NecSys 2015 and a semi-plenary speaker at the International Symposium MTNS 2016 and the SICE ISCS 2017. He is a recipient of the 2015 George S. Axelby Outstanding Paper Award. His research interests are in dynamics, information, and control in network systems with applications to cyber-physical systems, infrastructure networks, and social and economic networks.

Video URL: