April 17, 2020, Webb 1100

In a binary (0 -1) coordination game over a graph, where initially all agents are in the Nash equilibrium 0, what is the minimum number of agents that if forced to 1 will push the system to converge to the Nash equilibrium of all 1’s under a best response dynamics? This paper deals with such a problem for the more general class of super-modular games with binary actions, namely those games that exhibit the so-called increasing difference property. Our contribution is twofold: we show that the problem is NP-complete and we propose the design of an iterative algorithm for an efficient solution.

Fabio Fagnani got his Laurea degree in Mathematics from the University of Pisa and Scuola Normale Superiore of Pisa in 1986 and the PhD in Mathematics from the University of Groningen in 1991. He has been Assistant Professor of Mathematical Analysis at the Scuola Normale Superiore during 1991-1998, and in 1997 he held a Visiting Professor position at MIT. Since 1998 he is with the Politecnico of Torino where he is currently (since 2002) Full Professor of Mathematical Analysis. In the period 2012-2019, he has been the head of the Department of Mathematical Sciences of Politecnico di Torino. His current research interests are on the broad topic of dynamics and control over networks: opinion dynamics, inferential distributed algorithms, epidemic models, network games and learning dynamics in games, social and economic applications. He has published over 60 refereed papers on international journals and 50 over peer-reviewed conference proceedings.