Iterated backward inference

Oliver Schulte2003 · DOI

TL;DR

This paper introduces Iterated Backward Inference (IBI), a new algorithm for predicting rational behavior in games. IBI is based on the epistemic assumption of "Respect for Public Preferences," which states that if players commonly believe someone prefers option A to option B, they will act as if that preference holds. IBI generalizes standard backward induction and Dekel-Fudenberg procedures, offering a unified approach to finding strategies that are not properly rationalizable.

What Problem Does This Paper Address?

Game theory aims to predict rational behavior in strategic interactions. A key challenge is defining "rationality" and deriving its implications for player strategies. While concepts like backward induction and Nash equilibrium exist, they often rely on strong assumptions or don't fully capture the nuances of strategic reasoning. This paper tackles the question of what predictions can be made about player behavior given a weaker, yet still powerful, epistemic assumption: "Respect for Public Preferences." This assumption is crucial because it formalizes how players should react when they commonly believe another player has a specific preference, even if that preference isn't directly observed. The paper seeks to develop a computational procedure that derives the consequences of this assumption and to show its relationship to existing solution concepts like proper rationalizability.

Methods

The paper introduces Iterated Backward Inference (IBI), an algorithm that iteratively eliminates strategies from a game tree. IBI combines two core principles:

  1. Sequential Admissibility (Local Dominance): At each information set, strategies that are weakly or strictly dominated by other available strategies are eliminated. This is a "local" step, focusing on the choices available at a specific point in the game.
  2. Entailment Inference (Backward Inference): This principle connects eliminations at different information sets. If a strategy is considered unlikely at an earlier information set (meaning it's ruled out by the player's beliefs), and that information set "entails" a later one (meaning any path through the earlier set also leads to the later set), then the strategy is also considered unlikely at the later information set. This essentially propagates eliminations backward through the game tree.

IBI is built upon the framework of lexicographic probability systems (LPS), which allow agents to represent beliefs with a hierarchy of preferences, where lower-order beliefs are prioritized. The paper also formalizes "Respect for Public Preferences" using LPS and common belief.

Datasets

Not discussed in the paper. The paper uses theoretical game examples (Centipede Game, Kohlberg's Game) to illustrate its concepts and algorithms.

Key Insights and Ideas

  • "Respect for Public Preferences" is a powerful epistemic assumption: The paper shows that this relatively weak assumption, when commonly believed, has significant implications for player behavior, leading to the elimination of certain strategies.
  • IBI unifies existing solution concepts: IBI is shown to generalize both standard backward induction (for perfect information games) and the Dekel-Fudenberg procedure (for strategic form games). This provides a single framework for understanding these different solution methods.
  • IBI identifies non-properly rationalizable strategies: The paper establishes that strategies eliminated by IBI are not properly rationalizable. This makes IBI a tool for finding strategies that are "too irrational" to be played by sophisticated agents.
  • Game tree representation matters: The paper highlights that IBI's output can depend on the specific game tree representation of a strategic form game, suggesting that the structure of information sets plays a crucial role in the elimination process.

Key Results

  • IBI is a valid procedure: For finite games with perfect recall, if "Respect for Public Preferences" and "Lexicographic Rationality with Full Support" are common beliefs, then IBI correctly predicts which strategies will not be played.
  • IBI generalizes backward induction: For games with perfect information and a unique subgame perfect equilibrium, IBI yields the same outcome as backward induction.
  • IBI generalizes Dekel-Fudenberg: For strategic form games represented as game trees with two information sets, IBI is equivalent to first eliminating weakly dominated strategies and then iteratively eliminating strictly dominated strategies.
  • IBI returns a non-empty result: In finite games with perfect recall, IBI is guaranteed to leave at least one strategy profile.

Limitations and Future Work

  • Dependence on game tree structure: The paper notes that IBI can yield different results for different game trees representing the same strategic form game. The authors suggest that finding a "canonical" game tree for any given game, which would maximize the elimination power of IBI, is an important open question.
  • Forward Induction: The paper explicitly states that IBI does not incorporate forward induction arguments. It raises the question of whether additional epistemic principles can be found to validate forward induction.
  • Generalizing to more players and chance moves: While the paper focuses on 2-player games, it mentions that generalization to more players and chance moves is straightforward but adds technical complexity.

Summary updated

BibTeX
@misc{schulte2003iterated,
  author = {Oliver Schulte},
  title = {{Iterated backward inference}},
  year = {2003},
  doi = {10.1145/846242.846244},
}
Figure