The core in approval-based committee elections is never empty

Becker, Greger and Peters proved that every approval-based committee election has a committee in the core, computable in polynomial time; their arXiv paper says the proof was obtained with GPT-6 Astra.

Problem
In approval-based committee elections, can the core be empty?
Credit
Becker, Greger and Peters with GPT-6 Astra · Human-AI collaboration
Checked
Marked solved (human + AI) by Epoch AI
Timeline
arXiv 2609.11912, 2026-09-10
Sources
Epoch AI problem pagePaper (arXiv:2609.11912)
UN-
VERIFIEDHuman + AI · not peer reviewed

The problem

In an approval-based committee election, each voter approves some candidates and a committee of fixed size is chosen. The core is a strong fairness condition: no group of voters could do better by electing a smaller committee of its own. Whether a core committee always exists was a well-known open question. Epoch AI's FrontierMath Open Problems, which rates it a "major advance", asked for an election where no committee lies in the core.

What AI did

Becker, Greger and Peters proved the opposite: the core is never empty, and a core committee can be found in polynomial time (arXiv:2609.11912, 10 September 2026). The paper's arXiv comment reads "The proof was obtained with GPT-6 Astra." Peters told Epoch AI that the team doubts it would have found the proof without the model, and that the model cannot do it from a simple prompt.

How it was checked

We found no Lean formalization and no peer review yet.

Limitations

Epoch AI's problem asked for a counterexample, which this result shows cannot exist; Epoch counts that as solving the problem under its stated policy. Until the proof is checked independently, we grade it "unverified". Problem description paraphrased from Epoch AI (CC BY 4.0).

∎