A logical characterization of iterated admissibility

Joseph Y. Halpern, Rafael Pass

Introduction

In game theory, the concept of Iterated Admissibility (IA)—the successive elimination of weakly dominated strategies—is a fundamental tool for predicting player behavior. A strategy is weakly dominated if another strategy exists that performs at least as well in all scenarios and strictly better in at least one. While intuitively appealing, IA has long been plagued by an epistemic paradox: to justify the elimination of a strategy, a player must initially consider that strategy possible by assigning it positive probability. However, once the strategy is eliminated, the logic of the game suggests it should no longer be expected to occur.

Previous attempts to resolve this tension, most notably by Brandenburger, Friedenberg, and Keisler (2008), utilized lexicographic probability sequences (LPS). This approach effectively uses infinitesimals to suggest a strategy is "almost impossible" but still carries enough weight to be considered. However, these models often require "complete structures," which are mathematically complex and frequently uncountable. In "A Logical Characterization of Iterated Admissibility," Joseph Y. Halpern and Rafael Pass propose a more streamlined solution using standard probability and the logical concept of "all I know."

The Epistemic Logic Framework

Halpern and Pass shift the focus from complex probability sequences to Epistemic Modal Logic. They define a series of formal languages ($L_1$ through $L_4$) to express player beliefs. The core of their framework relies on two primary operators:

  • $B_i \phi$: Player $i$ believes $\phi$ with probability 1.
  • $\langle B_i \rangle \phi$: Player $i$ considers $\phi$ possible with some positive probability.

The authors introduce the concept of Strong Admissibility, which leverages the "all I know" operator ($O_i$). This operator captures a specific epistemic state: an agent believes a fact (e.g., "the other players are rational") and considers everything else consistent with that fact to be possible. This provides a natural bridge to IA: a player survives rounds of deletion because they assume others are rational, while simultaneously accounting for all possible strategies that rationality might allow.

Key Insights: "All I Know"

The paper’s central contribution is the realization that IA is the logical consequence of agents having "only" certain knowledge. If an agent knows only that their opponents are rational, they must assign positive probability to every strategy consistent with that rationality. This eliminates the need for infinitesimals; standard probability measures are sufficient if the logic is framed correctly.

Furthermore, this characterization is structure-independent. Unlike previous models that required uncountable "complete" structures, Halpern and Pass demonstrate that their conditions can be satisfied in structures with a finite number of states. This makes the logic applicable to a much broader range of game-theoretic scenarios.

Theoretical Results

The authors formalize these insights through two primary theorems:

  1. Theorem 2.7: A strategy $\sigma$ survives $k$ rounds of iterated deletion of weakly dominated strategies if and only if there exists a structure and a state where $\sigma$ is played and a specific formula ($D^k$), characterizing the logic of IA, holds.
  2. Theorem 3.2: Iterated Admissibility is shown to be equivalent to "strong admissibility." This confirms that an agent's belief is exactly characterized by the rationality of others.

By constructing "canonical structures"—where every state corresponds to a unique, satisfiable set of formulas—the authors prove that their logical definitions align perfectly with the physical strategies played in a game. They also show that their canonical structure is a "complete structure" in the sense of earlier literature, effectively unifying the new logical approach with traditional game-theoretic models.

Limitations and Language Sensitivity

The authors identify a subtle constraint regarding convergence. There is no single state where the formula for IA holds for all rounds $k$ simultaneously. This is because the requirements for the first round (considering all strategies possible) eventually conflict with the requirements for subsequent rounds (knowing that certain strategies have been deleted).

Additionally, the "all I know" operator is highly sensitive to the richness of the language used. If the language is too rich (uncountable), it becomes mathematically impossible to assign positive probability to every distinct possibility. The authors identify a "sweet spot" in a countable language ($L_3$), which is rich enough to express the necessary epistemic states but restricted enough to maintain probabilistic consistency.

Conclusion

Halpern and Pass provide a robust, logical foundation for Iterated Admissibility that avoids the mathematical overhead of non-standard analysis. By linking game theory to the "all I know" concept in logic, they offer a clearer understanding of how rationality and possibility interact in strategic environments. This work opens the door for extending logical characterizations to other solution concepts and dynamic games where information evolves over time.

Summary updated

BibTeX
@inproceedings{halpern2009logical,
  author = {Joseph Y. Halpern and Rafael Pass},
  title = {{A logical characterization of iterated admissibility}},
  booktitle = {TARK},
  year = {2009},
  doi = {10.1145/1562814.1562836},
}
Figure