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

C'est le problème d'apparier les membres de deux groupes de même taille, chacun avec des préférences classées sur l'autre groupe, de sorte qu'il n'y ait pas deux personnes non appariées l'une à l'autre qui préféreraient toutes deux l'être — un appariement 'stable' sans incitation à défection.

Comment fonctionne l'algorithme de Gale-Shapley ?

Les proposants non appariés proposent à plusieurs reprises à leur évaluateur le plus préféré qu'ils n'ont pas encore essayé ; chaque évaluateur conserve la meilleure offre reçue jusqu'à présent et rejette les moins bonnes, évinçant même un appariement antérieur si un meilleur proposant se présente, jusqu'à ce que tous les proposants soient appariés.

Un appariement stable existe-t-il toujours ?

Oui — l'algorithme de Gale-Shapley est une preuve constructive qu'un appariement stable existe toujours pour tout ensemble de listes de préférences complètes, quelle que soit la manière dont les préférences sont organisées.

Que signifie 'optimal pour les proposants' ?

Cela signifie que chaque proposant se retrouve avec le meilleur partenaire possible qu'il pourrait obtenir dans n'importe quel appariement stable — le compromis est que les évaluateurs, symétriquement, obtiennent leur pire résultat parmi tous les appariements stables comparé à l'exécution de l'algorithme avec les rôles inversés.

Les listes de préférences doivent-elles classer tout le monde ?

Oui — ce calculateur exige que la liste de préférences de chaque participant soit un classement complet de chaque membre du groupe opposé sans répétitions, correspondant à la formulation classique du problème.

L'appariement stable est-il unique ?

Pas nécessairement — différents appariements stables valides peuvent exister pour les mêmes préférences ; Gale-Shapley trouve spécifiquement celui optimal pour les proposants, pas un appariement stable arbitraire parmi éventuellement plusieurs.

Combien de participants ce calculateur peut-il gérer ?

Ce calculateur prend en charge jusqu'à 15 participants par côté, gardant l'algorithme et la validation des listes de préférences instantanés tout en couvrant des exemples typiques saisis manuellement.

Où le problème des mariages stables est-il utilisé dans la vie réelle ?

Le même algorithme (et sa variante plusieurs-à-un) est utilisé pour apparier les internes en médecine aux hôpitaux (le National Resident Matching Program), les étudiants aux écoles, et dans certaines plateformes d'échange de reins et d'appariement d'emplois.

Solveur du Problème des Mariages Stables — Trouvez un Appariement Stable Entre Deux Groupes

Notre Solveur du Problème des Mariages Stables trouve un appariement entre deux groupes de même taille — proposants et évaluateurs — tel qu'aucune paire ne préférerait mutuellement être ensemble plutôt qu'avec son partenaire assigné, à l'aide de l'algorithme d'acceptation différée de Gale-Shapley, étant donné la liste de préférences classée de chaque participant sur l'autre groupe.

Réponse rapide

Saisissez des listes de préférences classées pour deux groupes de même taille pour trouver instantanément un appariement stable via l'algorithme de Gale-Shapley.

Préférences des proposants

Une ligne par proposant : Nom : préf1, préf2, ... classant chaque évaluateur, par ex. A1: B2, B1, B3.

Préférences des évaluateurs

Une ligne par évaluateur : Nom : préf1, préf2, ... classant chaque proposant, par ex. B1: A3, A1, A2.

Comment utiliser Solveur du Problème des Mariages Stables — Algorithme de Gale-Shapley en Ligne

1
Saisissez les préférences de chaque proposant sous forme d'une ligne : Nom : préf1, préf2, préf3, ... (classées de la plus à la moins préférée).
2
Saisissez les préférences de chaque évaluateur de la même manière, en classant chaque proposant.
3
Cliquez sur 'Calculer' pour trouver un appariement stable via l'algorithme de Gale-Shapley.

Pourquoi utiliser Solveur du Problème des Mariages Stables — Algorithme de Gale-Shapley en Ligne ?

Un appariement entre deux groupes est 'stable' s'il n'y a aucune paire qui préférerait mutuellement être appariée l'une à l'autre plutôt qu'à ses partenaires actuellement assignés — une telle paire aurait une incitation à rompre ses appariements existants, rendant l'appariement instable. L'algorithme de Gale-Shapley trouve toujours un appariement stable (un résultat fondamental qui a valu le prix Nobel d'économie 2012) : chaque proposant non apparié propose à son meilleur choix restant, chaque évaluateur accepte provisoirement sa meilleure offre reçue jusqu'à présent et rejette le reste (même en évinçant un appariement antérieur si une meilleure offre arrive), et cela se répète jusqu'à ce que tout le monde soit apparié. Le résultat n'est pas seulement stable mais optimal pour les proposants — chaque proposant obtient le meilleur partenaire possible qu'il pourrait avoir dans n'importe quel appariement stable.

Questions fréquentes

Outils similaires

Calculateur de Flux Réseau — Flux Maximal via Edmonds-Karp en Ligne

Trouvez le flux maximal d'une source à un puits dans un graphe orienté à capacités à l'aide de l'algorithme d'Edmonds-Karp. Calculateur gratuit avec une simple liste d'arêtes.

Calculatrice de Coloration de Graphe — Algorithme de Welsh-Powell en Ligne

Coloriez les sommets d'un graphe pour qu'aucun nœud connecté ne partage une couleur, à l'aide de l'algorithme glouton de Welsh-Powell. Calculatrice gratuite avec une simple saisie de liste d'arêtes.

Calculatrice de Permutation — Calculer P(n,r) en Ligne

Calculez les permutations P(n,r) — le nombre de façons d'arranger r éléments parmi n éléments au total où l'ordre compte. Calculatrice gratuite avec solutions étape par étape et décomposition des formules.