« Un jour, un pianiste fût arrêté par la police secrète et accusé d’espionnage. Il portait des morceaux de papier couverts d’un code mystérieux. Malgré le fait qu’il persistait à déclarer qu’il s’agissait seulement des partitions pour la sonate du "Clair de lune" de Beethoven, le pauvre homme fut envoyé en cellule. Deux heures après, un sinistre individu vint l’interroger. "Il vaudrait mieux pour vous de tout nous dire, camarade", annonça-t-il avec un sourire en coin. "Nous avons attrapé votre ami Beethoven. Il est déjà en train de parler."
Cette histoire permet d’introduire le plus fameux problème en théorie des jeux : le dilemme du prisonnier. L’interrogateur explique que si un homme parle, mais pas l’autre, le premier sera libéré et le second sera envoyé pendant 25 ans au goulag. Si les deux hommes persistent à ne rien dire, ils vont chacun passer cinq ans en prison. Si tous les deux parlent, ils y passeront chacun 20 ans. Le dilemme est assez clair : chacun a individuellement intérêt à parler, qu’importe ce que fait l’autre ; pourtant, ils gagneraient collectivement à rester tous les deux silencieux.
Le dilemme a aujourd’hui soixante-dix ans. Il a été développé sous une forme mathématique simple en 1950 par les mathématiciens Merrill Flood et Melvin Dresher et sous une forme littérale par Albert Tucker. (…) Dresher, Flood et Tucker travaillaient au think-tank RAND. Le dilemme du prisonnier distillait la tension entre l’égoïsme et la coopération de façon éloquente, ce qui lui permettait d’illustrer le risque de destruction nucléaire et beaucoup d’autres choses. Le dilemme suscita une nouvelle vague d’intérêt en 1981, après la publication de The Evolution of Cooperation par le politologue Robert Axelrod et le biologiste William Hamilton. Leur article est non seulement le plus cité en science politique, mais il est en outre autant cité que les trois travaux les plus cités après réunis.
J’espère que les lecteurs m’excuseront de m’attaquer de la sorte à une idée si vénérée, parce qu’elle reste pertinente, instructive et largement incomprise. Une première idée très répandue, mais pourtant fausse, est l’idée que le problème est un problème de communication : si seulement le pianiste et Beethoven pouvaient se réunir et s’accorder sur une stratégie, ils se mettraient d’accord pour rester solidaires entre eux. Ce n’est pas le cas. La communication ne résout rien. Il est manifestement tentant de former une équipe ; donc la tentation de trahir aussi. Ceux qui croient que parler aiderait devraient regarder Golden Balls, un jeu télévisé basé sur un dilemme du prisonnier modifié. Ce qui rend le spectacle amusant à regarder est la vacuité des promesses que les participants se font les uns aux autres.
Plus problématique est la croyance erronée que le dilemme du prisonnier signifie que nous sommes condamnés à l’autodestruction du fait de notre égoïsme. La philosophie morale a désespérément cherché à le réfuter, à montrer qu’il est quelque peu rationnel de collaborer dans un dilemme du prisonnier joué une seule fois. Ce n’est pas le cas. Heureusement, la plupart des interactions humaines ne s’apparentent pas à un dilemme du prisonnier joué une seule fois.
L’article de 1981 (et le livre qui en fut tiré) peut avoir poussé la pendule trop loin dans le sens de l’optimisme. Le professeur Axelrod a lancé des tournois dans lequel des programmes d’ordinateur s’affrontaient les uns les autres, jouant le dilemme du prisonnier des centaines de fois. La répétition du jeu permet la coopération en raison de la menace de la sanction, quelque chose que les théoriciens des jeux savaient depuis les années cinquante. Quand Axelrod intégra cette idée dans un programme simple appelé "Tit for Tat", ce dernier triompha régulièrement contre les autres programmes.
Tit for Tat répondait à la coopération par la coopération et à la traitrise par la traitrise. Qu’importe ce que vous lui faites, il vous le fait également. Axelrod soulignait que le programme avait beau être "rude", il était "sympa", il essayait tout d’abord la coopération. Et il dressa de plus larges parallèles, en affirmant que le succès de la stratégie explique pourquoi les soldats dans les tranchées au cours de la Première Guerre mondiale étaient capables de se mettre d’accord sur des cessez-le-feu informels. Son message positif était que, dans les pires circonstances possibles, les gens sympas finissent premiers, pourvu qu’ils aient de l’acier en eux.
Mais cela va trop loin. Cette inclinaison à "vivre et laisser vivre" dans les tranchées s’explique peut-être plus simplement par le fait que ce n’est pas la même chose de tirer sur l’ennemi que de dénoncer Beethoven. C’est dangereux. On n’a pas besoin de la théorie des jeux pour expliquer pourquoi les soldats préfèrent faire profil bas. Axelrod a aussi donné trop d’importance à la "gentillesse" de Tit for Tat. D’autres stratégies prospèrent dans les tournois du dilemme du prisonnier, en fonction des détails des règles. Il y a parmi elles la stratégie "Pavlov", une stratégie qui essaye d’exploiter les "pigeons" et change de tactique quand elle rencontre une réponse punitive. Elle peut certes amener à la coopération, mais elle n’est pas "sympa".
Le dilemme du prisonnier existe. L’exemple le plus pressant aujourd’hui est celui du changement climatique. Chaque nation et chaque individu y gagneraient si les autres polluaient moins, mais chacun d’entre nous préférerait ne pas réduire sa propre pollution. Il serait stupide d’espérer que Tit for Tat permettrait de sauver la mise. Et nous n’avons pas à le faire. Nous avons des outils à notre disposition : au niveau domestique, les taxes et la réglementation ; au niveau international, les traités et les alliances. De tels outils modifient les incitations. Nous pouvons et devons les utiliser davantage. Le pianiste et son complice présumé étaient piégés. Nous ne le sommes pas. Contrairement à eux, nous pouvons changer le jeu. »
Tim Harford, « The prisoner’s dilemma at 70 – at what we get wrong about it », janvier 2020. Traduit par Martin Anota
Tag - théorie des jeux
lundi 24 février 2020
Le dilemme du prisonnier : célèbre, mais si mal compris
Par Martin Anota le lundi 24 février 2020, 17:00 - Epistémologie et histoire de la pensée
samedi 17 décembre 2016
La subversion méthodologique de Thomas Schelling
Par Martin Anota le samedi 17 décembre 2016, 10:42 - Epistémologie et histoire de la pensée
« Thomas Schelling est mort à 95 ans le 13 décembre 2016.
A une époque où la théorie économique devenait en quelque sorte une branche des mathématiques appliquées, il réussit à obtenir de profondes intuitions concernant un large éventail de phénomènes en s’appuyant seulement sur une observation fine des choses, un raisonnement précis et des modèles simples qui pouvaient être facilement décrits, mais qui possédaient des propriétés complexes et surprenantes.
Cela a trouvé un large écho. Mais son travail se caractérisait aussi par le fait qu’il tenait peu rigueur des normes méthodologiques dans sa profession. Cela lui permit de générer un nouveau savoir avec une grande liberté et d’apporter des innovations méthodologiques qui ont pu finir par être plus décisives que ses intuitions par rapport à la vie économique et sociale.
Considérons, par exemple, son fameux modèle du "damier" des voisinages autocréateurs, qui fut tout d’abord introduit dans un mémorandum en 1969, précisé dans un article en 1971, puis dans son livre Micromotives and Macrobehavior publié en 1978. Ce modèle est suffisamment simple pour être décrit littéralement en deux paragraphes, mais il a des propriétés qui sont extrêmement difficiles à déduire analytiquement. Il constitue également l’un des tous premiers modèles par informatique, il met en évidence quelques limites de l’approche de l’équilibre de la théorie économique et il continue d’aiguillonner la recherche empirique sur la ségrégation résidentielle.
Voici le modèle. Il y a un ensemble d’individus partitionnés en deux groupes (…). Chaque individu occupe un carré sur un damier et il a des préférences à propos de la composition de son voisinage. Le voisinage est ici composé (au maximum) de huit carrés adjacents. Chaque personne n’est pas insatisfaite à l’idée que son groupe soit minoritaire dans son quartier tant que le statut de minorité n’est pas trop extrême. Plus précisément, chacun désire qu’au minimum un tiers de ses voisins appartiennent à son propre groupe.
Initialement, supposons qu’il y ait 80 individus, disposés dans un ensemble de cases parfaitement intégré du damier, avec les quatre coins inoccupés. Ensuite, chaque individu au centre a dans son entourage immédiat autant de personnes appartenant à son propre groupe qu’au second groupe, si bien que chacun est satisfait. Ceux qui sont sur les bords sont dans une situation légèrement différente, mais même ici chaque individu a un voisinage dans lequel au moins un tiers des résidents appartiennent à leur propre groupe, si bien que chacun y est également satisfait.
Maintenant supposons que nous retirions au hasard vingt individus et que nous replacions cinq d’entre eux dans des logements inoccupés, également au hasard. Cette perturbation va rendre certains individus insatisfaits. Maintenant, choisissez l’un de ces insatisfaits et placez-le dans un endroit où il sera satisfait. Notez que cela va affecter deux autres types individus : ceux qui étaient précédemment les voisins des individus qui sont partis et ceux qui ont un nouveau voisin. Certains ne vont pas être affectés par le déménagement, d’autres peuvent gagner en satisfaction et d’autres risquent de devenir insatisfaits.
Aussi longtemps qu’il n’y a personne d’insatisfait sur le damier, vous répétez le processus que l’on vient de décrire : prenez un pion au hasard et déplacez-le à une case où il est satisfait. A quoi ressemble le damier lorsque plus personne ne veut se déplacer ?
Schelling a constaté qu’indépendamment de la fréquence avec laquelle ce processus se répéte, le résultat sera une forte ségrégation spatiale. Même si l’intégration parfaire est clairement une issue possible du processus dynamique que nous venons de décrire, elle est impossible à obtenir une fois que le système a été perturbé. Les préférences supposées sont suffisamment tolérantes pour être cohérentes avec l’intégration, mais les choix décentralisés, non coordonnés, que réalisent les individus fragilisent l’intégration et rendent la ségrégation extrêmement stable. Voici comment Schelling résuma son intuition :
"Les gens qui ont à choisir entre des extrêmes polarisés (…) vont souvent renforcer la polarisation à l’issue de leur choix. En agissant ainsi, ils ne démontrent pas qu’ils préfèrent la ségrégation, mais seulement que, si la ségrégation existe et qu’ils ont à choisir entre des associations exclusives, les gens choisissent les environnements qui leur sont les plus semblables."
Nous pouvons changer les paramètres du modèle, notamment la taille de la population, sa densité, les préférences à propos de la composition du voisinage et nous voyons que le résultat de Schelling est robuste. Et pour les raisons discutées dans cet essai, le seul raisonnement en termes d’équilibres ne peut être utilisé pour tomber sur ce résultat.
Nous pouvons également trouver un type de contribution très différent, mais qui a pourtant d’importantes implications méthodologiques, dans le classique La Stratégie du conflit (The Strategy of Conflict) de Schelling paru en 1960. Dedans, il considère la valeur adaptative qu’il y a à se prétendre irrationnel de façon à faires des menaces ou des promesses crédibles.
Comment pouvons-nous nous engager à l’avance à commettre un acte que l’on préférerait en fait ne pas avoir à réaliser, de façon à ce que notre engagement puisse dissuader l’autre participant ? La personne à l’origine de la menace peut bien sûr bluffer, pour faire croire à l’autre que les coûts ou dommages qu’il pourrait subir seraient mineurs ou négatifs. Chose plus intéressante, celui qui est à l’origine de la menace peut prétendre qu’il croit lui-même que ses coûts seront faibles, si bien qu’il serait prêt à mettre sa menace à exécution. Ou peut-être qu’il peut prétendre être tellement motivé par la vengeance qu’il se fiche des dommages qu’il pourrait subit ; mais cette option est surtout disponible pour ceux qui sont vraiment motivés par la vengeance.
De même, dans les situations de négociations, "le négociateur sophistiqué peut avoir des difficultés à se montrer aussi obstiné qu’un homme réellement obstiné". Et face à une menace, il peut être profitable d’être réputé comme faisant preuve d’"une véritable ignorance, obstination ou incrédulité, puisque cela permettra de se montrer plus convaincant face à toute personne susceptible de lancer une menace".
Suite à trois articles classiques dans le même numéro du Journal of Economic Theory paru en 1982, toute une littérature en économie a observé les implications pour le comportement rationnel qu’il y a à interagir avec des personnes qui, avec une faible probabilité, sont susceptibles d’être irrationnelles. Alors que ces travaux se sont surtout focalisés à caractériser les réponses rationnelles à l’irrationalité, Schelling parle aussi des gains et il soulève la possibilité que les écarts par rapport à la rationalité puissent avoir une valeur adaptative.
Les implications méthodologiques de cette idée sont profondes, parce qu'elle remet en question la justification habituelle qu’il y a à supposer que les agents économiques sont en fait pleinement rationnels. Jack Hirshleifer a exploré les implications de cette idée dans un fabuleux article sur la valeur adaptative des émotions et Robert Frank a écrit un livre entier sur le sujet. Mais l’idée est là, cachée sous nos yeux, dans les parenthèses de Schelling.
Enfin, considérons le paradoxe du cambrioleur que Schelling décrit dans La Stratégie du conflit : "Si, en pleine nuit, je descends l’escalier de ma maison avec un revolver après avoir entendu un bruit au rez-de-chaussée et que je me retrouve nez-à-nez avec un cambrioleur qui a également un révolver dans ses mains, cela risque de se finir en un dénouement qu’aucun de nous deux ne désire. Même s’il préfère juste s’en aller tranquillement et que je désire qu’il en fasse ainsi, il y a un risque qu’il puisse penser que je veuille tirer sur celui et qu’il tire le premier. Pire, il y a un risque qu’il puisse penser que je pense qu’il veuille me tirer dessus. Ou il peut penser que je pense qu’il pense que je veuille tirer sur lui. Et ainsi de suite. La 'légitime défense' est ambiguë lorsque l’on cherche juste à éviter de se faire tirer dessus en légitime défense."
Sandeep Baliga et Tomas Tomas Sjöström ont montré précisément comment une telle peur réciproque peut mener à un dénouement fatal et ils ont exploré les implications qu’il y a à permettre aux différentes parties de communiquer entre elles avant d’avoir affaire l’une à l’autre, même si cette communication n’engage à rien. (…) »
Rajiv Sethi, « Thomas Schelling, methodological subversive », 14 décembre 2016. Traduit par Martin Anota
lundi 22 août 2016
Comment l’équilibre de Nash a révolutionné la théorie des jeux
Par Martin Anota le lundi 22 août 2016, 16:00 - Epistémologie et histoire de la pensée
« John Nash est arrivé à l’Université de Princeton en 1948 pour commencer son doctorat avec une lettre de recommandation d’une seule phrase : "c’est un génie en mathématiques". Il n’a pas déçu. A l’âge de 19 ans et avec seulement un cours d’économie universitaire à son nom, il réalisa au cours des 14 premiers mois qui ont suivi l’obtention de son diplôme le travail qui finirait, en 1994, par lui faire gagner le "prix Nobel d’économie" pour sa contribution à la théorie de jeux.
Le 16 novembre 1949, Nash envoya une note plus grande qu’une page aux Proceedings of the National Academy of Sciences, où il développa le concept qui a depuis reçu le nom d’"équilibre de Nash". Ce concept décrit une situation stable qui résulte de personnes ou d’institutions prenant rationnellement des décisions en se basant sur ce qu’ils pensent que les autres vont faire. A un équilibre de Nash, personne n’est capable d’améliorer sa propre situation en changeant de stratégie : chaque personne fait aussi bien qu’elle le peut, même si cela ne se traduit pas par un dénouement optimal pour l’ensemble de la société. Avec d’élégants développements mathématiques, Nash montra que chaque "jeu" caractérisé par un nombre limité de joueurs, qui ne disposent chacun que d’un nombre limité d’options à choisir, présente au moins un tel équilibre.
Ses intuitions étendirent le champ de la science économique. Sur les marchés parfaitement concurrentiels, où il n’y a pas de barrières à l’entrée et où les produits de chacun sont identiques, aucun acheteur ou vendeur ne peut individuellement influencer le marché : personne ne va prêter attention à ce que les autres font. Mais la plupart des marchés ne sont pas comme cela : les décisions des rivaux et des clients importent. Des ventes aux enchères au marché du travail, l’équilibre de Nash donna à la science lugubre une manière de faire des prédictions dans le monde réel en s’appuyant sur l’information relative aux incitations auxquelles chaque personne est soumise.
Un exemple en particulier est souvent utilisé pour symboliser l’équilibre : le dilemme du prisonnier. Nash a utilisé l’algèbre et les chiffres pour décrire cette situation dans un article publié en 1951, mais la version qui est familière aux étudiants en économie est bien plus frappante. (…) Il implique deux truands placés dans deux cellules de prison séparées qui se voient accorder chacun la même proposition de la part du procureur. Si tous les deux confessent un meurtre sanglant, ils auront une peine de dix ans de prison. Si l’un des deux reste silencieux, tandis que l’autre le dénonce, alors ce dernier obtiendra une remise de peine, tandis que le premier sera emprisonné à vie. Et si tous les deux restent muets, alors chacun ne sera inculpé que pour un délit mineur et ne passera qu’un an en prison. Il n’y a qu’une solution dans le dilemme du prisonnier que l’on puisse qualifier d’équilibre de Nash : chacun balance l’autre. Pour chacun, c’est la meilleure réponse à la stratégie de l’autre ; comme l’autre peut avoir craché le morceau, le balancer assure d’éviter la prison à perpétuité. Ce dénouement est vraiment tragique : si les deux truands avaient pu mettre en place une certaine forme de coordination, ils auraient pu se retrouver au final dans une meilleure situation pour chacun.
L’exemple montre que les foules peuvent être aussi bien égoïstes que judicieuses ; ce qui est le mieux pour l’individu peut être désastreux pour le groupe. Cette issue tragique n’est que trop banale dans le monde réel. Libres de piller les mers, les individus vont pêcher bien plus que ce qui est optimal pour le groupe, ce qui entraîne l’épuisement des stocks de poissons. Si les salariés se font concurrence pour impressionner leur chef en restant travailler plus longtemps au bureau, la main-d’œuvre va s’épuiser. Les banques sont incitées à prêter plus qu’il n’est prudent de le faire lorsque les prix de l’immobilier explosent.
L’équilibre de Nash a aidé les économistes à comprendre comment des individus qui cherchent à améliorer leur situation peuvent former des foules autodestructrices. Qui plus est, il les a aidés à s’attaquer au problème : ils doivent juste s’assurer que chaque individu fait face aux meilleures incitations possibles. Si les choses vont toujours mal (par exemple, si les parents refusent de vacciner leurs enfants contre la rougeole), c’est peut-être parce que les gens n’agissent pas dans leur propre intérêt. Dans ce cas, le défi de la politique publique se situe dans le domaine de l’information.
L’idée de Nash avait des antécédents. En 1838, l’économiste français Antoine Augustin Cournot a théorisé ce qui se passera si, dans un marché avec où seules deux entreprises sont en concurrence, chacune voyait les désavantages qu’il y a à accroître sa part de marché en stimulant sa production : en l’occurrence, cela réduirait les prix et les profits. Involontairement, Cournot a donné un exemple d’équilibre de Nash. Il fait sens pour chaque entreprise de fixer ses niveaux de production en se basant sur la stratégie de ses concurrents ; les consommateurs, cependant, se retrouvent avec moins de biens et avec des prix plus élevés que si une concurrence à plein régime avait prévalu.
Le mathématicien hongrois John Neumann fut un autre pionnier. En 1928, l’année où Nash est né, von Neumann proposa une première théorie des jeux formelle, montrant que, dans les jeux à deux personnes et à somme nulle, il y aurait toujours un équilibre. Quand Nash partagea ses trouvailles avec von Neumann, qui était alors un demi-dieu intellectuel, ce dernier les considéra comme "triviales", en y voyant qu’une simple extension des siens. En fait, le fait que von Neumann se soit focalisé sur les jeux à deux personnes et à somme nulle n’offrait seulement qu’un ensemble très étroit d’applications pour sa théorie. La plupart d’entre elles étaient militaires. C’est le cas de la destruction mutuelle assurée, dans laquelle l’équilibre est atteint en armant les adversaires avec les armes nucléaires (certains ont suggéré que le personnage de film Docteur Folamour était basé sur von Neumann). Rien de tout cela n’était particulièrement utile pour observer les situations du monde réel, notamment la plupart des formes de marché, dans lesquelles la victoire d’un parti n’implique pas forcément la défaite de l’autre.
Néanmoins, les économistes partagèrent initialement l’avis de von Neumann et négligèrent largement la découverte de Nash. Ce dernier s’est lancé dans d’autres aventures mathématiques, mais les espoirs qu’elles nourrissaient s’effondrèrent lorsqu’en 1959 il commença à souffrir de délires et de paranoïa. (…) Alors même qu’il combattait sa maladie mentale, son concept d’équilibre devint de plus en plus central dans la discipline. La part des articles d’économie citant l’équilibre de Nash a été multipliée par sept depuis 1980, et le concept a été utilisé pour résoudre plusieurs problèmes de politique dans le monde réel. Un fameux exemple en est le système hospitalier américain, qui se trouvait dans les années quarante à un mauvais équilibre de Nash. (...)
L’équilibre de Nash n’aurait pas reçu son statut actuel sans quelques améliorations apportées à l’idée originelle. Premièrement, dans de nombreuses situations, il peut y avoir plus d’un équilibre de Nash. Les conducteurs choisissent sur quel côté de la route conduire en optant pour la meilleure réponse au comportement des autres conducteurs, avec des résultats très différents, en fonction de l’endroit où ils habitent ; ils roulent à gauche en Grande-Bretagne, mais à droite aux Etats-Unis. Au grand dam des économistes férus d’algèbre, la compréhension des stratégies nécessite de connaître les normes et habitudes sociales. Le théorème de Nash ne suffit pas.
Une seconde amélioration passe par la prise en compte des menaces non crédibles. Si un adolescent menace de fuguer si sa mère lui confisque son téléphone portable, alors il y a un équilibre de Nash où elle lui rend le portable pour maintenir la paix. Mais Reinhard Selten, un économiste allemand qui partagea avec John Nash et John Harsanyi le "prix Nobel d’économie" en 1994, affirmaie que ce n’est pas une issue plausible. La mère doit savoir que la menace de son enfant ne tient pas : qu’importe à quel point la perte d’un portable est tragique, une nuit dans les rues serait pire. Elle doit juste confisquer le portable pour forcer son fils à se focaliser sur ses devoirs.
Les travaux de Selten permettent aux économistes de restreindre le nombre possible d’équilibres de Nash. Harsanyi s’attaqua au fait que dans plusieurs jeux dans le monde réel, les gens ne sont pas sûrs de ce que leurs adversaires désirent. Les économistes auraient du mal à analyser les meilleures stratégies pour deux tourtereaux cherchant un lieu pour une date donnée sans avoir une idée de ce que l’autre préfère. En imbriquant les croyances de chaque personne dans le jeu (par exemple, la croyance que l’autre aime les pizzas autant que les sushis), Harsanyi rendit le problème solvable. Un problème différent persistait. Le pouvoir prédictif de l’équilibre de Nash dépend de la rationalité du comportement. Pourtant les êtres humains sont loin de toujours adopter un comportement rationnel. Dans les expérimentations répliquant le cadre du dilemme du prisonnier, environ la moitié des gens choisissent d’avouer. Pour les économistes qui se sont attelés à imbriquer la rationalité (et Nash) dans leurs modèles, c’est problématique. A quoi bon mettre en place les bonnes incitations si les gens n’agissent pas dans leur meilleur intérêt ? Tout n’était pas perdu. Les expérimentations ont aussi montré que l’expérience rend les joueurs plus avisés ; au dixième tour, seulement 10 % des joueurs environ refusaient d’avouer. Cela a amené les économistes à être plus prudents à propos de l’application de l’équilibre de Nash. Avec des jeux plus compliqués et des jeux où les joueurs n’ont pas la chance d’apprendre de leurs erreurs, ses intuitions ne marchent pas aussi bien.
L’équilibre de Nash joue toutefois un rôle central dans la microéconomie moderne. Nash est mort dans un accident de voiture en 2015 ; il avait alors retrouvé sa santé mentale, repris l’enseignement à l’université de Princeton et reçu un "prix Nobel" collectif pour avoir montré que les interactions au sein du groupe importent davantage que tout individu. »
The Economist, « Game theory: Prison breakthrough », 20 août. Traduit par Martin Anota