Bounded Löb and practical provability

How does game theory work when everyone is a computer program who can read everyone else's source code? This is the problem of 'program equilibria'. In this episode, I talk with Caspar Oesterheld on work he's done on equilibria of programs that simulate each other, and how robust these equilibria are.

Patreon: https://www.patreon.com/axrpodcast

Ko-fi: https://ko-fi.com/axrpodcast

Transcript: https://axrp.net/episode/2026/02/18/episode-49-caspar-oesterheld-program-equilibrium.html

Note from Caspar on 2:00:06: At least given my current interpretation of what you say here, my answer is wrong. What actually happens is that we're just back in the uncorrelated case. Basically my simulations will be a simulated repeated game in which everything is correlated _because I feed you my random sequence_ and your simulations will be a repeated game where everything is correlated. Halting works the same as usual. But of course what we end up actually playing will be uncorrelated. We discuss something like this later in the episode.

Topics we discuss, and timestamps:

0:00:44 Program equilibrium basics

0:14:20 Desiderata for program equilibria

0:24:35 Why program equilibrium matters

0:33:35 Prior work: reachable equilibria and proof-based approaches

0:53:26 The basic idea of Robust Program Equilibrium

1:07:47 Are ϵGroundedπBots inefficient?

1:15:06 Compatibility of proof-based and simulation-based program equilibria

1:18:32 Cooperating against CooperateBot, and how to avoid it

1:44:43 Making better simulation-based bots

2:01:22 Characterizing simulation-based program equilibria

2:21:24 Follow-up work

2:29:49 Following Caspar's research

Links for Caspar:

Academic website: https://www.andrew.cmu.edu/user/coesterh/

Google Scholar: https://scholar.google.com/citations?user=xeEcRjkAAAAJ&hl=en

Blog: https://casparoesterheld.com/

X / Twitter: https://x.com/c_oesterheld

Research we discuss:

Robust program equilibrium: https://link.springer.com/article/10.1007/s11238-018-9679-3

Characterising Simulation-Based Program Equilibria: https://arxiv.org/abs/2412.14570

Manifold open-source prisoner's dilemma tournament: https://manifold.markets/IsaacKing/which-240-character-program-wins-th

Results of Alex Mennen's open source prisoner's dilemma tournament: https://www.lesswrong.com/posts/QP7Ne4KXKytj4Krkx/prisoner-s-dilemma-tournament-results-0

A General Counterexample to Any Decision Theory and Some Responses: https://arxiv.org/abs/2101.00280

Cooperative and uncooperative institution designs: Surprises and problems in open-source game theory: https://arxiv.org/abs/2208.07006

Parametric Bounded Löb's Theorem and Robust Cooperation of Bounded Agents: https://arxiv.org/abs/1602.04184

A Note on the Compatibility of Different Robust Program Equilibria of the Prisoner's Dilemma: https://arxiv.org/abs/2211.05057

Episode art by Hamish Doodles: hamishdoodles.com