# Playing Large Games with Oracles and AI Debate

arXiv: https://arxiv.org/abs/2312.04792 · HTML: https://mlsanity.com/paper/2312.04792/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 8 Dec 2023.

## Builds on (most cited first, 18 of 18)

- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate](https://mlsanity.com/paper/2305.19118/) (2023)
- [ChatEval: Towards Better LLM-based Evaluators through Multi-Agent Debate](https://mlsanity.com/paper/2308.07201/) (2023)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Exploring Collaboration Mechanisms for LLM Agents: A Social Psychology View](https://mlsanity.com/paper/2310.02124/) (2023)
- [QuALITY: Question Answering with Long Input Texts, Yes!](https://mlsanity.com/paper/2112.08608/) (2021)
- [Examining Inter-Consistency of Large Language Models Collaboration: An In-depth Analysis via Debate](https://mlsanity.com/paper/2305.11595/) (2023)
- [Can ChatGPT Defend its Belief in Truth? Evaluating LLM Reasoning via Debate](https://mlsanity.com/paper/2305.13160/) (2023)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Scalable AI Safety via Doubly-Efficient Debate](https://mlsanity.com/paper/2311.14125/) (2023)
- [Let Models Speak Ciphers: Multiagent Debate through Embeddings](https://mlsanity.com/paper/2310.06272/) (2023)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Efficient Regret Minimization in Non-Convex Games](https://mlsanity.com/paper/1708.00075/) (2017)
- [Single-Turn Debate Does Not Help Humans Answer Hard Reading-Comprehension Questions](https://mlsanity.com/paper/2204.05212/) (2022)

## Built on by (most cited first, 6 of 6)

- [Avoiding Obfuscation with Prover-Estimator Debate](https://mlsanity.com/paper/2506.13609/) (2025)
- [Emergent Alignment via Competition](https://mlsanity.com/paper/2509.15090/) (2025)
- [Coherence Mechanisms for Provable Self-Improvement](https://mlsanity.com/paper/2511.08440/) (2025)
- [Multi-Agent Debate Strategies: Survey, Taxonomy, and Challenges](https://mlsanity.com/paper/2607.26212/) (2026)
- [The Hidden Game Problem](https://mlsanity.com/paper/2510.03845/) (2025)
- [How to Have a Sensitive Debate: An Instance-Optimal Protocol for AI Debate](https://mlsanity.com/paper/2610.02557/) (2026)

## Abstract (arXiv)

We consider regret minimization in repeated games with a very large number of actions. Such games are inherent in the setting of AI Safety via Debate citeirving2018ai, and more generally games whose actions are language-based. Existing algorithms for online game playing require per-iteration computation polynomial in the number of actions, which can be prohibitive for large games. We thus consider oracle-based algorithms, as oracles naturally model access to AI agents. With oracle access, we characterize when internal and external regret can be minimized efficiently. We give a novel efficient algorithm for simultaneous external and internal regret minimization whose regret depends logarithmically on the number of actions. We conclude with experiments in the setting of AI Safety via Debate that shows the benefit of insights from our algorithmic analysis.