Balanced Fair Division and Generalized Kneser Graphs
cs.GT
Submitted: 2026-11-03
Updated: 2026-11-03
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study indivisible goods allocated to two prescribed nonempty groups whose members have arbitrary monotone valuations.
Terminology
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 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 at least2, resolving Jafari and Alipour's conjecture, and at least ten for r=3, n at least4, improving the previous lower bound of six; the known upper bound is fourteen. We show that the standard box-complex Z 2-index bound yields exactly five and nine for n at least3 and n at least5, 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.
Sources
- Fair Division with Allocator's Preference
- Box complexes: at the crossroad of graph theory and topology
- On the chromatic number of generalized Kneser hypergraphs
- Discrepancy And Fair Division For Non-Additive Valuations
- Consensus Halving for Sets of Items
- Fair Division Among Couples and Small Groups
- Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
- Discrepancy Beyond Additive Functions with Applications to Fair Division
- Topological lower bounds for the chromatic number: A hierarchy
- Local chromatic number, Ky Fan's theorem, and circular colorings
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments