The bottom line: when you split a pile of indivisible goods fairly among groups of people instead of among individuals, someone in some group can still end up shortchanged by roughly $\sqrt{n/k}$ units relative to what a perfectly proportional split would give them — and a new paper shows this is essentially unavoidable, not just a weakness of current allocation methods. That closes a gap that researchers have been chipping away at for several years.
Picture splitting a company's assets among $k$ departments rather than among individual employees, where each department has its own headcount. A natural goal is that each department gets a $1/k$ share of the total value. But the goods themselves are indivisible — an office chair or a delivery truck can't be split fractionally — so someone is going to end up a little short. The question fair-division researchers ask is: how bad can that shortfall get for the worst-off person in the worst-off group, no matter how cleverly the allocation is designed?
Formally, with $k$ groups of sizes $n_1, \ldots, n_k$ and $n = n_1 + \cdots + n_k$ total agents, the quantity of interest is $\text{PROP}(n_1, \ldots, n_k)$: the largest possible downward deviation of any agent's share from its target $1/k$ portion, minimized over all allocation strategies but maximized over the adversary's choice of item values. Prior work by Manurangsi and Meka had shown this quantity sits between roughly $\Omega(\sqrt{n/(k^3 \log k)})$ and $O(\sqrt{n})$ — a real gap, especially as the number of groups $k$ grows. This paper tightens both ends and proves $\text{PROP}(n_1, \ldots, n_k) = \tilde\Theta(\sqrt{n/k})$, meaning the true answer scales with the square root of the average group size, up to logarithmic factors.
The proof route runs through discrepancy theory, a branch of combinatorics that studies how unevenly a set system can be forced to split into groups no matter how you try to balance it. Classical discrepancy theory looks at symmetric imbalance — how far a coloring deviates from balance in either direction. The technical contribution here is a way to work efficiently with one-sided discrepancy constraints, where only deviation in one direction (an agent falling below their fair share, not above it) actually matters for the fairness guarantee. That distinction sounds narrow, but it turns out to be exactly what's needed to shave the extra $k$-dependence out of the previous bound's lower-order terms.
This result doesn't sit in isolation — it's the latest move in an active back-and-forth. Manurangsi and Suksompong's earlier discrepancy framework, sharpened by Caragiannis, Larsen, and Shyam, and then again by Manurangsi and Meka, had converged on roughly matching $O(\sqrt{n})$ upper and $\Omega(\sqrt{n_1})$ lower bounds but without pinning down the exact dependence on $k$. Concurrent work by Hollender, Manurangsi, Meka, and Suksompong pushed the discrepancy connection further, extending it beyond additive valuations and landing an $O(\sqrt{n \log n})$ bound in that broader setting. The paper reviewed here instead sharpens the classical additive-valuation case all the way to a tight $\tilde\Theta$ bound, closing most of the remaining gap between what was provably achievable and what was provably unavoidable.
For anyone actually running a fair-division mechanism — splitting equipment among hospital departments, assets among merging business units, or seats among stakeholder groups — the practical takeaway is sobering but useful: no allocation algorithm, however clever, can guarantee better than roughly $\sqrt{n/k}$ worst-case shortfall for someone once groups are unequal in size and goods are indivisible. That's not a flaw in existing heuristics; it's a hard combinatorial limit. Knowing the limit is tight lets practitioners stop searching for allocation rules that beat it and instead focus on mechanisms that get close to it, or on relaxing the fairness notion (e.g., allowing a small subsidy or a few extra 'chore' items) when the guarantee genuinely can't be met.
The bigger story is how much of modern fair-division theory now runs on discrepancy-theoretic machinery originally built for entirely different combinatorics problems — set balancing, hypergraph coloring, and geometric approximation. The one-sided discrepancy tool introduced here is a reminder that fairness guarantees, allocation problems, and classical combinatorial optimization keep converging on the same underlying mathematics, and that improvements in one area (multicolor discrepancy bounds) translate almost immediately into sharper guarantees in a seemingly unrelated application (equitable resource splitting).
Sources: Manurangsi and Meka, 'Tight Lower Bound for Multicolor Discrepancy' (SOSA 2026), arXiv:2504.18489 · Hollender, Manurangsi, Meka, and Suksompong, 'Discrepancy Beyond Additive Functions with Applications to Fair Division', arXiv:2509.09252 · Caragiannis, Larsen, and Shyam, 'A New Lower Bound for Multicolor Discrepancy with Applications to Fair Division', ResearchGate publication 395158264 · 'Tight Asymptotic Bounds for Fair Division With Externalities', arXiv:2601.13287 · 'Bad News for Couples: Tight Lower Bounds for Fair Division of Indivisible Items', arXiv:2601.01012 · Primary source: 'Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy', arXiv:2609.03682v1
