Best response dynamics on random graphs

Jordan Chellig, Calina Durbac, Nikolaos Fountoulakis

Research output: Contribution to journalArticlepeer-review

Abstract

We consider evolutionary games on a population whose underlying topology of interactions is determined by a binomial random graph G(n, p). Our focus is on 2-player symmetric games with 2 strategies played between the incident members of such a population. Players update their strategies synchronously: 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 bias among the pure Nash equilibria, we determine a sharp threshold on p above which the largest connected component reaches unanimity with high probability. For p below this critical value, we identify those substructures inside the largest component that block unanimity.
Original languageEnglish
Pages (from-to)141-170
Number of pages46
JournalGames and Economic Behaviour
Volume131
Early online date24 Nov 2021
DOIs
Publication statusPublished - Jan 2022

Bibliographical note

Not yet published in issue as of 29/11/2021.

Keywords

  • random graphs
  • evolutionary games
  • best response dynamics

Fingerprint

Dive into the research topics of 'Best response dynamics on random graphs'. Together they form a unique fingerprint.

Cite this