TL;DR
This paper introduces a novel game-theoretic framework that incorporates the cost of computation into strategic decision-making. By treating players as Turing machines with associated computational costs, the authors demonstrate that traditional game theory assumptions, like the existence of Nash equilibria, no longer hold, offering a more psychologically realistic model of rational behavior.
What Problem Does This Paper Address?
Traditional game theory often assumes that players can perform an unlimited amount of computation "for free." This simplification, while mathematically convenient, can lead to predictions that starkly contrast with observed human behavior. For instance, in a simple game where a player must decide if a large number is prime or composite, traditional theory suggests they should always compute the correct answer, even if the computational cost is astronomical. However, humans intuitively understand that at some point, the cost of computation outweighs the potential gain, leading them to "play it safe." This paper addresses this gap by developing a framework where computational cost is an explicit factor in a player's utility, aiming to bridge the gap between theoretical rationality and observed behavior.
Methods
The core of the paper is the introduction of a "Bayesian machine game." In this framework, each player is modeled as a Turing machine (TM). Instead of simply choosing an action, a player chooses a TM. The output of this TM, when run on the player's "type" (representing private information), determines the player's action. Crucially, each TM is associated with a complexity function that quantifies the computational cost (e.g., running time, space used) for a given input. A player's utility is then a function of the actions taken by all players and the computational complexities of their chosen machines. This allows for scenarios where a player might choose a simpler, less computationally intensive strategy, even if it's not strictly optimal in a costless computation model, to avoid high computational expenses. The paper then redefines Nash equilibrium within this new framework, where a strategy profile is a Nash equilibrium if no player can improve their expected utility by unilaterally switching to a different TM.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Computational Cost as a Utility Factor: The most significant insight is the explicit integration of computational cost into utility functions. This moves beyond abstract strategy selection to a more grounded model of decision-making where resources (computation) are finite and have value.
- Challenging Traditional Game Theory Results: The paper demonstrates that fundamental results like the existence of Nash equilibria do not necessarily hold when computation is costly. This forces a re-evaluation of established game-theoretic concepts.
- Psychologically Plausible Explanations: By incorporating computational costs, the framework offers intuitive explanations for observed behaviors that are difficult to reconcile with traditional models. This includes cooperation in repeated games and biases in information processing.
- Costly Randomization: The paper highlights how charging for randomization (as a computational cost) can explain why players in games like rock-paper-scissors might not play the theoretically optimal mixed strategy.
Key Results
- Nash Equilibrium May Not Exist: The paper provides an example (rock-paper-scissors) where a Nash equilibrium does not exist when randomization incurs a cost.
- Cooperation in Repeated Prisoner's Dilemma: The framework can explain cooperation in finitely repeated prisoner's dilemma. For instance, the "tit-for-tat" strategy, which might be computationally expensive to implement optimally in later rounds due to the need for counting, can become a Nash equilibrium if the cost of computation outweighs the gain from defection.
- First-Impression Bias: The paper suggests that a "first-impression-matters" bias in information processing can be explained by a small cost associated with absorbing or interpreting new information. Agents may stop processing new signals once the marginal cost of processing exceeds the expected gain.
Limitations and Future Work
The authors acknowledge several limitations and suggest future research directions:
- Assumption of Known Costs: The current framework assumes agents perfectly understand the computational costs associated with each Turing machine. Future work could model uncertainty about these costs.
- Cost of Computing Probabilities and Utilities: The paper doesn't explicitly charge players for the computation required to determine probabilities or utilities. Extending the framework to include these costs is a natural next step.
- Generating Alternatives: The model assumes players have access to a given set of TMs. In reality, generating new strategies or TMs can also be computationally intensive, and this aspect could be incorporated.
- Exploration Costs: The paper doesn't account for the cost of "exploring" or searching for better strategies. This is a complex area that the authors are actively investigating.
Summary updated