Dominance and Iterated Elimination

USD 8.59 billion per day. Every search query triggers an auction in milliseconds - thousands of advertisers, thousands of bids. The optimal strategy for an advertiser in a second-price auction is truthful bidding - bid the real value. Not a little less. Exactly the true value. This is not ethics or naivety. It is mathematics: truthful bidding strictly dominates every other strategy. IESDS explains why the Vickrey mechanism works - lying is a dominated strategy and gets eliminated on the very first step. An auction worth eight billion dollars a day rests on one theorem.

• **Vickrey-Clarke-Groves (VCG) auctions**: second-price auction makes truthful bidding a dominant strategy - used by Google AdWords, Facebook Ads, eBay. Lying is strictly dominated and eliminated at step 1 of IESDS.
• **Multi-agent RL**: LOLA and MADDPG algorithms use dominance reasoning explicitly during training. DeepMind Hanabi challenge - cooperative MARL with explicit dominance reasoning outperforms baseline RL.
• **AI safety**: dominated strategies are 'failing plans' of a rational agent. If an agent selects a dominated action, rationality is violated or the value model is corrupted.

Предварительные знания

• Nash Equilibrium

Dominant Strategy

USD 8.59 billion per day. Every time a user types a query into Google, an auction runs in milliseconds - thousands of advertisers, thousands of bids. The question for an advertiser: how much to bid? Game theory's answer: bid the true value. Not slightly less. Not slightly more. Exactly what a click is actually worth. This is not advice - it is a theorem. Truthful bidding strictly dominates every other strategy.

Strategy sᵢ strictly dominates sᵢ' if uᵢ(sᵢ, s₋ᵢ) > uᵢ(sᵢ', s₋ᵢ) for ALL s₋ᵢ. Strategy sᵢ weakly dominates sᵢ' if uᵢ(sᵢ, s₋ᵢ) >= uᵢ(sᵢ', s₋ᵢ) for all s₋ᵢ, and > for at least one s₋ᵢ. Strict dominance: unconditionally better. Weak dominance: never worse, sometimes strictly better.

A dominant strategy equilibrium (DSE) is the strongest solution concept in game theory. It requires no knowledge of the opponent's rationality. No knowledge of the opponent's specific strategy. One's own rationality is sufficient - and the choice is unambiguous. This is exactly why the Vickrey mechanism (second-price auction) is so elegant: it engineers the auction so that DSE = honest bidding. Google does not ask advertisers to be honest. It makes honesty a dominant strategy.

Most interesting games lack a DSE - Battle of the Sexes, Matching Pennies, Rock-Paper-Scissors. But dominance does not lose its power: dominated strategies can be eliminated. And elimination exposes new dominated strategies that were hidden before - that is IESDS.

IESDS: Iterated Elimination

Remove a strictly dominated strategy - the game shrinks. In the smaller game, new dominated strategies appear that were not dominated before. Remove those - the game shrinks again. This process is IESDS (Iterated Elimination of Strictly Dominated Strategies). Each step relies on rationality: "since the opponent never plays X, the strategy Y is no longer needed". Each subsequent step requires knowing that the opponent knows about one's rationality.

A critical property: **order of elimination does not affect the result** - for strictly dominated strategies. It does not matter which one is removed first. The final set is always the same. Mathematically this is called confluence - as in lambda calculus. For weakly dominated strategies this property fails: order can change the result, and some NE may be eliminated.

IESDS rests on common knowledge of rationality (CKR): everyone is rational, everyone knows everyone is rational, everyone knows that everyone knows - and so on infinitely. Step 1 requires the player's own rationality. Step 2 - knowledge of the opponent's rationality. Step k - (k-1) levels of nested knowledge. In behavioral economics people stop at level 1-3. In the 'guessing game' (guess 2/3 of the average) IESDS predicts 0, real people guess around 22.

In multi-agent reinforcement learning (MARL), algorithms like LOLA (Learning with Opponent-Learning Awareness) explicitly use dominance reasoning during training. The DeepMind Hanabi challenge showed: cooperative agents capable of explicit dominance reasoning outperform agents optimizing only individual reward. Eliminating dominated strategies is not an academic exercise - it is an engineering primitive.

Rationalizability

After IESDS a set of strategies remains. Not arbitrary ones - only those a rational player can justifiably choose. A strategy is rationalizable if it is a best response to some rational beliefs about the opponent's actions. Beliefs must be rational - the opponent also best-responds to rational beliefs of their own. Recursive, without end.

Strategy sᵢ is rationalizable if there exists a chain of beliefs: - sᵢ is a best response to beliefs about sigma₋ᵢ - sigma₋ᵢ contains only rationalizable strategies of others - ...recursively For two-player games: the set of rationalizable strategies = the set surviving IESDS. For three or more players: rationalizability can be strictly broader than IESDS.

In AI safety research, rationalizability is used to analyze agent behavior. MIRI and Anthropic Alignment use dominance reasoning to classify agent actions: dominated strategies are 'failing plans' that a rational agent would never select under any model of the world. If an agent chooses a dominated strategy, this signals a violation of rationality or a corrupted value model - exactly the kind of anomaly corrigibility research targets.

Key ideas

• **Strict dominance** - a strategy is better under ALL opponent actions; DSE is the strongest solution concept and requires no knowledge of the opponent
• **Weak dominance** - never worse, sometimes strictly better; removing weakly dominated strategies is risky - some NE may be lost
• **IESDS** - iterated removal of strictly dominated strategies; order does not matter; never removes NE; requires common knowledge of rationality
• **Rationalizability** - strategies justifiable by rational beliefs; for two-player games coincides with IESDS

Related topics

Dominance and IESDS are the first step in analyzing any game, narrowing the space of possible outcomes:

• Nash Equilibrium — NE is a subset of IESDS: all Nash equilibria survive iterated elimination
• Prisoner's Dilemma — Classic case where DSE exists but leads to a Pareto-suboptimal outcome
• Introduction to RL — Multi-agent RL uses dominance reasoning to find Nash-compatible strategies

Вопросы для размышления

• The Vickrey auction makes truthful bidding a dominant strategy. But Google does not use a pure Vickrey - the rules are more complex. How does this affect whether truthful bidding is still dominant?
• In the 'guessing game' (guess 2/3 of the average) people stop at 1-3 steps of IESDS instead of the theoretically infinite chain. Does this mean people are irrational - or that common knowledge of rationality is an unrealistic assumption?
• Mechanism design engineers rules so that the desired action becomes a dominant strategy. What other real-world mechanisms achieve this - taxes, laws, social norms?

Связанные уроки

• gt-02 — Nash equilibrium - foundation for understanding dominance
• gt-04 — Prisoner's dilemma - dominance in action, DSE vs Pareto
• gt-05 — Incomplete information games: dominance under uncertainty
• rl-01 — Multi-agent RL: IESDS as iterative best-response reasoning
• prob-07-expectation — Expected payoff when dominated by mixed strategies
• alg-21-dp