Witness-Certified Fair Division with Comparison Queries
2026-08-17 • Computer Science and Game Theory
Computer Science and Game TheoryData Structures and Algorithms
AI summaryⓘ
The authors study how to fairly divide goods that cannot be split when agents only compare bundles without exact values. They show that just checking if an allocation is nearly envy-free (EF1) can be very difficult, so they use explicit fairness certificates to help. Their main method simplifies the problem, solves a smaller version, and then fixes the solution to maintain fairness. This approach works efficiently for many agents with identical or different valuation types, improving previous methods. They also explore a new hierarchy of fairness certificates between known fairness concepts EF1 and EFX.
fair divisionindivisible goodsenvy-freenessEF1EFXmonotone valuationsadditive valuationsMMS (maximin share)ordinal comparisonsfairness certificates
Authors
Tatsuhito Yamagata, Hanna Sumita
Abstract
We study fair division of indivisible goods when agents' valuations are accessed only through ordinal comparisons between bundles, with arbitrary tie-breaking. In this model, even deciding whether a given allocation is envy-free up to one good (EF1) can be impossible. This suggests explicit fairness certificates as a natural algorithmic object. Our main contribution is a certificate-preserving scaling framework, which recursively contracts goods, solves a smaller instance, and expands the solution while repairing an explicit envy-eliminating witness certificate. For arbitrary identical monotone valuations, this yields a certified EF1 allocation for $n$ agents and $m$ goods using $O(n \log n \log(m/n))$ comparison queries, within an $O(\log n)$ factor of the $Ω(n \log (m/n))$ communication lower bound. For identical additive valuations, we additionally obtain a $1/2$-MMS guarantee within the same query complexity. For non-identical additive valuations, exploiting our EF1+$1/2$-MMS algorithm, we accelerate the existing matching-based PROP1+$1/2$-MMS framework, improving the query complexity from $O(n^4\log m)$ to $O(n^3\log m)$. Finally, we study the structure of such certificates through $k$-witness EF1, a hierarchy between EF1 and EFX.