Que ce soit sur Netflix, sur Noovo ou sur les réseaux sociaux, le thème de la recherche de l’amour, de relations stables ou la création de couples stables sont depuis quelques années hyper populaires. Est-il possible d’utiliser un algorithme mathématique de pairages pour créer un couplage stable ? L’algorithme de Gale-Shapley permet, sans nécessairement jumeler chacun avec son premier choix, de créer méthodiquement un couplage stable, c’est-à-dire un ensemble de couples où aucune paire de couples n’a intérêt à échanger leurs partenaires. Cet algorithme simple, puissant, ne requérant aucune connaissance mathématique, ni théorèmes, ni calculs, fait partie des travaux pour lesquels Lloyd Shapley s’est mérité un prix Nobel d’économie en 2012.

Algorithme, rituel et couples stables

La version la plus simple de l’article originel [1] des mathématiciens David Gale et Lloyd Shapley (problème des mariages stables), datant de 1962 dans lequel ils décrivent à l’aide de la métaphore du mariage leur algorithme de création de couples, peut être présentée de la façon suivante.

Soit une population de \(n\) hommes et de \(n\) femmes dans laquelle chaque personne a des préférences de choix mutuelles de la personne de sexe opposé avec qui elle aimerait finir en couple. Chaque personne des deux groupes crée un classement de toutes les personnes du groupe opposé ordonné sans ex aequo selon ses préférences. Le problème est résolu lorsque chaque personne est jumelée avec une personne du groupe opposé et que cet ensemble de couples est stable, c’est-à-dire qu’il n’y a aucune situation où une paire de couples préféreraient échanger leurs partenaires.

Ainsi, le problème des mariages stables a pour but de jumeler les hommes et les femmes selon les deux règles suivantes :

Règle 1

Chaque homme doit être en couple seulement avec une femme et vice versa ;

Règle 2

Chaque ensemble de couples doit être stable, c’est-à-dire qu’il ne contient pas deux couples \(Aa\) et \(Bb\) tels que \(A\) préfère \(b\) à \(a\), et \(b\) préfère \(A\) à \(B\).

Exemple 1
(Angelina, brad et cie)
Soit les listes des préférences des personnes du groupe opposé ordonné sans ex aequo de deux femmes Angelina et Barbara et de deux hommes brad et alexander notées avec le symbole ≻ :

\[\left\{ \begin{array} {l} a: A \succ B \\b: A \succ B \end{array} \right. \text { et } \left\{ \begin{array} {l} A: b \succ a \\B: b \succ a \end{array} \right.\]

Les notations \(b:A \succ B\) et \(A:b \succ a\) nous informent que brad préfère Angelina à Barbara et qu’Angelina préfère brad à alexander. Ici, nous remarquons que les deux hommes préfèrent Angelina et que les deux femmes préfèrent brad. Pour former des couples stables, nous utiliserons l’algorithme de Gale-Shapley sous forme de rondes d’invitations.

À chaque ronde, les demandes des hommes (prétendants) sont notées par le symbole \(\mapsto\). On mettra en rouge les demandes acceptées par les femmes et en noir les demandes rejetées par celles-ci (Voir le tableau suivant). À la ronde suivante, le prétendant débouté (en noir) est redevenu célibataire et fait une demande à la femme suivante sur sa liste de préférences.

En première ronde, les hommes font une demande à leur premier choix. Comme \(a\) et \(b\) préfèrent \(A\), ils ont choisi \(A\), alors \(A\) doit faire un choix. Elle accepte la demande de \(b\), car \(b\) est plus haut sur la liste de \(A\) que \(a\). Angelina doit donc également rejeter la demande de \(a\). Ainsi, \(a\) devient un prétendant débouté, biffe sur sa liste le prénom de \(A\) et fera une demande différente à la ronde suivante. À la deuxième ronde, \(b\) est encore avec \(A\) (fiancés) et \(a\), qui est redevenu célibataire à la suite de sa dernière demande rejetée, fait une demande à \(B\) qui l’accepte. Ici, les rondes se terminent, car chaque femme a exactement un prétendant. On remarque qu’Alexander a épuisé sa liste de prénoms.

Le couplage \(Ba\) et \(Ab\) est stable, car aucun des couples \(Ba\) et \(Ab\) ne va se séparer pour en reformer un autre plus optimal.

Le problème des mariages stables de Gale et Shapley [1] garantit curieusement qu’il est possible de trouver un couplage stable entre \(n\) hommes et \(n\) femmes, c’est-à-dire un ensemble de couples satisfaisant à la Règle 2.

Le rituel

Cet algorithme de création d’un couplage stable peut être décrit comme un rituel qui se déroule par étapes sur plusieurs périodes, disons des jours ou des rondes. Le premier jour, chaque homme a sa liste complète numérotée en ordre de préférences, sans ex aequo, de toutes les femmes, et de même pour chaque femme. Ensuite, les événements suivants se produisent quotidiennement :

Le matin :

Chaque homme fait une demande à la femme qui est première sur sa liste actuelle. Lorsqu’un homme fait une demande à une femme, on dit qu’il est son prétendant.

L’après-midi :
Chaque femme répond « Peut-être » au prétendant qu’elle préfère et décline l’invitation des autres. En particulier, si ce jour-là elle reçoit une nouvelle demande meilleure que celle d’un jour précédent, elle oublie l’ancienne demande. L’homme qui a reçu une demande « Peut-être » est considéré fiancé.

Le soir :
Chaque homme dont la demande a été rejetée biffe de sa liste le nom de la femme qui a rejeté sa demande. Il redevient célibataire. Chaque femme termine la journée avec au plus un prétendant.

Remarque :
Le matin suivant, un homme célibataire descend dans sa liste pour faire une nouvelle demande. Si au contraire, il est fiancé, il maintient son offre de la veille, puisqu’elle était faite à la préférée de sa liste de la veille.

Condition de terminaison :
Quand arrive un jour où chaque femme a exactement un prétendant, le rituel se termine avec chaque femme se jumelant avec son prétendant.

Remarques :

• Il ne reste plus de célibataire à ce stade-ci puisqu’il y a autant de femmes que d’hommes. En effet, une femme qui a été fiancée le demeure à jamais. Donc, le nombre de femmes fiancées ne diminue jamais. De plus, chaque soir, chaque femme est fiancée à au plus un homme.Si la liste d’un célibataire était vide, cela signifierait qu’il a été rejeté par toutes les femmes. Et donc qu’elles sont toutes fiancées à des hommes différents. Mais il y a \(n\) femmes et \((n – 1)\) autres hommes en dehors du célibataire. Contradiction ;
• Si l’on continuait l’algorithme, on générerait la même solution d’une journée à l’autre. La solution générée est un point fixe de l’algorithme;
• Au fur et à mesure que l’algorithme avance, les femmes obtiennent de meilleurs partenaires, alors que c’est le contraire pour les hommes.

Appliquons l’algorithme précédent à une autre situation concrète :

Exemple 2
Quatre couples stables en quatre rondes
Soit les lettres \(a, b, c\) et \(d\) représentant quatre hommes et \(A, B, C\) et \(D\) quatre femmes. Nous notons les préférences de chaque personne avec le symbole ≻ :

\[\left\{ \begin{array} {l} a: A \succ B \succ D \succ C \\b: B \succ A \succ D \succ C \\ c: C \succ B \succ D \succ A \\ d: B \succ A \succ C \succ D \end{array} \right. \text { et } \left\{ \begin{array} {l} A: c \succ b \succ d \succ a \\B: b \succ a \succ c \succ d \\ C: b \succ d \succ a \succ c \\D: c \succ a \succ d \succ b \end{array} \right.\]

En utilisant la même notation qu’à l’Exemple 1, l’application de l’algorithme de Gale-Shapley mène aux cinq rondes suivantes :

Dans l’Exemple 2, les couples \(Da, Bb, Cc\) et \(Ad\) forment un couplage stable selon Gale-Shapley.

Propriétés de l’algorithme

• Remarquons que l’algorithme n’est pas symétrique. Les hommes font des demandes en choisissant parmi toutes les femmes de leur liste ordonnée, alors que les femmes n’ont qu’un choix restreint à chaque étape, dont elles conservent la meilleure demande. Cet algorithme est à l’avantage des demandeurs (hommes). En fait, il est même optimal pour les demandeurs ce qui les incite à être sincères dans leurs choix.
• Pour les femmes, l’algorithme de Gale-Shapley donne le pire résultat parmi tous les couplages stables.
• Il existe aussi un algorithme dual où les femmes font les demandes. Dans ce cas, le rituel se termine lorsque chaque homme est jumelé à une prétendante. Dans l’Exemple 2 précédent, si les femmes font les demandes, nous pouvons remarquer que les couples \(dA, bB, aC\) et \(cD\) obtenus dans les rondes suivantes forment un couplage stable du dual.

Exemple 3
Couplages stables identiques

Nous remarquons que dans l’Exemple 2, si nous changeons les préférences de \(b\) pour

\[ b : C \succ A \succ D \succ B,\]

alors l’algorithme génère les mêmes couples stables \(Ba, Cb, Dc\) et \(Ad\) peu importe que ce soient les hommes (en cinq rondes) ou les femmes (en trois rondes) qui font les demandes.

Cas distinct

La création de couples homosexuels est un cas distinct de l’algorithme de Gale-Shapley. Dans un problème de création de couples de même sexe, on dit que l’ensemble des couples est stable s’il n’existe pas deux partenaires \(X\) et \(Y\) qui se préfèrent mutuellement plutôt que leur partenaire dans des couples \(XU\) et \(YV\). Dans ce cas, un ensemble stable de couples n’est pas toujours possible.

Soit les préférences d’Alex, Bobby, Kin et Taylor, quatre personnes de même sexe notées avec le symbole ≻ :

\[\left\{ \begin{array} {l} A: B \succ T \succ K \\B: T \succ A \succ K \\ K: A \succ T \succ B \\ T: A \succ B \succ K \end{array} \right.\]

Nous remarquons qu’il y a un triangle amoureux entre Alex, Bobby et Taylor (préférence circulaire). Nous remarquons également que Kin est le dernier choix des trois autres personnes. Supposons que Kin soit en couple avec Alex. On a donc l’ensemble de couples \(KA\) et \(BT\). Mais \(A\) préfère \(B\) et \(T\) à \(K\). D’autre part, \(A\) est le premier choix de \(T\). Donc, l’ensemble de couples \(KA\) et \(BT\) n’est pas stable, puisque \(A\) et \(T\) se préfèrent à leur partenaire. De même si Kin est en couple avec Bobby ou avec Taylor. Dans ce cas, il n’y a pas d’ensemble de couples stables possibles.

De la théorie à la pratique !

La grande simplicité de la théorie du problème des mariages stables de Gale et Shapley et son ingénieux algorithme permettent de reprendre le modèle, de l’appliquer méthodiquement, parfois dans une version modifiée, dans plusieurs problèmes d’association et dans une variété de domaines dont voici quelques-uns :

1. Dans leur article originel, Gale et Shapley [1] traitent également du modèle plus général des admissions dans les universités ou collèges. Le modèle est identique à celui du mariage à la différence près que chaque université ou collège \(C_i\) peut désormais être jumelé à \(q_i \geq 1\) étudiant, où \(q_i\) représente la quantité d’accueil de \(C_i\). Dans cette version originelle qui favorise les candidats, la seule différence notable est la prise en compte de la capacité d’accueil de chaque institution dans le choix de garder temporairement ou de rejeter une candidature. Ainsi, à une étape donnée si la capacité d’accueil est dépassée d’une unité, la moins bonne candidature est rejetée.
2. En 1984, Alvin Roth [2] a publié une étude sur le recrutement des internes en médecine aux États-Unis, laquelle montrait la pertinence et les limites du modèle proposé par Gale et Shapley. Durant les années 80, de plus en plus de couples d’internes cherchaient des places d’internat dans le même hôpital. Le mécanisme en vigueur ne permettait pas de chercher des places « en couple ». Ainsi, Roth et certains de ses collègues ont mis au point, pour l’Association américaine de médecine et pour faire face au problème de la compétition entre les hôpitaux, une méthode de jumelage de couples d’internes et d’hôpitaux. Cette méthode pas nécessairement parfaite, mais performante appliquait la méthode des mariages stables sous une nouvelle configuration retrouvant ainsi les propriétés du modèle originel lorsqu’il y a un grand nombre d’internes.
3. En 2003, Abdulkadiroglu et Sönmez ont démontré que l’algorithme de Gale-Shapley pouvait aider à solutionner le problème de la répartition des enfants dans les écoles primaires et secondaires lorsque l’on donne aux parents la possibilité d’exprimer leurs choix sur la future école de leur enfant. Au public, seuls les parents ont des préférences. Les écoles publiques n’ont qu’un ordre de priorité sur les élèves qui habituellement ne dépend que de facteurs divers (proximité avec le lieu de résidence, présence de frères ou soeurs dans l’école, etc.). Ainsi, dans ces écoles, le problème des pairages consiste essentiellement en un problème d’élicitation des préférences des parents. Après avoir analysé le mécanisme utilisé par les écoles de Boston, les chercheurs ont convaincu les villes de Boston et de New York d’utiliser une méthode dérivée de l’algorithme de Gale-Shapley déclenchant ainsi une vague de réformes à travers les États-Unis. La littérature sur la répartition scolaire constitue encore aujourd’hui un domaine actif de la théorie du pairage.
4. Parallèlement à l’étude du problème de la répartition des enfants dans les écoles primaires et secondaires énoncée précédemment, Alvin Roth et ses collaborateurs Sönmez et Ünver ont développé à l’aide d’une version modifiée de l’algorithme de Gale-Shapley, un processus d’échange et de transplantation de rein. Ce processus d’échange permet à des patients atteints d’insuffisance rénale en attente d’une transplantation de trouver des donneurs compatibles. De plus, grâce à ce processus, les donneurs incompatibles avec leur receveur initial sont jumelés avec d’autres patients en attente de transplantation créant ainsi une chaîne d’échanges de reins. L’algorithme développé permet de maximiser le nombre de patients recevant une transplantation rénale compatible tout en minimisant le temps d’attente pour une transplantation.

En conclusion

L’article de Gale et Shapley écrit en 1962 sur le problème des mariages stables est considéré comme un modèle de référence et l’un des articles fondateurs de la théorie du pairage. Il est, de façon étonnante, très court, ne contient aucune équation mathématique et il est d’une très grande simplicité. La pertinence de cet ingénieux algorithme a eu un rôle déterminant et a un impact significatif sur la recherche en économie, en mathématiques appliquées et en théorie des jeux. L’auteur Lloyd Shapley et son collègue Alvin Roth ont reçu le prix Nobel d’économie en 2012 pour leur travail sur la théorie du pairage et pour leur contribution à l’économie expérimentale. La venue d’ordinateurs a rendu l’algorithme de Gale-Shapley encore plus puissant et plus rapide à exécuter même s’il y a un grand nombre de personnes. L’algorithme de Gale-Shapley garantit qu’il est possible de résoudre un problème des mariages stables et que tous les couples formés sont stables, c’est-à-dire qu’il n’y a pas de « couple insatisfait ».

Pour en s\(\alpha\)voir plus !

• Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
• Knuth, D. E. (1976). Mariages stables et leurs relations avec d’autres problèmes combinatoires. Les Presses de l’Université de Montréal, 106, ISBN 978-2-7606-0529-9.
• Voici un lien intéressant d’une vidéo sur l’intégration des lycéens français à l’enseignement supérieur (Parcoursup) et sur l’algorithme de Gale-Shapley : https://scienceetonnante.com/2020/01/09/parcoursup/.

PDF