Note on the size of a stable matching

Résumé Technique : Note sur la taille d'un appariement stable

Énoncé du Problème
L'article étudie la relation entre la taille d'un appariement stable et la taille du plus grand appariement individuellement rationnel (maximum) dans un marché d'appariement bilatéral un-à-un (travailleurs et entreprises avec un seul poste disponible). Bien que le cadre de Gale-Shapley garantisse l'existence d'appariements stables, il ne garantit pas que ces appariements maximisent le nombre de travailleurs employés ou de postes pourvus. Les auteurs abordent la question suivante : étant donné un marché où le plus grand appariement individuellement rationnel contient $n$ paires, quelle est la limite inférieure du nombre de paires dans tout appariement stable ? De plus, ils cherchent à caractériser les structures de préférences spécifiques qui forcent les appariements stables à être aussi petits que possible par rapport au maximum, et analysent le chevauchement entre les paires stables et les paires maximales.

Méthodologie
Les auteurs utilisent une approche de théorie des graphes pour modéliser le marché d'appariement, en utilisant des formulations de graphes orientés et non orientés.

1. Formulation par Graphe Non Orienté : Le marché est modélisé comme un graphe biparti $G = (W, F; E)$, où les arêtes représentent des paires acceptables. Les auteurs utilisent les propriétés des appariements maximaux et maximums pour établir des bornes.
2. Formulation par Graphe Orienté (Digraphe) : Pour caractériser les structures de préférences, les auteurs adoptent la formulation de digraphe d'appariement proposée par Maffray (1992). Dans ce digraphe $D = (V, A)$, les sommets représentent des paires acceptables $(w, f)$, et les arcs représentent les classements de préférences (par exemple, un arc de $(w, f)$ vers $(w, f')$ indique que le travailleur $w$ préfère $f'$ à $f$).
3. Suppression Itérative des Alternatives Peu Attractives (IDUA) : Les auteurs utilisent la procédure IDUA (Balinski et Ratier, 1997 ; Gutin et al., 2023) pour réduire le marché à sa « forme normale ». Ce processus élimine itérativement les paires qui ne peuvent appartenir à aucun appariement stable (par exemple, les paires où un participant est associé à un partenaire moins préféré alors que son partenaire le plus préféré est sans correspondance).
4. Caractérisation Constructive : Les auteurs définissent des classes spécifiques de marchés ($G_n$ et $F_n$) en construisant des profils de préférences qui étendent un marché de base possédant un appariement stable maximum, en ajoutant de nouveaux participants dont les préférences sont structurées pour être « peu attractives » pour les participants stables existants.

Contributions Clés et Résultats

• Théorème 1 (Borne de Taille) : Le résultat principal établit que dans tout marché où le plus grand appariement individuellement rationnel est de taille $n$, tout appariement stable doit avoir une taille d'au moins $\lceil n/2 \rceil$.

  • Logique de Preuve : La preuve repose sur deux faits : (i) un appariement stable est un appariement maximal (aucune paire acceptable n'existe où les deux parties sont sans correspondance), et (ii) tout appariement maximal dans un graphe est au moins de la moitié de la taille d'un appariement maximum.
  • Implication : Le taux d'emploi à l'équilibre ne peut jamais descendre en dessous de 50 % de l'emploi maximum atteignable, à condition que l'appariement maximum soit individuellement rationnel.

• Théorème 2 (Caractérisation des Préférences Extrémales) : L'article caractérise la classe de profils de préférences ($F_n$) qui atteignent cette borne inférieure.

  • Un marché atteint la borne (taille stable = $\lceil n/2 \rceil$, taille max = $n$) si et seulement s'il appartient à la classe $F_n$.
  • Propriété Structurelle : Dans ces marchés, les participants qui n'apparaissent dans aucun appariement stable (les « sans correspondance » en équilibre) doivent se trouver mutuellement inacceptables. S'ils se trouvaient acceptables, ils formeraient une paire bloquante, augmentant ainsi la taille de l'appariement stable.
  • Accord au Sommet : Une sous-classe naturelle de ces marchés présente un « accord au sommet », où les participants dans le noyau stable classent tous les nouveaux participants non stables en dessous de leur partenaire stable le moins préféré.

• Théorème 3 (Chevauchement et Sacrifice) : Les auteurs analysent l'intersection entre l'ensemble des paires dans un appariement stable ($\mu^*$) et un appariement maximum ($\mu$).

  • Soit $r$ le nombre de paires communes. Le théorème stipule que : $|\mu^*| \geq (|\mu| + r) / 2$.
  • Implication : Lorsque l'appariement stable est minimisé (c'est-à-dire $|\mu^*| = \lceil |\mu|/2 \rceil$), le chevauchement $r$ doit être nul. Cela signifie que si le marché est structuré de telle sorte que les appariements stables soient aussi petits que possible, aucune des paires de l'appariement stable ne figure dans l'appariement maximum.
  • Coût de la Stabilité : Maximiser l'emploi (pourvoir tous les postes) peut nécessiter de « sacrifier » tous les appariements qui seraient autrement présents dans une configuration stable plus petite.

Signification et Portée
L'article présente son analyse comme une exploration du « coût de la stabilité ». Il quantifie l'arbitrage entre la stabilité et l'efficacité (mesurée par la taille de l'appariement). Les auteurs notent que bien que la stabilité garantisse l'absence de paires bloquantes, elle peut entraîner une réduction significative du nombre de travailleurs employés par rapport au maximum théorique, spécifiquement dans les marchés dotés des structures de préférences identifiées dans le Théorème 2.

Les auteurs limitent explicitement la portée de leurs résultats aux marchés d'appariement bilatéraux un-à-un. Ils reconnaissent que bien que le cadre soit largement applicable (par exemple, étudiant-université, médecin-hôpital), les bornes et caractérisations spécifiques dérivées ici ne s'étendent pas automatiquement à des environnements plus complexes tels que les marchés de type un-à-plusieurs, les marchés avec des couples, ou les problèmes « colocataire » unilatéraux. L'article ne propose pas de nouveaux algorithmes ou d'applications expérimentales, mais fournit plutôt une borne théorique et une caractérisation structurelle des scénarios de pire cas pour les taux d'emploi dans les équilibres stables.