Game Theory with Costly Computation

43 concepts26 papers1 proposal

Classical game theory relies on a convenient fiction: the assumption of perfect, costless rationality. In this idealized framework, agents possess infinite computational resources. They can instantly look ahead to the end of time, evaluate every branch of a massive game tree, and select the mathematically optimal move without spending a single unit of time, memory, or energy.

In reality, computation is a physical process that consumes scarce resources. Whether an agent is a human calculating an auction bid, a software agent negotiating a contract, or a neural network training on a game state, thinking has a cost. When the computational effort required to find a strategy exceeds the available time or processing power, the predictions of classical game theory break down. Strategies that are theoretically optimal become practically useless if they are computationally intractable.

To bridge this gap, a growing body of research integrates computational constraints directly into the fabric of game theory. By treating computation as a costly, finite resource, this direction redefines what it means to act rationally in a complex world.

The Core Mechanism: Internalizing Computational Costs

The foundational insight of this field is that computation should not be treated as an external step performed before a game, but rather as a core component within the game itself.

To build intuition, consider how classical utility is calculated. Typically, an agent chooses a strategy, and their utility is simply the payoff dictated by the game's rules. In the framework of algorithmic rationality, however, the utility function is modified to account for the effort of thinking:

$$\text{Net Utility} = \text{Game Payoff}(\text{Strategy}) - \text{Computational Cost}(\text{Strategy})$$

As formulated by Joseph Halpern et al. in Algorithmic Rationality: Game Theory with Costly Computation, agents can be modeled as Turing machines rather than abstract rational entities. Every machine has an associated cost function based on the resources (like time or memory) it consumes to compute an action.

This simple shift fundamentally changes how we evaluate "optimal" behavior. A highly complex strategy might yield a slightly higher game payoff than a simple heuristic, but if the computational cost of running that complex strategy is massive, its net utility becomes negative. Consequently, a simpler strategy becomes the truly rational choice.

Furthermore, these costs are not always static or isolated. As noted by Eli Ben-Sasson et al. in An Approach to Bounded Rationality, computational costs can be interactive: the resource consumption or complexity of a player's strategy can be directly influenced by the specific counter-strategies chosen by their opponent.

Why Bounded Capacity Stabilizes Cooperation

One of the most compelling features of this framework is its ability to explain real-world behaviors that classical game theory labels as "irrational." A classic example is the finitely repeated Prisoner's Dilemma. Under perfect rationality, backward induction dictates that both players will defect on the very last round, which causes cooperation to unravel all the way back to the first round. Yet, in practice, humans and algorithms frequently cooperate.

When we introduce computational costs, this paradox disappears. Tracking the exact history of an opponent's moves, counting the precise number of remaining rounds, and adjusting strategies accordingly requires memory and processing power. As shown by Joseph Y. Halpern et al. in Beyond Nash Equilibrium: Solution Concepts for the 21st Century, when maintaining a detailed history of play is expensive, complex defection strategies become suboptimal, making sustained cooperation a stable computational Nash equilibrium.

Taking this a step further, Lijie Chen et al. demonstrate in Bounded Rationality of Restricted Turing Machines that strict resource bounds can paradoxically act as a benefit. If agents are modeled as Turing machines restricted to polynomial time or logarithmic space, they may simply lack the raw computational capacity required to calculate intricate, deceptive betrayal strategies. In this light, computational boundedness serves as a credible commitment mechanism: because an agent cannot compute a complex defection, their partner can trust them to cooperate.

Computation as a Strategic Action

In complex, time-sensitive environments, agents cannot afford to compute a complete strategy beforehand. Instead, they must treat computation itself as an active choice during the game, deciding dynamically where to allocate their limited "thinking power."

This perspective is explicitly modeled by Kate Larson et al. in Deliberation in Equilibrium: Bargaining in Computationally Complex Problems. In a multi-agent bargaining scenario where the underlying problem is too complex to solve perfectly, agents must strategically allocate their limited deliberation time. They must choose whether to spend time improving their own fallback solution, optimizing a joint solution, or even computing solutions for their opponent—all while trying to anticipate how much computation the other agent is performing.

This shift moves the focus away from calculating static, uncomputable equilibria and toward what Yoav Shoham terms "game theory pragmatics" in Game Theory Pragmatics: A Challenge for AI. Instead of assuming infinite reasoning, practical multi-agent systems focus on how resource-constrained agents navigate complex game states using heuristic search, planning, and truncated lookaheads.

Weaponizing Complexity in Mechanism Design

While computational limitations are often viewed as a hurdle for agents, they can be leveraged as a powerful tool by mechanism designers. Traditional mechanism design assumes that participants will always calculate and execute the most profitable way to cheat or manipulate a system (such as lying about their true preferences in an auction).

However, if calculating an optimal lie is computationally harder than telling the truth, designers can use this tractability gap to enforce honesty. For instance, Yoram Bachrach et al. exploit this principle in Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents. They design a network flow mechanism where strategic manipulation is theoretically possible, but finding the exact optimal deviation is an NP-complete problem. Because the participating agents are computationally bounded, the sheer difficulty of calculating the optimal lie acts as a barrier, forcing them to default to honest reporting.

As summarized by Vincent Conitzer in Computational Aspects of Mechanism Design, the computational complexity of agent participation should not be viewed merely as an obstacle. Instead, by treating computational hardness as a deliberate design variable, we can build economic systems that remain robust and efficient precisely because the agents within them have finite minds.

Key Foundational Work

Automated Negotiation: Prospects, Methods and Challenges (2000) — contributed 2 concept elements to this direction.
Deliberation in Equilibrium: Bargaining in Computationally Complex Problems (2000) — contributed 1 concept elements to this direction.
The Formation of Coalitions Among Self-Interested Agents (1994) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_unbounded_rationality_assumption_5680ee6f,
  title = {unbounded rationality assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unbounded-rationality-assumption/rdr_5680ee6fc9c74ba7b77ec24db0a0263a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_unbounded_rationality_assumption_5680ee6f_v1,
  title = {unbounded rationality assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unbounded-rationality-assumption/rdr_5680ee6fc9c74ba7b77ec24db0a0263a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake