L'algorithme qui mit fin
à la course aux internes
En 1952, les hôpitaux américains cessent de se disputer les étudiants en médecine et confient l'affectation à une procédure unique. Dix ans plus tard, deux mathématiciens en écrivent la théorie, sans que personne ne fasse encore le lien.
Des offres lancées deux ans à l'avance
Dès les années 1920, la création des programmes de résidence aux États-Unis ouvre une compétition féroce entre hôpitaux pour recruter les internes. Les offres partent jusqu'à deux ans avant le début de la formation, bien avant que l'on puisse juger un étudiant. En 1945, les facultés de médecine conviennent de ne plus transmettre relevés de notes ni lettres de recommandation avant une date fixée, ce qui ramène la sélection à la quatrième année d'études.
La course se déplace alors vers la vitesse : le délai laissé pour répondre à une offre passe de dix jours en 1945 à moins de douze heures en 1950. L'étudiant doit accepter sur-le-champ, sans savoir ce que proposeront les autres hôpitaux. En 1951, des délégués de 79 facultés forment un comité national qui réclame une autre méthode. En 1952 a lieu le premier Match : étudiants et hôpitaux remettent chacun une liste de préférences, et une procédure centralisée fait le tri.
Le principe tient en une phrase : nul n'a plus rien à gagner à répondre le premier. Les préférences sont classées à l'avance, les postes sont attribués tous ensemble, par tours successifs, et aucun engagement n'est définitif avant la fin. La rapidité cesse d'être un avantage, et la peur de manquer l'offre disparaît avec elle.
La pratique avait précédé la théorie
En 1962, David Gale et Lloyd Shapley publient « College Admissions and the Stability of Marriage », où ils décrivent une procédure d'acceptation différée et montrent qu'elle aboutit toujours à des appariements stables, c'est-à-dire sans étudiant et hôpital qui préféreraient l'un l'autre à leur affectation. En 1984, Alvin Roth établit que l'algorithme du Match, en usage depuis plus de trente ans, produit lui aussi un résultat stable. Les hôpitaux avaient trouvé par tâtonnement ce que les mathématiciens démontreraient ensuite.
Roth observe aussi que, dans la version d'origine, les hôpitaux font les propositions et obtiennent alors le meilleur résultat stable pour eux, au détriment des étudiants. Le NRMP adopte en 1997 une version où les candidats proposent, appliquée à partir de 1998, et Roth et Shapley reçoivent en 2012 le prix de la Banque de Suède en sciences économiques. Les débats actuels sur l'affectation des élèves ou des étudiants posent la même question : qui propose, et à qui revient le meilleur résultat ?
Un marché qui s'emballe ne se calme pas toujours seul : parfois, il faut en réécrire les règles.