Balanced allocations with EF1 and fractional Pareto optimality
Follow the latest progress by email.
For indivisible goods and nonnegative additive valuations, does an allocation always exist whose bundle sizes differ by at most one, which is envy-free up to one good, and which admits no balanced fractional Pareto improvement?
Why it matters and what counts as progress
Why it matters: Balanced bundle sizes add an allocation constraint not covered by known simultaneous EF1 and fractional Pareto guarantees.
What counts as progress: Prove simultaneous existence of all three guarantees, give an algorithm with those guarantees, or find an incompatible valuation instance.
How the problem developed
- 2016 · Existence result [1]
Caragiannis and coauthors Showed that maximum-Nash-welfare allocations are EF1 and Pareto optimal for additive valuations without a balancedness constraint.
- 14 Mar 2026 · Partial result [2]
Yasushi Kawase and Ryoga Mahara Proved balanced EF1 and fPO existence in two restricted cases: personalized bivalued valuations or at most two valuation types.
- 6 Aug 2026 · Reported claim [3]
Benjamin Cookson, Nisarg Shah and Paritosh Verma, with GPT-5.6-Sol Reported balanced EF1 and fPO allocations for arbitrary nonnegative additive valuations; the paper also gives a category-constrained relaxation.
AI contribution
Fair and Efficient Balanced Allocations for Additive Valuations
For any number of indivisible goods and agents with nonnegative additive valuations, an allocation exists with bundle sizes differing by at most one, envy-free up to one good, and no balanced fractional reallocation that Pareto improves it.
Sources
Website timeline
Publication dates and editorial changes.