Algorithme de Gale-Shapley
- Introduite par
- David Gale, Lloyd Shapley
- Année
- 1962
- Type
- algorithm
- Famille
- Game-theoretic
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
L'algorithme de Gale-Shapley résout le problème du mariage stable : comment apparier deux groupes (par exemple, des internes en médecine à des hôpitaux, des étudiants à des écoles) de telle sorte qu'aucune paire ne se préfère mutuellement à ses partenaires assignés.
Introduit par David Gale et Lloyd Shapley en 1962, l'algorithme garantit un appariement stable en temps polynomial grâce à un processus d'acceptation différée où une partie propose séquentiellement et l'autre partie répond, révisant ses choix à mesure que de meilleures options se présentent.
L’intuition derrière la méthode
Imaginez l'appariement de médecins à des hôpitaux. L'algorithme fonctionne comme un jeu de chaises musicales : chaque médecin propose à l'hôpital qu'il préfère le plus ; chaque hôpital accepte provisoirement le meilleur médecin disponible. À mesure que les hôpitaux reçoivent de meilleures propositions, ils révisent leurs choix, rejetant potentiellement des acceptations antérieures. Les médecins rejetés proposent à l'hôpital qu'ils préfèrent ensuite. Le processus se poursuit jusqu'à ce qu'aucun médecin ne veuille proposer davantage et qu'aucun hôpital ne veuille échanger son appariement actuel. Le résultat est stable : aucune paire médecin-hôpital ne préférerait être appariée l'une à l'autre plutôt qu'à ses partenaires assignés.
Histoire
David Gale et Lloyd Shapley ont publié leur solution au problème du mariage stable en 1962, prouvant que des appariements stables existent toujours pour les marchés bilatéraux. Leur algorithme a donné naissance à une vaste littérature sur la théorie des appariements avec des applications couvrant la médecine, l'éducation et les marchés du travail. En 2012, Alvin Roth a remporté le prix Nobel d'économie pour ses travaux expérimentaux et théoriques appliquant la théorie des appariements à la conception de marchés réels, validant l'importance pratique du cadre de Gale-Shapley.
Quand l’utiliser
Appliquez l'algorithme de Gale-Shapley lors de l'appariement de marchés bilatéraux où la stabilité est cruciale : placement des internes en médecine, affectation des étudiants aux écoles, échange de reins, appariement sur le marché du travail ou marchés de rencontres en ligne. Utilisez-le lorsqu'il existe un risque d'instabilité d'appariement (paires bloquantes) qui pourrait défaire un appariement après l'affectation. L'algorithme est idéal lorsqu'une partie peut agir en premier avec un avantage stratégique.
Limites et points d’attention
- Non Pareto-optimal : l'appariement peut ne pas maximiser le bien-être total ; il peut exister des paires bloquées qui pourraient toutes bénéficier d'un échange de partenaires
- Vulnérabilité stratégique : le côté proposant peut gagner en déformant ses préférences, tandis que le côté répondant est honnête
- Asymétrie : les résultats dépendent fortement du côté qui propose en premier
- Ne gère pas les contraintes : difficile d'incorporer des préférences complexes (par exemple, couples, préférences régionales) sans modification algorithmique
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Stabilité garantie : aucune paire bloquante n'existe dans l'appariement final
- Temps polynomial : complexité en O(n^2), ce qui le rend efficace pour de grandes populations
- Implémentation simple : facile à exécuter en pratique avec une collecte transparente des préférences
- Incitatifs stratégiques : le côté proposant a un avantage stratégique, préférant les propositions précoces aux propositions tardives
- Applicable universellement : fonctionne pour tous les profils de préférences sans supposer la convexité ou la transitivité
Applications
- Appariement des internes en médecine : jumelage des diplômés en médecine aux programmes de résidence hospitalière via le NRMP
- Choix de l'école : affectation des élèves aux écoles publiques en fonction des préférences et des contraintes de capacité
- Échange de reins : appariement des donneurs et receveurs d'organes pour maximiser les transplantations compatibles
- Appariement sur le marché du travail : connexion des demandeurs d'emploi avec les employeurs sur les marchés du travail bilatéraux
- Rencontres en ligne : appariement des utilisateurs sur les plateformes de rencontres pour améliorer la stabilité des appariements et la satisfaction des utilisateurs
Comment ça marche
Comment ça marche
Créez des listes de préférences pour tous les individus des deux groupes, représentant leur classement de l'autre partie.
À chaque tour, chaque personne non appariée du côté proposant fait une proposition à la personne la mieux classée de l'autre côté à laquelle elle n'a pas encore proposé.
Chaque personne du côté recevant accepte provisoirement la proposition si elle n'est pas appariée, ou si le proposant est mieux classé que son partenaire actuel, auquel cas elle révoque l'engagement précédent.
L'algorithme s'arrête lorsque chaque personne est appariée et qu'aucune autre proposition n'a lieu, produisant un appariement stable.
Pièges courants
- Supposer que la stabilité seule est suffisante pour l'équité ou le bien-être ; les appariements stables peuvent être très asymétriques en faveur d'une partie
- Confondre stabilité et optimalité ; un appariement stable n'est pas nécessairement maximisant du bien-être
- Négliger l'avantage stratégique du côté proposant : les membres du côté proposant ont tendance à être appariés à des partenaires mieux classés
- Oublier que l'algorithme suppose des listes de préférences complètes ; les préférences incomplètes nécessitent une modification
Questions fréquentes
Pourquoi la stabilité est-elle importante dans l'appariement ?
Sans stabilité, les paires appariées pourraient découvrir plus tard qu'elles se préfèrent mutuellement à leurs partenaires assignés, créant une incitation à rompre l'appariement. Les appariements stables empêchent de telles paires bloquantes, garantissant que l'appariement persiste sans renégociation.
L'algorithme de Gale-Shapley produit-il toujours le même appariement ?
Non. Des listes de préférences ou des ordres de proposition différents peuvent produire des appariements stables différents. Cependant, il existe toujours un appariement stable « optimal pour les hommes » (le meilleur pour tous les proposants) et un appariement stable « optimal pour les femmes » (le meilleur pour tous les répondants).
Comment Gale-Shapley gère-t-il les préférences sur les groupes (par exemple, les couples) ?
L'algorithme standard ne gère pas directement les couples ou d'autres contraintes. Des extensions comme l'algorithme des couples existent mais sont plus complexes et peuvent ne pas garantir la stabilité pour tous les profils de préférences.
Méthodes associées
Sources
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Ouvrir la référence DOICopié.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
Ouvrir la référence DOICopié.