L'algorithme de Gale et Shapley de 1962 a rendu les marchés d'appariement honnêtes

David Gale et Lloyd Shapley ont publié « College Admissions and the Stability of Marriage » dans l'American Mathematical Monthly en 1962. Ils se demandaient si des appariements stables — des affectations dans lesquelles aucun couple d'agents ne préférerait être ensemble — existent toujours dans les marchés bilatéraux comme le mariage ou l'admission à l'université.

Leur réponse était constructive : l'algorithme d'acceptation différée, dans lequel un côté propose et l'autre conserve des offres provisoires, se termine toujours par un appariement stable. La même procédure donne au côté proposant son meilleur résultat stable possible, ce qui explique pourquoi un classement sincère est la stratégie dominante pour les proposants.

Cinquante ans plus tard, l'Académie royale des sciences de Suède a décerné le prix d'économie 2012 à Shapley et Alvin Roth « pour la théorie des allocations stables et la pratique de la conception de marchés ». Roth avait montré que la stabilité explique quels marchés réels survivent, et avait reconstruit l'appariement des résidents, le choix scolaire et l'échange de reins sur cet algorithme.

L'acceptation différée trouve un appariement stable pour tous

L'existence plus un algorithme ont rendu la stabilité utilisable, et non abstraite.

Les listes de préférences sincères sont devenues la stratégie dominante pour les proposants.

Cela a donné aux concepteurs une lunette : les marchés stables survivent, les instables s'effondrent.

Cela a alimenté des refontes pratiques en médecine, en éducation et dans l'échange d'organes.

Avant de construire un marché, vérifiez que le mécanisme d'appariement est stable et stratégiquement sûr : si la fausse déclaration paie, le marché se remplit de manipulation. Un algorithme qui rend l'honnêteté optimale est de la conception de marché.

L'algorithme est devenu le moteur de la refonte de l'appariement des résidents aux États-Unis, du choix scolaire à Boston et New York, et des chaînes d'échange de reins — tous cités dans la motivation du prix Nobel. Gale-Shapley fait désormais partie du vocabulaire standard en conception de marchés, en recherche opérationnelle et en informatique.