Best response dynamics on random graphs

• 成果类型: Article
• 署名作者: Chellig, Jordan; Durbac, Calina; Fountoulakis, Nikolaos
• 署名单位: University of Birmingham
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2021.11.003
• 发表日期: 2022
• 页码: 141-170
• 关键词: Random graphs; evolutionary games; Unanimity

摘要

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 further 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. (C) 2021 Elsevier Inc. All rights reserved.