Mixed strategy elimination trails pure strategy by one round in games
Iterated Elimination of Dominated Mixed Strategies
Computer Science and Game Theory
Summary
The paper studies two ways to simplify games by successively removing less effective strategies. The first method removes strategies that are not helpful even when mixed with others, and the second method removes strategies only if they are pure and dominated. The authors find that the mixed strategy removal procedure takes at most one extra step compared to the pure strategy one. They also show how to check mixed strategy improvements by looking only at pure strategies, simplifying analysis.
What this means in practice
- •For market designers: Determine when simplifying agents' strategies with mixed strategies gains little over eliminating pure strategies in auction and matching markets.
- •For algorithm designers: Use the equivalence of mixed strategy checks against pure strategies to optimize iterative strategy elimination algorithms in continuous games.
A theory result. No direct application yet.
Authors
Federico Echenique, Amanda Friedenberg
Abstract
This note compares two iterated dominance procedures, one based on eliminating mixed strategies and one based on eliminating pure strategies. It shows that, in compact and continuous games, the mixed-strategy procedure can trail the pure-strategy procedure by at most one round: If the pure-strategy procedure terminates at round $M$, the mixed-strategy procedure terminates at either $M$ or $M+1$, and this bound is tight. It also provides two characterizations of the mixed-strategy procedure that are round-for-round equivalent to it and that require checking for improvements only against opponents' pure strategies.