Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 37 ยท Games and Strategies

Iterated Elimination of Dominated Strategies

Solve games by repeatedly removing strictly dominated strategies, learn why order does not matter for strict dominance, and code IESDS including mixed-strategy dominance.

A rational player never plays a strictly dominated strategy. But the other players know that, and they can use it. Once a strategy is thrown out, the game shrinks, and in the smaller game a new strategy may become dominated. Repeat until nothing more can be removed. This procedure is iterated elimination of strictly dominated strategies, abbreviated IESDS (or IEDS), and it can solve games that have no dominant strategy at all.

Behind the procedure lies the assumption of common knowledge of rationality from Rational Choice and Utility: I know you are rational, you know that I know, and so on. Each round of elimination is one more level of "I know that you know that...". You already saw its twin in the beauty contest, where guesses above 67 vanish, then guesses above 44, and so on.

A worked example by hand

Consider a game where Ann picks a row and Bob picks a column. Payoffs are (Ann, Bob).

L M R
T (4, 3) (2, 7) (0, 4)
C (5, 5) (3, 1) (3, 2)
B (3, 0) (1, 4) (1, 3)

Step by step:

  1. Ann's row B is strictly dominated by C: 5 > 3, 3 > 1, 3 > 1. Remove B.
  2. Now Bob compares columns on the remaining rows T and C. Column R gives Bob 4 and 2; column M gives 7 and 1. Column L gives 3 and 5. Nothing is dominated yet. Check R against L: 4 > 3 but 2 < 5. R against M: 4 < 7 but 2 > 1. No luck for Bob.
  3. Ann compares T and C again. T gives 4, 2, 0 and C gives 5, 3, 3. C beats T in every column, so C strictly dominates T. Remove T.
  4. Only row C remains. Bob compares his columns on that row: L gives 5, M gives 1, R gives 2. L is best, so M and R are dominated. Remove them.

The surviving profile is (C, L) with payoffs (5, 5). The game is dominance solvable.

flowchart LR
    S0["3x3 game"] --> S1["Remove B<br/>(dominated by C)"]
    S1 --> S2["Remove T<br/>(dominated by C)"]
    S2 --> S3["Remove M, R<br/>(dominated by L)"]
    S3 --> S4["Solution: (C, L)"]

Each elimination step makes a new elimination possible.

IESDS in code

We can automate this loop. We keep track of which rows and columns are still alive. In each pass we check whether any alive row is strictly dominated by another alive row (comparing only the alive columns), and likewise for columns. We stop when a full pass removes nothing.

Python Iterated elimination of strictly dominated pure strategies

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Running it reproduces the hand analysis. The order of messages tells you the order of eliminations. For strict dominance the final surviving set does not depend on that order: if a strategy is strictly dominated now, it will remain strictly dominated in any smaller game, because we only ever remove other strategies that the dominating one beats anyway, and removing columns can only make fewer comparisons.

Order matters for weak dominance

For weak dominance the story changes. Removing a weakly dominated strategy can destroy ties that mattered and can lead to different survivors depending on the order. Here is a small game where two different orders give two different answers.

L R
T (1, 1) (0, 0)
M (1, 1) (2, 1)
B (0, 0) (2, 1)
Python Weak dominance: the answer depends on the order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first order leaves Ann with M or B against Bob playing R, where Ann earns 2 and Bob earns 1. The second order leaves Ann with T or M against Bob playing L, where the payoffs are (1, 1). Different orders, different predictions. Because of this ambiguity, serious analysis uses strict dominance for iteration. Weak dominance is a heuristic you apply with care.

Dominance by a mixed strategy

A pure strategy can be strictly dominated by a mixture of other strategies even when no single pure strategy dominates it. Consider Ann's payoffs in this game (Bob has two columns).

L R
T 3 0
M 0 3
B 1 1

No pure row beats B in both columns. But a 50-50 mix of T and M gives 1.5 in each column, which is better than B's 1 in each. So B is strictly dominated by the mix.

Testing this in general is a small linear program: find a probability vector p over the other rows such that p @ A > A[b] in every column. A trick is to maximize the smallest margin and see whether it is positive. We use scipy.optimize.linprog.

Python Is a row dominated by a mixture?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result reports the mixture (weights 0.5 and 0.5) and the margin (0.5). Real implementations of IESDS include this test; it removes strictly more strategies than the pure-only version.

Why IESDS matters (and its limits)

IESDS gives strong predictions with minimal assumptions, but it needs a game with a lot of structure. Many games, such as coordination games, have no dominated strategies at all, so IESDS removes nothing. For them we need the sharper tool of Nash equilibrium. A useful fact connects the two: every Nash equilibrium survives IESDS. So IESDS can narrow down the search before you look for equilibria.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main idea behind iterated elimination?

    Once dominated strategies are removed, the remaining game is smaller, so comparisons involve fewer cases and new dominance relations may appear.
  2. 2. Does the order of elimination affect the final result when using strict dominance?

    With strict dominance the final set of surviving strategies is independent of the order. This fails for weak dominance.
  3. 3. Row B pays (1, 1) and rows T and M pay (3, 0) and (0, 3). Is B dominated?

    A pure comparison finds nothing, but the 50-50 mixture gives 1.5 against either column, which strictly beats 1.
  4. 4. What is true of Nash equilibria and IESDS?

    A strictly dominated strategy is never part of a Nash equilibrium, and the argument repeats, so all equilibria survive.

Summary

  • IESDS removes strictly dominated strategies round after round until nothing more can be removed.
  • It relies on common knowledge of rationality; a game that reduces to one profile is dominance solvable.
  • With strict dominance the order of removal does not matter; with weak dominance it can.
  • A pure strategy can be dominated by a mixture; a small linear program tests this.
  • Every Nash equilibrium survives IESDS, so elimination safely narrows the search.

Next: Zero-Sum and Constant-Sum Games