Subexponential Algorithm for High Multiplicity Fair Division of Mixed Instances via Stereometry
This work provides a theoretical breakthrough for envy-free allocation in a restricted setting (three item types), offering a subexponential algorithm where previously only exponential or pseudopolynomial methods existed.
The paper presents the first subexponential-time algorithm for computing envy-free allocations of indivisible items with three types (goods, chores, or mixed), achieving running time (n·m)^{O(√n)}. The algorithm either finds an EF allocation or correctly reports nonexistence.
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.