Le prix Nobel d’économie 2012

Encore un lemme des mariages !

Piste verte 14 novembre 2012  - Ecrit par  Jérôme Buzzi 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.

L’apport d’Alvin Roth

Dans les années 1980, A. Roth étudie :

  • les possibilités de tricheries (peut-on « voler » l’affectation d’un autre en mentant sur ses propres préférences ?) ;
  • la prise en compte dans le recrutement des internes des conjoints, parfois tous les deux médecins ;
  • le don d’organe où il faut tenir compte des incompatibilités immunitaires ainsi que de la volonté d’un donneur $a$ de donner pour un proche $A$ plutôt que pour n’importe qui. On va donc rechercher des « chaînes » ($a$ donnant à $B$, $b$ donnant à $C$, $c$ donnant à $A$ –la chaîne la plus longue jamais trouvée et mise en place a atteint 60 personnes, ce qui n’est pas sans poser de sérieux problèmes pratiques quand il faut coordonner ces soixantes opérations chirurgicales...

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.

Stabilité et optimum de Pareto

Une solution stable $S$ au sens défini ci-dessus est optimale au sens de Pareto : il n’existe pas d’autre solution où tout le monde serait mieux loti. Voyez-vous pourquoi ?

Solution

En effet, supposons que $S$ et $S'$ sont deux solutions distinctes telles que $S'$ est meilleure (ou au moins aussi bonne) que $S$ du point de vue de chacun. Comme $S'\ne S$, il y a un mariage prévu par $S$, disons $(A,a)$, qui diffère de celui prévu par $S'$, disons $(A,b)$. Notons $B$ l’épouse de $b$ prévue par $S$. $S'$ étant par hypothèse meilleure que $S$ pour tout le monde, $A$ préfère $b$ à $a$ et $b$ préfère $A$ à $B$. Autrement dit $S$ est instable.

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.

  1. 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.
  2. 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]
  3. 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.
  4. 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.
  5. 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.
  6. 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).

Algorithme et preuve

La preuve proposée par Gale et Shapley repose sur une proposition d’algorithme ou disons simplement un programme qu’on pourra trouver dans l’article original de Gale et Shapley cité ci-dessus ou bien ici . En voici une description informelle :

Choix numéro 1 :
 
Chaque femme propose le mariage à l’homme qu’elle préfère [7]
Chaque homme retient (pour l’instant) parmi les propositions reçues la femme qu’il préfère.
 
Choix numéro 2 :
 
Les femmes qui n’ont pas été retenues par leur premier choix font une proposition à leur deuxième choix.
Chaque homme cherche parmi les nouvelles propositions et celle précédemment retenue celle qu’il préfère et ne retient que celle-ci.
 
Choix numéro 3 :
 
....
....
....
 
Choix numéro N :
 
...
 
La solution se lit en prenant pour chaque femme $A$, le couple $(A,a)$ où $a$ est l’homme retenu après la $N$ème étape.

Attention Le programme permet (s’il a les propriétés annoncées) de résoudre tout problème de mariage collectif et d’expérimenter sur ordinateur autant que l’on veut. Mais ce programme n’est pas une preuve. On peut toutefois en tirer une preuve, par exemple en montrant que :

  1. le programme se termine toujours (on peut le voir en remarquant qu’à chaque proposition de mariage, on enlève un homme d’une liste de préférence d’une femme et que ceci ne peut pas se produire plus de $N^2$ fois. [8]) ;
  2. le programme produit toujours un mariage collectif stable ;
  3. ce mariage collectif est bien optimal pour les femmes ;
  4. il n’est pas difficile de montrer enfin l’unicité du mariage stable optimal pour les femmes.

(On peut consulter l’article original de Gale et Shapley, page 12, pour la preuve élémentaire, mais parfois astucieuse, de chacun de ces points.)

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.
Post-scriptum :

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.

Article édité par Jérôme Buzzi

Notes

[1Mê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).

[2En 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.

[3Shapley travaille à temps partiel pour la RAND corp, le temple de cette théorie.

[4Si 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.

[5Une remarque à la fin de l’article souligne leur intention pédagogique.

[6On 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.

[7Selon sa propre liste de préférence.

[8On 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

Crédits image :

Image à la une - Le logo vient de ce site qui propose de jouer avec l’algorithme de Gale-Shapley.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM