Tom Johnston

Game connectivity and adaptive dynamics

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 dynamic, 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 this 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.