Balanced fair division achievable for small groups with indivisible goods
Balanced Fair Division and Generalized Kneser Graphs
Computer Science and Game Theory
Summary
Dividing things fairly among two groups can be tricky, especially when the items can't be split and people value them differently. The authors explore ways to ensure fairness that almost eliminates envy, even if just a few items are removed. They prove this is possible for small groups of up to five or nine people, depending on the fairness level. Their work uses deep connections to special math structures called generalized Kneser graphs to prove these fairness guarantees.
What this means in practice
- •For resource allocation teams: Ensure balanced nearly envy-free allocation of indivisible resources across two groups with complex preferences for small teams.
- •For algorithm designers: Use chromatic number bounds on specialized graphs to guide algorithms finding fair allocations with provable guarantees.
A theory result. No direct application yet.
Authors
Sharareh Alipour, Amir Jafari
Abstract
We study indivisible goods allocated to two prescribed nonempty groups whose members have arbitrary monotone valuations. We guarantee balanced envy-freeness up to one good (EF1) for at most five agents and up to two goods (EF2) for at most nine, for any number of goods. Bundle sizes differ by at most one. The EF1 threshold is sharp: every split of six agents can fail. EF2 improves the previous five-agent guarantee. Via the connection of Kyropoulou, Suksompong, and Voudouris, these guarantees follow from chromatic bounds for $\mathrm{KG}(2n,n,r)$, whose vertices are $n$-subsets of a $2n$-set, adjacent when their intersection has size less than $r$. We prove its chromatic number is six for $r=2$, $n\ge2$, resolving Jafari and Alipour's conjecture, and at least ten for $r=3$, $n\ge4$, improving the previous lower bound of six; the known upper bound is fourteen. We show that the standard box-complex $\mathbb{Z}_2$-index bound yields exactly five and nine for $n\ge3$ and $n\ge5$, respectively. To exceed these bounds, we exploit restrictions on maps induced by colorings: a proper five- or nine-coloring must induce a nonzero homology map, yet local constraints force all generators, supported on pentagon or rook configurations, to map to zero. The ten-color proof compares integral and fractional common centers using a sharp rounding theorem for five subset constraints. A linear-time retraction from the full allocation graph onto balanced layers adds cardinality balance to known nonlinear discrepancy guarantees. For each fixed removal allowance in the guaranteed-existence range, finding a balanced fair allocation or an explicit monotonicity violation from valuation circuits is polynomial-time equivalent to finding a monochromatic edge in a circuit-specified coloring of the corresponding graph. The reverse reduction produces normalized monotone binary valuations using ordinary circuits.