Halpern & Pass's 'algorithmic rationality' prices computation into game theory, and standard results such as Nash equilibrium existence no longer hold

game-theorycomputational-complexitybounded-rationalitycostly-computationnash-equilibriumjoseph-halpernrafael-pass

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 (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).