Les mariages stables : apparier sans argent

Gale et Shapley parlaient déjà d'« admissions à l'université » : un établissement accueille plusieurs élèves. L'algorithme s'étend sans peine. Chaque élève sans place demande le lycée suivant de sa liste. Chaque lycée garde provisoirement ses meilleurs candidats dans la limite de ses places et refuse les autres. Un élève refusé passe au lycée suivant, et ainsi de suite. Une place gardée peut encore être reprise par un meilleur candidat : d'où le nom d'acceptation différée. C'est le principe des procédures d'affectation au lycée (Affelnet en France, celles de New York ou de Boston) et de l'appariement des internes américains (NRMP).

Revenons au cas d'une place par établissement, avec n candidats et n établissements. Il peut exister plusieurs affectations stables. La page les trouve toutes, en examinant les n! affectations possibles. Elles s'ordonnent d'une façon remarquable : si tous les candidats préfèrent (ou trouvent égale) l'affectation A à l'affectation B, alors tous les établissements préfèrent B à A. Les intérêts des deux côtés sont exactement opposés. On peut ranger les solutions stables en un diagramme (un treillis) qui va de la meilleure pour les candidats, en haut, à la meilleure pour les établissements, en bas.

Une règle d'affectation ne vaut que si les candidats donnent leurs vraies préférences. Dans l'acceptation différée où les candidats proposent, mentir ne rapporte jamais rien à un candidat (Dubins et Freedman, 1981 ; Roth, 1982). Comparez avec l'ancienne méthode de Boston : chaque lycée remplit d'abord ses places avec ceux qui l'ont mis en premier vœu, définitivement ; puis avec les deuxièmes vœux, et ainsi de suite. Mettre en premier un lycée trop demandé y est risqué : un élève malin place plutôt en tête un lycée moins couru où il est sûr d'entrer. La page essaie, pour un candidat donné, les 120 façons d'ordonner ses 5 vœux.

En 1974, Lloyd Shapley et Herbert Scarf étudient un marché sans argent : chacun possède une maison et a ses préférences sur toutes les maisons. Peut-on organiser des échanges dont personne ne voudra sortir ? Ils publient une méthode due à David Gale : les cycles d'échanges (en anglais top trading cycles). Chacun pointe vers le propriétaire de la maison qu'il préfère. Il existe forcément au moins un cycle : on réalise les échanges de ce cycle, ses membres partent avec leur nouvelle maison, et l'on recommence avec ceux qui restent.

Un malade a trouvé un proche prêt à lui donner un rein, mais leurs groupes sanguins sont incompatibles, ou ses anticorps rejetteraient l'organe. Ailleurs, une autre paire est dans la même impasse. Si le donneur de la première convient au malade de la seconde, et inversement, on peut croiser les dons : deux greffes au lieu de zéro. Avec trois paires, le cycle s'agrandit. Un donneur altruiste, sans receveur attitré, peut lancer une chaîne. On ne vend rien : on échange, comme dans le marché de Shapley et Scarf. Les premiers dons croisés datent des années 1990 ; en 2004, Alvin Roth, Tayfun Sönmez et Utku Ünver ont montré comment les organiser à grande échelle avec les outils de Shapley et Scarf. Des milliers de greffes en ont bénéficié depuis dans le monde.