Research map / Multi-agent systems and games / Games and equilibria
Characterising Simulation-Based Program Equilibria
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalises the epsilon-Grounded-pi-Bot program equilibrium to n players by having programs choose a geometric 'time step' and manipulate simulated opponents' randomness; proves a folk theorem with shared randomness and characterises (and partly limits) equilibria without it.
Problem
Simulation-based programs in program games cannot simulate multiple opponents without halting issues, so they fail in games with three or more players and fall short of the program equilibrium folk theorem even with two players.
Approach
Each program samples its own geometric time step and calls opponents with truncated random sequences so simulated programs believe they are on earlier time steps, enabling multi-opponent simulation while still halting; with shared randomness this yields a full folk theorem, and without it, a characterisation of attainable equilibria plus a negative result for simulationist programs.
Key results
- With shared randomness, correlated epsilon-GroundedPiBots achieve a folk theorem: any feasible strictly individually rational payoffs are attainable in equilibrium.
- Without shared randomness, uncorrelated epsilon-GroundedPiBots cannot achieve the full folk theorem (pirate example), but achieve a folk theorem for additively separable utilities.
- Simulationist programs without shared randomness cannot attain (C,C,C) in the three-player pirate game.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| allow shared randomness for correlated εGroundedπBots | Correlated εGroundedπBots · General finite games | feasible strictly individually rational payoffs attainable in equilibrium | Helped |
| use uncorrelated εGroundedπBots instead of correlated bots | Uncorrelated εGroundedπBots · Games without shared randomness | full program-equilibrium folk theorem attainability | Hurt |
| use uncorrelated εGroundedπBots in additively separable games | Uncorrelated εGroundedπBots · Additively separable games | feasible strictly individually rational payoffs attainable in equilibrium | Helped |
| use simulationist programs rather than uncorrelated εGroundedπBots | Simulationist programs · Trust game (S,F) profile | equilibrium attainability | Helped |
| use simulationist programs without shared randomness | Simulationist programs · Pirates game (C,C,C) profile | equilibrium attainability | Hurt |
| allow non-myopic policies and simulations across multiple time steps | Correlated εGroundedπBots · Games with three or more players | equilibrium attainability | Helped |
| use uncorrelated εGroundedπBots rather than the original εGroundedπBots | Uncorrelated εGroundedπBots · Two-player trust game | mixed-strategy equilibrium attainability | Helped |
Surprising findings
- Without shared randomness, simulation-based programs cannot attain the full program-equilibrium folk theorem, even with simulationist programs more general than epsilon-GroundedPiBots.
- The epsilon-GroundedPiBot of prior work cannot simulate more than about one opponent in expectation without halting failing, so naive extension to three players fails.
Limitations
- Uncorrelated programs do not achieve the full folk theorem; exact set of attainable equilibria in the uncorrelated setting remains open.
- Shared randomness is assumed in the main folk theorem; practical implementation via shared seeds has a maximum time-step issue.
- Expected runtime is infinite without memoization.
Experimental setup
Metrics: equilibrium payoffs expected runtime
Baselines: epsilon-GroundedPiBot
Builds on: epsilon-GroundedPiBot program equilibrium epsilon-GroundedFairBot
Closest papers by meaning
- Calibration of Shared Equilibria in General Sum Partially Observable Markov Games (NeurIPS 2020 · similarity 0.86)
- Equilibrium Refinement for the Age of Machines: The One-Sided Quasi-Perfect Equilibrium (NeurIPS 2021 · similarity 0.86)
- Evaluating LLMs in Open-Source Games (NeurIPS 2025 · similarity 0.86)
- Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games (NeurIPS 2022 · similarity 0.85)
- The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.85)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.