Balanced EF1 and fPO Allocations
Does every instance of indivisible goods with additive valuations admit a balanced allocation (any two bundles differing in size by at most one) that is simultaneously envy-free up to one good (EF1) and fractionally Pareto optimal (fPO)? Kawase et al. established existence only for personalized bivalued valuations or at most two valuation types. Proved in general, via the Knaster-Kuratowski-Mazurkiewicz lemma applied to a weighted-welfare duality framework plus a new price interlacing lemma.
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Fair division; algorithmic game theory
- Posed by
- Kawase et al.
- Year posed
- 2026
- Years open
- 0y
- Solved
- 2026-08-06
- Model
- GPT-5.6-Sol (via OpenAI Codex), Claude Fable 5
- Vendor
- OpenAI, Anthropic
- Collaborators
- Benjamin Cookson, Nisarg Shah, Paritosh Verma
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
The paper records how the collaboration actually went: the authors first aimed at a counterexample showing EF1 and PO incompatible under matroid constraints, and when the model surfaced fundamental difficulties with that plan they redirected toward proving the positive result instead. The paper also extends the technique to category constraints and leaves a pseudopolynomial-time algorithm open.
What the AI did
The acknowledgement is unusually specific: "All the mathematical proofs and counterexamples were derived by OpenAI Codex (GPT-5.6-Sol at Max effort) based on research directions, literature connections, proof and search strategies, and inspirations supplied by the authors." The authors verified every detail and simplified the exposition with both models, and retain responsibility.
Verification
An arXiv preprint days old. The authors state they verified all the mathematics themselves, which is not independent review, and no formalization is reported.
Source
Submitted by VibeGene on