Finding pure Nash equilibria in large random games

Andrea Collevecchio, Tuan-Minh Nguyen and Ziwen Zhong

Papers from arXiv.org

Abstract: Best Response Dynamics (BRD) is a class of strategy updating rules to find Pure Nash Equilibria (PNE) in a game. At each step, a player is randomly picked, and the player switches to a "best response" strategy based on the strategies chosen by others, so that the new strategy profile maximises their payoff. If no such strategy exists, a different player will be chosen randomly. When no player wants to change their strategy anymore, the process reaches a PNE and will not deviate from it. On the other hand, either PNE may not exist, or BRD could be "trapped" within a subgame that has no PNE. We consider a random game with $N$ players, each with two actions available, and i.i.d. payoffs, in which the payoff distribution may have an atom, i.e. ties are allowed. We study a class of random walks in a random medium on the $N$-dimensional hypercube induced by the random game. The medium contains two types of obstacles corresponding to PNE and traps. The class of processes we analyze includes BRD, simple random walks on the hypercube, and many other nearest neighbour processes. We prove that, with high probability, these processes reach a PNE before hitting any trap.

Date: 2024-06, Revised 2024-08
New Economics Papers: this item is included in nep-gth and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://arxiv.org/pdf/2406.09732 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2406.09732

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().