In bed with Gale-Shapley

Le temps passe vite, je n’ai pas écrit depuis décembre. Pour me remettre en selle, j’ai écrit un article plus court que d’habitude qui parle de mathématiques et, aussi, de féminisme. Car oui, nous allons faire de l’algorithmique de genre (avouez que ça claque). Plus exactement, nous allons parler de l’algorithme de Gale-Shapley, ingénieuse solution au problème dit des « mariages stables ». 

Si vous avez suivi les débats autour de la réforme de l’enseignement supérieur (#ParcoursSup), vous avez peut-être entendu parler de cet algorithme : c’est celui qui était utilisé par le logiciel APB (pour décider à quelle fac aurait droit chaque bachelier), et qui est abandonné par la nouvelle réforme. Un choix très critiquable, et très critiqué, principalement parce qu’il va transformer une plateforme injuste en usine à gaz injuste (je vous conseille notamment l’article de Zeste de Savoirs à ce sujet). Parmi les opposants à la réforme, nombreux relaient de telles critiques, en précisant que, personnellement, ils ne comprenaient pas bien les questions algorithmiques qu’il y avait derrière. C’est bien dommage, car ce sont des questions plutôt simples, en réalité assez ludiques, et qui, en plus, font partie des rares questions algorithmiques intéressantes à connaître d’un point de vue féministe.

Assez de raisons pour que je m’empare du sujet et vous présente un petit peu ce qu’il y a à savoir sur l’algorithme de Gale-Shapley, et de manière générale ce problème de mariages stables. On ne parlera pas ici de ce qui était effectivement fait dans la plateforme APB, ni de ce qui sera fait par ParcoursSup, mais des mathématiques qui se cachent derrière. Et dans la bonne humeur. Mais trèves de bavardages, Gale-Shapley, nous voici !

C’est quoi le problème ?

Prenons un certain nombre d’hommes et autant de femmes. Nous cherchons à créer des « mariages » hétérosexuels et monogames, c’est-à-dire des paires homme-femme telles que chaque personne soit dans une et une seule paire. L’on suppose que chaque personne a des préférences quant à son futur conjoint, et l’on représente ces préférences par une liste ordonnée : chaque homme a fait une liste de toutes les femmes, de la première à la dernière, et chaque femme a fait de même pour les hommes.

Bien évidemment, il ne sera pas possible de faire plaisir à tout le monde, et d’apparier chacun avec son premier choix, mais le but, c’est de trouver un moyen de faire au mieux. Qu’est-ce que ça veut dire, « faire au mieux » ?  Eh bien, nous allons poser deux critères :

• Le premier, qu’on va appeler optimalité, c’est le fait qu’il n’y ait pas d’autre solution strictement meilleure, c’est-à-dire qu’il n’y ait pas d’autre solution dans laquelle chacun et chacune se retrouverait avec de « meilleurs » partenaires par rapport à ses propres critères. Évidemment, on doit composer avec des volontés différentes, mais ce serait quand même la preuve que notre solution est mauvaise s’il avait une solution qui aurait mieux convenu à tout le monde (la méthode utilisée par ParcoursSup, par exemple, est sous-optimale, c’est-à-dire qu’elle ne garantit pas que la solution obtenue respecte ce critère de base).
• L’autre critère, c’est la stabilité. Lorsqu’un homme et une femme se préfèrent mutuellement à leurs conjoints respectifs, ils auraient alors intérêt à les quitter pour convoler ensemble : c’est ce qu’on appelle une configuration instable. On dit qu’une solution est « stable », fort logiquement, quand il n’y a aucune instabilité. Ce critère est strictement plus fort que le premier : si un appariement est stable, alors il sera optimal, mais tous les appariement optimaux ne sont pas stables (vous pouvez vous amuser à vérifier ça si vous voulez).

Voilà donc le problème des « mariages stables ». Comme on le voit, quand on parle de problème en algorithmique, ce n’est pas comme en cours de mathématiques au collège (ou l’on cherche à répondre à une question), c’est pour désigner un ensemble de situations similaires pour laquelle on cherche une procédure standardisée (un algorithme, quoi) que l’on pourra appliquer à n’importe quelle instance de ce problème (c’est-à-dire, à n’importe quel groupes d’hommes et de femmes et n’importe quelles listes de préférences). Il n’y a donc pas une solution à ce problème mais toute une ribambelle, chacune avec ses avantages et ses inconvénients.

Quel rapport avec ParcoursSup, me direz-vous ? Eh bien, cette question de mariages entre hommes et femmes n’est qu’une métaphore, on peut en pratique vouloir « marier » n’importe quoi avec n’importe quoi. Par exemple, des étudiants et des places en fac : chaque étudiant fournit une liste de préférence parmi les facs, et, pour chaque place, la fac fournit une liste de préférences pour les étudiants. C’est le même problème, mathématiquement que d’apparier des fonctionnaires avec des postes disponibles, ou des donneurs et de receveurs pour des transplantations de rein. Mais l’application aux places en universités, ainsi que l’analogie des mariages, font partie de l’histoire de ce problème, et ce, depuis le tout début.

Le premier article de mathématiques paru sur le sujet, écrit en 1962 par David Gayle et Lloyd Stowell Shapley (futur prix Nobel d’économie), s’intitulait « College Admissions and the Stability of Marriage » (Amer. Math. Month., vol. 69, 1962, p. 9-14). Et c’est de cet article dont nous allons parler ici.

La ronde des prétendants

Si Gayle et Shapley ont utilisé une analogie avec le mariage, ce n’est pas seulement parce que le problème s’y prête, mais aussi que la solution qu’ils proposent colle également avec cette image : un algorithme de la forme « proposer/disposer », inspiré du fonctionnement genré de la séduction dans nos sociétés (mais vu à travers le prisme un peu perché d’un mathématicien). Le fonctionnement de l’algorithme est le suivant :

• Au début, personne n’est marié avec personne. Un des groupes (on va dire les hommes) est chargé de « proposer », l’autre groupe (les femmes, donc) de « disposer ». Notons que c’est l’algorithme qui va faire jouer aux hommes et aux femmes des rôles différents. Dans la donnée du problème, les deux groupes sont identiques.
• Les femmes obéissent à une instruction simple, qui se déclenche quand un homme leur fait une proposition de mariage. Si elles sont célibataires, elles acceptent. Si elles ne le sont pas, elles comparent le prétendant à leur actuel mari et choisissent le plus haut dans leur liste de préférence.
• Les hommes, un à un, s’avancent et se proposent à la femme la plus élevée dans leur liste.
  • S’ils sont acceptés, ils s’arrêtent là.
  • En cas de refus, ils passent à la suivante, jusqu’à ce que l’une accepte (il y aura toujours une célibataire pour accepter, puisque les deux groupes sont de même taille).
  • Si celle qui accepte était déjà mariée, son précédent époux, redevenu célibataire, reprend sa prospection à l’endroit de sa liste où il en était.

Cet algorithme possède un certain nombre de propriétés intéressantes qui ont fait sa célébrité. Elles ne sont pas très difficiles à démontrer (vous pouvez même essayer vous-mêmes, ou, si vous êtes justes curieux, aller les chercher dans le cours de théorie des jeux de Tim Roughgarden pour Standford.

Propriétés 1-3. Cet algorithme :

• se termine toujours. On ne rentre jamais dans une boucle où les personnes changent de fiancé à l’infini (c’est quand même le moins qu’on puisse lui demander).
• est déterministe. Il n’y a pas de hasard dans le résultat cet algorithme : peu importe l’ordre dans lequel on demande aux hommes de s’avancer, le résultat sera toujours le même.
• donne toujours des mariages stables (il est donc optimal, puisque l’un implique l’autre).

Mission accomplie, donc. Nos hommes et nos femmes sont bien mariés, nos étudiants sont bien répartis dans les universités. Mais ce n’est pas fini : cet algorithme a encore plein de propriétés amusantes. Parce que, grâce à Gayle et Shapley, nous avons trouvé une solution stable. Mais des solutions stables, il y en a possiblement plusieurs. Quelles sont les propriétés de la solution ainsi obtenue par rapport aux autres solutions possibles ? Et c’est là que, pour les féministes que j’ai appâtées jusqu’ici, ça devient intéressant.

 Algorithmes et conséquences

Si vous voulez voir une explication en vidéo de ce problème, vous pouvez aller regarder celle de Science4All. Au passage, vous pourrez noter que, dans les commentaires les plus appréciés, on y trouve celui d’un certain Flutterwondershy Yay, courageux internaute qui ose poser la question qui dérange :

Oui, tiens. Si nous sommes dans une société patriarcale, pourquoi ce sont les femmes qui choisissent ? Ne serait-ce pas la preuve de la domination féminine ? Si quelqu’un peut sincèrement se poser la question, c’est que dans cet algorithme, la part de choix qui revient aux femmes est effectivement plus visible. Les hommes aussi disposent d’une capacité de choix, puisqu’ils décident dans quel ordre ils vont aller courtiser leurs prétendantes, mais ils n’ont, à aucun moment, à rejetter qui que ce soit. Pour autant, est-ce que cet algorithme est avantageux pour les femmes ? Pas du tout, en réalité, c’est tout l’inverse. Mais pour l’expliquer, il faut faire un peu plus de maths.

Il nous faut quelques autres définitions. Supposons qu’Adam et Eve aient très envie de finir leur vie ensemble : Adam a mis Eve en haut de sa liste et Eve a mis Adam en haut de la sienne. Dans ce cas de figure, toute solution stable doit marier Adam et Eve ensemble. C’est bien dommage pour Gérard, qui lui aussi a mis Eve en premier : elle lui est inaccessible. Quelque soit la méthode employée pour organiser ces mariages (de façon stable), il ne finira pas avec Eve. Nous disons que Gérard n’est pas un prétendant crédible pour Eve (et que Eve n’est pas crédible pour Gérard). De manière générale, pour un membre d’un groupe donné, un prétendant crédible est un membre de l’autre groupe avec lequel il est possible de se marier (c’est-à-dire, tel qu’il existe une solution stable dans laquelle les deux sont mariés). 

Pour un participant donné, prenons son prétendant crédible le plus haut dans la liste de préférence, le plus haut qu’il puisse raisonnablement viser, donc. On l’appelle le prétendant idéal. A l’inverse, le pire prétendant sera le prétendant crédible le plus bas dans la liste de préférence (ce qui peut être quand même très haut : Adam est le seul prétendant crédible d’Eve, il est donc son prétendant idéal et son pire prétendant en même temps).

On peut maintenant présenter une nouvelle propriété de l’algorithme de Gale-Shapley :

Propriété 4.  Les hommes sont retrouvent tous mariés avec leur prétendante idéale, et les femmes sont toutes mariées avec leur pire prétendant. 

Oui, vous avez bien lu : cette solution est la plus avantageuse possible pour les hommes, et la plus désavantageuse possible pour les femmes. La nouvelle est un peu rude, donc on va prendre un exemple pour s’en convaincre. Imaginons que tous les hommes aient mis des femmes différentes en haut de leur liste. Ils se proposeront donc à elles en premier, elles accepteront et aucune ne recevra d’autres propositions. Elles se verront donc toutes imposer leur prétendant, sans avoir pu faire aucun choix, et pourrons même tout à fait se retrouver chacune avec le mec qu’elles avaient mis en dernier dans leur liste. Ce ne serait vraiment pas de chance, mais c’est possible.

Au final, c’est compréhensible : les femmes ont dans cet algorithme, en réalité, moins de choix à faire que les hommes. Elles n’ont de marge de manœuvre que pour trancher les conflits entre eux. Leur seul pouvoir est un pouvoir d’arbitrage. Bref, le vieux principe selon lequel « les hommes proposent, les femmes disposent » est, même dans la pure théorie, avantageux pour les hommes et désavantageux pour les femmes quant au résultat qu’elles obtiennent, et plus que n’importe quel autre mode stable de fonctionnement (eh oui, ça calme, désolé, Flutterwondershy Yay).

Mais ce n’est pas fini ! Ajoutons maintenant à notre algorithme la possibilité pour les participants de tricher, c’est-à-dire de suivre un ordre différent de leur vrai ordre de préférence. On appelle « tricher », pour un homme, le fait de se proposer aux femmes dans un ordre différent de son ordre réel, et pour une femme, de refuser un prétendant en étant célibataire, ou de choisir, parmi deux hommes qui se proposent, le plus bas dans sa liste de préférence plutôt que le plus haut. Qu’observe t’on ?

Propriété 5. Il peut être avantageux pour une femme de tricher.

Prenons un exemple : Albert a mis Alice en premier dans sa liste, et Cécile en deuxième. Il s’est présenté a Alice, qui a accepté. Voici maintenant Bilal, qui a mis lui aussi Alice en premier et Cécile en deuxième. Il se présente donc à Alice. Alice préfère Bilal a Albert, elle devrait donc rejeter Albert et garder Bilal.

Seulement, elle a en réalité des vues sur Clément, qui est vraiment très beau, drôle, et intelligent. Clément, lui, a mis Cécile en premier et Alice en deuxième. Quand à Cécile, ses préférences sont l’ordre suivant : Bilal > Clément > Albert. Dans cette situation, si Alice rejette Albert, Clément va aller se proposer à Cécile et se mettre avec elle. Mais, si Alice triche, qu’elle garde Albert et rejette Bilal, celui-ci ira chercher son réconfort chez Cécile, qui, du coup, rejettera Clément quand celui-ci s’avancera. Une fois rejetté, Clément viendra donc voir Alice, qui obtient donc l’élu de son coeur au prix d’intrigues et de manigances. 

Vous n’avez pas compris ? Ce n’est pas grave, retenez juste que cet algorithme incite les femmes à manigancer si elles veulent espérer avoir mieux que leur pire possibilité. Et les hommes, me direz-vous ?

Propriété 6. Il n’est jamais avantageux pour un homme de tricher, même quand les femmes trichent.

Les hommes n’ont pas besoin de tout ça : ils peuvent courtiser sans arrière-pensée l’élue de leur coeur. Qu’ils n’aient pas besoin de tricher quand les femmes ne trichent pas est évident (puisqu’ils se retrouvent alors avec leur prétendante idéale), mais même quand les femmes manipulent leurs faveurs, ils n’ont toujours aucun intérêt à faire preuve de fourberie ou de malice.

Prenez Bilal, de l’exemple précédent, par exemple : on a vu que s’il respecte son ordre et se présente à Alice en premier, il finira au mieux avec elle (si Alice ne triche pas), au pire avec Cécile (si Alice triche). Mais s’il essaye d’être sournois et se présente à Cécile en premier, comme il est son premier choix, Cécile va accepter et ne pas le laisser filer ensuite. Ce n’est pas mieux pour lui. On peut observer la même chose pour Clément. Bref, la meilleure stratégie pour un homme est toujours la même : proposer aux femmes dans l’ordre exact de ses préférences, sans se poser de questions, mais en espérant que les femmes soient sincères dans leurs réponses. Car, dans cet algorithme inégalitaire, l’honnêteté des femmes se fait à leur détriment et à l’avantage des hommes.

---

On m’a posé la question de savoir qui, dans APB, propose et dispose : l’algorithme est-il à l’avantage des étudiants ou des universités ? Réponse de Hervé Mignot : à l’avantage des universités. On m’a également demandé quelle solution algorithmique je préconisais dans la situation, et personnellement je suis opposé à la sélection à l’entrée de l’université, y mettre fin règlerait le problème de manière plutôt gordienne.

Pour celleux que le problème intéresse d’un point de vue mathématique, je vous recommande le livre « Mariage stables et leur relation avec d’autres problèmes combinatoires », écrit par le légendaire Donald E. Knuth, oldies but goodies. La version française est disponible en pdf.