Subexponential Algorithm for High Multiplicity Fair Division of Mixed Instances via Stereometry
2026-07-10 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to fairly divide a set of items among several people when items can be good, bad, or mixed in value. They focus on finding envy-free allocations, meaning no one prefers someone else's share. They introduce a new algorithm that runs faster than before for this problem, using geometry and graph theory to break the problem into smaller parts. Their method can also handle cases where some people’s shares are fixed in advance and still keep the division envy-free.
envy-free allocationindivisible itemsadditive valuationsgoods and choresconvex polyhedraplanar cycle-separator theoremsubexponential algorithmbalanced decompositionfair division
Authors
Yuriy Dementiev, Fedor Pribytkov, Danil Sagunov
Abstract
We study the problem of computing an envy-free (EF) allocation of $m$ indivisible items among $n$ agents when items come in three distinct types. Each agent holds additive valuations over item types that may be positive (goods), negative (chores), or mixed. We present the first subexponential-time algorithm with running time time $(n \cdot m)^{O(\sqrt{n})}$ that finds an EF allocation whenever one exists, or correctly reports that none exists. Our approach exploits a geometric representation of EF allocations as convex polyhedra in $\mathbb{R}^3$ and applies Miller's planar cycle-separator theorem to recursively decompose the agent set into balanced subgroups. We further extend the algorithm to handle agents whose allocations are fixed in advance, preserving envy-freeness across all agents.