Randomized strategies need at most one extra round of elimination

Two ways to eliminate inferior choices

Iterated dominance removes strategies that another available strategy strictly outperforms against every remaining possibility for opponents’ play. Removing those choices can make further strategies dominated, so the process repeats until nothing more changes.

A pure strategy selects one action with certainty. A mixed strategy assigns probabilities to actions. Importantly, the paper’s pure-strategy procedure does not restrict the replacement strategy to a single action: a pure strategy can be eliminated because a mixture of surviving pure strategies strictly beats it. The distinction between the procedures concerns what gets removed—individual actions or entire probability distributions.

Echenique and Friedenberg motivate their comparison partly through rationalizability, which connects surviving strategies with rational choice and successive levels of belief in others’ rationality. They also point to an observational difficulty: seeing an action does not reveal whether someone deliberately chose it or obtained it through randomization. An undominated action might be the realized outcome of a dominated mixture.

A tight one-round bound

The researchers prove their main result for games in which each player’s pure-strategy space is a compact metric space and payoffs are continuous. These assumptions also encompass finite games.

If eliminating pure strategies finishes at round M, eliminating mixed strategies finishes at either M or M + 1. Here, the termination round is the last round that actually removes strategies; round zero applies when no elimination occurs at all.

The result resolves a potential complication in finite games. There are only finitely many pure actions to remove, but infinitely many probability distributions over those actions. Nevertheless, the mixed-strategy procedure cannot continue indefinitely after the pure-strategy procedure stops. The authors also establish the converse: finite termination of the mixed procedure implies finite termination of the pure procedure.

For games with infinite pure-strategy spaces, the theorem remains conditional on finite termination. Compactness and continuity do not, by themselves, turn the result into a universal finite-round guarantee.

Why the extra round can matter

A two-player example shows that the one-round allowance cannot be reduced. The first player chooses among U, M and D; the second among L, C and R. The pure-strategy procedure removes R in its first round and then stops, without removing any of the first player’s actions.

The mixed-strategy procedure initially removes every second-player mixture assigning positive probability to R. Once R is unavailable, however, some first-player randomizations become dominated—even though U, M and D individually remain undominated.

Specifically, any mixture giving positive probability to both U and M can be improved by shifting equal amounts of probability away from those two actions and toward D. Against either remaining opponent action, this raises expected payoff. For a particularly simple illustration, an equal mixture of U and M earns 2 against L and 2 against C, while D earns 2.1 against either.

Those mixtures disappear in round two, after which the mixed procedure stops. The example demonstrates the central distinction: retaining every action in a mixture does not guarantee that the mixture itself survives.

Equivalent checks using pure strategies

The paper also establishes two alternative elimination procedures that reproduce the mixed procedure’s surviving sets at every round.

The first, called “grandfather dominance,” checks whether a mixture can be strictly improved against every opponent pure-strategy profile surviving the corresponding pure-strategy elimination rounds. Its drawback is that the analyst must also compute that separate procedure.

The second, “support dominance,” obtains the relevant pure profiles from the mixed-strategy procedure itself, using actions that can receive positive probability in surviving mixtures. It therefore avoids relying on a separately computed elimination process.

These equivalences are mathematical characterizations, not reported computational benchmarks. They reduce the opponent choices against which improvements must be checked, but the paper does not establish a general runtime advantage. Nor does its bound describe how quickly people learn or how many rounds of reasoning they actually perform. The work is a theoretical arXiv preprint: its contribution is a precise relationship between elimination procedures under stated assumptions, rather than an empirical test of strategic behavior.