Annotations

En attendant l'édition actualisée de l'ouvrage de Jean-Edouard Colliard et Emmeline Travers, je propose ici une traduction d’un billet de Timothy Taylor (« The 2012 Nobel Prize to Shapley and Roth ») où ce dernier revient sur les travaux des deux derniers « nobélisés » en économie. Je le remercie à nouveau de m’accorder l’opportunité de le traduire.

L’annonce officielle se lit ainsi : « Le prix de la Banque de Suède en sciences économique à la mémoire d’Alfred Nobel de l’année 2012 fut conjointement attribué à Alvin E. Roth et Lloyd Shapley pour la théorie des allocations stables et la pratique de la conception du marché (market design) ». Donc, le prix cherche à souligner l’interaction entre la théorie économique mathématisée et les applications concrètes. Chaque année lorsque le prix Nobel est attribué, le Comité du Prix met à disposition une documentation utile pour expliquer leur choix : son article pour l’« information du public » est disponible ici et son article revenant sur « le contenu scientifique » est disponible là. Je vais par la suite me baser sur les deux.

Dans cette dualité entre théorie et application, Lloyd Shapley est présenté comme le théoricien. En effet, dans une entrevue avec l’Associated Press ce lundi, il dit : « Je me considère moi-même comme un mathématicien et la récompense est destinée à l’économie. Je n’ai jamais, jamais de ma vie, pris un cours en économie ». Mais bien sûr, les économistes voient leur champ comme suffisamment vaste pour y inclure au moins quelques mathématiciens – et en particulier ceux qui étudient la théorie des jeux, comme le Prix Nobel attribué en 1998 à John Nash et à d’autres.



Shapley et son co-auteur David Gale publièrent un célèbre article en 1962 dans la revue American Mathematical Monthly appelé « College Admissions and the Stability of Marriage » (vol. 69, n° 1, pp. 9-15). (…) Ils y prennent comme exemple l’admission au collège (…). Il y a un certain nombre de collèges et un certain nombre de candidats. Les collèges ont des préférences pour les étudiants qu’ils voudraient admettre, tandis que les candidats ont des préférences pour les collèges où ils aimeraient aller. Comment peuvent-ils être appariés d’une manière qui « satisfasse » les deux côtés ? Avant d’aller plus loin, notons que ce problème d’une multiplicité d’agents des deux côtés (et la difficulté à les apparier de manière à « satisfaire » toutes les parties) est une caractéristique des marchés matrimoniaux (bien que dans ce cas, chacun ne cherche qu’un seul partenaire), mais également du marché du travail avec les employeurs et leurs (potentiels) salariés.

(…) Il est évidemment impossible de “satisfaire” toutes les parties dans le sens où chacun obtiendrait son premier choix. Le collège ne peut être certain que tous ses candidats préférés désirent venir dans son établissement ; tous les candidats ne vont probablement pas obtenir leur premier choix. Donc, Gale et Shapley cherchèrent plutôt à trouver une solution qui soit « stable ». Cela signifie dans l’exemple des admissions au collège que, une fois que chacun est apparié, il n’y a pas de combinaison étudiant-collège pour laquelle l’étudiant voudrait plutôt aller dans un autre collège ET où le collège préfèrerait aussi avoir cet élève à la place de l’un des candidats qu’il a déjà sélectionnés. En d’autres termes, ni les étudiants, ni les collèges ne vont chercher à contourner un mécanisme stable. Gale et Shapley proposèrent une procédure d’« acceptation différée » (deferred acceptance) pour obtenir un résultat stable à leur problème d’appariement. Voici comment le comité Nobel décrit le processus :

« Les agents d’un côté du marché, disons les services médicaux, font des offres aux agents de l’autre côté du marché, les étudiants en médecine. Chaque étudiant passe en revue les propositions qu’il reçoit, garde celle qu’il préfère (en supposant qu’elle soit acceptable) et rejette les autres. Un aspect crucial de cet algorithme est que les offres désirables ne sont pas immédiatement acceptées, mais simplement mises de côté : il s’agit de l’acceptation différée. Tout service de soin dont l’offre est rejetée peut faire une nouvelle offre à un autre étudiant. La procédure continue jusqu’au moment où il n’y a plus de service médical qui veuille faire une nouvelle offre ; c’est à cet instant-là que les étudiants acceptent définitivement les propositions qu’ils avaient mis de côté.

Au cours de ce processus, chaque service hospitalier commence en faisant sa première offre au candidat au sommet de son classement, c’est-à-dire à l’étudiant de médecine qu’il aimerait le plus avoir comme interne. Si l’offre est rejetée, il fait ensuite une offre au candidat qu’il classe comme numéro deux, etc. Donc, au fur et à mesure de l’opération de l’algorithme, les attentes du service médial sont révisées à la baisse comme celui-ci fait des offres à des candidats toujours plus bas dans ses préférences. (Bien sûr, aucune offre n’ait faite aux candidats inacceptables.) Inversement, puisque les étudiants gardent toujours l’offre la plus désirable qu’ils ont reçue et que les offres ne peuvent être retirées, la satisfaction de chaque étudiant est une fonction croissante et monotone durant l’opération de l’algorithme. Quand les attentes revues à la baisse des services de santé sont devenus cohérentes avec les plus grandes aspirations des étudiants, l’algorithme s’arrête. »

Voici comment la procédure marcherait sur le marché matrimonial:

« L’algorithme de Gale-Shapley peut être exécuté de deux manières différentes : soit les hommes font des propositions aux femmes, soit ce sont les femmes qui font des propositions aux hommes. Dans ce dernier cas, le processus commence avec chaque femme demandant en mariage l’homme qu’elle désire le plus. Chaque homme regarde alors les différentes propositions qu’il a reçues, retient ce qu’il considère comme la plus intéressante d'entre elles (mais il ne l’accepte pas encore) et rejette les autres. Les femmes qui furent rejetées au premier tour font alors une proposition à leur deuxième meilleur choix, tandis que les hommes gardent encore leur meilleure offre et rejettent les autres. Cela continue jusqu’à ce que plus aucune femme ne veuille faire de nouvelles propositions. Comme chaque homme accepte alors la proposition qu’il a gardée, le processus s’arrête. »

Gale et Shapley prouvent que cette procédure aboutit à une solution « stable ». Encore une fois, ceci ne signifie pas que chacun obtient son premier choix ! Cela signifie que lorsque ce résultat est atteint, il n’y a pas de combinaison d’école médicale et de candidat (ou bien d’homme et de femme dans l’exemple du mariage) où l’un et l’autre préfèreraient un autre appariement. Mais Gale et Shapley sont allés plus loin. Il s’avère qu’il y a souvent plusieurs combinaisons stables et, lorsque l’on compare ces solutions stables, l’identité de celui qui effectue le choix importe. Si les femmes font des propositions aux hommes, elles vont voir la solution finale comme la meilleure de toutes les possibilités d’appariement, tandis que les hommes verront celle-ci comme la pire ; si les hommes font au contraire des propositions aux femmes, ils vont voir cette solution comme la meilleure de toutes les possibilités d’appariement stables, tandis que les femmes la verront au contraire comme la pire. Comme le comité Nobel l’écrit, « des institutions stables peuvent être conçues pour favoriser systématiquement un côté du marché ».

Il existe plusieurs autres améliorations et dénouements possibles. Que faire s’il y des paiements monétaires en jeu ? Que faire si les participants au marché s’échangent des objets invisibles ? Ces questions et de nombreuses autres ont occupé toute une génération de théoriciens des jeux. (…) Bien que j’aie présenté la procédure d’acceptation différée comme un processus séquentiel où les parties font une offre à la fois, un processus équivalent peut être géré par une chambre de compensation si les parties révèlent suffisamment d’informations.



Et c’est là qu’Alvin Roth entre en scène, en rapportant des implications pratiques détaillées pour l’analyse. Il fit remarquer dans un article de 1984 que le National Resident Matching Program destiné à apparier les internats et les étudiants de l’école de médecine fut effectivement un proche cousin de la procédure Gale-Shapley. L’analyse théorique de Roth mit en évidence que la forme de l’appariement qu’ils utilisèrent permit aux écoles médicales, plutôt qu’aux étudiants, d’être les « proposants », et donc générèrent des résultats que les écoles de médecine virent comme la meilleure des options stables, alors que les étudiants les virent comme la pire des options stables. Il modifia le cadre d’appariement de manière à laisser les étudiants être les proposants, mais aussi pour prendre en compte le fait que des couples mariés ou engagés ont voulu dans de nombreux cas aller à la même école ou dans le même lieu géographique.

Roth trouva ensuite d’autres applications pour ce qu’il appela l’approche de la « conception du marché” (market design approach). (C’est ironique, mais vrai, que l’approche de la conception du marché peut éventuellement inclure les prix, mais ne nécessite finalement pas les prix pour fonctionner.) Les problèmes clés dans ces scénarios d’appariement impliquent souvent une contrainte temporelle. Il y a souvent une pression sur différentes parties (que ce soit dans le cas du mariage ou des admissions au collège) à s’engager plus tôt, ce qui peut mener à des situations où la solution sera défaite comme les gens cherchent un moyen de sortir de leurs engagements prématurés. De l’autre côté, si le processus s’accomplit trop tardivement, la « congestion » peut survenir quand une offre est rejetée et il est alors trop tard pour formuler d’autres offres.

Roth trouva des applications de l’approche de l’appariement de Shapley dans une large variété de cadres universitaires d’appariement, à la fois aux Etats-Unis et dans d’autres pays. Il appliqua aussi un processus similaire aux étudiants choisissant entre différentes écoles publiques à New York et à Boston. Plus récemment, il a cherché à appliquer ces intuitions au problème de l’appariement entre les donneurs de reins et ceux nécessitant une transplantation de rein. (Pour être juste, il faut souligner que Roth a écrit de nombreux articles théoriques également solides, mais le comité Nobel a surtout mis en avant ses préoccupations d’ordre pratique et je suis ici leur exemple). Comme on peut s’y attendre, ces situations du monde réel soulèvent divers problèmes pratiques. Vaut-il mieux déjouer le système en ne révélant pas son premier choix, que l'on risque de ne probablement pas obtenir, et de prétendre être très enthousiaste pour son cinquième choix, que l'on aura plus de chances d’obtenir ? De telles questions sont quelquefois possibles dans une situation concrète, mais il s’avère plus difficile d’agir ainsi qu’on ne peut le penser. Habituellement, il vaut mieux simplement révéler ses véritables préférences et voir comment le mécanisme fonctionne. (...)

lire le billet original de Timothy Taylor