Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème des mariages stables
Résumé
vignette|Algorithme de Gale Shapley.
En mathématiques, informatique et économie, le problème des mariages stables consiste à trouver, étant donné n hommes et 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 (Dupont préfère à , et préfère Dupont à 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 ou les trouver avec certitude, juste appliquer différents algorithmes, plus ou moins performants.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.