Problème des mariages stables

Algorithme de Gale Shapley.

En mathématiques, informatique et économie, le problème des mariages stables consiste à trouver, étant donné Modèle:Mvar hommes et Modèle:Mvar femmes, et leurs listes de préférences, une façon stable de les mettre en couple. Une situation est dite instable s'il y a au moins un homme et une femme qui préféreraient se mettre en couple plutôt que de rester avec leurs partenaires actuels (Modèle:M. préfère Modèle:Mme à Modèle:Mme, et Modèle:Mme préfère Modèle:M. à Modèle:M.). Ce problème a des applicationsModèle:Lesquelles en économie, en théorie des jeux et en physique statistiqueModèle:Référence nécessaire.

On sait trouver une solution stable, mais il en existe en général un grand nombre et l'on ne sait pas les trouver toutes, quand Modèle:Mvar est grand. On peut modifier l'énoncé en lui ajoutant une condition d'optimisation : il existe alors une solution optimale (ou plusieurs mais équivalentes), mais on ne sait pas la ou les trouver avec certitude, juste appliquer différents algorithmes, plus ou moins performants.

Histoire

Le problème des mariages stables est énoncé Modèle:Incise pour la première fois en 1962, avec en vue le problème de l'affectation des étudiants aux diverses formations universitaires. Cette même application (algorithme compris) est reprise entre 2009 et 2017 par le service Admission Post-Bac du ministère français de l'Enseignement supérieur.

Alors que l'énoncé du problème est symétrique, l'algorithme de Gale et Shapley est dissymétrique : il fait jouer un rôle différent aux hommes (« prétendants ») et aux femmes (« choisisseurs »). Si l'on inverse les rôles, on obtient une autre solution stable. On peut montrer que la première variante favorise les hommes, et même qu'elle est optimale pour eux Modèle:Incise et la pire possible pour les femmes. Naturellement, c'est le contraire si l'on inverse les rôles (femmes « prétendants » et hommes « choisisseurs »). Dans l'admission Post-Bac ci-dessus, les formations étaient dans le rôle des « prétendants » et les étudiants dans celui des « choisisseurs ».

Le problème des mariages stables possède en général un grand nombre de solutions. On peut en modifier l'énoncé en ajoutant une condition d'optimisation, en l'occurrence, la volonté de maximiser le « bonheur général » (qu'il est possible de définir de différentes façons, non équivalentes). En réalité, un problème équivalent (avec optimisation) avait été énoncé Modèle:Incise par Gaspard Monge dès 1781 : disposant d'un certain nombre de mines et du même nombre de dépôts où transporter le minerai (la liste de préférence des uns étant celle des autres classée par ordre de distance croissante), comment les relier deux par deux pour économiser le coût total du transport ?

Le problème des mariages stables avec optimisation s'apparente à d'autres problèmes d'optimisation difficiles comme celui du « voyageur de commerce ». Son application à « la théorie des allocations stables et la pratique de la conception de marchés » vaut à Alvin Roth et Lloyd Shapley le prix Nobel d'économie 2012.

Définition formelle du problème

On se donne deux ensembles Modèle:Mvar et Modèle:Mvar, supposés disjoints, ayant chacun Modèle:Mvar éléments. On se donne aussi, pour chaque élément de Modèle:Mvar et de Modèle:Mvar, une fonction de préférence, qui classe tous les éléments de l'autre ensemble. On cherche alors à associer de façon bijective les éléments de Modèle:Mvar avec ceux de Modèle:Mvar, pour qu'il n'existe pas $a\in A$ et $b\in B$ tels que Modèle:Mvar préfère Modèle:Mvar à l'élément qui lui est associé, et Modèle:Mvar préfère Modèle:Mvar à l'élément qui lui est associé.

Problèmes algorithmiques proches

• Problème d'affectation
• Problème des colocataires
• Algorithme d'affectation de candidats après concours multiples

Voir aussi

Articles connexes

• Algorithme de Gale et Shapley

Liens externes

• Modèle:Autorité
• Modèle:Dictionnaires
• Modèle:Bases