Verification of Stochastic Dominance Envy-Freeness in Time Proportional to Input Size
2026-06-15 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors developed the fastest possible method to check if dividing items among people is fair based on their preferences, focusing on a fairness rule called Stochastic Dominance Envy-Freeness (SD-EF) and a relaxed version called SD-EF1. Their approach uses a simple, single-step check for each person, which cuts down the time needed from previous methods. They proved their method is as efficient as it can be given the size of the input data.
Stochastic DominanceEnvy-FreenessFair DivisionIndivisible GoodsAlgorithm ComplexityPrefix-Dominance CheckLazy InitializationTime-Optimal AlgorithmPreference Matrix
Authors
Kui-Wang Choi
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^2m)$ 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.