Gale-Shapley en milonga : stable ne veut pas dire équitable
L’algorithme récompensé par le prix Nobel 2012 garantit qu’aucune paire de danseurs ne préférerait se former en dehors de l’appariement obtenu. Il ne garantit à personne de danser, et l’écart entre ces deux propriétés est plus important 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 toutes les tandas et d’autres presque aucune. 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 : un article de 1962, un prix Nobel en 2012, et des affectations qui portent aujourd’hui sur des dizaines de milliers de personnes. Reste à voir ce que cette théorie garantit pour une telle soirée, et ce qu’elle ne garantit pas.
Le rapprochement vient de Loren Shure, qui a publié en 2020 sur le blog de MathWorks un billet sur l’appariement stable, parti 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 points : l’appariement à l’intérieur d’un même camp, les listes incomplètes et les ex æquo. Ce texte reprend les deux premiers et remplace ses règles strictes par des proportions, parce que les membres d’une salle ne partagent jamais tous le même avis.
David Gale et Lloyd Shapley publient en 1962 un article au titre d’apparence 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 est le suivant : étant donné deux groupes dont chaque membre classe les membres de l’autre, peut-on toujours former des couples de sorte qu’aucune paire ne préfère se reformer autrement ? L’instabilité reçoit une définition précise, dont dépend tout l’énoncé : deux personnes qui se préfèrent mutuellement 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 la rend utile. L’algorithme se décrit par journées. 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 les autres ; 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’une meilleure proposition arrive. On recommence jusqu’à ce que plus personne ne soit refusé. L’algorithme s’écrit en une seule boucle.
Les danseurs attendent au bord de la piste. Une invitation traverse la salle ; une personne qui en reçoit plusieurs en accepte une et refuse les autres, et les personnes refusées réessaient au tour suivant. Les couples formés rejoignent le centre. Il y a six invitants pour huit invitées, comme dans une salle réelle : deux invitées restent assises, et l’appariement est stable quand même. L’animation rejoue les tours réels de l’algorithme.
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 Riehl 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 et observez qui danse. Une ligne par personne, une colonne par tanda, les personnes qui ont le moins dansé en haut. Le compteur de paires instables sert de critère : à zéro, l’appariement est stable au sens de Gale-Shapley ; au-dessus, le théorème ne s’applique plus. Le partenaire obtenu est exprimé en rang dans la liste de préférence de chacun : vingt pour cent signifie dans le premier cinquième.
Chaque ligne est une personne, chaque colonne une tanda, et une case pleine une tanda dansée. Les lignes sont triées de la personne qui a le moins dansé à celle qui a le plus dansé, de sorte que les personnes laissées de côté apparaissent en haut du bloc. Le seul critère est le nombre de paires instables : à zéro, l’appariement est stable au sens exact de Gale-Shapley. Les trois sections suivantes modifient chacune une hypothèse du théorème pour voir laquelle ne tient plus ; les quatre suivantes portent sur ce dont il ne dit rien.
Une milonga n’a presque jamais autant d’hommes que de femmes. On pourrait croire que ce déséquilibre rend l’appariement instable, mais ce n’est pas le cas. Avec dix-huit femmes pour six hommes, le compteur de paires instables reste à zéro. Douze personnes ne dansent pas, mais aucune ne peut désigner quelqu’un qui la préférerait en retour. Le déséquilibre laisse des personnes assises sans créer d’instabilité. C’est ce qu’énonce le théorème un, et la mesure le confirme sur tous les 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 lancé et non rendu, et c’est la traduction la plus fidèle de « ne pas danser cette tanda ». Le théorème reste valable dans ce cas : sur trois cents tirages croisés avec neuf réglages de refus et d’étiquette, à six hommes pour dix-huit femmes, le compteur n’a jamais dépassé zéro. Un marché à listes incomplètes admet toujours un appariement stable, et la même boucle le trouve.
Le refus ne remet donc pas en cause la garantie. Il modifie en revanche tout le reste. Avec des listes complètes, presque tout le monde trouve un partenaire, et le nombre de personnes sans aucune danse tend vers zéro. Le refus est donc nécessaire pour que des personnes soient exclues. Il ne suffit pas à lui seul, pas plus que l’accord sur les goûts : dans une salle de vingt-huit personnes pendant quatre heures, l’un ou l’autre poussé au maximum ne laisse personne sans danser. Il faut les deux à la fois, et la taille de la salle détermine alors la suite, comme on le verra plus bas.
Il reste une hypothèse, que Riehl pose dans la première minute de la vidéo avant de la laisser de côté : on ne considère que des mariages hétérosexuels, ce qui, selon Riehl, « compte vraiment beaucoup pour les mathématiques ». La phrase semble n’être qu’une précaution de langage, mais cette hypothèse conditionne tout le résultat. Le théorème vaut sur un graphe biparti : deux camps, des couples formés entre les deux, jamais à l’intérieur d’un camp.
Or dans une milonga, deux femmes dansent ensemble, et c’est courant. Le curseur correspondant fixe la part des femmes ouvertes à cette possibilité, une paire ne pouvant se former que si les deux le sont. Le graphe n’est alors plus biparti, et le problème devient celui des colocataires, pour lequel Gale et Shapley donnent eux-mêmes, dans le même article, un exemple sans aucune solution stable.
La garantie ne disparaît pas à partir d’un seuil : elle se dégrade progressivement avec la proportion, ce qu’un simple interrupteur ne pouvait pas montrer. À dix pour cent de femmes ouvertes, un tirage sur deux cents comporte déjà une paire instable. À trente pour cent, vingt-trois sur deux cents. À cent pour cent, cent quatre-vingt-quinze sur deux cents, avec six paires en moyenne. L’hypothèse bipartite ne peut donc pas être satisfaite de façon approximative : la moindre exception suffit à faire apparaître des paires instables. Le code fonctionne toujours : la boucle s’arrête et renvoie un appariement, mais cet appariement n’est plus garanti stable.
Reste le théorème le plus cité, selon lequel il vaut bien mieux inviter qu’être invité. Il est exact, et le simulateur le montre : à effectifs égaux, listes complètes et goûts indépendants, le côté qui invite danse avec une personne placée en moyenne à quatorze pour cent de sa propre liste, l’autre côté à vingt-huit, soit 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. Si l’autre côté invite, l’écart s’inverse exactement. L’écart est important et parfaitement symétrique, et c’est ce chiffre que retiennent les exposés.
L’écart devient négligeable dès qu’on quitte le cas d’école. Avec un accord sur les goûts de quatre-vingts pour cent, il se réduit à presque rien. Si le refus tronque plus de la moitié des listes, 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 : l’avantage de celui qui propose est l’écart entre le meilleur et le pire appariement stable. Plus les gens s’accordent sur qui est désirable, moins il existe d’appariements stables, jusqu’à ce qu’il n’en reste qu’un, où le meilleur et le pire se confondent.
L’avantage de celui qui propose est d’un demi-point. Un autre effet, mesuré dans la même unité, atteint dix-sept points. Avec huit hommes pour dix-huit femmes, et les hommes qui proposent, les hommes obtiennent un partenaire à dix-sept pour cent de leur liste, les femmes à trente-quatre. En inversant les effectifs, l’écart s’inverse exactement : trente-trois contre dix-sept. Le côté minoritaire est avantagé, quel que soit celui qui invite. Son avantage est du même ordre que celui du droit d’inviter dans le cas d’école, alors que ce droit n’apporte ici presque plus rien.
Je ne cherchais pas ce résultat, mais c’est lui qui explique le mieux la soirée. Le théorème est exact et son effet mesurable, mais cet effet est inférieur d’un ordre de grandeur à celui d’une variable qu’il ne traite pas. « Invite au lieu d’attendre » est un conseil fondé et démontré, sans effet mesurable dans une salle réelle. « Viens le soir où ton côté est minoritaire » n’est démontré nulle part, et permet d’obtenir un partenaire classé deux fois plus haut dans sa propre liste.
Le théorème ne dit rien non plus des règles qu’une salle se donne. La plus visible, en milonga, veut qu’on ne redanse pas avec la même personne au cours de la soirée. Shure l’impose sans exception : dans son modèle, personne ne danse deux fois avec le même partenaire. Ici, c’est un curseur, parce qu’une salle ne suit jamais une convention de manière uniforme : à zéro, on retrouve exactement sa contrainte, à cent, l’étiquette a disparu.
Le résultat va dans le sens opposé à celui que j’attendais. Quand personne ne redanse avec le même partenaire, personne ne reste assis : sur une soirée de quatre heures, aucune des vingt-huit personnes ne termine sans avoir dansé. Quand tout le monde peut redanser, neuf d’entre elles n’ont aucune tanda. Et le partenaire obtenu est meilleur pour tous : vingt et un pour cent de sa propre liste contre trente-huit. Une convention a donc un effet redistributif : interdire de reprendre un partenaire impose une rotation, qui limite le nombre de tandas qu’une même personne peut obtenir.
Je ne défends pas ici l’étiquette. Le modèle ignore le plaisir de redanser avec quelqu’un avec qui l’on danse bien, et ne mesure qu’une chose : le nombre de personnes qui restent assises. Sur cet indicateur, la règle est efficace, et sans aucune coordination : l’effet vient de la contrainte, pas 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. Avec des goûts indépendants, personne n’est laissé de côté, quelle que soit la taille de la salle. Avec des goûts très concordants mais sans aucun refus, personne non plus. Il faut les deux conditions à la fois, l’accord sur qui est désirable et le refus du bas de sa liste, et c’est alors la taille qui détermine l’ampleur de l’exclusion. Un festival ne crée donc pas l’exclusion ; il atteint l’effectif à partir duquel l’effet de ces deux conditions 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 est aussi utilisé dans l’infrastructure du web. Un réseau de diffusion de contenu doit affecter des milliards de requêtes par heure à des dizaines de milliers de serveurs de périphérie, 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 selon leur capacité et leur latence, et chaque côté classe l’autre. Les groupes de clients veulent les grappes les mieux notées, les grappes veulent les groupes les moins exigeants. Ce choix tient à la performance : les autres approches combinatoires étaient trop lentes pour ce débit.
Ce sont les serveurs qui proposent, note Shure. Le théorème trois indique alors qui est le mieux servi, et ce n’est pas la requête. Le sens de la proposition détermine donc qui est avantagé, et dans les deux cas cités ici, quelqu’un a dû le choisir. Pour les internes en médecine, le sens a fini par être inversé. Pour les 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 figure, mais de façon grossière : elle interdit de reprendre un partenaire pendant toute la soirée, alors que l’usage vise surtout deux tandas consécutives. Le niveau, la fatigue, la musique de la tanda, le fait de venir accompagné, la disposition des tables n’y sont pas représentés. Les goûts sont tirés au sort à chaque tanda autour d’une réputation fixe, ce qui est une hypothèse forte et non un fait observé. Enfin, le cabeceo diffère d’une proposition : c’est un regard que l’autre peut ne pas remarquer, ce qui relève d’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 indiqués à chaque fois, et décrivent le modèle, non une salle réelle. On peut en retenir trois points. Une garantie de stabilité ne dit rien de la répartition des danses. Elle résiste aux effectifs inégaux et aux refus. Elle disparaît dès qu’un couple peut se former à l’intérieur d’un même camp.