Algorithme de Gale et Shapley

Carte Rare · n° 56016

En informatique, l'algorithme de Gale et Shapley est un algorithme qui résout le problème des mariages stables. Il est nommé d'après ses inventeurs David Gale et Lloyd Shapley tous deux mathématiciens et économistes. Dans ce problème, il y a un même nombre d'hommes et de femmes. Chaque homme a des préférences sur les femmes : chaque femme a des préférences sur les hommes. L'objectif est de marier hommes et femmes de façon stable, c'est-à-dire sans qu'il y ait un homme et une femme qui préféreraient quitter leurs partenaires pour se mettre ensemble. Le principe de l'algorithme de Gale et Shapley est le suivant : chaque homme fait des propositions en commençant par la femme qu'il préfère ; les femmes, elles, disposent en fonction de leurs propres préférences.

Lire sur Wikipédia