« Le prix de la Banque de Suède en sciences économiques en mémoire d’Alfred Nobel décerné cette année à Lloyd Shapley et Alvin Roth s'étend de la théorie abstraite développée dans les années 1960 aux travaux empiriques des années 1980, en passant par les efforts permanents visant à trouver des solutions pratiques aux problèmes du monde réel. Parmi les exemples, on peut citer l'affectation de nouveaux médecins aux hôpitaux, l'affectation d’élèves aux écoles et la transplantation d'organes humains aux receveurs. Lloyd Shapley a réalisé les premières contributions théoriques, qui ont été adoptées de manière inattendue deux décennies plus tard lorsqu'Alvin Roth a étudié le marché des médecins aux États-Unis. Ses conclusions ont suscité davantage de développements analytiques, aussi bien que la conception pratique d’institutions de marché.
L'analyse économique traditionnelle étudie les marchés où les prix s'ajustent de manière à ce que l'offre soit égale à la demande. La théorie et la pratique montrent toutes deux que les marchés fonctionnent bien dans de nombreux cas. Mais dans certaines situations, le mécanisme standard du marché rencontre des difficultés et il arrive que les prix ne puissent pas du tout être utilisés pour allouer les ressources. Par exemple, de nombreuses écoles et universités ne peuvent pas facturer de frais de scolarité et, dans le cas des organes humains destinés à la transplantation, les paiements monétaires sont exclus pour des raisons éthiques. Pourtant, dans ces cas (et dans bien d'autres encore), une allocation doit être faite. Comment ces processus fonctionnent-ils et quand le résultat est-il efficient ?
La théorie de l'appariement
L'algorithme de Gale-Shapley
L'analyse des mécanismes d'allocation repose sur une idée plutôt abstraite. Si des individus rationnels (connaissant leurs intérêts et agissant en conséquence) s'engagent dans des échanges mutuels sans restriction, le résultat devrait alors être efficient. Sinon, certains individus inventeraient de nouveaux échanges qui amélioreraient leur situation. Une allocation où aucun individu ne perçoit de gain d’une poursuite des échanges est dite « stable ». La notion de stabilité est un concept central de la théorie des jeux coopératifs, un domaine abstrait de l'économie mathématique qui cherche à déterminer comment une constellation d'individus rationnels pourrait choisir de façon coopérative une allocation. Le principal architecte de cette branche de la théorie des jeux était Lloyd Shapley, qui en a développé les principaux concepts dans les années 1950 et 1960.
Le libre échange est un présupposé clé sous-jacent au concept de stabilité. Bien qu'il permette une analyse claire, il est difficile à imaginer dans de nombreuses situations réelles. En 1962, Shapley a appliqué le concept de stabilité à un cas particulier. Dans un bref article, rédigé en collaboration avec David Gale, il a examiné le cas de l'appariement par paires : comment des individus peuvent être appariés alors qu'ils ont tous des opinions divergentes quant à savoir quel serait le meilleur appariement.
Apparier les partenaires
Gale et Shapley ont analysé l'appariement à un niveau abstrait, général. Pour l’illustrer, ils ont utilisé le mariage comme exemple. Comment apparier dix femmes et dix hommes, tout en respectant leurs préférences individuelles ? Le principal défi était de concevoir un mécanisme simple qui aboutirait à un appariement stable, où aucun couple ne se sépare et ne forme de nouveaux appariements qui amélioreraient leur situation. La solution, l'algorithme d'« acceptation différée » (deferred acceptance) de Gale-Shapley, consiste en un ensemble de règles simples qui conduisent toujours directement à un appariement stable.
L'algorithme de Gale-Shapley peut être configuré de deux manières : soit les hommes demandent en mariage les femmes, soit les femmes demandent en mariage les hommes. Dans ce dernier cas, chaque femme demande en mariage l'homme qui lui plaît le plus. Chaque homme examine ensuite les propositions reçues (le cas échéant), retient celle qu'il considère comme la plus attrayante (mais ne l’accepte pas) et rejette les autres. Les femmes rejetées au premier tour demandent alors en mariage leur deuxième meilleur choix, tandis que les hommes conservent leur meilleure offre et rejettent les autres. Cela continue jusqu'à ce qu'aucune femme ne souhaite faire de nouvelles propositions. Lorsque chaque homme accepte sa proposition, le processus prend fin. Gale et Shapley ont démontré mathématiquement que cet algorithme conduit toujours à un appariement stable.
La configuration spécifique de l'algorithme s'est avérée avoir d'importantes conséquences en termes de répartition ; il est important de savoir si le droit de proposer est accordé aux femmes (comme dans notre exemple) ou aux hommes. Si ce sont les femmes qui font des propositions, le résultat est meilleur pour elles que si les hommes proposent, car certaines femmes finissent par choisir des hommes qu'elles apprécient davantage et aucune femme ne se trouve dans une situation pire que si les hommes avaient eu le droit de faire les propositions. Ainsi, l'appariement qui en résulte est meilleur pour les femmes que tout autre appariement stable. À l'inverse, l'algorithme inverse (où les hommes proposent) conduit au pire résultat du point de vue des femmes.
La clarté et l'élégance de l'article de Gale-Shapley l'ont placé parmi les listes de lectures universitaires des étudiants en économie dans le monde entier. Mais sa pertinence concrète n'a été reconnue que bien plus tard. Au début des années 1980, Alvin Roth s'est attaché à étudier un problème d'allocation très concret : le marché des médecins nouvellement diplômés.
Les analyses empiriques
Les marchés pour les nouveaux médecins
Aux États-Unis, les étudiants diplômés en médecine sont généralement employés comme internes dans les hôpitaux, où ils constituent une part importante des effectifs. Au début des années 1900, ce marché était largement décentralisé. Dans les années 1940, la concurrence pour attirer les rares étudiants en médecine a contraint les hôpitaux à proposer des internats de plus en plus tôt, parfois plusieurs années avant l'obtention du diplôme. Des appariements étaient faits avant même que les étudiants puissent démontrer leurs qualifications et avant même qu'ils ne sachent dans quelle branche de la médecine ils souhaitaient exercer. Lorsqu'une offre était rejetée, il était souvent trop tard pour proposer des offres à d'autres candidats. Un marché en proie à de telles difficultés ne produit pas d’appariements stables, car les offres ne sont pas suffisamment nombreuses à temps pour garantir des échanges mutuellement avantageux. Afin de proposer davantage d'offres rapidement, les hôpitaux imposaient des délais stricts pour répondre aux offres. Cela obligeait les étudiants à prendre des décisions hâtives sans savoir quelles autres opportunités leur auraient été disponibles plus tard.
En réponse à ces problèmes, une "chambre de compensations", appelé National Resident Matching Program (NRMP), a été mis en place au début des années 1950. Dans un article de 1984, Alvin Roth a étudié l'algorithme utilisé par cette chambre de compensations et a découvert qu'il était étroitement lié à l'algorithme de Gale-Shapley. Il a ensuite supposé que la raison fondamentale du succès du NRMP était la production d’appariements stables. Au début des années 1990, Roth a étudié des marchés médicaux similaires au Royaume-Uni. Là-bas, il a constaté que différentes régions avaient adopté des algorithmes différents, certains produisant des appariements stables et d'autres non. Ceux qui ont abouti à des appariements stables se sont avérés efficaces, tandis que les autres algorithmes ont échoué de diverses façons.
Conception pratique
Apparier médecins et hôpitaux
Malgré son succès, le NRMP rencontrait encore des difficultés. Le nombre d'étudiantes en médecine avait augmenté et il devenait de plus en plus fréquent que des couples de médecins recherchent un internat dans la même région. Le NRMP ne pouvait pas répondre à ces demandes, si bien que de nombreux demandeurs choisissaient de ne pas utiliser ce mécanisme, signe de son instabilité. Le NRMP (à travers lequel les hôpitaux offraient des postes aux étudiants) était également critiqué pour favoriser systématiquement les hôpitaux au détriment des étudiants. En effet, comme Gale et Shapley l'avaient montré théoriquement, le côté du marché qui faisait des offres (en l'occurrence, les hôpitaux) est systématiquement favorisé. En 1995, Roth fut sollicité pour contribuer à la conception d'un algorithme amélioré pour éliminer ces problèmes. Avec Elliott Peranson, il élabora un algorithme basé sur les propositions des candidats et conçu pour satisfaire les couples. Le nouvel algorithme, adopté par le NRMP en 1997, a bien fonctionné et plus de 20.000 postes ont depuis été attribués chaque année à des candidats.
Appariement des médecins et des hôpitaux. Lorsque les médecins font des offres, ils choisissent d'abord l'hôpital A, qui accepte le médecin 1 (premier choix de l'hôpital). Dans un deuxième temps, le médecin 2 fait une offre à l'hôpital B et le médecin 3 à l'hôpital C, ce qui donne un appariement stable. Lorsque ce sont les hôpitaux qui font des offres, le résultat est que le médecin 2 est apparié avec l'hôpital C et le médecin 3 avec l'hôpital B.
La recherche sous-jacente à la conception révisée a donné lieu au développement d'une nouvelle théorie. Il semblait que les candidats pouvaient manipuler l'algorithme original (en refusant les offres qu'ils préféraient en définitive et en conservant celles qui étaient moins avantageuses) afin d'obtenir un meilleur résultat. Dans plusieurs articles théoriques, Roth a montré comment une mauvaise représentation de ses véritables préférences pouvait être dans l’intérêt du côté qui reçoit les propositions (les étudiants du NRMP original) dans certains algorithmes. En s’appuyant sur ce constat, l'algorithme révisé du NRMP a été conçu pour être immunisé contre les mauvaises représentations des étudiants. De plus, des simulations informatiques ont vérifié qu'en pratique il était insensible aux manipulations stratégiques des hôpitaux.
Apparier élèves et lycées
L'algorithme de Gale-Shapley s'est révélé être utile dans d'autres applications, comme le choix du lycée. Jusqu'en 2003, les candidats aux lycées publics de New York devaient classer leurs cinq choix préférés, après quoi ces listes de préférences étaient envoyées aux établissements. Les écoles décidaient ensuite des élèves à admettre, à rejeter ou à placer sur liste d'attente. Le processus était répété deux tours supplémentaires et les élèves qui n'avaient pas été affectés à un établissement à l’issue du troisième tour étaient alors affectés par un processus administratif. Cependant, cela ne laissait pas suffisamment de possibilités aux candidats pour indiquer leurs préférences et les établissements n'avaient pas suffisamment de possibilités pour faire des offres. En conséquence, environ 30.000 élèves se retrouvaient chaque année dans des établissements qu'ils n'avaient pas demandés. De plus, ce processus donnait lieu à une mauvaise représentation des préférences. Les établissements étant plus susceptibles d'admettre les élèves qui les classaient comme leur premier choix, les élèves peu susceptibles d'être admis dans leur établissement préféré trouvaient dans leur intérêt d'indiquer une option plus réaliste comme premier choix, tandis que les candidats qui se contentaient d'indiquer leurs véritables préférences se retrouvaient dans une situation inutilement médiocre.
En 2003, Roth et ses collègues ont contribué à repenser ce processus d'admission, en s’appuyant sur une version de l'algorithme de Gale-Shapley qui se basait sur les propositions des candidats. Ce nouvel algorithme s'est avéré efficace, avec une réduction de 90 % du nombre d'élèves affectés à des établissements pour lesquels ils n'avaient exprimé aucune préférence. De plus en plus de métropoles américaines ont ensuite utilisé une variante de l'algorithme de Gale-Shapley.
Les cadres d’appariement
Apparier les reins et les patients
Les situations d'appariement décrites jusqu'à présent impliquent deux côtés qui prennent tous les deux activement des décisions. Cependant, certaines situations réelles sont unilatérales, dans le sens où seul un côté est actif. Un exemple concret est l'appariement de reins et d'autres organes humains à des patients nécessitant une transplantation. Comment cela peut-il être accompli efficacement ?
Ce problème a été étudié par Shapley et ses collègues, toujours de manière abstraite et en se basant sur la notion de stabilité. L'algorithme proposé, appelé « cycle d’échange optimal » (top trading cycle) est en fait très simple. Il se base sur une allocation initiale d'objets et la permutation subséquente. Dans le cas des organes humains, la compatibilité de certaines paires rein-patient peut constituer un défi et les permutations multilatérales complexes peuvent être très chronophages. Là encore, une combinaison de théorie et de travail expérimental a été utilisée pour comparer différentes versions de l’échange optimal. Par conséquent, des chaînes de dons de reins de plus en plus complexes sont désormais adoptées dans plusieurs États américains.
Extensions à de nouveaux marchés
Un aspect frappant des exemples ci-dessus est que les prix ne font pas partie du processus. L'absence de mécanisme de prix dans l'algorithme de base de Gale-Shapley limite-t-elle son applicabilité ? Pas nécessairement. Shapley et d'autres ont examiné des extensions du modèle original qui intègrent les prix (par exemple les salaires, dans le cas du marché des médecins) dans les offres. Les algorithmes incluant les prix fonctionnent de manière similaire et produisent des appariements stables avec des caractéristiques assez similaires. En fait, l’appariement avec les prix est étroitement lié aux enchères, où des objets sont appariés avec les acheteurs et où les prix sont déterminants. La recherche qui relie les algorithmes d’appariement aux enchères a récemment généré d’intéressants résultats théoriques, qui semblent applicables en pratique. Les enchères sur Internet en sont un exemple, en particulier les moteurs de recherche qui mettent aux enchères des espaces pour les annonceurs publicitaires. Les entreprises du secteur ont bénéficié des intuitions inhérentes aux algorithmes de Gale-Shapley et ont fait appel à des économistes comme experts pour concevoir de nouvelles enchères.
Le prix de cette année récompense un champ de recherche florissant, où théorie, observation empirique et conception sont utilisées de manière interactive. Lloyd Shapley et Alvin Roth ont travaillé indépendamment l'un de l'autre, mais le succès de leurs travaux repose sur la combinaison des résultats théoriques de Shapley et des réflexions de Roth sur leur valeur pratique. Ce domaine continue de se développer et est très prometteur pour l'avenir. »
Académie royale des sciences de Suède, « Stable matching: Theory, evidence, and practical design », 15 octobre 2012. Traduit par Martin Anota
Aucun commentaire:
Enregistrer un commentaire