Stability and Efficiency of Random Serial Dictatorship

Technical Summary: Stability and Efficiency of Random Serial Dictatorship

Problem Statement
This paper addresses the validity of the "cutoff representation" framework in large matching markets, specifically within the context of the Random Serial Dictatorship (RSD) mechanism. While cutoff representations, proposed by Azevedo and Leshno (2016) and Menzel (2015), have become a standard tractable analytical tool for studying large markets (and form the basis for empirical studies like Abdulkadroğlu et al., 2017), their theoretical validity has previously been established only in asymptotic limits where the number of students ($n$) tends to infinity while the number of schools ($m$) remains finite.

The central problem is whether this representation remains accurate in "real-world" settings where both $n$ and $m$ grow large, particularly when they are of similar magnitude. The paper investigates the non-asymptotic convergence of RSD cutoffs (defined as the normalized rank of the lowest-ranked admitted student) to deterministic counterparts under arbitrary student preferences.

Methodology
The author departs from traditional mechanism design literature by employing analytic tools from randomized algorithms and discrete probability. The core methodology involves:

1. Probabilistic Bounds: Establishing concentration inequalities for the RSD lottery probabilities and cutoffs.
2. Lipschitz Analysis: Utilizing Talagrand's concentration of measure results (Talagrand, 1995) and properties of the Hamming distance on permutations to bound the fluctuations of the number of students preferring a specific school.
3. Phase Transition Analysis: Investigating the relationship between the number of students ($n$) and schools ($m$) to identify regimes where cutoffs converge versus where they diverge.

The analysis defines a school's cutoff $\gamma_k$ based on a random permutation $\Pi$ of students. It compares the observed stochastic cutoff to a deterministic cutoff $\bar{\gamma}_k$, defined via the expectation of the number of students who weakly prefer a school to their assigned option.

Key Contributions and Results

• Phase Transition Threshold: The paper identifies a critical phase transition in the behavior of RSD cutoffs occurring in the region where $m \ln m \asymp n$.

  • Below Threshold ($n \lesssim m \ln m$): Cutoffs do not converge uniformly. The paper provides a toy example demonstrating that if $n \leq \alpha m \ln m$ for a finite constant $\alpha$, the minimum cutoff does not converge in probability to 1, implying the cutoff representation is invalid.
  • Above Threshold ($n \gg m \ln m$): Cutoffs converge uniformly to 1 (and more generally, to their deterministic counterparts) with high probability.

• Non-Asymptotic Convergence Theorem (Theorem 1):
  For fixed student preferences and uniform random ordering, the paper proves that for any school $k$ with capacity $\alpha_k$, the observed cutoff $\gamma_k$ concentrates around a deterministic value $\bar{\gamma}_k$. Specifically:
  $$P(|\gamma_k - \bar{\gamma}_k| \geq \varepsilon) \leq 17 \exp\left\{ -\frac{\varepsilon \alpha_k}{32 \bar{\gamma}_k} \right\}$$
  This bound holds even against adversarial (arbitrary) student preferences.

• Uniform Convergence (Corollary 1):
  By applying a union bound across all $m$ schools, the paper establishes that the full vector of cutoffs converges uniformly with probability 1 in asymptotic sequences where capacities are $n/m$ and the condition $m \ln m \ll n$ holds.

• Sharpness of Results:
  The paper demonstrates that the condition $m \ln m \ll n$ is sharp. The provided example shows that without this condition (specifically when $n$ is comparable to $m \ln m$), uniform convergence fails, even in simplified deterministic preference structures.

Significance and Claims
The paper claims to resolve the open question of whether cutoff representations adequately describe real-world matching markets where the number of schools and students are of similar size. By proving non-asymptotic convergence under the condition $m \ln m \ll n$, the author provides a theoretical justification for:

1. The finite-sample accuracy of statistical estimators that rely on the cutoff representation (e.g., estimating school value-added).
2. The asymptotic validity of the cutoff representation in settings where both $n$ and $m$ grow to infinity, provided the growth rate of students outpaces $m \ln m$.

The work distinguishes itself by showing that concentration of RSD probabilities holds even against adversarial preferences, a robustness not guaranteed by prior asymptotic results limited to finite-school limits. The results suggest that while RSD is stable and efficient in sufficiently large markets (relative to the number of schools), the "large market" approximation breaks down if the number of schools grows too quickly relative to the number of students.