TL;DR
This paper introduces a novel framework for analyzing sequential equilibrium in games where players use Turing machines (TMs) to compute their strategies, incorporating the cost of computation. They demonstrate that this computational setting resolves long-standing conceptual issues with sequential equilibrium in games of imperfect recall, leading to a more unified understanding of ex ante and interim notions of rationality.
What Problem Does This Paper Address?
Traditional game theory often assumes perfect recall, meaning players remember all past information. However, in real-world scenarios and more complex games, players might rationally choose to "forget" or have imperfect recall due to computational limitations or costs. This paper tackles the challenge of defining and analyzing sequential equilibrium – a solution concept that captures rational play at every decision point – in the context of games where players employ Turing machines (TMs) to compute their strategies. The cost of computation introduces a trade-off: players can invest more in computation for better accuracy but incur higher costs. This setting naturally leads to imperfect recall, and the authors aim to reconcile the theoretical difficulties that arise with sequential equilibrium in such scenarios, particularly the distinction between ex ante (planning before the game) and interim (reconsidering during the game) rationality.
Methods
The authors extend the concept of Bayesian games to "Bayesian machine games" where players choose Turing machines (TMs) to represent their strategies. The TM's output is its action, and its complexity (e.g., running time) affects the player's utility. They define sequential equilibrium in two ways:
- Ex ante sequential equilibrium: A player commits to a strategy (TM) chosen before the game starts, ensuring it remains optimal even off the equilibrium path.
- Interim sequential equilibrium: A player can reconsider their strategy at each information set (represented by TM states) and switch to a different TM if it's more optimal at that point.
A key innovation is that information sets are not exogenously given but are determined endogenously by the TM's states. They also introduce the concept of "local variants" of TMs, which are crucial for relating the two notions of sequential equilibrium.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Computational cost resolves imperfect recall issues: The computational framework naturally models imperfect recall and, importantly, resolves some deep conceptual problems previously associated with interim sequential equilibrium in standard games of imperfect recall.
- Endogenous information sets: Unlike traditional game theory, information sets are determined by the chosen TM's states, offering a more nuanced view of player knowledge.
- Unification of ex ante and interim rationality: Under natural assumptions (like local complexity functions), the ex ante and interim notions of sequential equilibrium coincide in these computational games, simplifying the analysis.
- TMs as a formal model for "forgetting": The ability of TMs to have fewer states or different transition functions directly models rational forgetting or imperfect recall due to computational constraints.
Key Results
- The paper provides formal definitions for ex ante and interim sequential equilibrium in Bayesian machine games.
- They show that in games with local complexity functions, interim sequential equilibrium implies ex ante sequential equilibrium, and vice-versa.
- Under the assumption of "positive state cost" (where adding states to a TM never improves utility), every Nash equilibrium (NE) is shown to be an ex ante sequential equilibrium.
- For games with a finite set of possible TMs, they prove the existence of an ex ante sequential equilibrium whenever a Nash equilibrium exists.
Limitations and Future Work
- The paper acknowledges that while their framework resolves some issues, the interpretation of extensive-form games as mediated games can still affect equilibrium outcomes, leaving open the question of the "right" way to interpret such games.
- Future work includes exploring how to charge for the computation of beliefs and strategies themselves, and how these computational costs should affect solution concepts.
- They also plan to explore the implications of these findings for reconciling determinism and free will, suggesting that agents might feel they have choices at "conscious states" but ultimately stick to their "program" because it's optimal.
Summary updated