Problème des mariages stables

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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.

Définition formelle du problème[modifier | modifier le code]

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

Utilisations[modifier | modifier le code]

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

Algorithmes[modifier | modifier le code]

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

Problèmes algorithmiques proches[modifier | modifier le code]

Notes et références[modifier | modifier le code]

(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