Stability and Efficiency of Random Serial Dictatorship

Résumé technique : Stabilité et efficacité de la dictature sérielle aléatoire

Énoncé du problème
Cet article examine la validité du cadre de « représentation par seuil » dans les grands marchés d'appariement, spécifiquement dans le contexte du mécanisme de dictature sérielle aléatoire (RSD). Alors que les représentations par seuil, proposées par Azevedo et Leshno (2016) et Menzel (2015), sont devenues un outil analytique standard et maniable pour étudier les grands marchés (et constituent la base d'études empiriques comme Abdulkadroğlu et al., 2017), leur validité théorique n'avait été établie jusqu'alors que dans des limites asymptotiques où le nombre d'étudiants ($n$) tend vers l'infini tandis que le nombre d'écoles ($m$) reste fini.

Le problème central est de savoir si cette représentation reste précise dans des contextes « réels » où $n$ et $m$ augmentent tous deux, en particulier lorsqu'ils sont de magnitude similaire. L'article étudie la convergence non asymptotique des seuils RSD (définis comme le rang normalisé de l'étudiant admis le moins bien classé) vers des contreparties déterministes sous des préférences d'étudiants arbitraires.

Méthodologie
L'auteur s'écarte de la littérature traditionnelle sur la conception de mécanismes en employant des outils analytiques issus des algorithmes randomisés et des probabilités discrètes. La méthodologie centrale comprend :

1. Bornes probabilistes : Établissement d'inégalités de concentration pour les probabilités de loterie RSD et les seuils.
2. Analyse de Lipschitz : Utilisation des résultats de concentration de la mesure de Talagrand (Talagrand, 1995) et des propriétés de la distance de Hamming sur les permutations pour borner les fluctuations du nombre d'étudiants préférant une école spécifique.
3. Analyse de transition de phase : Investigation de la relation entre le nombre d'étudiants ($n$) et d'écoles ($m$) pour identifier les régimes où les seuils convergent par rapport à ceux où ils divergent.

L'analyse définit le seuil $\gamma_k$ d'une école basé sur une permutation aléatoire $\Pi$ des étudiants. Elle compare le seuil stochastique observé à un seuil déterministe $\bar{\gamma}_k$, défini via l'espérance du nombre d'étudiants qui préfèrent faiblement une école à leur option assignée.

Contributions et résultats clés

• Seuil de transition de phase : L'article identifie une transition de phase critique dans le comportement des seuils RSD se produisant dans la région où $m \ln m \asymp n$.

  • En dessous du seuil ($n \lesssim m \ln m$) : Les seuils ne convergent pas uniformément. L'article fournit un exemple jouet démontrant que si $n \leq \alpha m \ln m$ pour une constante finie $\alpha$, le seuil minimum ne converge pas en probabilité vers 1, impliquant que la représentation par seuil est invalide.
  • Au-dessus du seuil ($n \gg m \ln m$) : Les seuils convergent uniformément vers 1 (et plus généralement, vers leurs contreparties déterministes) avec une forte probabilité.

• Théorème de convergence non asymptotique (Théorème 1) :
  Pour des préférences d'étudiants fixes et un ordre aléatoire uniforme, l'article démontre que pour toute école $k$ avec une capacité $\alpha_k$, le seuil observé $\gamma_k$ se concentre autour d'une valeur déterministe $\bar{\gamma}_k$. Plus précisément :
  $$P(|\gamma_k - \bar{\gamma}_k| \geq \varepsilon) \leq 17 \exp\left\{ -\frac{\varepsilon \alpha_k}{32 \bar{\gamma}_k} \right\}$$
  Cette borne vaut même face à des préférences d'étudiants adverses (arbitraires).

• Convergence uniforme (Corollaire 1) :
  En appliquant une borne d'union sur l'ensemble des $m$ écoles, l'article établit que le vecteur complet des seuils converge uniformément avec une probabilité de 1 dans les suites asymptotiques où les capacités sont de $n/m$ et que la condition $m \ln m \ll n$ est satisfaite.

• Précision des résultats :
  L'article démontre que la condition $m \ln m \ll n$ est précise. L'exemple fourni montre que sans cette condition (spécifiquement lorsque $n$ est comparable à $m \ln m$), la convergence uniforme échoue, même dans des structures de préférences déterministes simplifiées.

Portée et affirmations
L'article prétend résoudre la question ouverte de savoir si les représentations par seuil décrivent adéquatement les marchés d'appariement réels où le nombre d'écoles et d'étudiants est de taille similaire. En prouvant la convergence non asymptotique sous la condition $m \ln m \ll n$, l'auteur fournit une justification théorique pour :

1. La précision des échantillons finis des estimateurs statistiques qui reposent sur la représentation par seuil (par exemple, l'estimation de la valeur ajoutée des écoles).
2. La validité asymptotique de la représentation par seuil dans des contextes où $n$ et $m$ tendent tous deux vers l'infini, à condition que le taux de croissance des étudiants dépasse $m \ln m$.

L'ouvrage se distingue en montrant que la concentration des probabilités RSD vaut même face à des préférences adverses, une robustesse non garantie par les résultats asymptotiques antérieurs limités aux limites d'écoles finies. Les résultats suggèrent que si le RSD est stable et efficace dans des marchés suffisamment grands (par rapport au nombre d'écoles), l'approximation de « grand marché » s'effondre si le nombre d'écoles croît trop rapidement par rapport au nombre d'étudiants.