vignette|Algorithme de Gale Shapley. En mathématiques, informatique et économie, le problème des mariages stables consiste à trouver, étant donné hommes et 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 actuelsDonald E. Knuth ( préfère à , et préfère à ). Ce problème a des applications pratiques en économie, en théorie des jeux et en physique statistique.

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 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é 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 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é 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 et , supposés disjoints, ayant chacun éléments. On se donne aussi, pour chaque élément de et de , une liste de préférence, qui classe tous les éléments de l'autre ensemble. On cherche alors une bijection f de dans , pour qu'il n'existe pas et tels que préfère à f(a), et préfère à f(b).

Problèmes algorithmiques proches Problème d'affectation Problème des colocataires Algorithme d'affectation de candidats après concours multiples

Notes et références

Voir aussi Bibliographie Donald E. Knuth, Mariages Stables et leurs relations avec d'autres problèmes combinatoires. Introduction à l'analyse mathématique des algorithmes, Montréal, Les Presses de l'Université de Montréal, 1976, 106pp.

Articles connexes Algorithme de Gale et Shapley

Liens externes Serge Fontaine, Couples stables et prix Nobel

Catégorie:Théorie des jeux Catégorie:Combinatoire Mariage Catégorie:Couplage (théorie des graphes) Mariage