Iterated Elimination of Dominated Mixed Strategies

arXiv:2611.05705 · econ.TH, cs.GT · Submitted 2026-11-03 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.

Ruth: We're looking at the paper: "Iterated Elimination of Dominated Mixed Strategies".

Warren: Here's the gist of the paper. This note compares two iterated dominance procedures, one based on eliminating mixed strategies and one based on eliminating pure strategies, showing that in compact and continuous games, the mixed-strategy procedure can trail the pure-strategy procedure by at most one round.

Ruth: The Core Finding In any compact and continuous game, the mixed-strategy elimination procedure can trail the pure-strategy procedure by at most one step, meaning if the pure-strategy procedure terminates at round M, the mixed-strategy procedure will either terminate at M or M + 1.

Warren: This bound is tight.

Ruth: Conceptual Framework and Equivalence The paper introduces "grandfather dominance" as an intermediate concept, which shows that iterated dominance based on mixed strategies is round-for-round equivalent to iterated grandfather dominance.

Paper summary: Ruth: To get into specifics on the paper, "Iterated Elimination of Dominated Mixed Strategies," it compares two procedures: one based on eliminating mixed strategies and one based on eliminating pure strategies. The central claim is that for compact and continuous games, the mixed-strategy procedure can trail the pure-strategy procedure by at most one round, meaning if pure strategy elimination takes M rounds, mixed strategy elimination takes M or M plus one >

Warren: And this bound is tight because they show that this lag actually happens in certain cases >

Iris: The paper also introduces concepts like "iterated support dominance," which they say is round-for-round equivalent to both iterated dominance and iterated grandfather dominance, and it only requires searching for improvements relative to a set of the opponents' pure strategies >

Ruth: And this equivalence means that you can use these other procedures instead of the main one if you want a more focused search; it simplifies how we think about finding those undominated mixed strategies >

Warren: It suggests that instead of dealing with the whole, potentially much larger set of previously undominated mixed strategies, you can focus on what’s relevant to the current stage using these support dominance ideas >

Iris: The termination conditions they establish are also pretty clean; for compact and continuous games, both procedures stop shrinking at the first limit ordinal, meaning they are guaranteed to halt eventually >

Ruth: And what's really interesting is that if you look at the characterization of undominated strategies, it relates them directly to those not dominated relative to all pure strategies that can get strictly positive probability under a strategy in a previously undominated set >

Warren: That sounds like a way to make the search more targeted; checking against the supports of sets rather than every single mixed strategy available >

Iris: The paper proves an equivalence between the set of m-undominated mixed strategies and the m-grandfather undominated strategies by showing that a strategy is in one if and only if its characteristic function satisfies certain properties related to improvements over the set at round m minus i >

Ruth: So, ultimately, this work provides a way to compute those undominated mixed strategies by searching for improvements relative to just the (m minus one)-undominated pure strategies instead of the larger set of all (m minus one)-undominated mixed strategies >

Conclusion: Ruth: So, to wrap up, this paper "Iterated Elimination of Dominated Mixed Strategies" establishes that in compact and continuous games, the mixed-strategy elimination procedure can trail the pure-strategy procedure by at most one round >

Warren: That tight bound is pretty significant because it directly addresses the inference problem when players choose stochastic strategies; it shows a potential large disconnect between the number of rounds needed for pure versus mixed strategy elimination >

Iris: It also offers an alternative characterization of m-undominated mixed strategies based on support dominance, which requires searching only relative to the (m minus one)-undominated pure strategies instead of the larger set of all previously undominated mixed strategies >

Ruth: And if you see that the procedure based on mixed strategies terminates in finitely many rounds, then so does the procedure based on pure strategies; they are equivalent in that way >

Warren: So, if one procedure stops, the other one stops too; it implies that for these specific games, you don't need to worry about a massive gap between them stopping times >

Federico Echenique, Amanda Friedenberg

econ.TH, cs.GT

Submitted: 2026-11-03

Updated: 2026-11-03

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 81/100

The gist: This note compares two iterated dominance procedures, one based on eliminating mixed strategies and one based on eliminating pure strategies, showing that in compact and continuous games…

Key concepts

Iterated Dominance
This is a process used to eliminate strategies that are strictly worse than others, applied repeatedly. The paper examines this process when applied to mixed strategies versus pure ones, showing how closely they track each other in continuous games.
Grandfather Dominance
An intermediate concept introduced to show that iterated dominance based on mixed strategies is equivalent to a specific type of grandfather dominance. This links the two procedures together, simplifying the analysis of how one procedure relates to the other.
Support Dominance
An alternative procedure that focuses only on checking for improvements relative to a set of opponents' pure strategies rather than all previously undominated mixed strategies. This offers a potentially more computationally efficient way to find undominated mixed strategies.
Termination Conditions
These are the specific rules that determine when the elimination procedures stop. For compact and continuous games, both procedures are guaranteed to stop at the first limit ordinal, characterized by stabilization after a finite number of rounds or meeting specific set conditions.

Terminology

Summary

This note compares two iterated dominance procedures, one based on eliminating mixed strategies and one based on eliminating pure strategies, showing that in compact and continuous games, the mixed-strategy procedure can trail the pure-strategy procedure by at most one round. p. 0

The Core Finding

In any compact and continuous game, the mixed-strategy elimination procedure can trail the pure-strategy procedure by at most one step, meaning if the pure-strategy procedure terminates at round M, the mixed-strategy procedure will either terminate at M or M + 1. This bound is tight. p. 0

Conceptual Framework and Equivalence

The paper introduces grandfather dominance as an intermediate concept, which shows that iterated dominance based on mixed strategies is round-for-round equivalent to iterated grandfather dominance. Furthermore, it defines iterated support dominance, an alternative procedure that is round-for-round equivalent to both iterated dominance and iterated grandfather dominance, requiring only searching for improvements relative to a set of the opponents’ pure strategies.

Termination Conditions

The analysis establishes conditions under which these procedures terminate, noting that for compact and continuous games, both procedures are guaranteed to stop shrinking at the first limit ordinal. The termination condition is characterized by stabilization after a finite number of rounds M, where either (i) M = 0 and the set remains undominated for all m ≥ 0, or (ii) S M ⊊ S M−1 and the set stabilizes at S M. p. 3

Computational Utility

The equivalence between iterated dominance and iterated grandfather dominance provides a method for computing m-undominated mixed strategies by searching for improvements relative to all (m − 1)-undominated pure strategies instead of the larger set of all (m − 1)-undominated mixed strategies. This suggests a more targeted approach to finding undominated mixed strategies than relying solely on the larger set of previously undominated mixed strategies. p. 1

Characterization of Undominated Strategies

The paper introduces two characterizations for the mixed-strategy procedure that require checking for improvements only against opponents’ pure strategies. Specifically, the support dominance procedure relates undominated mixed strategies to those not dominated relative to all pure strategies that can get strictly positive probability under a strategy in a previously undominated set. p. 7 This suggests that checking against the supports of relevant sets is sufficient for determining the next level of undominated strategies. p. 0 The support dominance procedure is self-referential, unlike grandfather dominance, as it does not require computing an alternate procedure first. p. 2 The paper also shows that the set of m-undominated mixed strategies coincides with the m-grandfather undominated strategies. p. 1 This equivalence is proven by showing that a strategy si ∈ S m i if and only if δsi ∈ Σ m i. p. 6 The proof relies on the fact that for each si ∈ S m i, its characteristic function fi(si) satisfies certain properties related to improvements over the set S m−i. p. 8 The final result shows that the procedure based on mixed strategies eliminates all mixed strategies that place strictly positive probability on U and M without eliminating any pure strategies of player 1. p. 5 The paper concludes by proving Theorem 1, establishing the relationship between the termination of both procedures. p. 3 The proof relies on Lemma 3, which states that a strategy si ∈ S m i if and only if δsi ∈ Σ m i. p. 7 The proof of Theorem 1 proceeds by induction, utilizing the properties of the set functions V m i and the construction of a measurable selection gi. p. 7 The proof also establishes that for each i = 1,. p. 4.., I and each m ≥ 1, S m i and Σ m i are compact. p. 0 p. 0

The Role of Auxiliary Definitions

Auxiliary definitions are introduced to facilitate the proof structure, such as U m i which is defined as ui(σi, s−i) - ui(si, s−i) and is continuous. Lemma 2 proves that S m i and Σ m i are closed for m ≥ 1. p. 2 Corollary 1 states that for each i = 1,..., I and each m ≥ 1, S m i and Σ m i are compact. Lemma 4 provides a measurable function fi: S m i → ∆(S m i) that links undominated pure strategies to the mixed strategy space. p. 1 This function fi satisfies conditions such as if si ∈ S m i, then fi(si) = δsi. p. 2 Lemma 5 proves that if a mixed strategy is dominated given Σ 0 i × Σ m−i, it is dominated given Σ m i × Σ m−i. p. 3 This lemma is crucial for the proof of Proposition 1, showing that domination relative to a smaller set implies domination relative to the larger set. p. 1 Lemma 3 provides conditions under which strategies in S infinity and Σ infinity are undominated given their respective infinite product spaces. p. 2 The proof of Lemma 3 relies on the compactness of the product spaces and the continuity of ui. p. 8 The proof of Lemma 4 uses a measurable selection theorem to construct fi. p. 9 Lemma 2 is proven by showing that S m i is closed if S m−i is closed and the set of strategies not dominated by any pure strategy in S m−i is relatively open. p. 2 The proof of Lemma 5 uses a map Υ m i to show that domination relative to Σ m−i implies domination relative to Σ m. p. 1 The proof of Proposition 2 is by induction, showing that the set of m-support-undominated strategies coincides with the set of m-grandfather undominated strategies. p. 7 The proof for Proposition 2 relies on the fact that Supp(Σ m−i) = S m−i. p. 8

Where the Gains Come From

The primary gain of this work is providing a tight upper bound on the divergence between iterated dominance based on pure strategies and iterated dominance based on mixed strategies, showing it can trail by at most one step. The main result establishes that if the pure-strategy procedure terminates at M, the mixed-strategy procedure terminates at M or M + 1. p. 0 This tight bound is significant because it addresses the inference problem when players choose stochastic strategies, highlighting a potential large disconnect between the number of rounds required for pure versus mixed strategy elimination. p. 1 The paper also offers an alternative characterization of m-undominated mixed strategies based on support dominance, which requires searching only relative to the (m − 1)-undominated pure strategies. p. 2 This provides a potentially more computationally efficient method for finding undominated mixed strategies than checking against the entire set of previously undominated mixed strategies. p. 1 The overall contribution is unifying solution concepts under a single framework and providing concrete bounds on the complexity of these procedures. p. 0 The paper also notes that if the procedure based on mixed strategies terminates in finitely many rounds, then so does the procedure based on pure strategies, implying equivalence. p. 6 This implies that one procedure terminates if and only if the other does. p. 6 The paper also addresses the question of how many additional steps may be required compared to the iterated dominance based on pure strategies. p. 6

Related Concepts and Context

The work builds upon foundational results in game theory, linking iterated dominance to rationalizability concepts from Bernheim (1984) and Pearce’s (1984). The study explicitly moves beyond the implicit assumption of pure strategies to model choice behavior consistent with mixed-strategy Nash equilibrium. p. 0 The paper addresses the complication that a mixed strategy can be dominated even if each pure strategy in its support is undominated, which complicates inferring players’ reasoning from observed behavior. p. 1 The motivation stems from the question of how far the mixed-strategy elimination procedure can trail the pure-strategy procedure in finite games. p. 1 The paper also references related work such as Arieli (2010) on rationalizability in continuous games. p. 3 This places the current research within a modern framework of solution concepts for games. p. 0 The paper also references Glicksberg’s theorem regarding Nash equilibrium points. p. 0

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Iterated Elimination of Dominated Strategies can be used to compute m-undominated mixed strategies by searching for improvements only relative to the (m minus 1)-undominated pure strategies instead of the larger set of (m minus 1)-undominated mixed strategies, as stated in Section 5.

  2. A new self-referential procedure called support dominance can be introduced, which requires searching for improvements relative to a set of opponents pure strategies and does not require computing an alternate procedure first.

  3. The system can determine if a mixed strategy is undominated given the product of sets using the equivalence between iterated dominance and iterated grandfather dominance, which allows searching for improvements relative to all (m minus 1)-undominated pure strategies instead of the larger set of all (m minus 1)-undominated mixed strategies.

  4. The system can efficiently compute m-undominated mixed strategies by leveraging the fact that if si is grandfather dominated given S m i × S m−i, then si is dominated given Σ m i × Σ m−i through the proof of Proposition 1 and Lemma 5.

  5. The AI system can implement a procedure to check if a pure-strategy elimination procedure terminates at round M by verifying if the mixed-strategy elimination procedure terminates at either M or M plus 1, providing a tight upper bound on divergence.

Related papers