problème des mariages stables

algorithme de Gale-Shapley

COMBINATOIRE
INFORMATIQUE

Proposé en 1962 par David Gale et Lloyd Shapley, le problème des mariages stables est le suivant : étant donnés n hommes et n femmes dont chacun a donné une liste de préférence des personnes de l’autre sexe (sans égalité, liste exhaustive), il s’agit de trouver comment les mettre en couples (mariages) de façon stable.
Ici « stable » signifie qu’on ne peut pas avoir de couples (a α) et (b β) où a préfère β à α et où β préfère a à b.

Gale et Shapley ont proposé un algorithme qui répond à la question.
L’algorithme optimal pour les hommes est organisé ainsi : à chaque étape chaque homme fait une proposition à la femme qu’il préfère (même si elle est déjà « mariée »). Les femmes choisissent parmi les propositions qui leur sont faites (même déjà « mariées »). On recommence jusqu’à ce que tout le monde soit marié.
Il y a un algorithme dual, optimal pour les femmes.

Il y a des nombreuses variantes et applications. Quelques exemples : les compagnons de chambre (mariages unisexes), les étudiants dans les universités (femmes polyandres : on remplace les hommes par des étudiants et les femmes par des universités), etc.

Suivant les ensembles considérés et le critère à minimiser, il y a ou non des algorithmes résolvant la question.