Fair and Efficient Balanced Allocations for Additive Valuations
2026-08-06 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to fairly and efficiently divide indivisible items among people so that no one envies another's share too much, and the sizes of the shares are almost equal. They prove that such balanced and fair divisions exist for any way people value items, extending earlier results that had more limitations. Their proof uses advanced mathematical tools, including the KKM lemma and a new price-interlacing idea, to handle complex fairness conditions. They also adapt their method to situations where items belong to categories, showing a relaxed but still fair allocation exists. Notably, all proofs were generated with AI assistance and verified by the authors.
indivisible goodsbalancedness constraintenvy-freeness up to one good (EF1)fractional Pareto optimality (fPO)additive valuationsKnaster-Kuratowski-Mazurkiewicz lemmaprice-interlacing lemmacategory constraintspartition-matroid constraints
Authors
Benjamin Cookson, Nisarg Shah, Paritosh Verma
Abstract
We study the existence of fair and efficient allocations of indivisible goods under the balancedness constraint, which requires that any two agents' bundles differ in size by at most one. Our main result establishes the existence of balanced allocations that satisfy envy-freeness up to one good (EF1) and fractional Pareto optimality (fPO) for arbitrary additive valuations. This generalizes a recent result of Kawase et al. (2026), which establishes existence only for personalized bivalued valuations or when there are at most two distinct valuation types. Our proof applies the Knaster-Kuratowski-Mazurkiewicz (KKM) lemma to a weighted-welfare duality framework and develops a novel price-interlacing lemma to overcome barriers encountered by prior work. We extend this technique to category constraints, also known as partition-matroid constraints. In this setting, we establish the existence of an fPO allocation satisfying a weaker, category-sensitive relaxation of EF1, under which envy can be eliminated by removing at most one good from each category. All proofs in this paper were obtained using GPT-5.6-Sol with guidance from the authors. The authors verified the proofs, expanded the exposition, and simplified the arguments with assistance from GPT-5.6-Sol and Claude Fable 5.