Solveur du Problème des Mariages Stables

Solveur du Problème des Mariages Stables

Le Solveur du Problème des Mariages Stables est une implémentation interactive de l'algorithme d'acceptation différée de Gale-Shapley. Cet algorithme de mise en correspondance de 1962, conçu par David Gale et Lloyd Shapley, a prouvé qu'il produit toujours un appariement stable entre deux groupes de taille égale, à condition que chaque membre fournisse un classement complet de l'autre côté. Cet outil prend vos listes de préférences, exécute l'algorithme étape par étape et affiche le résultat sous forme d'appariement stable, de visualisation biparti animée, de cartes de chaleur de préférences et d'une preuve vérifiée qu'aucune paire bloquante n'existe.

Qu'est-ce que le problème des mariages stables ?

Étant donné deux ensembles disjoints de taille égale — disons n hommes et n femmes, ou n candidats et n postes — et une liste de préférences complète de chaque membre classant chaque membre de l'autre côté, un appariement est une correspondance biunivoque entre les deux ensembles. L'appariement est dit stable si aucune paire (a, b) en dehors de l'appariement ne préférerait être ensemble plutôt que de rester avec leurs partenaires assignés.

Formellement, un appariement M est stable s'il n'y a pas de paire bloquante — une paire (a, b) avec a apparié à b' et b apparié à a' telle que :

Si les deux conditions sont remplies, a et b abandonneraient tous deux leurs partenaires actuels, ce qui déstabiliserait l'appariement. Un appariement stable est un appariement où aucune paire de ce type n'existe.

L'algorithme de Gale-Shapley

Gale et Shapley ont prouvé — de manière constructive — qu'un appariement stable existe toujours pour tout ensemble de préférences, et ils ont donné un algorithme efficace pour en trouver un. L'algorithme se déroule par rounds :

1. Chaque proposant non engagé propose au receveur le mieux classé sur sa liste qui ne l'a pas encore rejeté.
2. Chaque receveur ayant reçu une ou plusieurs propositions choisit celle qu'il préfère le plus (par rapport à tout fiancé provisoire actuel) et l'accepte provisoirement ; tous les autres sont rejetés.
3. Les proposants rejetés redeviennent libres et passent à leur choix suivant au round suivant.
4. L'algorithme se termine lorsque chaque proposant est engagé — ce qui est garanti d'arriver en au plus n² propositions.

Propriétés théoriques clés

Existence et unicité

Un appariement stable existe toujours (Gale & Shapley, 1962), mais n'est pas nécessairement unique. Pour un ensemble de préférences donné, il peut y avoir plusieurs appariements stables, et ils forment un treillis ordonné par préférence conjointe.

Optimalité du proposant

Lorsqu'un côté propose, Gale-Shapley produit l'appariement stable optimal pour le proposant : chaque proposant reçoit le meilleur partenaire avec lequel il pourrait être apparié dans n'importe quel appariement stable. Par un argument symétrique, c'est aussi l'appariement pessimal pour le receveur — le côté receveur obtient son pire partenaire stable. Changer le côté proposant dans ce calculateur change souvent le résultat.

Résistance à la stratégie pour les proposants

Sous Gale-Shapley, les proposants n'ont aucun intérêt à fausser leurs préférences : dire la vérité est une stratégie dominante pour eux. Les receveurs, en revanche, peuvent parfois bénéficier d'une déclaration stratégique erronée — c'est l'une des raisons pour lesquelles le marché hôpitaux-résidents aux États-Unis est conçu avec les étudiants comme côté proposant.

Théorème des hôpitaux ruraux

L'ensemble des agents non appariés est identique dans tous les appariements stables. Ainsi, si votre instance a des tailles déséquilibrées (au-delà du cadre de cet outil classique), les mêmes personnes resteront non appariées dans chaque solution stable.

Format d'entrée

Ce calculateur attend une ligne par membre, avec le nom suivi de deux points et d'une liste complète de préférences classées séparées par des virgules :

Exigences :

• Les deux groupes doivent avoir exactement le même nombre de membres.
• Chaque membre doit classer chaque membre de l'autre groupe — pas de listes partielles.
• Les noms peuvent utiliser des lettres, des chiffres, des underscores, des tirets, des espaces et des lettres Unicode courantes.
• Jusqu'à 15 membres par côté sont pris en charge pour une animation interactive rapide.

Comment utiliser ce calculateur

1. Saisissez les préférences du Groupe A dans la zone de texte de gauche — une ligne par membre, liste complète classée.
2. Saisissez les préférences du Groupe B dans la zone de texte de droite — une ligne par membre, même format.
3. Choisissez le côté proposant. Sélectionnez le Groupe A ou le Groupe B. Essayez les deux pour comparer les résultats A-optimal et B-optimal.
4. Cliquez sur "Résoudre l'appariement stable". Le calculateur exécute Gale-Shapley et produit les paires stables, les statistiques, l'animation et la preuve de stabilité.
5. Parcourez l'animation avec les commandes lecture / étape / réinitialisation pour voir chaque proposition, acceptation, échange et rejet dans l'ordre.
6. Inspectez la carte de chaleur. Chaque cellule affiche le classement ; les cellules entourées de jaune forment l'appariement final — regardez à quelle hauteur ces cellules se situent pour voir à quel point chaque côté est "satisfait".

Exemple concret — Le 3×3 classique

Hommes : Alex, Bryan, Chris. Femmes : Bea, Claire, Diana. Préférences :

L'exécution de Gale-Shapley avec les hommes qui proposent donne Alex–Bea, Bryan–Claire, Chris–Diana en un seul round (le premier choix de chaque homme correspond à une femme dont le premier choix est quelqu'un d'autre — pas de conflit). L'appariement est stable : aucune paire homme-femme ne serait mieux lotie en échangeant de partenaire, il n'y a donc pas de paire bloquante.

Applications dans le monde réel

Pourquoi Lloyd Shapley a remporté un prix Nobel

En 2012, l'Académie royale des sciences de Suède a décerné le prix Nobel d'économie à Lloyd Shapley (pour la théorie, aux côtés de David Gale qui était décédé) et Alvin Roth (pour l'application de la théorie aux marchés réels, y compris la refonte du match de résidence médicale aux États-Unis et des réseaux d'échange de reins). Le prix récompensait "la théorie des allocations stables et la pratique de la conception de marchés".

Foire aux questions

Qu'est-ce que le problème des mariages stables ?

Le problème des mariages stables pose la question suivante : étant donné deux groupes de taille égale où chaque membre classe tous les membres de l'autre groupe du plus au moins préféré, pouvons-nous apparier tout le monde de manière à ce que deux personnes ne préfèrent pas toutes deux quitter leurs partenaires actuels l'une pour l'autre ? Un tel appariement est appelé un appariement stable. L'algorithme de Gale-Shapley résout ce problème en un temps O(n²) et trouve toujours un appariement stable.

Comment fonctionne l'algorithme de Gale-Shapley ?

L'algorithme d'acceptation différée de Gale-Shapley procède par rounds. À chaque round, chaque proposant actuellement non engagé propose au receveur le mieux classé sur sa liste qui ne l'a pas encore rejeté. Chaque receveur accepte provisoirement la meilleure proposition reçue jusqu'à présent et rejette les autres ; tout proposant évincé redevient libre. L'algorithme se termine lorsqu'aucun proposant n'est libre, ce qui arrive en au plus n² propositions.

L'appariement stable est-il unique ?

Non. Une instance de problème de mariage stable peut avoir plusieurs appariements stables. Cependant, lorsqu'un côté propose, Gale-Shapley produit toujours l'appariement stable optimal pour le proposant : chaque proposant obtient le meilleur partenaire qu'il pourrait obtenir dans n'importe quel appariement stable. Par symétrie, c'est aussi l'appariement pessimiste pour le receveur de l'autre côté. Changer le côté proposant donne souvent un appariement stable différent.

Qu'est-ce qu'une paire bloquante ?

Une paire bloquante est une paire (a, b) qui n'est pas actuellement appariée où a préfère b à son partenaire actuel ET b préfère également a à son partenaire actuel. Si une paire bloquante existe, l'appariement est instable car ces deux-là préféreraient s'apparier entre eux. Un appariement stable n'a pas de paires bloquantes, ce que ce calculateur vérifie automatiquement après chaque résolution.

Quelles sont les applications réelles de l'appariement stable ?

L'algorithme de Gale-Shapley alimente le National Resident Matching Program qui affecte les étudiants en médecine aux résidences aux États-Unis, les systèmes de choix d'école à Boston et New York, les admissions à l'université dans plusieurs pays, les chaînes d'échange de reins de donneurs d'organes et les systèmes d'affectation de colocataires. Lloyd Shapley et Alvin Roth ont remporté le prix Nobel d'économie 2012 en partie pour ces travaux.

Les deux groupes doivent-ils être de la même taille ?

Dans la formulation classique du mariage stable, oui. Les deux côtés doivent avoir le même nombre de membres et chacun doit fournir un classement complet de l'autre côté. Des variantes déséquilibrées (telles que l'appariement stable avec des listes incomplètes ou le problème des hôpitaux et des résidents) existent mais nécessitent des algorithmes modifiés. Ce calculateur impose des tailles égales et des listes de préférences complètes.

Lectures complémentaires

• Problème des mariages stables — Wikipédia
• Algorithme de Gale-Shapley — Wikipédia
• National Resident Matching Program — Wikipédia
• Prix Nobel de sciences économiques 2012 — Shapley & Roth