Dominance Solvability in Random Games

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.