Dominant Strategies and Iterative Elimination

The Logic of "Eliminating Unprofitable Actions"

Before searching for a Nash equilibrium, it is useful to ask a simpler question: are there strategies that are never profitable to use? Such strategies are called dominated: no matter what the opponents do, another strategy is always better. A rational player will never choose a dominated strategy — it can be "eliminated" to simplify the game.

By repeating this procedure iteratively, we sometimes arrive at a single outcome — the equilibrium. This method requires not only rationality from each player, but also common knowledge of rationality: I know you are rational; you know that I know; and so on.

Strict and Weak Domination

Strict domination: Strategy $s_i$ strictly dominates $s_i'$ if for all $s_{-i} \in S_{-i}$: $u_i(s_i, s_{-i}) > u_i(s_i', s_{-i})$. A strictly dominated strategy is never chosen by a rational player, regardless of beliefs about the opponents.

Weak domination: $u_i(s_i, s_{-i}) \geq u_i(s_i', s_{-i})$ for all $s_{-i}$, and for at least one $s_{-i}$ the inequality is strict. Weakly dominated strategies require more careful handling — elimination may depend on the order.

Domination by mixed strategies: A pure strategy may be dominated by a mixed strategy, even if no other pure strategy dominates it. This is important: pairwise domination checks are not sufficient.

IESDS Algorithm

IESDS (Iterated Elimination of Strictly Dominated Strategies):

1. Find strictly dominated strategies for each player
2. Eliminate them from the game
3. Repeat with the remaining (smaller) game
4. Continue until stabilization

Theorem: The order of elimination in strict domination does not affect the final result (order invariance). For weak domination, it may affect the outcome!

If IESDS leads to a single profile — it is the unique Nash equilibrium. If it leads to several — IESDS has not solved the problem of equilibrium selection.

Numerical Example: 3×3 Matrix

Step 1. Analyze Player 2's strategies (columns). Compare C and R: for T: $u_2$(C)=1, $u_2$(R)=2 → R>C; for M: $u_2$(C)=4, $u_2$(R)=6 → R>C; for B: $u_2$(C)=6, $u_2$(R)=8 → R>C. Strategy C is strictly dominated by R. Eliminate C.

Step 2. Remaining game (without C):

Analyze Player 1's strategies. Compare T and B: for L: $u_1$(T)=4, $u_1$(B)=3 → T>B; for R: $u_1$(T)=6, $u_1$(B)=2 → T>B. Strategy B is strictly dominated by T. Eliminate B.

Step 3. Remaining game:

Analyze Player 1's strategies. T vs M: for L: 4>2 → T better; for R: 6>3 → T better. M is strictly dominated by T. Eliminate M.

Step 4. Player 1 remaining — only T. Player 2 chooses: $u_2$(L|T)=3, $u_2$(R|T)=2 → L better.

Result: (T, L) — the unique Nash equilibrium. Payoffs: (4, 3).

Prisoner's Dilemma via Domination

In the prisoner's dilemma, "Betray" strictly dominates "Silent" for each player — one step of IESDS leads to the equilibrium (Betray, Betray). This explains the paradox: the equilibrium is unique and found by elimination of dominated strategies, but it is Pareto-suboptimal.

Limited Depth of Strategic Thinking

IESDS assumes infinite "embedding" of knowledge about rationality. In reality, people think strategically only up to a few levels (level 0: chooses randomly; level k: optimally responds to level k−1).

Nagel's experiment — p-beauty contest: Players name a number from 0 to 100. The winner is the one whose number is closest to $p \times$ (average of all). For $p = 2/3$:

Level 0: naive choice 50. Level 1: thinks everyone is at level 0, chooses $50 \times 2/3 \approx 33$. Level 2: chooses $33 \times 2/3 \approx 22$. Level 3: $\approx 15$. Nash equilibrium: 0.

In real experiments, most answer 22–33. This is "level 2–3" strategic thinking. Investment fund managers show level 4–5 — higher than students, but still far from equilibrium.

Real Application: Pricing in Aviation

Airlines set prices almost simultaneously several times a day. Strategies: keep high price (H) or reduce (L). If H strictly dominates L for any competitor's strategy — there will be no price war. If not — IESDS does not yield an answer; analysis of the repeated game is needed.

Dominant Strategies in Market and Auction Design

The concept of dominant strategies has fundamental practical significance: a mechanism in which truthful behavior is a dominant strategy for every participant is called strategy-proof. The Vickrey (second-price) auction is a classic example: regardless of what others do, truthful declaration of one’s own value dominates. This property underpins the VCG (Vickrey–Clarke–Groves) mechanism, applied in spectrum auctions and online advertising. The iterative elimination of strictly dominated strategies (IESDS) is used in behavioral economics to predict outcomes of experiments. "k-level thinking" models show: real people usually do 1–2 elimination iterations, not infinitely many, which explains deviations from Nash equilibrium in experiments. In corporate negotiations, knowing which strategies are strictly dominated for the opponent allows one to "cut down" the set of possible outcomes and more accurately predict behavior. This is used by investment banks in structuring complex deals with multiple counterparties.

Task: Given a matrix. Apply IESDS. Does the result coincide with the Nash equilibrium? Is there domination by mixed strategies?