The Distribution of Envy in Matching Markets

1. Problématique et Contexte

L'article s'intéresse à la distribution de l'envie dans les marchés d'appariement aléatoires à deux faces, spécifiquement sous l'algorithme de Deferred Acceptance (DA) (Acceptation Différée), également connu sous le nom d'algorithme de Gale-Shapley.

Bien que la stabilité (absence d'envie justifiée) soit une propriété fondamentale de DA, les auteurs cherchent à quantifier l'ampleur de l'envie globale (qu'elle soit justifiée ou non). Plus précisément, ils étudient deux catégories d'agents (étudiants) dans le côté proposant :

1. Les étudiants que personne n'envie (unenvied) : Ceux qui sont affectés à des écoles sous-démandées.
2. Les étudiants qui n'envient personne (envy-free) : Ceux qui obtiennent leur premier choix.

L'importance de ces mesures réside dans trois aspects :

• Efficacité Pareto : DA n'est pas toujours Pareto-efficace. Comprendre la distribution de l'envie aide à identifier les gains potentiels d'amélioration.
• Bien-être : Les étudiants qui n'envient personne correspondent à ceux qui obtiennent leur premier choix, une métrique clé pour les décideurs politiques.
• Impossibilité d'amélioration : Tout étudiant qui n'envie personne ou qui n'est pas envié par quiconque est « improvable » (unimprovable) : il ne peut pas être rendu plus heureux par aucun échange partant du résultat DA.

2. Modèle et Méthodologie

Modèle :

• Un marché d'appariement à deux faces avec $n$ étudiants et $n$ écoles (quotas unitaires).
• Les préférences strictes des étudiants et les priorités des écoles sont tirées indépendamment et uniformément au hasard (modèle i.i.d.).
• L'analyse se concentre sur le bien-être du côté des étudiants (proposants).

Outils Mathématiques :
Les auteurs utilisent des outils de probabilité appliquée, notamment :

• La méthode de la décision différée (principle of deferred decisions) pour construire les préférences à la volée.
• Le lien entre l'implémentation séquentielle de DA (McVitie et Wilson, 1971) et le problème du collectionneur de coupons (Coupon Collector Problem).
• Des bornes asymptotiques et des calculs exacts pour les marchés finis.

3. Résultats Principaux

A. Nombre d'étudiants que personne n'envie ($NEn$)

Les auteurs établissent un résultat exact pour tout $n$ fini.

• Résultat : L'espérance du nombre d'étudiants que personne n'envie est égale au $n$-ième nombre harmonique :
  $$NEn = H_n = \sum_{k=1}^n \frac{1}{k}$$
• Démonstration : En utilisant l'implémentation séquentielle de DA, ils montrent que le nombre d'écoles sous-démandées (reçues par exactement un étudiant distinct) correspond au nombre de « coupons uniques » dans le problème du collectionneur de coupons au moment de l'arrêt (lorsque tous les coupons ont été collectés). Myers et Wilf (2006) ont démontré que cette espérance est $H_n$.
• Comportement asymptotique : Puisque $H_n \approx \ln n + \gamma$, la fraction d'étudiants non enviés tend vers zéro ($H_n/n \to 0$) lorsque $n \to \infty$. Pour un marché de 10 000 étudiants, on s'attend à moins de 10 étudiants non enviés.

B. Nombre d'étudiants qui n'envient personne ($ENn$)

Pour cette catégorie, les auteurs fournissent une approximation asymptotique.

• Résultat : La distribution des rangs des étudiants sous DA est approximée par une loi géométrique de paramètre $1/H_n$. Par conséquent, l'espérance du nombre d'étudiants qui obtiennent leur premier choix est :
  $$ENn \approx \frac{n}{H_n}$$
• Interprétation : Bien que ce nombre soit plus grand que celui des étudiants non enviés, il reste faible en proportion du marché. Pour $n=10\,000$, environ 1 100 étudiants obtiennent leur premier choix (soit ~11 %), alors que le nombre d'étudiants non enviés est négligeable.

C. Comparaison avec la Dictature Séquentielle Aléatoire (RSD)

Les auteurs comparent DA à la Random Serial Dictatorship (RSD), où les étudiants choisissent selon un ordre aléatoire.

• Étudiants qui n'envient personne :
  • Sous RSD : $\approx n/2$ (une fraction constante).
  • Sous DA : $\approx n/H_n$ (beaucoup plus faible).
  • Conclusion : DA est nettement moins performant que RSD pour l'attribution des premiers choix.
• Étudiants que personne n'envie :
  • Résultat surprenant : Sous RSD, l'espérance est exactement $H_n$, identique à celle de DA.
  • Signification : Ce résultat suggère que le nombre d'étudiants non enviés ($H_n$) est une propriété fondamentale des marchés aléatoires, indépendante du mécanisme spécifique (DA ou RSD), et non une déficience de DA.

4. Contributions Clés

1. Formule exacte pour les marchés finis : Contrairement à la plupart des résultats asymptotiques sur les marchés aléatoires, l'article fournit une expression exacte ($H_n$) pour le nombre d'étudiants non enviés, valable pour tout $n$.
2. Lien avec le problème du collectionneur de coupons : L'analyse établit une connexion rigoureuse et élégante entre l'exécution de l'algorithme DA et la statistique des coupons uniques.
3. Invariance du nombre d'étudiants non enviés : La découverte que DA et RSD génèrent le même nombre attendu d'étudiants non enviés ($H_n$) remet en question l'idée que ce métrique dépend fortement du mécanisme d'appariement.
4. Quantification des limites d'amélioration : L'article démontre que la fraction d'étudiants « impropres à l'amélioration » (unimprovable) tend vers zéro dans les grands marchés, indiquant que la majorité des étudiants pourraient potentiellement être améliorés par des échanges, même si DA est stable.

5. Signification et Implications

• Efficacité vs Stabilité : Bien que DA soit stable, il laisse une très petite fraction d'étudiants dans des positions « optimales » (soit en obtenant leur premier choix, soit en étant non enviés). La majorité des étudiants subissent une forme d'envie.
• Robustesse du résultat $H_n$ : Le fait que ce résultat s'applique aussi bien à DA qu'à RSD (et par extension au Top Trading Cycles avec dotation aléatoire) suggère que la structure des marchés aléatoires impose une limite naturelle au nombre d'agents totalement satisfaits ou non enviés, indépendamment de la complexité du mécanisme.
• Limites pour les politiques publiques : Les décideurs ne doivent pas s'attendre à ce que des mécanismes stables comme DA garantissent un grand nombre d'étudiants sans envie ou avec leur premier choix dans de grands marchés.

En résumé, l'article démontre que dans les marchés d'appariement aléatoires, les étudiants qui sont soit totalement satisfaits (pas d'envie), soit totalement ignorés (pas enviés), constituent une fraction négligeable du marché à mesure que celui-ci grandit, et que cette propriété est intrinsèque au hasard des préférences plutôt qu'au mécanisme d'allocation.