Witness-Certified Fair Division with Comparison Queries

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\mathrm{/}n))$ comparison queries, within an $O(\log n)$ factor of the $\mathrm{\Omega }(n\log (m\mathrm{/}n))$ communication lower bound. For identical additive valuations, we additionally obtain a $1\mathrm{/}2$-MMS guarantee within the same query complexity. For non-identical additive valuations, exploiting our EF1+$1\mathrm{/}2$-MMS algorithm, we accelerate the existing matching-based PROP1+$1\mathrm{/}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.