AI-Human Collaboration Settles a Nine-Year Open Problem: The Core Always Exists in Approval-Based Committee Elections

A group of voters must elect a seven-person delegation. Everyone lists candidates they approve, and the seven with sufficient support are chosen. The hard question: after the committee is picked, could some coalition of voters propose an alternative slate that every one of them strictly prefers? If such a coalition could always exist, a 'fair delegation' would be an illusion. For nine years, researchers searched for concrete counterexamples. In September 2026, a 20-page paper gave a different answer: no such instance exists.

The Core Problem

This sits in a specific branch of computational social choice: approval-based committee elections.

The stability benchmark is the core, a concept from cooperative game theory. A committee is in the core if no coalition of voters, wielding its proportionate claim on seats, can propose an alternative committee that every member strictly prefers. The claim is defined by quotas: the Hare quota is n/k (voters divided by seats) and the Droop quota is n/(k+1).

The question—posed formally in 2017—was whether the core can ever be empty under extreme preferences. For nine years the literature hung on this.

Harmonic Entropy: Turning Stability Into an Optimization Problem

The paper is *Existence of the Core in Approval-Based Committee Elections*, arXiv:2609.11912, submitted 2026-09-10, classified cs.GT, by Patrick Becker, Matthias Greger, and Dominik Peters (CNRS and the LAMSADE lab, Paris Dauphine).

The abstract's third sentence carries the most weight:

> We settle the main open question in the theory of approval-based multi-winner elections: we show that there always exists a committee in the core.

The arXiv Comments field adds:

> 20 pages. The proof was obtained with GPT-6 Astra.

The technical key is a newly constructed voting rule that maximizes an objective called harmonic entropy, defined jointly over committees and a payment system. The chain of reasoning looks indirect: rather than proving the core nonempty directly, the authors build an objective function and show every local optimum satisfies a stronger condition (core+, a strengthening of the core with relaxed integrality plus payment certificates), which implies membership in the core. The detour buys two things:

• Constructiveness. The answer is not just 'the core exists' but 'it exists and can be computed in polynomial time,' via local search plus a linear-programming simplification—no exhaustive enumeration needed.
• Verifiability. The existence result has been formally verified in Lean, in the repository ABCVotingLean. A proof assistant acts like a compiler for logic: it will not let a subtle step pass.

Epoch AI's New Label: Making Attribution Auditable

The story went viral on September 20 when Epoch AI's FrontierMath page updated. FrontierMath is a benchmark of open research-level math problems. This problem was rated Major Advance—and it is the first of the six Major Advance problems to be solved; the other five remain open.

More significant than the 1-of-5 ratio is the label Epoch attached. They added a new status category: 'Human + AI'. Their note says both that Astra supplied core ideas and the proof framework across long multi-turn sessions, and that Astra could not solve the problem from a simple prompt alone. This explicitly rejects the stronger claim of 'autonomous AI solution.' Epoch's framing: the model is a high-leverage collaborator that opens argumentative routes, while humans select, probe, and formalize.

Co-author Dominik Peters, as relayed in coverage, said:

> I'm particularly glad the argument is this beautiful… It could easily have been a non-constructive proof, or required a massive case analysis. I don't find it ugly at all, and the techniques used here may well generalize to other settings.

'Generalize to other settings' points at harmonic entropy itself, not just this problem.

Three Modes of AI Mathematics, Side by Side

The event is most informative when contrasted with two others from the same month:

1. The fleet approach: the early-September Navier–Stokes scaling attempt—roughly 10,000 concurrent agents over 88 hours, ~130 billion output tokens. 2. The solo lab: a software developer's month-long Lean-verified proof of a refined Conway conjecture (~40 billion tokens), not independently checked by mathematicians. 3. Long-term collaboration: this paper—model provides core ideas and proof structure, three researchers present to question and formalize.

The most practical difference lies beyond compute: *who judges whether the model is going in circles*. In mode three, that judgment rests with three domain researchers; in the first two, it rests with engineering orchestration and the author's own intuition.

Open Questions

The paper leaves clear boundaries:

• Whether the harmonic entropy rule satisfies proportionality axioms beyond core+ (e.g., FJR+, payability).
• Actual runtime on large real-world election instances—the paper proves polynomial time but reports no benchmarks.
• Whether local optima are unique, and under what conditions.
• Whether this human-AI interaction pattern extends to other open problems.
• No peer review yet—formal verification does not check every modeling choice.

That last point deserves emphasis. Lean verification guarantees every step from statement to conclusion; it cannot guarantee the statement itself is the right one, or that modeling assumptions are apt. The paper's conclusion—'the core is nonempty under both Hare and Droop quotas'—is already tightly scoped, but a 20-page preprint becoming consensus requires peer review and broader axiom testing.

One detail is easily buried: the problem originally asked 'find an election instance with an empty core.' The final answer is a proof that no such instance exists. Benchmark designers likely didn't anticipate this outcome: a problem's answer can be *stop looking*. The next question: if even a disproof—the answer most easily mistaken for failure—counts as complete progress, how should evaluation systems distinguish 'AI had a good idea' from 'AI had an idea worth remembering'?

---

References

1. Patrick Becker, Matthias Greger, Dominik Peters, *Existence of the Core in Approval-Based Committee Elections*, arXiv:2609.11912v1 [cs.GT], 2026-09-10. https://arxiv.org/abs/2609.11912 2. Epoch AI, *The Core in Approval-Based Committee Elections (FrontierMath Open Problems)*, 2026-09. https://epoch.ai/frontiermath/open-problems 3. Brocker, *AI Model Solves Nine-Year Problem in Committee Voting Theory*, 2026-09-20. https://www.brocker.org/gpt-6-astra-proves-core-exists-approval-committee-elections 4. Ground Truth / DEV Community, *GPT-6 Astra helps solve FrontierMath's first Major Advance problem*, 2026-09-20. https://dev.to/breachprotocol/gpt-6-astra-helps-solve-frontiermaths-first-major-advance-problem-3m6g 5. 新智元, *首次！GPT-6 Astra 破解「重大进展」级难题*, 2026-09-20. https://finance.sina.com.cn/wm/2026-09-20/doc-inismvnz1687113.shtml