Best response dynamics in random graphs

In this talk, we will discuss evolutionary games on a binomial random graph G(n,p). These games are determined through a 2-player symmetric game with 2 strategies which are played between the adjacent members of the vertex set. Players/vertices update their strategies synchronously: at each round, each player selects the strategy that is the best response to the current set of strategies its neighbours play. We show that such a system reduces to generalised majority and minority dynamics. We show rapid convergence to unanimity for p in a range that depends on a certain characteristic of the payoff matrix. In the presence of a certain type of bias in the payoff matrix, we determine a sharp threshold on p above which the largest connected component reaches unanimity with high probability, and below which this does not happen.

This is joint work with Jordan Chellig and Calina Durbac.