L’algorithme de Gale-Shapley

T’es-tu déjà retrouvé dans la situation où ton professeur demande à chacun une liste de préférences pour former des binômes en classe ? Ceci est un exemple du problème des mariages stables dont Gale et Shapley ont démontré la solution en 1962. Leur algorithme est aujourd’hui très répandu, nous allons t’expliquer comment ça marche et pourquoi dans notre vidéo.

Dans le cadre du projet d’année de BA3, nous nous sommes intéressés à l’algorithme de Gale-Shapley. Cet algorithme de couplage a été conçu en 1962 et tient son nom de ses deux concepteurs: David Gale et Lloyd Shapley. Ces deux mathématiciens étaient convaincus qu’il était possible d’imaginer une solution pour résoudre le problème des mariages stables.
Le problème des mariages stables s’agit de la situation où deux groupes, ici, des hommes et des femmes, cherchent à former des couples. Chaque membre des deux groupes possède un classement des membres du groupe opposé ordonné selon ses préférences pour son.sa partenaire idéal.e. Le problème est résolu si tout le monde est associé avec une personne du groupe opposé et que cet arrangement est “stable”. C’est-à-dire qu’il n’y a aucune situation où deux couples préféreraient échanger de partenaire entre eux.
L’algorithme fonctionne par étapes :
A la première étape, chaque homme fait une demande à la femme qu’il préfère. Si l’élue n’a pas reçu de meilleure proposition selon ses préférences, ou si elle est encore libre, elle accepte temporairement d’être associée à cet homme. Sinon elle décline son invitation. Si la nouvelle proposition est meilleure que la précédente, elle oublie l’ancienne.
A chaque étape suivante, les hommes qui ont été rejetés sont à nouveau libres. Ils répètent l’opération en faisant une demande à la femme qu’ils préfèrent mais en excluant celles qui ont déjà refusé leur demande précédente.
Gale et Shapley garantissent que, lorsque tous les couples sont formés à la fin de l’opération, ceux-ci sont stables. Ce procédé peut être repris et s’appliquer pareillement à n’importe quelle situation pour un problème d’association.
Pour notre part, nous avons imaginé la situation d’un refuge animal cherchant à faire adopter leurs animaux de manière à garantir une compatibilité optimale entre l’animal et sa nouvelle famille. Pour ce faire, nous avons attribué des critères tels que le budget, le besoin d’espace et d’affection, etc… à chaque famille et à chaque animal. Un ordre de préférence est ensuite construit sur base de ces critères et l’algorithme de Gale-Shapley s’occupe d’associer les familles à leur animal idéal.
Dans notre vidéo, nous commençons par une brève introduction sur l’algorithme et son histoire. Ensuite, nous décrivons l’algorithme plus en détail en donnant des exemples et en expliquant son fonctionnement plus profondément. Enfin, nous présentons l’application que nous avons développée afin d’illustrer cet algorithme.