Dominance Solvability in Random Games

Noga Alon, Kirill Rudov and Leeat Yariv

Papers from arXiv.org

Abstract: We study the effectiveness of iterated elimination of strictly-dominated actions in random games. We show that dominance solvability of games is vanishingly small as the number of at least one player's actions grows. Furthermore, conditional on dominance solvability, the number of iterations required to converge to Nash equilibrium grows rapidly as action sets grow. Nonetheless, when games are highly imbalanced, iterated elimination simplifies the game substantially by ruling out a sizable fraction of actions. Technically, we illustrate the usefulness of recent combinatorial methods for the analysis of general games.

Date: 2021-05
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://arxiv.org/pdf/2105.10743 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:2105.10743

Access Statistics for this paper

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