Verification of Stochastic Dominance Envy-Freeness in Time Proportional to Input Size

Abstract

We present a time-optimal algorithm for verifying Stochastic Dominance Envy-Freeness (SD-EF) and its relaxation, SD-EF up to one good (SD-EF1), in the fair division of indivisible goods. By leveraging a single-pass prefix-dominance check per agent and lazy-initialization, we reduce the verification complexity from the previously known $\mathcal{O}(n^{2}m)$ by Aziz (2016) to $\mathcal{O}(nm)$. Given that the input preference matrix is of size $nm$, our algorithm is asymptotically optimal with respect to the input size.

6 pages