Ouvrir le menu principal

En mathématiques et en informatique, le problème des mariages stables consiste à trouver, étant donné n hommes et n femmes, et leurs préférences, une façon stable de les mettre en couple. Il y a instabilité lorsqu'un homme et une femme préfèrent tous deux se mettre en couple l'un avec l'autre plutôt que de rester chacun avec son conjoint respectif. Un exemple de situation instable serait que Monsieur Dupont préfère Madame Durand à Madame Dupont, et Madame Durand préfère Monsieur Dupont à Monsieur Durand.

Sommaire

Définition formelle du problèmeModifier

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 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é.

UtilisationsModifier

Le service Admission Post-Bac, permettant entre 2009 et 2017 d'affecter les lycéens de terminale à la première année des formations de l'enseignement supérieur en France, utilisait l'algorithme de Gale-Shapley[1], cité plus bas, les formations dans le rôle des prétendants et les étudiants dans celui des choisisseurs[2].

AlgorithmesModifier

Le principal algorithme pour résoudre ce problème est l'algorithme de Gale et Shapley.

Problèmes algorithmiques prochesModifier

Notes et référencesModifier

(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. « Cédric Villani : « Ce qui a “buggé” dans APB, ce n’est pas le logiciel, mais bien l’Etat » », sur lemonde.fr,
  2. Cour des comptes, Admission Post-Bac et accès à l'enseignement supérieur : un dispositif contesté à réformer, (lire en ligne [PDF]), p. 118