Title

Dominance Solvability in Random Games

Author(s)

Noga Alon Noga Alon (Princeton University)

Kirill Rudov Kirill Rudov (Princeton University)

Leeat Yariv Leeat Yariv (Princeton University)

Abstract

We study the effectiveness of iterated elimination of strictly dominated actions in random two-player 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, at least when one of the players has a small action set, iterated elimination simplifies the game substantially by ruling out a sizable fraction of actions. This is no longer the case as both players’ action sets expand. With more than two players, iterated elimination becomes even less potent in altering the game players need to consider. Technically, we illustrate the usefulness of recent combinatorial methods for the analysis of general games.

Creation Date

2021-05

Section URL ID

Paper Number

2021-84

URL

http://lyariv.mycpanel.princeton.edu//papers/DominanceSolvability.pdf

File Function

Jel

C70, C79

Keyword(s)

Random Games, Dominance Solvability, Iterated Elimination

Suppress

false

Series

13