Best response dynamics on random graphs

DOI10.1016/J.GEB.2021.11.003MaRDI QIDQ2078038zbMATH OpenOpenAlexFDO

Authors Jordan Chellig, Calina Durbac, Nikolaos Fountoulakis

Publication date 25 February 2022

Published in Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.12983

zbMATH Keywords

evolutionary gamesrandom graphsunanimity

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80) Multistage and repeated games (91A20) Evolutionary games (91A22) Games involving graphs (91A43)

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. 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 bias among the pure Nash equilibria of the game, we determine a sharp threshold on $p$ above which the largest connected component reaches unanimity with high probability. For $p$ below this critical value, where this does not happen, we identify those substructures inside the largest component that remain discordant throughout the evolution of the system.

Recommendations

• Best-response dynamics, playing sequences, and convergence to equilibrium in random games
• Evolutionary games on the lattice: best-response dynamics
• Pure Nash equilibria and best-response dynamics in random games
• The frequency of convergent games under best-response dynamics
• Games on graphs

Cites work

• Bootstrap percolation in living neural networks
• Bootstrap percolation on homogeneous trees has 2 phase transitions
• Bootstrap percolation on the hypercube
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• Contagion
• Contagion and uninvadability in local interaction games: the bilingual game and general supermodular games
• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
• Diffusion and cascading behavior in random networks
• Ergodic theorems for weakly interacting infinite systems and the voter model
• Evolutionary game dynamics
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 7221274 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• Paths in graphs
• Periodic behaviour of generalized threshold functions
• Random Graphs
• Rapid innovation diffusion in social networks
• Resolution of a conjecture on majority dynamics: rapid stabilization in dense random graphs
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Social Stability and Equilibrium
• The logic of animal conflict
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The sharp threshold for bootstrap percolation in all dimensions
• The speed of innovation diffusion in social networks
• Voter and majority dynamics with biased and stubborn agents
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)

Cited in

(9)

• Local interactions and \(p\)-best response set
• A note on best response dynamics.
• Lumping evolutionary game dynamics on networks
• Majority dynamics on sparse random graphs
• Multistability and Hopf bifurcation analysis for a three-strategy evolutionary game with environmental feedback and delay
• Dynamic games on arbitrary networks with two types of players
• Partitioning problems via random processes
• Exact characterisation of asymptotic running time for approximate gradient descent on random graphs
• Evolutionary games on the lattice: best-response dynamics

This page was built for publication: Best response dynamics on random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2078038)