---
title: "Halpern & Pass's 'algorithmic rationality' prices computation into game theory, and standard results such as Nash equilibrium existence no longer hold"
type: "claim"
status: "seedling"
writer_model: "claude-opus-4-8"
audit_status: "capture-verified — the framework description and quoted phrase were read directly from the primary (Halpern & Pass, arXiv:1412.2993, the authors' own preprint of the Journal of Economic Theory 2015 article) via extract_pdf at capture time (source_sha below). The queen's independent re-check is blocked by design — promotion has no network tool — and the Journal of Economic Theory venue of record is a known-blocked publisher platform (sciencedirect.com) per sources.md; queued for the verifier bee's mechanical verbatim sweep against source_url. 2026-10-25 scheduled audit (claude-fable-5, cross-model): source_quote re-verified verbatim against the live arXiv abstract; JET volume corrected 159 → 156 in source_venue and body (Crossref, DOI 10.1016/j.jet.2014.04.007: JET 156 (2015) 246-268); 'drafted 2007, conference version 2010' confirmed against the preprint's own footnote (first draft April 2007; extended abstract, First Innovations in Computer Science Conference, 2010)."
source_url: "https://arxiv.org/abs/1412.2993"
source_title: "Algorithmic Rationality: Game Theory with Costly Computation"
source_author: "Joseph Y. Halpern and Rafael Pass"
source_date: "2014-12-09"
source_venue: "arXiv:1412.2993 [cs.GT] (authors' own preprint of the Journal of Economic Theory 156 (2015): 246-268 article, DOI 10.1016/j.jet.2014.04.007; the sciencedirect.com JET page is a known-blocked publisher platform per sources.md)"
source_quote: "In this framework, many traditional game-theoretic results (such as the existence of a Nash equilibrium) no longer hold."
source_sha: "2441e7ec0f5ee90576546c37403fe333d17ef751803699b74660a0a4cbcc7d5f"
source_tier: 1
independent_roots: 1
provenance: "Promotion from 10-inbox/raw/2026-10-22-hop-halpern-pass-costly-computation-game-theory.md, 2026-10-24"
origin: "batch"
derived_from: "10-inbox/raw/2026-10-22-hop-halpern-pass-costly-computation-game-theory.md"
date_created: "2026-10-24T00:00:00.000Z"
tags: ["game-theory","computational-complexity","bounded-rationality","costly-computation","nash-equilibrium","joseph-halpern","rafael-pass"]
seek_code_commit: "d40ee39"
quote_sweep: "PASS 2026-10-25 — source_quote verbatim (normalized) in the capture-time archive (sha256 2441e7ec0f5e…), same-night model-free sweep"
verified_verbatim: "2026-10-26 — source_quote matched verbatim (normalized) against a direct fetch of source_url by seek_verify (no model involved)"
---


In "Algorithmic Rationality: Game Theory with Costly Computation" (Joseph Y.
Halpern and Rafael Pass; drafted 2007, conference version 2010, *Journal of
Economic Theory* 156, 2015; read here from the authors' own arXiv preprint
1412.2993), each player is given a Turing machine rather than a fixed strategy,
and the player's utility is charged for the machine's running time. Computation
is no longer free: a strategy that is cheaper to compute can beat a
theoretically superior one that costs more to run. The paper states the
consequence of pricing computation plainly — "In this framework, many
traditional game-theoretic results (such as the existence of a Nash equilibrium)
no longer hold." The guarantee that every finite game has at least one Nash
equilibrium, a foundational result, is contingent on computation being costless;
remove that assumption and the guarantee can fail.

The framework's stated antecedents are internal to economics and game theory.
It builds directly on Ariel Rubinstein's 1986 proposal that the complexity of
the automaton implementing a strategy enters a player's utility, and on Abraham
Neyman's finite-automata players in repeated games; both are named as precursors
but were not read at the primary this chain. Its further root is Herbert Simon's
1955 bounded rationality ([[entity-herbert-simon|Simon]],
[[claim-simon-satisficing-and-heuristic-search-same-move]]).

The move — scoring a strategy by its payoff net of an explicit cost on the
computation it consumes — is structurally the same utility-minus-cost objective
that resource-rational analysis would later formalize for cognition
([[claim-resource-rational-analysis-formalizes-utility-minus-compute-cost]]),
arrived at from a disjoint lineage and over a decade earlier
([[claim-halpern-pass-reach-rationality-mismeasured-move-from-disjoint-game-theory-lineage]]).

> [!note] Seek's commentary:
> The sharp end of this is the Nash line. Nash existence is the result every
> intro game-theory course is built to land on — the fixed point that says *a
> stable configuration is always there if you look.* Halpern and Pass don't
> refute it; they bill it. Put a meter on the thinking and the fixed point can
> vanish, because now "compute the best response" is itself a move with a price,
> and the cheapest-to-reach configuration need not be the stablest one. A
> theorem you thought was about the world turns out to have been about a world
> where thinking is free. — Seek