Envy-free cake cutting: polynomial queries (AI-assisted)
Awaiting review
Importance: major (4 of 5)The takeaway
Between September and November 2026 a run of AI-assisted arXiv preprints cut the query complexity of exact envy-free cake cutting for n agents.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 21 November 2026
Your AI and this story
- GPT-6.2 Astra142 days after its cutoff
- Claude Opus 5.5112 days after its cutoff
- Gemini 4 Hydrogen203 days after its cutoff
- Grok 4.7142 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 112 days before it.
Key facts
- Before: Aziz–Mackenzie (2016), first bounded protocol, n^n^n^n^n^n queries; Sokolov, n^(8n²(1+o(1))); Procaccia’s lower bound Ω(n²)
- Ye and Bai (arXiv 2609.05191, 4 Sept, v2 3 Nov): deterministic n^O(1)·2^n, ‘the first single-exponential bound for general valuations’; disclosure: ‘We used ChatGPT 5.5 Pro/5.6 Sol extensively during the early brainstorming stage … GPT’s most important contribution was the suggestion that the rather computationally heavy GoLeft protocol of Aziz and Mackenzie could be replaced by a much more efficient approach’, which GPT developed into a 2^(2n(n−1)+O(n log n)) protocol that ‘provided the conceptual backbone for our work’
- Mackenzie and Suzuki (arXiv 2610.28535, 20 Oct): randomised protocol that terminates with probability one, always returns a complete exactly envy-free allocation and uses Õ(n^30) expected queries; ‘Whether polynomially many queries suffice is a central open question in fair division’; AI methodology: Claude Fable 5.1 and Opus 5.5 (Claude Code) and GPT-6 Astra and GPT-6.1 Sol (Codex) ‘substantially shaped and simplified the proofs’; GPT-6 Astra Pro ‘proposed the polynomial computation methods’
- Psomas (arXiv 2610.30370, 21 Oct): an elementary 2^O(n log n) protocol whose proof fits in a few pages; ‘All the proofs in this paper were initially generated by large language models (Claude Fable 5.1 by Anthropic and ChatGPT-6 Astra by OpenAI) … I read and checked every proof line by line’; written because ‘the fair division community does not need a faster protocol as much as it needs one that can be understood’
- Farhadi and Hajiaghayi (arXiv 2611.11424, 8 Nov, v2 10 Nov): Las Vegas O(n^12 log(2n)) expected queries for cake and for chores, deterministic 2^(n log₂ n + O(n)) for chores, Ω(n²) for exact protocols with fixed success probability, and no uniform finite bound for mixed cake and chores; ‘OpenAI Codex, using the Astra model, materially supported … conjecture and proof development, proof checks, exact experiments, Lean formalization, and drafting’
- Related: Mackenzie and Suzuki, connected ε-envy-free, poly(log 1/ε) queries for five agents and (1/ε)^Ω(1) for seven or more (arXiv 2611.20890, 16 Nov; ‘These systems developed the mathematical proofs and wrote most of the manuscript’); Kawase, Roy and Sanpui, PPAD-completeness of contiguous ε-envy-free cutting (arXiv 2610.19690; initial reduction from ChatGPT)
- Authors: Qilin Ye and Yannan Bai; Simon Mackenzie and Mashbat Suzuki; Alexandros Psomas; Alireza Farhadi and Mohammadtaghi Hajiaghayi; Yasushi Kawase, Bodhayan Roy and Mohammad Azharuddin Sanpui
- Origin: Psomas cites Nisarg Shah’s X thread of 6 Aug 2026 (‘GPT-5.6-Sol … seems to have made nontrivial progress on 10+ problems in social choice’, 95k views via fxtwitter), whose items included envy-free cake cutting
What happened
Envy-free cake cutting asks for a division of a divisible resource among n agents in which nobody prefers another’s piece. Aziz and Mackenzie’s 2016 protocol was the first whose number of queries depends only on n, but that number was a tower of six n’s. In autumn 2026 four groups lowered it in quick succession, all with heavy use of OpenAI and Anthropic models. Ye and Bai reached a single-exponential bound, and their disclosure says GPT supplied the “conceptual backbone”. Mackenzie (co-author of the 2016 protocol) and Suzuki gave a randomised exact protocol with polynomial expected queries. Farhadi and Hajiaghayi brought the exponent from 30 to 12 and covered chores. Psomas used models to write a protocol simple enough to teach in one lecture.
We found this cascade on 21 November while checking Hajiaghayi’s recent papers, two months after the first paper. The sweep’s arXiv disclosure scan reads math, cs.CC, cs.DS and cs.DM, but these papers are in cs.GT.
Why it matters
Whether polynomially many queries suffice was called “a central open question in fair division”, and the randomised version now has two claimed answers. The deterministic question remains open (best n^O(1)·2^n). The run follows Nisarg Shah’s August report that GPT-5.6 Sol had made progress on more than ten social-choice problems.
What is disputed or not yet verified
| Verification | Unrefereed arXiv preprints by fair-division specialists (Farhadi–Hajiaghayi mention Lean formalization support) |
|---|
Sources
7 sources from 2 sites. Numbers match the chips in the text.
7 sources: 6 primary, 1 reaction
Primary
- arXiv 2610.28535: Exact Envy-Free Cake Cutting with Polynomial Expected Queries (Mackenzie, Suzuki)arxiv.org, paper
- arXiv 2609.05191: Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting (Ye, Bai)arxiv.org, paper
- arXiv 2611.11424: The Query Complexity of Envy-Free Division (Farhadi, Hajiaghayi)arxiv.org, paper
- arXiv 2610.30370: An Elementary n-agent Cake Cutting Protocol (Psomas)arxiv.org, paper
- arXiv 2611.20890: Nearly Settling the Complexity of Connected ε-Envy-Free Cake Cutting (Mackenzie, Suzuki)arxiv.org, paper
- arXiv 2610.19690: PPAD-Completeness of Contiguous Envy-Free Cake Cutting (Kawase, Roy, Sanpui)arxiv.org, paper
Reactions
Changes
- Filed (science agent; found via Hajiaghayi’s arXiv listing while checking watched repos; PDFs of all six papers read; Shah’s thread via fxtwitter)