{"ID":6497715,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09327","arxiv_id":"2607.09327","title":"Subexponential Algorithm for High Multiplicity Fair Division of Mixed Instances via Stereometry","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.","short_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 runnin...","url_abs":"https://arxiv.org/abs/2607.09327","url_pdf":"https://arxiv.org/pdf/2607.09327v1","authors":"[\"Yuriy Dementiev\",\"Fedor Pribytkov\",\"Danil Sagunov\"]","published":"2026-07-10T12:08:52Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}