This week's seminar is given by Tom Johnstone, University of Bristol.
Title: Game connectivity and adaptive dynamics
Abstract: We consider a generic game where there are $n$ players who can each be in one of $k$ states and at each time step the players can choose to change their state based on the current states of the other players. It is known that there are no ``simple'' dynamics which converge to a pure Nash equilibrium in every generic game that has one, but are there a small number of difficult games or is it hard to converge in most of the games?
One simple dynamic is the best response with inertia, in which case convergence is a question about the connectivity of the best-response graph. We will look at the connectivity of a random best-response graph, and show that our simple dynamic converges to a pure Nash equilibrium in almost all generic games that have one.
Based on joint work with Michael Savery, Alex Scott and Bassel Tarbush.
