Voir la source de Problème des mariages stables

[[Fichier:Gale-Shapley.gif|vignette|Algorithme de Gale Shapley.]]
En [[mathématiques]], [[informatique]] et [[Économie (discipline)|économie]], le '''problème des mariages stables''' consiste à trouver, étant donné {{mvar|n}} hommes et {{mvar|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 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<ref>{{Article| langue=en| titre=The Stable Marriage Problem: An interdisciplinary review from the physicist’s perspective| auteur1=Enrico Maria Fenoaltea| auteur2=Izat B. Baybusinov| auteur3=Jianyang Zhao| auteur4=Lei Zhou| auteur5=Yi-Cheng Zhang| périodique=[[Physics Reports]]| volume=917| date=18 juin 2021| pages=1-79| doi=10.1016/j.physrep.2021.03.001| accès url=libre}}.</ref> ({{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{{Lesquelles|date=1 septembre 2023}} en [[économie (discipline)|économie]], en [[théorie des jeux]] et en [[physique statistique]]{{Référence nécessaire|date=1 septembre 2023}}.

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 {{mvar|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 ou les trouver avec certitude, juste appliquer différents algorithmes, plus ou moins performants.

== Histoire ==
Le problème des mariages stables est énoncé {{incise|et résolu ([[algorithme de Gale et Shapley]])}} pour la première fois en 1962, avec en vue le [[problème d'affectation|problème de l'affectation]] des étudiants aux diverses formations universitaires<ref name=Gale1962>{{Article| langue=en| titre=College admissions and the stability of marriage| auteur1=D. Gale| auteur2=L. S. Shapley| périodique=[[The American Mathematical Monthly ]]| volume=69| numéro=1| date=1962| pages=9-15| lire en ligne=https://www.jstor.org/stable/2312726| accès url=payant}}.</ref>. Cette même application (algorithme compris) est reprise entre 2009 et 2017 par le service [[Admission Post-Bac]] du [[Ministère de l'Enseignement supérieur (France)|ministère français de l'Enseignement supérieur]]<ref>{{lien web| url=https://www.lemonde.fr/idees/article/2017/12/06/cedric-villani-ce-qui-a-bugge-dans-apb-ce-n-est-pas-le-logiciel-mais-bien-l-etat_5225204_3232.html| site=[[Le Monde]]| date=06/12/2017 |titre=Cédric Villani : « Ce qui a “buggé” dans APB, ce n’est pas le logiciel, mais bien l’Etat »| consulté le=7 juillet 2021}}.</ref>.

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 {{incise|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<ref name=Gale1962/>. 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 »<ref>{{ouvrage| format=pdf| auteur=[[Cour des comptes (France)|Cour des comptes]]| lire en ligne=https://www.ccomptes.fr/sites/default/files/2017-10/20171019-rapport-admission-post-bac_0.pdf| titre=Admission Post-Bac et accès à l'enseignement supérieur| sous-titre=un dispositif contesté à réformer| site=ccomptes.fr| date=10/2017| passage=118}}.</ref>.

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é {{incise|mais non résolu}} par [[Gaspard Monge]] dès 1781 : disposant d'un certain nombre de [[mine (gisement)|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<ref name=Gale1962/> ?

Le problème des mariages stables avec optimisation s'apparente à d'autres problèmes d'optimisation difficiles comme [[problème du voyageur de commerce|celui du « voyageur de commerce »]]<ref name=Gale1962/>. 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 de la Banque de Suède en sciences économiques en mémoire d'Alfred Nobel|prix Nobel d'économie]] [[Prix de la Banque de Suède en sciences économiques en mémoire d'Alfred Nobel#Années 2010|2012]]<ref>{{lien web| url=https://www.lemonde.fr/economie/article/2012/10/15/nobel-les-americains-alvin-roth-et-lloyd-shapley-recompenses-pour-leurs-travaux-sur-les-marches_1775714_3234.html| titre=Le prix Nobel d'économie attribué aux Américains Alvin Roth et Lloyd Shapley| site=[[Le Monde]]| date=15 octobre 2012| consulté le=9 juillet 2021}}.</ref>.

== Définition formelle du problème ==
On se donne deux [[ensemble]]s {{mvar|A}} et {{mvar|B}}, supposés disjoints, ayant chacun {{mvar|n}} éléments. On se donne aussi, pour chaque élément de {{mvar|A}} et de {{mvar|B}}, une fonction de préférence, qui classe tous les éléments de l'autre ensemble. On cherche alors à associer de façon [[Bijection|bijective]] les éléments de {{mvar|A}} avec ceux de {{mvar|B}}, pour qu'il n'existe pas <math>a \in A</math> et <math>b \in B</math> tels que {{mvar|a}} préfère {{mvar|b}} à l'élément qui lui est associé, et {{mvar|b}} préfère {{mvar|a}} à 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]]

== Notes et références ==
{{Traduction/Référence|en|Stable marriage problem|501972818|type=note}}
{{références}}

== Voir aussi ==
=== Articles connexes ===
* [[Algorithme de Gale et Shapley]]

=== Liens externes ===
* {{Autorité}}
* {{Dictionnaires}}
* {{Bases}}

{{Portail|informatique théorique}}

[[Catégorie:Théorie des jeux]]
[[Catégorie:Combinatoire]]
[[Catégorie:Problème algorithmique|Mariage]]
[[Catégorie:Couplage (théorie des graphes)]]
[[Catégorie:Satisfaction de contraintes|Mariage]]