Lloyd Shapley

L’appariement inattendu de Lloyd Shapley, une certaine Hélène et d’autres garçons

Jean-Edouard — 26/10/2012 – 14:12

Venons-en aux travaux des lauréats de cette année. Commençons chronologiquement par Shapley. Petite précaution : ce billet n’est pas du tout écrit dans l’esprit d’une future note de type « Repère » sur Shapley, qui arrivera en temps voulu (vers 2016 probablement).

Notons d’abord que pendant que je me débattais avec les problèmes informatiques du blog (et d’autres sans rapport mais peut-être plus importants) beaucoup d’excellents billets ont fleuri pour expliquer les travaux des nouveaux lauréats. Voir par exemple ceux de Gizmo et d’Alexandre Delaigue, pour n’en citer que deux.

Les économistes disposent d’une théorie pour étudier la formation des prix et les allocations de marché pour des biens fournis et demandés par un grand nombre de personnes depuis Hicks et Arrow-Debreu. Plus récemment, grâce à l’économie industrielle notamment, on en est arrivé aussi à peu près à comprendre comment les prix sont formés dans des marchés moins densément peuplés. Les Nobel de 2010 ont aussi étudié des marchés plus complexes où il faut chercher qui sont les vendeurs ou les acheteurs, et quels prix ils proposent. Les Nobel de cette année sont allés un peu dans les deux directions à la fois, en étudiant des marchés où les offreurs comme les demandeurs sont tous hétérogènes, ce qui leur donne en quelque sorte un pouvoir de marché. L’exemple typique en est le marché matrimonial : chaque individu y est unique et obtiendrait une satisfaction différente d’être en couple avec chacun des autres individus présents sur le marché. Les autres exemples classiques incluent l’allocation des chambres d’étudiants (surtout lorsqu’ils doivent être plusieurs par chambre), le marché du travail pour certains postes (typiquement, et au hasard, le recrutement des universitaires), le choix des écoles/collèges/lycées/universités, voire le don d’organes (voir plus bas). Tous ces marchés ont en commun que le choix des agents ne porte pas sur une quantité d’un bien homogène, mais sur quel(s) « partenaire(s) » choisir. De plus, bien qu’on puisse introduire des prix, il est intéressant de constater que bien souvent il n’y a pas de transferts monétaires (du moins immédiats) sur certains de ces marchés. Soit pour des raisons morales (don d’organes, marché matrimonial), soit typiquement parce que les prix fonctionneraient très mal, notamment pour les raisons mises en avant par les Nobel de l’année 2001 (un salarié qui accepte de travailler pour un salaire trop faible peut révéler qu’il n’a pas d’autre option, donc qu’il n’est peut-être pas très bon, et ne mérite peut-être pas même ce salaire faible).

1. Une théorie des séries dites romantiques

Gale et Shapley ont été les premiers à étudier ce type de situation dans un article célèbre de 1962. Je vais simplement donner un exemple basé sur le marché matrimonial. Ou plutôt ce marché tel qu’il est représenté dans certaines séries télé très populaires auprès des sœurs de futurs économistes des années 1990. La particularité des séries est de reposer souvent sur des hexagones amoureux, alors que les romans privilégient les triangles. Je n’ai pas de théorie plus générale de la géométrie amoureuse dans les différents produits culturels, mais l’hexagone convient fort bien à l’exemple. Soient donc trois femmes prénommées Hélène, Cathy et Johanna, et trois hommes prénommés Nicolas, Etienne et Christian, ayant tous des vues les uns sur les autres (comme souvent pour ne pas compliquer la théorie les préférences sont supposées strictement hétérosexuelles, mais on pourrait tout à fait introduire José). Supposons que l’on connaisse les préférences de chacun, notées avec des initiales :

H : N > E > Ch
C : N > E > Ch
J : N > Ch > E
N : H > C > J
E : H > C > J
Ch : H > J > C

Supposons que les couples se forment un peu au hasard des beuveries au gré des circonstances, et que temporairement on voie se former les couples H-Ch, C-E, J-N. S’il n’y avait qu’une seule chose à retenir de l’approche de Gale et Shapley, ce serait qu’ils posent la question suivante :

Est-ce que ces couples sont « stables » et que la série va s’arrêter là, ou au contraire va-t-il forcément y avoir au bout d’un moment des tromperies, des ruptures, des larmes etc. ?

Dans notre cas, on voit que Hélène se retrouve avec Christian, alors qu’elle aimerait mieux être avec Nicolas. Nicolas préfèrerait lui aussi être avec Hélène qu’avec Johanna. Il est donc impossible que notre combinaison tienne sur le long terme : après un certain nombre d’épisodes Hélène et Nicolas finiront forcément par quitter leurs partenaires respectifs pour aller l’un vers l’autre. Notre combinaison, ou « matching », était donc instable.

Si le spectateur est en général intéressé par les péripéties qui surviennent lorsque les combinaisons se font et se défont, l’économiste préfère s’interroger sur l’état de long terme du système, c’est-à-dire sur la situation qui devrait prévaloir à la fin de la série. Y a-t-il un ou des matching stables, et comment les trouver ?

La solution de Gale et Shapley est la suivante. Supposons que les hommes fassent une « proposition » (pas nécessairement indécente) de match à leur partenaire préférée. Si une femme reçoit une seule offre elle l’accepte temporairement, c’est-à-dire qu’elle se réserve le droit de revenir sur sa décision. Si une femme reçoit plusieurs offres, elle accepte temporairement celle qui lui plaît le plus, et rejette les autres. Les hommes qui ont vu leur offre rejetée font alors une proposition à la deuxième femme sur leur liste. Une femme qui n’a encore reçu aucune proposition accepte (toujours temporairement). Si elle a déjà reçu une proposition, elle peut en accepter une nouvelle si celle-ci lui semble meilleure, en quel cas elle signifie à son galant précédent qu’elle revient sur sa décision. Le galant en question devra alors lui-même soumettre une nouvelle offre. Le processus s’arrête quand aucun homme ne veut plus faire de nouvelle proposition.

Je remercie Gu Si Fang pour ce lien, qui illustre comment fonctionne l’algorithme. C’est dommage qu’ils ne permettent pas d’entrer les préférences des différents agents, je n’aurais pas eu à tout faire à la main.

Appliquons ce mécanisme à notre exemple. Au premier tour de propositions les trois hommes contactent H. Devant ces trois offres, H rejette Ch et E et accepte temporairement N. C et J sont sur la touche, mais Ch et E ont été repoussés. Ch fait alors une offre à J, et E une offre à C. Les deux jeunes personnes acceptent, puisqu’elles n’ont pas encore d’offre. Plus personne ne fait d’offre, et on vérifie facilement que notre algorithme aboutit a une situation stable : C et J ne voudraient quitter leur partenaire que pour N, mais N préfère rester avec H, tandis que E et Ch ne voudraient quitter leur partenaire que pour H, qui préfère rester avec N.

Considérons un autre exemple intéressant :

H : N > E > Ch
C : E > Ch > N
J : Ch > N > E
N : C > J > H
E : J > H > C
Ch : H > C > J

Appliquons le même algorithme, en supposant que les hommes fassent les propositions. N se déclare à C, E à J et Ch à H. Chaque femme, ne recevant qu’une offre, l’accepte temporairement. Chaque homme voit son offre acceptée, donc le processus s’arrête là. On a bien un matching stable : comme chaque homme a sa compagne préférée, il est impossible qu’une femme arrive à changer la situation. Mais supposons maintenant que ce soient les femmes qui prennent l’initiative. On arrive alors à une situation différente : H avec N, C avec E, J avec Ch. Là encore c’est un matching stable : chaque femme est avec son partenaire préféré, les hommes ne peuvent pas changer la situation.

On a là un résultat très important. Il est tout à fait possible que plusieurs matchings soient stables. Lorsque les hommes proposent, le matching sera optimal pour les hommes. Lorsque les femmes proposent, le matching sera optimal pour les femmes. Dans cet exemple extrême, dans le premier cas chaque homme a sa partenaire préférée et au contraire chaque femme celui qu’elle aime le moins, et inversement dans le deuxième cas. C’est intéressant à garder en tête si on se demande pourquoi dans beaucoup de cultures c’est traditionnellement aux hommes d’exprimer leurs intentions. Mais c’est très intéressant aussi pour comprendre certains marchés : sur le marché de l’emploi par exemple c’est en général, hors situation de plein emploi en tout cas, l’employeur qui fait des offres, tandis que pour les inscriptions dans divers établissements d’enseignement le mécanisme revient in fine a ce que les établissements fassent des propositions. Emmeline suggère que c’est en général le côté le moins peuplé qui fait les offres, autrement dit un certain « pouvoir de marché » déterminerait le mécanisme de matching utilisé.

2. Un problème de mensonge et de vidéo

Les lecteurs assidus du blog se souviendront peut-être que nous avions fait référence à Shapley dans ce billet sur un sujet apparemment sans rapport, en introduisant le concept de la valeur de Shapley. La raison en est que le mécanisme de Gale et Shapley est fortement inspiré par la théorie des jeux coopératifs, dont Shapley est le grand représentant, et ne satisfait pas forcément aux critères de la théorie des jeux non coopératifs dont il est plus souvent question sur ce blog.

Plus concrètement, le mécanisme de Gale et Shapley peut conduire à supposer que les agents ne se comportent pas en suivant un équilibre de Nash, ce qui a longtemps été considéré comme très problématique (voir le billet suivant sur Roth et les liens entre jeux coopératifs et non coopératifs). L’illustration requiert d’introduire de nouveaux agents, que nous appellerons Adeline et Sébastien. Supposons maintenant les préférences suivantes :

H : N > E > Ch > S
C : N > Ch > E > S
J : N > E > S > Ch
A : Ch > S > E > N

N : A > J > C > H
E : A > H > J > C
Ch : H > C > A > J
S : C > H > A > J

Supposons encore que ce soient les hommes qui fassent les propositions. Au premier round N et E font une offre à A, qui accepte celle de E, H accepte l’offre de Ch, et C l’offre de S. N et J se retrouvent tout seuls. Au tour suivant, N passe au deuxième nom sur sa liste, qui est justement J, et l’algorithme se termine. On aboutit à N-J, E-A, Ch-H, S-C.

Mais supposons maintenant que Adeline soit diaboliquement intelligente et choisisse d’accepter l’offre de N. Je dis diaboliquement, parce que pour accepter N elle rejette une offre de E, qu’a priori elle préfère. Ce petit mensonge a priori anodin va permettre de générer au moins deux saisons complètes d’une série romantique exigeante. Au premier round on aboutit dans ce cas aux paires N-A, Ch-H, S-C, et c’est E qui se retrouve tout seul. E passe au second nom sur sa liste, qui est H. H préfère E à Ch et accepte donc l’offre de E. On a donc les couples N-A, E-H, S-C et c’est Ch qui se retrouve tout seul. Au round suivant Ch fait donc une offre à C, qui accepte avec enthousiasme de quitter S. On a alors N-A, E-H, Ch-C et c’est S qui se retrouve tout seul. Celui-ci fait une offre à H, qui préfère rester avec E. S doit alors se rabattre sur A, ce qui est exactement ce que celle-ci attendait depuis le début ! A quitte N qu’elle déteste pour S, et on se retrouve donc avec E-H, Ch-C et S-A. N fait une offre à J qui est seule depuis le début et commence à trouver le temps long, celle-ci accepte, et l’algorithme s’arrête.

Résultat des courses : on aboutit à un autre matching stable (celui qu’on aurait eu en laissant les femmes prendre l’initiative à vrai dire), dans lequel A finit avec S au lieu d’être avec E si elle avait dit la vérité (ou plus précisément respecté les règles du mécanisme). Or justement A préfère S à E, elle avait donc tout intérêt à agir stratégiquement ! Cet exemple suffit à montrer que le comportement prêté aux agents dans le mécanisme de Gale et Shapley n’est pas un comportement d’équilibre au sens de Nash.

L’exemple, que j’adapte de la documentation fournie par le comité Nobel, est un peu tordu je l’admets. Mais cela revient tout simplement à un bon vieux raisonnement du type « je préfère l’emploi / la femme / l’homme / la classe prépa / la formation A à l’emploi / la femme / l’homme / la classe prépa / la formation B, qui serait toujours mieux que le boulot pourri / la peste / le beauf / le redoublement / le stage de sécurité routière C. Je m’attends à ce que A soit très demandé, alors que je peux avoir B en agissant plus vite que les autres. Donc je tente ma chance d’abord avec B pour éviter C. »

3. Interprétation : les jeux coopératifs

Pour beaucoup d’économistes cette faiblesse du mécanisme de Gale-Shapley a sans doute été vue comme très importante. D’ailleurs une grande partie des travaux de Roth, dont il sera question dans un prochain billet, a consisté à étudier dans quelle mesure cette faiblesse se présentait en pratique, et à montrer que dans bien des cas elle était en fait assez secondaire, ce qui a relancé l’intérêt pour cette approche.

Cette attitude a peut-être étonné Gale et Shapley, parce qu’a priori leur point de départ était entièrement différent. Rappelons-nous que l’idée de base était de trouver des situations « stables », l’aboutissement des intrigues amoureuses de notre série télévisée, et pas du tout de proposer un mécanisme pour accélérer le dénouement ! Le mécanisme n’est qu’un outil pour calculer la situation finale, vérifier s’il en existe une ou non, étudier ses propriétés etc. Les éventuelles faiblesses stratégiques du mécanisme ne sont des faiblesses que si on essaie de se servir en pratique de ce mécanisme théorique, ce qui est très différent. On touche ici aux débats sur l’épistémologie et l’usage de la théorie des jeux, analysés notamment dans cette note d’Emmeline.

Selon moi, théorie des jeux coopératifs et théorie des jeux non coopératifs devraient être vues comme complémentaires. Pour une petite introduction à la théorie des jeux coopératifs, voir ce billet. Les tenants de la première reprochent à la seconde que les résultats dépendent beaucoup trop des règles exactes du jeu étudié et ne sont donc pas robustes. Les partisans de la seconde reprochent à la première que l’hypothèse « coopérative » est en général beaucoup trop forte, et que de plus, comme souvent en théorie des jeux, le terme est mal choisi en ce qu’il suggère une opposition avec l’hypothèse de rationalité plus ou moins égoïste que les économistes utilisent en général.

De mon point de vue, lorsqu’un économiste calcule un équilibre de Nash dans un jeu donné, il répond à la question « étant données des institutions, un cadre économique particulier, vers quelles stratégies les agents vont-ils finir par se tourner et quel sera le résultat ? ». Lorsqu’il calcule une valeur de Shapley ou un autre concept coopératif, il répond davantage à la question « en supposant que sur le long terme les institutions conduisant à des situations inefficaces sont modifiées, quelles sont les allocations possibles qui soient compatibles avec le pouvoir de négociation de chacun ? ». Autrement dit pour moi la théorie coopérative est un peu le très long terme là où la théorie non coopérative est le moyen-long terme. Shapley est la personne qui pourra vous dire sur quels appariements possibles une série télé peut s’arrêter si vous lui décrivez en cinq minutes les préférences des personnages (ce qui est très utile pour les scénaristes, qui savent quoi éviter pour se garder des rebondissements possibles). En revanche si vous passez plusieurs heures à expliquer un théoricien non-coopératif tous les détails de la série il sera beaucoup plus à même d’en prévoir les développements à moyen terme.

Pour un autre aspect de la concurrence entre les deux approches, voir aussi ce billet, en anglais mais intéressant quand même, cité par Rationalité Limitée.

Licence Creative Commons – Auteur:Jean-Edоuard Cоlliard

Be the first to comment

Leave a Reply

Votre adresse de messagerie ne sera pas publiée.


*