# Algorithmic Rationality: Game Theory with Costly Computation

arXiv: https://arxiv.org/abs/1412.2993 · HTML: https://mlsanity.com/paper/1412.2993/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Dec 2014.

## Built on by (most cited first, 4 of 4)

- [Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents](https://mlsanity.com/paper/2505.02077/) (2025)
- [Beyond Preferences in AI Alignment](https://mlsanity.com/paper/2408.16984/) (2024)
- [Will AI Trade? A Computational Inversion of the No-Trade Theorem](https://mlsanity.com/paper/2512.17952/) (2025)
- [The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach](https://mlsanity.com/paper/2608.16438/) (2026)

## Abstract (arXiv)

We develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. In this framework, many traditional game-theoretic results (such as the existence of a Nash equilibrium) no longer hold. Nevertheless, we can use the framework to provide psychologically appealing explanations of observed behavior in well-studied games (such as finitely repeated prisoner's dilemma and rock-paper-scissors). Furthermore, we provide natural conditions on games sufficient to guarantee that equilibria exist.