RSD Allocation Algorithm Is √2-Envy-Free, Settling Decades-Old Fairness Question
A tight bound proving RSD never exceeds 41% envy gap in house allocation.
A team of computer scientists (Connor, Dupré la Tour, Langevin, Narayan, Ndiaye, Rahman, Vetta) has delivered a tight theoretical result for Random Serial Dictatorship (RSD), a canonical algorithm for the house allocation problem. The headline finding: RSD is √2-envy-free, meaning the ratio between an agent's expected utility for another agent's allocation and their own is at most √2 ≈ 1.414. This matches a previously known lower bound, closing a decades-old gap on how well this simple, widely-implemented mechanism approximates envy-freeness in expectation.
The paper also extends analysis to variants like randomized round-robin and iterated-RSD under unequal agent/object counts and more complex valuations. For additive valuations, round-robin's envy-ratio lies between 1.5 and 1.707, while iterated-RSD stays at exactly √2. Under submodular valuations, constant bounds are given. For XOS/subadditive valuations, the ratio becomes unbounded—a negative result for broader fairness. Published in EC 2026, this work provides the first tight or nearly-tight quantitative fairness guarantees for RSD and its generalizations.
- RSD's envy-ratio is exactly √2 (≈1.414) – matching the lower bound from prior work.
- Randomized round-robin has envy-ratio between 1.5 and 1.707 for additive valuations.
- Under XOS/subadditive valuations, both mechanisms have unbounded envy-ratio as agent count grows.
Why It Matters
Tight fairness guarantees for a foundational allocation algorithm used in housing, course scheduling, and resource distribution.