Le prix Nobel d’économie 2012
Encore un lemme des mariages !
Piste verte Le 14 novembre 2012 Voir les commentaires
Comment affecter de manière efficace les internes en médecine aux hôpitaux en tenant compte autant que possible des préférences de chacun ? Comment apparier au mieux donneurs d’organes et malades en tenant compte des incompatibilités et des motivations ? Comment éviter les manipulations par certains acteurs ?
Le prix pour les sciences économiques de la banque de Suède en la mémoire d’Alfred Nobel, dit prix « Alfred Nobel » d’économie, récompense cette année Llyod Shapley et Alvin Roth pour des travaux qui ont apporté des réponses non seulement mathématiques mais aussi pratiques à ce type de problèmes.
Pour traiter ces problèmes éminemment pratiques d’affectations, les méthodes les plus répandues ne sont pas forcément les meilleures [1]. Voici un exemple de procédure « naïve » :
Chaque interne indique ses préférences puis chaque hôpital examine d’abord les candidats l’ayant demandé en premier choix, puis s’il reste des places les choix en deuxième position, etc.
Dans le cadre de cette procédure, les internes sont donc fortement incités à ne postuler qu’à coup sûr, et donc à chercher la cote des différentes institutions et à renoncer pour la plupart à leur vrai choix, tandis que les hôpitaux les plus prestigieux peuvent se retrouver avec un nombre insuffisant de candidats ou décider de proposer le recrutement un peu avant les autres (mais ces autres ont alors la même idée), etc...
Cet article présente la contribution fondatrice de Lloyd S. Shapley et David Gale : le lemme [2] des mariages stables. C’est en effet ce résultat (ou certains de ses « descendants ») qui fournit la base mathématique de nombreux travaux appliqués sur les problèmes d’affectation jusqu’à aujourd’hui.
Né en 1923, mathématicien, L. Shapley s’est largement consacré à la théorie des jeux (l’étude mathématique des interactions entre participants rationnels) et notamment à la recherche de bonnes propriétés de « stabilité » vis-à-vis de coalitions d’ensemble de stratégies (ce que Shapley a appelé le noyau du jeu). Le lemme des mariages stables est un exemple simple mais important, où on ne considère que les coalitions de deux joueurs.
Alvin Roth, né trente ans plus tard et spécialisé en recherche opérationnelle, reprend dans les années 1980 les travaux de Shapley pour les enrichir théoriquement de façon à pouvoir analyser de nouvelles situations. Dans cet article de vulgarisation mathématique, nous nous concentrerons toutefois sur le lemme des mariages stables de Gale et Shapley et laisserons de côté les résultats et les applications parfois spectaculaires d’A. Roth.
David Gale n’était pas éligible au prix « Alfred Nobel », étant décédé en 2008.
Du problème concret à son analyse mathématique
Gale et Shapley sont les premiers dans les années 1960 à considérer mathématiquement le problème de l’affectation dans le cadre de la théorie des jeux [3] alors encore récente.
L’analyse mathématique d’un problème pratique consiste typiquement en quatre étapes :
- la modélisation : définir une version mathématique du problème et de ses solutions ;
- le choix des propriétés que doit avoir « une bonne solution » [4] ;
- l’étude si une telle solution existe ;
- si oui, la recherche d’une méthode pratique pour trouver une solution.
Gale et Shapley présentent une forme simplifiée de leurs résultats dans l’American Mathematical Monthly (un journal qui parle de l’actualité mathématique aux mathématiciens non spécialistes du sujet considéré). Cet article intitulé « College Admissions and the Stability of Marriages » peut être lu en ligne gratuitement ici. Les auteurs ont fait l’effort de rester élémentaires, y compris dans leurs notations [5] .
Modélisation de Gale-Shapley
Gale et Shapley commencent par simplifier à outrance le problème des internes et des hôpitaux : ils traitent en premier lieu un problème de mariage collectif (constituer 100 couples à partir de 100 femmes et 100 hommes dont on connaît les préférences individuelles) – comme si chaque hôpital ne pouvait accueillir qu’un seul interne.
Un problème de mariage collectif consiste en :
- Le même nombre $N$ de femmes et d’hommes.
- Chacun est déterminé à se marier avec une personne de l’autre sexe.
- Chacun a déterminé une fois pour toutes ses préférences sous la forme d’une liste ordonnée des personnes de l’autre sexe (sans ex æquo, sans omission) et cette liste est connue.
Une solution à ce problème est une liste de $N$ couples (une femme, un homme) (!) prescrivant autant de mariages.
Qu’est-ce qu’une bonne solution ?
Gale et Shapley définissent une solution à un problème de mariage collectif comme raisonnable, ou plutôt stable, si cette solution a la propriété suivante :
La solution ne doit pas prescrire de mariages tels qu’une femme $A$ et un homme $b$ se préfèrent mutuellement à leurs conjoints prévus. Formellement, il ne doit pas y avoir deux mariages distincts $(A,a)$ et $(B,b)$ tels que $A$ et $b$ (ou $a$ et $B$) préféreraient être mariés ensemble. En effet, (on peut imaginer qu’alors) ils divorceraient pour se remarier.
Cette propriété est un cas particulier du problème général en théorie des jeux de la stabilité vis-à-vis de coalitions quelconques (et non pas réduites comme ci-dessus à deux éléments, ci-dessus $A$ et $b$). Shapley a étudié ce problème de façon détaillée au cours de sa carrière. Notons que la recherche de critères de stabilité ou de viabilité d’une combinaison de choix ou de stratégies des différents participants est un problème qui a valu à plus d’un chercheur un prix « Alfred Nobel » d’économie : John Nash, pour citer un mathématicien célèbre.
Nous pouvons maintenant énoncer le résultat mathématique de Gale et Shapley :
Le Lemme des mariages stables
Tout problème de mariage collectif admet au moins une solution stable.
Il existe d’ailleurs une unique solution stable qui soit optimale pour les femmes au sens que chaque femme ne puisse obtenir un meilleur mariage dans une autre solution stable.
Remarques.
- Le lemme des mariages est un outil classique de combinatoire expliqué dans cet article d’Images des Mathématiques. Ce résultat classique permet également de produire un appariement entre les éléments de deux ensembles, mais sous une hypothèse de nature assez différente du lemme de Gale et Shapley.
- Il y a symétrie complète entre hommes et femmes dans la définition du problème. Il existe donc aussi une solution optimale pour les hommes, mais attention ce n’est en général pas la même ! [6]
- Gale et Shapley soulignent dans leur article comment ce résultat explique la procédure réellement utilisée pour l’affectation des internes aux hôpitaux aux Etats-Unis depuis les années 1950.
- Une idée peut-être plus naturelle pour construire une solution serait de définir un ordre de désirabilité global sur les hommes et sur les femmes pour marier le plus désirable avec la plus désirable, etc. Le théorème d’impossibilité de Kenneth Arrow (voir aussi cet article-ci et celui-là) montre que cela ne marcherait pas.
- On peut croire que ce résultat fournit une analyse complète de ce problème (au moins dans sa version simplifiée). Mais tout bon chercheur a une réserve de questions dans sa besace. Ici, les théoriciens des jeux vont par exemple se demander dans quelles conditions il est possible de tricher. Cela fait partie des problèmes que résout A. Roth.
- Le problème de l’affectation considéré ici ne fait intervenir ni prix, ni marché. C’est un coordonnateur central qui propose une solution qui devrait être acceptée volontairement du fait de son caractère stable (du socialisme à visage humain, en somme). D’autres économistes ont analysé des problèmes mixtes, combinant listes de préférences (aspect combinatoire ou discret) et prix (aspect continu).
Un peu de lecture
- L’annonce officielle de l’attribution du prix de la banque de Suède pour les sciences économiques en la mémoire d’Alfred Nobel se trouve ici.
- L’informaticien bien connu Donald E. Knuth a écrit un petit livre en français sur ce type d’algorithmes et leur analyse.
- Le New York Times propose quelques liens dont ce site qui permet de jouer avec l’algorithme de Gale-Shapley.
L’auteur souhaite remercier les relecteurs et commentateurs dont les noms ou pseudonymes suivent : Jérôme Germoni, julesdep, Vincent Beck, le_chevelu, François Béguin, dont la lecture attentive et les suggestions ont permis d’améliorer notablement le texte initial.
Notes
[1] Même si l’exemple suivant provient des États-Unis, on connaît bien cette méthode en France aussi (par exemple pour l’admission post-bac à certaines catégories d’écoles ou de classes préparatoires).
[2] En mathématiques, un lemme est un résultat intermédiaire. Certains lemmes ne servent qu’une fois et sont vite oubliés. D’autres deviennent des outils essentiels pour analyser toute une catégorie de problèmes.
[4] Si on est trop gourmand, il risque de ne pas souvent exister de bonnes solutions. Si on n’en demande pas assez, on risque au contraire une pléthore de solutions pas très intéressantes.
[5] Une remarque à la fin de l’article souligne leur intention pédagogique.
[6] On voit que, même dans ce cas pourtant très simplifié les détails du principe adopté influent sur les résultats. On regrettera d’autant plus que ces détails soient rarement précisés.
[7] Selon sa propre liste de préférence.
[8] On dit que la complexité informatique de l’algorithme est en $\mathcal O(N^2)$.
Partager cet article
Pour citer cet article :
Jérôme Buzzi — «Le prix Nobel d’économie 2012» — Images des Mathématiques, CNRS, 2012
Laisser un commentaire
Actualités des maths
-
6 février 2023Journées nationales de l’APMEP, appel à ateliers (9/4)
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
-
3 mai 2022Comment les mathématiques se sont historiquement installées dans l’analyse économique (streaming, 5/5)
Commentaire sur l'article