Random Serial Dictatorship is $\sqrt{2}$-Envy-Free
2026-07-03 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how fairly a method called random serial dictatorship (RSD) assigns objects to people when everyone values objects differently. They find that while RSD is often thought to be fair on average, it can cause people to feel some envy, measured by an "envy-ratio." They prove this envy-ratio is at most about 1.414 (the square root of 2) for the basic problem. They also examine related methods for cases where the number of objects and people differ or valuations are more complex, showing the envy-ratio can be higher or sometimes unlimited. Their work gives precise limits on how close these methods come to being envy-free.
House allocation problemRandom serial dictatorship (RSD)Cardinal utilitiesEnvy-freenessEnvy-ratioRandomized round-robin mechanismIterated-RSD mechanismAdditive valuationsSubmodular valuationsXOS valuations
Authors
Frank Connor, Max Dupré la Tour, Louis-Roy Langevin, Vishnu V. Narayan, Ndiamé Ndiaye, Neil Rahman, Adrian Vetta
Abstract
We analyze the house allocation problem, in which a set of agents must be matched to a set of objects for which they have cardinal utilities. A central mechanism for this problem is random serial dictatorship (RSD), which has long served as a canonical subject of study due to its simplicity and the existence of exact characterizations by its properties. Despite this extensive understanding, a basic quantitative question about the fairness of this mechanism remains unresolved. Although RSD is often viewed as fair ex ante, surprisingly, it is not envy-free in expectation. We quantify its deviation from envy-freeness via the envy-ratio, which is the maximum over all instances and pairs of agents of the ratio between an agent's expected utility for another agent's random object and for its own random object. Prior work shows a factor-$\sqrt{2}\approx 1.414$ lower bound on the envy-ratio of RSD. Our headline result is a matching upper bound, showing that RSD is $\sqrt{2}$-envy-free in the house allocation problem. We further analyze the two natural extensions of RSD (the randomized round-robin mechanism and the iterated-RSD mechanism) to settings with unequal numbers of agents and objects and more general valuation classes. For additive valuations, this ratio increases to at least $1.5$ and at most $1.707$ for randomized round-robin, but remains exactly $\sqrt{2}$ for iterated-RSD. For submodular valuations, we prove constant-factor upper and lower bounds for both mechanisms, leaving only a small constant gap in both cases. For the more general classes of XOS and subadditive valuations, we present a tight analysis for both mechanisms, showing that the envy-ratio is unbounded in the number of agents. These results provide the first tight or nearly tight quantitative guarantees on the extent to which random serial dictatorship and its natural generalizations approximate envy-freeness.