Distributed learning in potential games over large-scale networks

Fabio Fagnani

Politecnico di Torino, Italy


Distributed learning in potential games over large-scale networks Fabio Fagnani Department of Mathematical Sciences Politecnico di Torino A central issue in game theory is that of providing sound dynamical foundations for Nash equilibria, whose original notion is a purely static one. Several efforts have been made, generating new research fields such evolutionary game theory or the theory of learning in games. However, satisfactory answers to the aforementioned problem have been found only for special classes of games and assuming that all agents can directly interact with each other. In this talk, we study the imitative noisy best response dynamics with small spontaneous mutations for population games under the assumption that pairwise learning interactions can only take place along the edges of a preassigned graph. Our main result shows that if the game is a potential one and the graphs are large-scale expanders, Nash equilibria can be recovered in the double limit of large population size and zero mutation noise. More specifically, we show that the invariant probability measure of the Markov process describing the learning dynamics concentrates in a neighborhood of the set of Nash equilibria. Expander graphs turn out to be particularly relevant for applications as many of the proposed random graph models of complex social and economic networks are known to be expanders with high probability. BIO: Fabio Fagnani got his Laurea degree in Mathematics from University of Pisa and from Scuola Normale Superiore of Pisa in 1986. He got the PhD in Mathematics from University of Groningen nel 1991. He has been Assistant professor of Mathematical Analysis at the Scuola Normale Superiore during 1991-1998 and in 1997 he has been visiting professor al MIT. Since 1998 he is with the Politecnico of Torino where he is currently (since 2002) full professor of Mathematical Analysis. He has acted as coordinator of the PhD program Mathematics for Engineering Sciences of Politecnico di Torino in the period 2006-2012. From June 1012 he is the head of the Department of Mathematical Sciences of Politecnico di Torino. His current research topics are on cooperative algorithms and dynamical systems over graphs, inferential distributed algorithms, opinion dynamics. He has published over 50 refereed papers on international journals, he has delivered invited conferences in many international workshops and conferences and in many universities (including MIT, Yale, IMA, EPFL, UCSB, UCSD, CWI, University of Groningen, University of Kyoto) He regularly serves as referee in most of the top journal of his research area: IEEE Trans. Inf. Theory, IEEE Trans. Aut. Control, SIAM J. Control Optim., Automatica. He is Associate Editor of IEEE Transactions on Network Systems. He is member of the international program committee for the events NECSYS. WARNING: due to the Inria's access policy, people external to Inria should communicate in advance their participation to Giovanni Neglia (giovanni.neglia@inria.fr)

[Fabio Fagnani]
Politecnico di Torino, Italy