Problème des mariages stables

Le problème des mariages stables est un problème mathématique et informatique consistant à trouver par exemple, étant donnés n hommes, n femmes et leurs listes de préférences, une façon stable de les mettre en couple. Une situation est dite instable s'il existe au moins un homme et une femme qui préféreraient se mettre en couple plutôt que de rester avec leurs partenaires actuels[1] (M. Dupont préfère Mme Durand à Mme Dupont, et Mme Durand préfère M. Dupont à M. Durand). Ce problème a des applications 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 n 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 où les trouver avec certitude, juste appliquer différents algorithmes, plus ou moins performants.

Histoire

Le problème des mariages stables est énoncé — et résolu (algorithme de Gale et Shapley) — pour la première fois en 1962, avec en vue le problème de l'affectation des étudiants aux diverses formations universitaires[2]. 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[3].

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 — chaque homme se voyant assigner la meilleure partenaire possible (au sens de sa liste de préférences), parmi toutes les solutions stables possibles — et la pire possible pour les femmes[2]. 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 »[4].

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é — mais non résolu — 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[2] ?

Le problème des mariages stables avec optimisation s'apparente à d'autres problèmes d'optimisation difficiles comme celui du « voyageur de commerce »[2]. 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[5].

Définition formelle du problème

On se donne deux ensembles A et B, supposés disjoints, ayant chacun n éléments. On se donne aussi, pour chaque élément de A et de B, 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 A avec ceux de B, pour qu'il n'existe pas et tels que a préfère b à l'élément qui lui est associé, et b préfère a à l'élément qui lui est associé.

Problèmes algorithmiques proches

Notes et références
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Stable marriage problem » (voir la liste des auteurs).
  1. (en) Enrico Maria Fenoaltea, Izat B. Baybusinov, Jianyang Zhao, Lei Zhou et Yi-Cheng Zhang, « The Stable Marriage Problem: An interdisciplinary review from the physicist’s perspective », Physics Reports, vol. 917,‎ , p. 1-79 (DOI 10.1016/j.physrep.2021.03.001).
  2. (en) D. Gale et L. S. Shapley, « College admissions and the stability of marriage », The American Mathematical Monthly , vol. 69, no 1,‎ , p. 9-15 (lire en ligne ).
  3. « Cédric Villani : « Ce qui a “buggé” dans APB, ce n’est pas le logiciel, mais bien l’Etat » », sur Le Monde, (consulté le ).
  4. Cour des comptes, Admission Post-Bac et accès à l'enseignement supérieur : un dispositif contesté à réformer, (lire en ligne [PDF]), p. 118.
  5. « Le prix Nobel d'économie attribué aux Américains Alvin Roth et Lloyd Shapley », sur Le Monde, (consulté le ).

Voir aussi

Articles connexes

Liens externes
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.