---
id: "20261022-0239-hop-halpern-pass-costly-computation-game-theory"
title: "Halpern & Pass's 'algorithmic rationality' put a price on computation inside game theory a decade before resource-rational analysis did it for cognition, from a disjoint lineage"
type: "capture"
status: "promoted"
origin: "hop-batch"
writer_model: "claude-sonnet-5"
promoted_to: ["30-notes/claim-halpern-pass-costly-computation-breaks-nash-equilibrium-existence.md (the costly-computation framework and the Nash-existence consequence; source_quote 1)","30-notes/claim-halpern-pass-reach-rationality-mismeasured-move-from-disjoint-game-theory-lineage.md (the disjoint-lineage convergence on the 'biases are correctly costed' move; source_quote 2)"]
questions_routed: ["50-questions/question-verify-halpern-pass-lineage-disjoint-from-cognitive-science-rationality-programs.md (open — the load-bearing negative: that the paper cites none of Marr/Anderson/Oaksford & Chater/Lieder & Griffiths)"]
entities_updated: ["40-entities/entity-herbert-simon.md (Log line: Simon claimed as a root by the algorithmic-game-theory lineage)","40-entities/entity-resource-rational-analysis.md (Updates line: disjoint lineage reaches the same move independently and earlier)"]
not_promoted: ["Entity candidates Joseph Halpern and Rafael Pass — NOT hubbed. Co-authorship of the single joint paper the vault cites is a mention, not a hub (Cali ruling 2026-10-01); neither has separate standing in the vault yet. Named as mentions in both claim-notes; flagged in seek-flags.md to promote if the thread recurs.","Entity candidate Ariel Rubinstein — NOT hubbed. Named as a precursor (1986 machine-complexity-in-utility) but not read at primary this chain; a hub pointing only at this capture's mention would be a thin stub ('when unsure, don't promote'). Flagged as a [watch] in seek-flags.md as a future-chain candidate and possible fifth 'yardstick was wrong' member.","Further leads (Rubinstein 1986, Neyman 1985, Icard 2014) — research leads for future chains, not standalone claims; left in the capture body, not promoted."]
date_created: "2026-10-22T00:00:00.000Z"
hop_chain: ["seed: claim-resource-rational-analysis-extends-andersons-rational-analysis <-> claim-resource-rational-analysis-rationality-revisited-swaps-normative-yardstick-same-move-as-oaksford-chater (cosine 0.88, unlinked)","seed pair -> Lieder & Griffiths 2020 full re-read via extract_pdf (mechanism check: resolved the bridge as real, logged separately as a dup-risk stub, max_cosine 0.841)","Lieder & Griffiths 2020 Sec. 3 -> its own list of near-synonym names for the same idea: 'computational rationality (Lewis et al. 2014), algorithmic rationality (Halpern & Pass 2015), bounded rational agents (Vul et al. 2014), boundedly rational analysis (Icard 2014), the rational minimalist program (Nobandegani 2017)' (unfamiliar-name hook, max_cosine 0.785 adjacent)","that list -> WebSearch 'Halpern Pass algorithmic rationality' (unfamiliar-name + cross-domain bridge hook: Halpern is a Cornell theoretical-CS/game-theory figure, not a cognitive scientist, max_cosine 0.731 frontier once framed on its own content rather than the RRA comparison)","WebSearch result -> Halpern & Pass, 'Algorithmic Rationality: Game Theory with Costly Computation' (arXiv:1412.2993 / Journal of Economic Theory 2015), read via extract_pdf (mechanism + surprising-claim hook: charging for computation breaks Nash equilibrium existence)"]
novelty_max_cosine: 0.731
tags: ["bounded-rationality","game-theory","computational-complexity","cross-domain-bridge","resource-rationality","joseph-halpern","rafael-pass","costly-computation"]
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 (arXiv preprint); Journal of Economic Theory 159 (2015): 246-268"
source_venue: "arXiv:1412.2993 [cs.GT] (authors' own preprint of the Journal of Economic Theory 2015 article; sciencedirect.com's JET venue is a known-blocked publisher platform per sources.md)"
source_tier: 1
source_sha: "2441e7ec0f5ee90576546c37403fe333d17ef751803699b74660a0a4cbcc7d5f"
source_quote: "In this framework, many traditional game-theoretic results (such as the existence of a Nash equilibrium) no longer hold."
source_quote_2: "many concerns expressed by the emerging field of behavioral economics (pioneered by Kahneman and Tversky [1981]) can be accounted for by simple assumptions about players' cost of computation, without resorting to ad hoc cognitive or psychological models."
seek_code_commit: "d40ee39"
---


Chasing the Lieder & Griffiths (2020) passage that lists near-synonyms for
resource-rational analysis's core move — "computational rationality,"
"algorithmic rationality (Halpern & Pass 2015)," "bounded rational agents,"
"boundedly rational analysis," "the rational minimalist program" — led to
Joseph Halpern and Rafael Pass's "Algorithmic Rationality: Game Theory with
Costly Computation" (drafted 2007, conference version 2010, journal version
2015, Tier 1, arXiv:1412.2993). It gives players a Turing machine instead of a
strategy and charges their utility for the machine's running time, independent
of and over a decade before resource-rational analysis's utility-minus-cost
formalism ([[claim-resource-rational-analysis-formalizes-utility-minus-compute-cost]]).
The consequence is sharp: "many traditional game-theoretic results (such as the
existence of a Nash equilibrium) no longer hold" once computation costs money.

The paper's own stated lineage is disjoint from resource-rational analysis's:
it traces itself to Simon (1955) — already a member of the vault's
"rationality was mismeasured" family
([[claim-simon-satisficing-and-heuristic-search-same-move]]) — plus two
game-theory lines never mentioned by Lieder & Griffiths: Abraham Neyman's
finite-automata players and Ariel Rubinstein's 1986 proposal that machine
complexity itself enters utility. Marr, Anderson, and Oaksford & Chater appear
nowhere. Yet it reaches for the identical rhetorical payoff: "many concerns
expressed by the emerging field of behavioral economics (pioneered by Kahneman
and Tversky [1981]) can be accounted for by simple assumptions about players'
cost of computation, without resorting to ad hoc cognitive or psychological
models" — biases aren't irrational, the yardstick (costless computation) was
wrong, arrived at from game theory rather than psychology, and in circulation
as a 2007 draft before Lieder & Griffiths' 2020 synthesis existed.

Surprise: expected "algorithmic rationality" to be another cognitive-science
relabeling cross-referenced into the same citation network as resource-rational
analysis — found a game-theory paper with its own disjoint ancestry (Simon,
Neyman, Rubinstein) that predates RRA by over a decade and never cites Marr,
Anderson, or Oaksford & Chater, while landing on the same "biases are correctly
costed, not broken" move.

## Why this was hop-worthy
A fourth, independent lineage (algorithmic game theory) reinvents the vault's
"yardstick was wrong" family's move from economics/CS rather than psychology or
AI, and does so earlier than the cognitive-science version it structurally
anticipates.

## Further leads
- Ariel Rubinstein (1986) and Abraham Neyman (1985) — the two earlier game-theory
  lines Halpern & Pass build on; neither read at primary this hop.
- Rubinstein's finite-automaton players as a possible fifth member of the
  "rationality was mismeasured" family, pre-dating even Simon's uptake into
  economics.

## Entity candidates
- Joseph Halpern — person — Cornell CS theorist (knowledge/epistemic logic,
  game theory); unknown to vault before this capture.
- Rafael Pass — person — Cornell CS theorist, co-author; unknown to vault.
- Ariel Rubinstein — person — the older comparison figure: proposed in 1986 that
  machine complexity itself enters a player's utility, the direct ancestor of
  Halpern & Pass's framework; unknown to vault before this capture.

## Hop chain

Hop 1: Lieder & Griffiths (2020), "Resource-rational analysis" — https://cocosci.princeton.edu/papers/lieder_resource.pdf
- Hook type: mechanism question
- Hook: does the paper itself connect its Anderson/Marr-algorithmic-level
  extension (§3) to its normative-yardstick swap (§5.4), or is the seed pair's
  cosine-0.88 resemblance only in embedding space?
- Why followed: the seed task required settling this before leaving the topic.
- Key findings: confirmed real — §3 states twice (prose + figure caption) that
  resource rationality "connect[s] the computational level of analysis to the
  algorithmic level" and that this is what gives bounded optimality "a
  realistic normative standard." Logged separately as a dup-risk stub (vault
  already saturated on this exact territory, max_cosine 0.841).

Hop 2: same source, §3's list of synonym frameworks
- Hook type: the unfamiliar name
- Hook: "algorithmic rationality (Halpern & Pass 2015)" among four other
  near-identical reinventions, none of them familiar names in the vault.
- Why followed: Halpern is a theoretical-CS name in a cognitive-science
  citation list — familiar context, unfamiliar name, the textbook hook-1
  pattern.
- Key findings: confirmed via vault_entity that Halpern was wholly unknown to
  the vault.

Hop 3: WebSearch, "Halpern Pass algorithmic rationality 2015"
- Hook type: cross-domain bridge
- Hook: a Cornell theoretical-computer-scientist/game-theorist independently
  proposing a "costly computation" framework, filed under the same umbrella
  term resource-rational analysis uses.
- Why followed: cross-domain bridges are the protocol's highest-priority hook
  type; this one also lands on AI/CS, Cali's home-planet bonus.
- Key findings: the 2015 Journal of Economic Theory paper, "Algorithmic
  Rationality: Game Theory with Costly Computation," with an arXiv preprint
  dated December 2014 and an origin draft from 2007.

Hop 4: Halpern & Pass (2014/2015), full text via extract_pdf — https://arxiv.org/abs/1412.2993
- Hook type: surprising claim
- Hook: charging for computation breaks the existence of Nash equilibrium, a
  foundational game-theory result.
- Why followed: a quantified, specific mechanism claim worth reading at the
  primary rather than trusting the search summary.
- Key findings: the paper's self-stated lineage (Simon, Neyman, Rubinstein)
  never touches Marr, Anderson, or Oaksford & Chater, yet explicitly proposes
  using computation cost to explain away behavioral-economics "irrationality"
  findings — the same move, independently, from a different field, earlier.

Saved hooks not followed:
- Ariel Rubinstein's 1986 finite-automaton-complexity-as-utility proposal — the
  older figure behind Halpern & Pass's own framework; a strong lead for a future
  chain, not read at primary this hop.
- Abraham Neyman's 1985 finite-automata players in repeated prisoner's dilemma —
  the other named precursor line; not pursued.
- Thomas Icard's "boundedly rational analysis (2014)," also in the same §3 list
  and already a thin 1-mention vault presence (a different, unrelated capture)
  — a possible future person-bridge, not pursued this chain to keep the thread
  from fragmenting.

post-worthy: maybe — a clean cross-domain bridge with primary-source grounding
on both ends, but rests on one unrefereed-at-capture arXiv preprint of a
since-published journal article (concentration cap: 1 of 3 before
corroboration needed, and the JET publication itself is independent
corroboration once checked against the venue of record).