Gale-Shapley en milonga : stable ne veut pas dire équitable
L’algorithme qui a valu le prix Nobel 2012 garantit qu’aucun couple ne quittera la piste ensemble. Il ne garantit à personne de danser. Entre ces deux promesses, l’écart est plus large qu’il n’y paraît.
Une milonga est une soirée de tango argentin : une salle, des disques ou un orchestre, et des gens venus danser avec des inconnus. La soirée s’y découpe en tandas : trois ou quatre morceaux avec la même personne, puis une coupure, et tout le monde se rassoit. Une soirée de quatre heures en compte une vingtaine, soit autant d’occasions de danser ou de rester assis.
À la fin, certains ont dansé presque tout et d’autres presque rien. On l’attribue au niveau, à la timidité, au hasard des regards. Ces explications sont plausibles et ce texte ne les écarte pas. Mais une salle où chacun classe les autres est aussi un marché, et il existe une théorie de ces marchés-là : un article de 1962, un prix Nobel en 2012, et des affectations qui tournent aujourd’hui sur des dizaines de milliers de personnes. Reste à savoir ce qu’elle promet sur une soirée pareille, et ce qu’elle ne promet pas.
Le détour n’est pas de moi. Loren Shure a publié en 2020, sur le blog de MathWorks, un billet sur l’appariement stable qui part précisément d’un défi lancé lors d’une milonga. Son code enchaîne déjà les tandas en interdisant de reprendre le même partenaire, et traite les effectifs inégaux d’une soirée de danse. Il laisse explicitement de côté trois choses : l’appariement à l’intérieur d’un camp, les listes incomplètes et les ex æquo. Ce texte reprend les deux premières, et transforme au passage ses règles fermes en proportions, parce qu’une salle n’est jamais tout entière du même avis.
David Gale et Lloyd Shapley publient en 1962 un article au titre trompeusement scolaire, « College Admissions and the Stability of Marriage ». La lecture suivie ici est celle qu’en donne la mathématicienne Emily Riehl dans deux vidéos de Numberphile. Le problème posé est le suivant : étant donné deux groupes dont chaque membre classe les membres de l’autre, peut-on toujours former des couples tels que personne ne s’enfuie ? L’instabilité y reçoit une définition exacte, dont dépend tout l’énoncé : deux personnes qui se préfèrent l’une l’autre au partenaire qui leur a été attribué. Rien d’autre ne compte comme instabilité.
Il y a instabilité si et seulement si deux personnes se préfèrent mutuellement au conjoint qu’on leur a attribué.
La démonstration est constructive, ce qui est la partie utile. L’algorithme se raconte jour par jour. Le premier jour, chaque personne du côté qui invite se tourne vers son premier choix. Ceux qui reçoivent plusieurs propositions gardent la meilleure et refusent le reste ; les engagements sont provisoires. Le deuxième jour, chaque personne refusée se tourne vers son choix suivant, qu’il soit libre ou non, et ceux qui reçoivent rompent dès qu’il leur vient mieux. On recommence jusqu’à ce que plus personne ne soit refusé. L’ensemble tient en une boucle.
On attend au bord de la piste. Une invitation traverse la salle ; qui en reçoit plusieurs en garde une et laisse partir les autres, et les refusés se rassoient pour retenter au tour suivant. Les couples qui tiennent s’avancent au milieu. Six invitants pour huit invitées, comme dans une vraie salle : deux resteront assises, sans que cela rende l’appariement instable. Ce sont les vrais tours de l’algorithme qui défilent, pas une histoire dessinée.
while (free.length) {
const a = free.pop()!;
if (next[a] >= list[a].length) continue; // nobody left to ask
const b = list[a][next[a]++]; // ask the next one down
const held = partner[b];
if (held === -1) { // b is free: provisionally taken
partner[b] = a;
partner[a] = b;
} else if (rank[b][a] < rank[b][held]) { // b trades up, held goes back
partner[b] = a;
partner[a] = b;
partner[held] = -1;
free.push(held);
} else {
free.push(a); // refused, ask again tomorrow
}
}Riehl en tire quatre théorèmes. Zéro : la boucle s’arrête toujours, parce qu’une proposition n’est jamais refaite. Un : le résultat est stable, et elle insiste sur le fait qu’aucune restriction n’est nécessaire ni sur les effectifs de chaque côté, ni sur les listes de préférences. Deux : le côté qui invite obtient, simultanément pour tous, le meilleur partenaire qu’un appariement stable puisse lui donner. Trois : le côté qui reçoit obtient le pire. Les deux derniers partagent une seule démonstration, et il a fallu une dizaine d’années pour que quelqu’un remarque la seconde moitié. L’article de 1962 faisait proposer les hommes, on a vu tout de suite qu’ils y gagnaient, et beaucoup plus tard que les femmes y perdaient.
Réglez la salle, puis regardez qui danse. Une ligne par personne, une colonne par tanda, les plus délaissés en haut. Le compteur de paires instables est le seul juge : à zéro, l’appariement est stable au sens de Gale-Shapley ; au-dessus, le théorème ne dit plus rien. Le partenaire obtenu se lit en pourcentage de sa propre liste : vingt pour cent veut dire dans le premier cinquième.
Chaque ligne est une personne, chaque colonne une tanda, une case pleine une tanda dansée. Les lignes sont triées du moins dansant au plus dansant, si bien que ceux que la soirée laisse de côté remontent en haut du bloc plutôt que de se perdre dedans. Le seul chiffre qui tranche est le nombre de paires instables : à zéro, l’appariement est stable au sens exact de Gale-Shapley. Les trois sections qui suivent poussent chacune sur une hypothèse du théorème, pour voir laquelle cède ; les quatre suivantes portent sur ce dont il ne dit rien.
Une milonga n’a presque jamais autant d’hommes que de femmes. On s’attend à ce que le déséquilibre casse quelque chose, et il ne casse rien : mettez dix-huit femmes pour six hommes, le compteur de paires instables reste à zéro. Douze personnes ne dansent pas, mais aucune d’elles ne peut désigner quelqu’un qui la préférerait en retour. Le déséquilibre produit des gens assis, pas de l’instabilité. C’est ce qu’énonce le théorème un, et la mesure le confirme sur la totalité des tirages.
Le curseur « part de la salle que chacun refuse » tronque les listes : au-delà d’un certain rang, on préfère rester assis. C’est le cabeceo, ce regard qu’on lance et qui n’est pas rendu, et c’est la façon la plus fidèle de traduire « ne pas danser cette tanda ». Le théorème survit là aussi : sur trois cents tirages croisés avec neuf réglages de refus et d’étiquette, à six hommes contre dix-huit femmes, le compteur n’est jamais monté au-dessus de zéro. Un marché à listes incomplètes garde un appariement stable, et la même boucle le trouve.
Le refus ne casse donc pas la garantie. Il change tout le reste. Avec des listes complètes, le marché se vide presque entièrement et le nombre de personnes sans aucune danse tend vers zéro. Le refus est donc la condition nécessaire à l’apparition d’exclus. Mais il n’y suffit pas seul, et l’accord sur les goûts non plus : dans une salle de vingt-huit personnes sur quatre heures, l’un ou l’autre poussé à fond ne laisse personne sans danser. Il faut que les deux se rencontrent, et c’est alors la taille de la salle qui décide de la suite. On y revient plus bas.
Il reste une hypothèse, et Riehl la pose dans la première minute de la vidéo avant de l’écarter pour la journée : on ne parle que de mariages hétérosexuels, ce qui, dit-elle, « compte vraiment beaucoup pour les mathématiques ». La phrase passe comme une précaution de langage. Cette hypothèse conditionne l’ensemble du résultat. Le théorème vaut sur un graphe biparti : deux camps, des couples qui traversent, jamais à l’intérieur.
Or dans une milonga, deux femmes dansent ensemble, et c’est banal. Le curseur correspondant fait exactement une chose : il fixe la part des femmes ouvertes à cette idée, une paire ne se formant que si les deux le sont. Le graphe cesse d’être biparti et le problème devient celui des colocataires, dont Gale et Shapley donnent eux-mêmes, dans le même article, un exemple sans aucune solution stable.
La garantie ne cesse pas par seuil : elle décroît continûment avec la proportion, ce qu’un interrupteur ne pouvait pas montrer. À dix pour cent de femmes ouvertes, un tirage sur deux cents porte déjà une paire instable. À trente pour cent, vingt-trois sur deux cents. À cent, cent quatre-vingt-quinze sur deux cents, avec six paires en moyenne. L’hypothèse bipartite n’est donc pas une commodité qu’on pourrait satisfaire approximativement : la moindre entaille y suffit. Ce n’est pas une défaillance du code : la boucle continue de s’arrêter et de rendre un appariement, elle a seulement cessé de promettre quoi que ce soit.
Reste le théorème le plus cité, celui qui dit qu’il vaut bien mieux inviter qu’être invitée. Il est vrai, et le simulateur le montre : à effectifs égaux, listes complètes et goûts indépendants, le côté qui invite danse avec quelqu’un qu’il a placé en moyenne à quatorze pour cent de sa propre liste, l’autre à vingt-huit, deux fois plus bas. Un partenaire « à quatorze pour cent de sa liste » est celui qu’on aurait classé quatorzième sur cent : plus le chiffre est petit, meilleur est le partenaire. Faites inviter l’autre côté et l’écart se retourne à l’identique. C’est énorme, c’est parfaitement symétrique, et c’est le chiffre qu’on retient des exposés.
L’écart devient négligeable dès qu’on sort du cas d’école. Montez l’accord sur les goûts à quatre-vingts pour cent, l’écart se réduit à presque rien. Coupez plus de la moitié des listes par le refus, et les deux côtés se retrouvent à vingt-huit pour cent, à un demi-point près, quel que soit celui qui invite. La raison est mécanique et se dit en une phrase : l’avantage du proposant est l’écart entre le meilleur et le pire appariement stable, or plus les gens s’accordent sur qui est désirable, moins il existe d’appariements stables, et à la limite il n’en reste qu’un, où le meilleur et le pire sont le même.
L’avantage du proposant se chiffre à un demi-point. Un autre effet, mesuré dans la même unité, se chiffre à dix-sept. Huit hommes pour dix-huit femmes, les hommes proposant : les hommes obtiennent un partenaire à dix-sept pour cent de leur liste, les femmes à trente-quatre. Inversez les effectifs et l’écart s’inverse à l’identique : trente-trois contre dix-sept. Le côté rare gagne, quel que soit celui qui invite. Il gagne à peu près ce que rapportait le droit d’inviter dans le cas d’école, sauf qu’ici, ce droit-là ne rapporte plus rien.
C’est le résultat que je ne cherchais pas et qui rend la soirée lisible. Le théorème est exact et son effet mesurable, mais il est d’un ordre de grandeur inférieur à celui d’une variable qu’il ne traite pas. « Invite au lieu d’attendre » est un conseil fondé, démontré, et sans effet mesurable dans une vraie salle. « Viens le soir où ton côté est en minorité » ne se démontre nulle part, et double la hauteur à laquelle on danse.
Le théorème ne dit rien non plus des règles qu’une salle se donne à elle-même. La plus visible, en milonga, est qu’on ne redanse pas avec la même personne au cours de la soirée. Shure la code en dur : chez lui, personne ne se répète. Ici c’est un curseur, parce qu’une salle ne suit jamais une convention en bloc : à zéro on retrouve exactement sa contrainte, à cent l’étiquette a disparu.
Le résultat est de signe opposé à celui que j’attendais. Quand personne ne redanse, personne ne reste assis : sur une soirée de quatre heures, pas une seule des vingt-huit personnes ne finit sans avoir dansé. Quand tout le monde peut redanser, neuf d’entre elles n’ont aucune tanda. Et le partenaire obtenu est meilleur pour tout le monde : vingt et un pour cent de sa propre liste contre trente-huit. Une convention d’usage produit donc un effet redistributif : l’interdiction de répéter un partenaire impose une rotation, qui borne le nombre de tandas qu’une même personne peut capter.
Ce n’est pas un plaidoyer pour l’étiquette. Le modèle ne sait rien du plaisir de redanser avec quelqu’un avec qui ça marche, et il ne mesure qu’une chose : combien de gens restent assis. Sur cet indicateur, la règle est efficace, et elle l’est sans coordination : l’effet provient de la contrainte, non des intentions des participants.
Une milonga de quartier réunit trente personnes, un festival en réunit cent. On attend de la grande salle qu’elle protège : plus de monde, plus de partenaires possibles, plus de chances pour chacun. La mesure donne le résultat inverse. À trois hommes pour quatre femmes et sur quatre heures : à quatorze, personne ne reste assis ; à vingt-huit, personne non plus ; à cinquante-six, un dixième de la salle ; à quatre-vingt-douze, plus du quart.
La taille n’est pourtant pas la variable explicative. Reprenez les mêmes salles avec des goûts indépendants : personne n’est laissé de côté, à aucune taille. Reprenez-les avec des goûts très accordés mais sans aucun refus : personne non plus, à aucune taille. Il faut les deux ensemble, l’accord sur qui est désirable et le refus du bas de sa liste, et alors seulement la taille décide de la dureté. Un festival ne fabrique donc pas l’exclusion. Il fournit à une conjonction déjà présente l’effectif à partir duquel son effet devient mesurable.
Chaque section précédente mesure une variable. Réunies, elles deviennent comparables : la seule que le théorème traite est le droit d’inviter, et c’est celle dont l’effet est le plus faible dans une salle réaliste.
Le tableau se lit en deux parties. Les deux premières lignes donnent le théorème, puis ce qu’il en reste une fois sorti du cas d’école : l’écart s’annule. Les quatre suivantes portent sur des variables que Gale et Shapley ne traitent pas, à savoir la composition de la salle, la règle d’usage appliquée, l’effectif et les appariements admis. Chacune produit un effet supérieur à celui que le théorème garantit.
Rien de tout cela n’est resté théorique. Dans les années cinquante, l’affectation des internes en médecine aux hôpitaux américains se faisait de gré à gré et produisait des appariements instables. Le programme national qui l’a remplacée fait tourner exactement cette boucle chaque mois de mars, aux États-Unis et au Canada. Il a d’abord fait proposer les hôpitaux, et donc favorisé les hôpitaux ; au milieu des années quatre-vingt-dix, quand on a compris de quel côté penchait le théorème trois, le sens a été inversé au profit des internes. Riehl ajoute un quatrième théorème qui explique pourquoi le procédé tient socialement : le côté qui propose n’a aucun intérêt à mentir sur ses préférences.
Le même algorithme tourne aussi dans une salle de machines. Un réseau de diffusion de contenu doit affecter des milliards de requêtes par heure à des dizaines de milliers de serveurs edge, et Akamai le fait avec une variante de Gale-Shapley : les clients sont regroupés par zone et par type de trafic, les serveurs en grappes notées sur la capacité et la latence, chaque côté classant l’autre. Les groupes de clients veulent les grappes les mieux notées, les grappes veulent les groupes les moins gourmands. Le motif du choix n’est pas l’élégance : les autres approches combinatoires étaient trop lentes, et celle-ci tient le débit.
Ce sont les serveurs qui proposent, note Shure. Le théorème trois dit alors exactement qui est servi le mieux, et ce n’est pas la requête. Le sens de la proposition n’est donc pas un détail d’implémentation : c’est le seul endroit du système où se décide qui a l’avantage, et dans les deux cas cités ici quelqu’un a dû trancher. Pour les internes en médecine, le sens a fini par être renversé. Dans le cas des requêtes web, il n’a jamais été remis en question.
Le prix Nobel d’économie est allé en 2012 à Lloyd Shapley et Alvin Roth, pour la théorie des allocations stables et la conception de marchés. Gale, mort en 2008, n’était plus éligible.
Le modèle ignore beaucoup de ce qui fait une soirée réelle. L’étiquette y est entrée, mais grossièrement : elle interdit de reprendre un partenaire de toute la soirée, là où l’usage vise surtout deux tandas d’affilée. Le niveau, la fatigue, la musique de la tanda, le fait de venir accompagné, la géographie des tables : rien de tout cela n’existe. Les goûts sont retirés au sort à chaque tanda autour d’une réputation fixe, ce qui est une hypothèse forte et non un fait observé. Et le cabeceo n’est pas une proposition : c’est un regard que l’on peut ne pas voir, ce qui en fait un mécanisme à information incomplète que ce modèle ne représente pas.
Surtout, aucun de ces chiffres ne vient d’une milonga. Ils viennent du simulateur ci-dessus, avec les réglages annoncés à chaque fois, et ils décrivent le modèle et non la salle. Ce qu’on en retire est plus étroit, et plus solide, qu’une leçon de danse : une garantie de stabilité ne dit rien sur la répartition, elle survit aux effectifs inégaux et aux refus, et elle tombe entièrement dès qu’un couple peut se former à l’intérieur d’un camp.