Un problème d’appariement.
David Gale et Lloyd Shapley, deux économistes mathématiciens, publient en 1962 un court article de six pages dans le journal American Mathematical Monthly sur la stabilité du mariage. Gale et Shapley, qui utilisent le mariage comme une métaphore, n’entrevoient pas toutes les applications possibles de leurs résultats. Alvin Roth, un autre mathématicien de formation, s’en chargera à partir des années 1980 en montrant que le modèle permet de décrire de nombreuses relations économiques qui se fondent sur l’appariement d’agents de deux types distincts : élèves et écoles, internes et hôpitaux, donneurs et receveurs d’organe, etc. En 2012, le comité Nobel en Économie récompense Shapley et Roth pour l’ensemble de leurs travaux sur les marchés d’appariement.
En 1962, les problèmes d’appariement sont déjà largement étudiés en théorie des graphes. L’originalité de l’article de Gale et Shapley consiste à introduire dans le problème de l’appariement les préférences des agents sur leurs partenaires possibles. Leur modèle se réduit à un ensemble d’hommes et de femmes et aux préférences de chacun sur les individus de sexe opposé. Ils construisent un algorithme produisant un ensemble de couples (l’appariement) stable au sens suivant : il n’existe pas un homme et une femme qui seraient plus heureux d’être mariés ensemble, plutôt que de rester chacun avec le conjoint qui leur a été attribué. Appliqué au cas de l’affectation dans les écoles, l’existence d’un appariement stable garantit qu’un écolier admis dans une école ne préfère aucune autre école qui admet un écolier moins bien classé que lui.
Lloyd Shapley, David Gale et Alvin Roth
Aujourd’hui encore, les travaux de Gale, Shapley et Roth alimentent des questions d’actualité. Ils concernent par exemple la possibilité de concilier la stabilité avec l’existence de quotas sur les minorités raciales dans les procédures d’admissions des universités américaines. Dans le cas du problème de greffes de reins étudié avec succès par Roth, le modèle de mariage s’avère également pertinent avec d’un côté les donneurs de reins et de l’autre les futurs greffés qui ont des préférences sur les donneurs (âge du donneur, taille du rein, etc.). Encore plus proche de nous, l’algorithme de Gale et Shapley, qui est simple (polynomial) au niveau calculatoire, est utilisé en France à grande échelle pour l’entrée des élèves dans les collèges et les lycées comme pour l’entrée des étudiants de première année dans l’enseignement supérieur, via les procédures AFFELNET et APB.
Pour conclure, il est fascinant de voir à quel point les mathématiques conduisent à des carrières inattendues, à l’image de Roth, passé en l’espace de 30 ans d’une thèse en mathématiques à l’Université de Stanford, à la mise au point du programme américain d’échange pour les greffes du rein. Que nos jeunes lecteurs qui doutent encore des débouchés des études de mathématiques en prennent bonne note !
Brève rédigée par Vincent Iehlé (Univ. Paris-Dauphine).
Pour en savoir plus :
- Jérôme Buzzi (2012), « Le prix Nobel d’économie 2012 », Images des Mathématiques, CNRS.
- Compte rendu du comité Nobel 2012.
- F. Forges, G. Haeringer, V. Iehlé (2013): Appariement: des modèles de Lloyd Shapley à la conception de marchés d’Alvin Roth.
- Une vidéo sur le problème du mariage stable (stable mariage problem) par Emily Riehl (Harvard University) [En anglais].
- Roth, A. et M. Sotomayor (1990), Two-Sided Matching : A Study in Game-Theoretic Modelling and Analysis. Econometric Society Monographs. Cambridge University Press.
- Brève connexe : « Le problème des tourtereaux ».
Crédits Images : Birds gallery et The golden goose award.
Imprimer
