La théorie des jeux constitue avec l'économie un vaste champ d'exploration de l'hypothèse de rationalité et des dynamiques engendrées par cette hypothèse. Pour ce qui est de la théorie des jeux, l'un des élements principaux d'analyse des jeux est la notion d'équilibre de Nash. Nous allons dans un premier temps donner un fondement à cette notion centrale à la théorie des jeux, pour ensuite présenter le dilemme du prisonnier et le domaine de la simulation comportementale qui s'est développé, en prenant comme principe dynamique la répétition de ce dilemme avec deux même joueurs, et en essayant de comprendre l'émergence de la coopération dans un cadre décentralisé.
Equilibre de Nash
Dilemme du prisonnier et dynamiques engendrées
Les résultats obtenus en simulation informatique
Bibliographie indicative
Définition
On va considérer que l'on est dans un le cadre d'un jeu à n joueurs, pour chaque joueur, on a une stratégie. L'ensemble des stratégies est donc un vecteur de dimension n, chaque joueur choisissant une stratégie au sein de l'espace de ses stratégies possibles. L'équilibre de Nash va se définir dans un environnement décentralisé, on parle de théorie des jeux non coopérative : dans cette théorie, il n'y a pas de négociation contraignant le comportement des agents a priori. Les agents n'ont pas de connaissances l'un sur l'autre à priori et aucun agent n'a d'assurance sur le comportement des autres.
Un équilibre de Nash est un vecteur de stratégies, ce vecteur est tel que, pour tout joueur, la stratégie qu'il choisit est la réponse optimale aux n-1 autres stratégies choisies par les autres joueurs.
Un équilibre de Nash va décrire un point où aucun joueur n'a intérêt à changer de stratégie puisque sa stratégie est optimale. Tant que l'on n'est pas à l'équilibre de Nash, il va y avoir au moins un joueur qui va avoir intérêt à changer de stratégie. L'équilibre de Nash joue le rôle d'un état attracteur pour le systeme qu'est le jeu. L'équilibre de Nash repose sur la notion de rationaliré totale puisque chacun ds joueurs va jouer la réponse optimale aux stratégies des autres tout en connaissant l'espace des stratégies de n-1 autres joueurs et en sachant qu'ils vont tenter d'obtenir le score maximal, comme on va l'illustrer dans l'exemple qui suit.Exemple et découverte de l'équilibre de Nash d'un jeu
Joueur 2 t1 t2 t3 Joueur 1 s1 (1,3) (1,0) (-1,-1) s2 (2,4) (1,1) (-1,-1) Dans les cases de cette matrice de jeu, sont indiqués les couples de gains (gain du Joueur 1, gain du Joueur 2). Les individus vont jouer simultanément, les si et les ti étant les stratégies que peuvent respectivement choisir le joueur 1 et le joueur 2. On cherche l'équilibre de Nash de ce jeu pour illustrer la notion. On part de la case (2,3), qui correspond aux stratégies s2 et t3 (on pourrait commencer sur n'importe quelle case) :
Chacun des deux joueurs va faire ce type de raisonnement indépendamment, ne disposant pas d'autres éléments (théorie des jeux non-coopérative) et les deux joueurs vont jouer le couple (s2,t1).
- Du point de vue du joueur 2, si il considère que le joueur 1 va conserver sa stratégie s2, il va jouer t2 (t2 lui apportera 1) plutôt que t3 (qui lui apporterait -1).
- En considérant le point (s2,t2), on voit que ce point n'est pas stable : si le joueur 1 n'a pas tendance à changer de stratégie puisque s1 lui apporterait le même score, le joueur 2 aura plutôt tendance à jouer t1.
- A partir de (s2,t1), aucun des deux joueurs n'a tendance à changer de stratégie si l'autre n'en change pas non plus : on a donc un équilibre de Nash sur ce jeu.
Remarques
- Certains jeux n'ont pas d'équilibre de Nash
- D'autres jeux ont plusieurs équilibres de Nash : c'est notamment le cas de beaucoup de jeux répétés, ce qui a conduit à la formation du "Folk's Theorem" qui implique que certains jeux répétés peuvent être interprétés de diverses façon. Sur l'exemple précedent, on peut noter qu'il n'y a qu'un seul équilibre de Nash.
- La notion d'équilibre de Nash renvoie, du point de vu mathématique, à des théorèmes de points fixes (Brower et Kakutani)
- La notion est-elle crédible au delà d'une perspective fonctionaliste, pour décrire les situations sociales ? Il semble que non, certains résultats obtenus en économie expérimentale montreraient que l'équilibre de Nash n'est pas la solution qui émerge d'une situation "réelle".
Le dilemme du prisonnier
La force de ce dilemme est l'expression de la force de la notion d'équilibre de Nash. Ce dilemme est central dans les développement de la théorie des jeux computationnelle qui a été initiée par Axelrod. Il concerne deux individus qui viennent d'être arrétés. Ils sont séparés et ne se sont pas coordonnés a priori (on reste dans le cadre de la théorie des jeux non coopérative). Chacun se voit offrir un choix : s'il avoue et dénonce son camarade, il ira 5 ans en prison si l'autre prisonnier a avoué lui aussi, sinon, il n'ira que 1 an en prison, si il choisit de se taire, alors, si il est dénoncé par l'autre prisonnier, il ira 8 ans en prison, si son camarade décide de se taire, les deux subissent 2 ans de prison. Cela donne la matrice de gains suivante :
Joueur 2 se tait dénonce Joueur 1 se tait (-2,-2) (-8,-1) dénonce (-1,-8) (-5,-5)
Le principe du dilemme du prisonnier est que chacun des prisonniers va avoir intérêt à trahir : si le prisonnier/joueur 1 pense que le prisonnier/joueur 2 va se taire, il a intérêt à le trahir. Le prisonnier 2 va inférer ce raisonnement du prisonnier 1 (rationalité parfaite) et va considérer qu'il va perdre beauoup à se taire et donc, il va décider de trahir. Comme les situations des deux prisonniers sont symétriques, les deux vont choisir de trahir : le point (dénoncer,dénoncer) est un équilibre de Nash pour le jeu du dilemme du prisonnier. Le dilemme du prisonnier montre que, sous certaines conditions, une solution émerge qui est n'est pas la situation qui aurait été préferée par tous les joueurs. En effet, la coopération, qui consistait en (se tait, se tait) est la situation de gain optimale, ou le gain total (gain du joueur 1 + gain du joueur 2) est le plus important. Le dilemme du prisonnier illustre le fait que l'organisation non coopérative, décentralisée et concurrentielle est suceptible d'aboutir à des situations non optimales.
Les dynamiques engendrées : le dilemme du prisonnier repété
Des dynamiques vont pouvoir être génerées à partir de ce dilemme : on considere deux joueurs pour lesquels on va répéter un certain nombre de fois la situation du dilemme du prisonnier, avec une contrainte sur les gains : le gain total des joueurs qui jouent (coopérer,coopérer) est toujours supérieur au gain global de toute autre situation. Une stratégie va se définir comme une série de choix coopérer/trahir dans sa forme extensive et comme une règle de décision générant ces choix à chaque coup, dans sa forme intensive (cette règle peut induire de l'aléa : on peut tirer au hasard le coup joué à chaque tour, mais elle sera la plupart du temps déterministe). Par exemple, si on suppose que deux stratégies sous forme extensive : une qui joue CCCTTCT face à une autre qui joue TCCTCCC, au premier tour (C,T) sera joué et les scores repectifs seront : (-8,-1), au deuxième tour (C,C) sera joué et le score sera (-2;-2), le score global donnant (-10,-3) etc... On peut donner des exemples de spécification de stratégie :
- Stratégie méchante : choisi trahir à chaque fois
- Stratégie gentille : coopére à chaque fois
- Stratégie aléatoire : tire son comportement au hasard
- Stratégie "tit-for-tat" : coopére au premier coup puis reproduit le dernier coup de son adversaire
La prochaine partie va développer les résultats qui ont été obtenus dans le cadre du modele dynamique qui vient d'être présenté.
Historique et premiers résultats
La théorie des jeux a d'abord été développée par Von Neumann et Morgenstern à la fin des années 40s. Nash a présenté l'idée de son équilibre dans les années 50s. Pour ce qui est de la question du modele dynamique basé sur le dilemme du prisonnier, son développement doit beaucoup à Axelrod [1]. Ce dernier s'est interrogé sur l'émergence de la coopération, et son maintien, dans le cadre du modele précedent ou chaque individu va chercher à maximiser son résultat.
Il a oganisé un tournoi invitant les gens à proposer des programmes, implémentant une stratégie comme celles décrites plus haut, dans le but d'obtenir une stratégie optimale. Un tournoi va fonctionner de cette façon : chaque stratégie joue pendant n tours contre chacune des stratégies, puis pour chacune des stratégies, on fait la somme des scores de ses duels, ce qui permet d'établir un classement des stratégies participantes au tournoi.
Axelrod a conclu sur les caractéristiques d'une bonne stratégie :L'auteur a conclu, à ce titre, à la superiorité de la stratégie tit-for-tat. Cette stratégie consiste à coopérer au premier coup et à jouer pour tout tour n (n>1), ce que l'adversaire a joué au tour précent. Cette stratégie va perdre face à une stratégie qui trahit tout le temps : en effet, elle obtiendra moins que cette stratégie au premier coup, puisque jouera coopératif alors que l'autre jouera trahir, mais elle ne perdra pas plus, puisqu'elle aussi se mettra à trahir à chaque tour. On peut noter qu'une telle stratégie est robuste et qu'elle gagne beaucoup des tournois qui sont organisés.
- la réactivité
- la bienveillance (la stratégie ne trahit pas la premiere, elle joue coopérer au tour 1 et tant qu'elle n'est pas trahie)
- l'indulgence (la stratégie doit pouvoir permettre que s'instaure de nouveau la coopération même si elle a été trahie)
- la simplicité
Résultats récents
Des travaux ont été développés par la suite sur cette question de la modélisation comportementale et de la robustesse du résultat de la supériorité de "tit-for-tat". Cette stratégie a été montré performante dans le cadre de simulations de type tournoi. Ce mode opératoire d'évaluation des stratégies est pourtant profondément problématique en cela que le classement obtenu sur un tournoi (stratégie1>stratégie2) pourra être invalidé par le classement obtenu sur un autre tournoi (stratégie2>stratégie1), en effet, si une stratégie s1 est favorable à la coopération, elle sera désavantagée dans un contexte de stratégies ayant tendance à trahir, obtenant alors un score moyen voire mauvais, alors qu'elle serait mieux classée face aux stratégies agressives dans un contexte comprenant les même stratégies agressives mais aussi des stratégies coopératives.
La recherche d'une stratégie optimale est en plus rendue complexe par le fait que l'on peut montrer qu'il n'existe aucune stratégie qui est meilleure que toute les autres. En effet, si une telle stratégie devait exister : elle devrait au moins faire jeu égal avec une stratégie qui trahi à tous les coups et donc, notre stratégie optimale devrait jouer trahir à la premiere itération du jeu, faute d'obtenir un moins bon score que ne l'obtiendrait une stratégie "traitresse". Parallèlement, pour être une stratégie optimale face à une stratégie qui coopére tout le temps, il faut définir une stratégie qui coopére au premier coup... Donc une stratégie optimale devrait à la fois trahir et coopérer au premier coup : une telle stratégie n'existe pas.
Les deux élements qui précèdent invitent à une reflexion sur la découverte de straégies performantes et non plus optimales. Dans cette optique, on va substituer à la méthode des tournois la méthode de la simulation d'une évolution de population où les individus sont des stratégies, avec des évolutions comparables à celles engendrées par des algorithmes génétiques. On va faire évoluer des classes de stratégies en provoquant des mutations sur les paramètres des sratégies au sein d'une classe. Des mesures de robustesse ont été développées et montrent que cette méthode est robuste : à savoir qu'une stratégie performante émergera comme telle même si elle est en petite minorité dans la population de départ[2][3]. Cette méthode a été inspirée par John Maynard Smith [4] qui a été un pionnier dans l'étude de l'application de la théorie des jeux à la biologie. Au final, dans ces évolutions, et dans le cadre de simulations de type tournois multipliées de façon exhaustives sur l'ensemble des configurations possibles pour neutraliser les conditions initiales, les auteurs vont arriver à certaines conclusions qui invalident pour partie les résultats initiaux d'Axelrod. La supériorité de certaines stratégies est avérée [3] :On voit que l'orientation change et que parmi les critères de bonne stratégie d'Axelrod, l'un d'eux est remis en question : la simplicité, puisque on dispose de stratégies plus performantes mais non pas simples, introduisant des aspects cognitifs tels la mémoire ou un début de représentation de l'adversaire.
- La stratégie graduelle : une stratégie qui va commencer par coopérer mais qui n'hésitera pas à punir son adversaire (ie à jouer "trahir"), les punitions s'alourdissant avec la répétition des trahisons de l'autre agent (la stratégie mettra plus longtemps avant de rejouer "coopérer").
- La stratégie "bad bet" qui va consister à disposer d'un certain nombre de stratégie et de sélectionner celle qu'on va considérer comme la plus appropriée apres une phase de test, ie une phase ou on tente de se faire une idée sur la façon dont joue l'adversaire.
Recherche Actuelle et persectives
On peut conclure cette présentation en parlant des développement futurs. Plusieurs voies s'ouvrent à partir des travaux qui viennent d'être évoqués :
- L'étude d'autres principes de base que le dilemme du prisonnier à l'origine de la dynamique.[5] Le dilemme de l'ascenseur est une version modifiée du dilemme du prisonnier : le gain total d'une situation coopérer/tahir sera supérieur à celui de coopérer/coopérer, de sorte que de nouvelles stratégies pourront émerger et un échange optimal entre stratégies ne sera plus (coopérer,coopérer) mais une succession de (trahir,coopérer), avec le problème de la coordination et des rôles qui se posent, les auteurs introduisant l'idée de méta-coopération dans ce cadre : les agents vont pouvoir accepter d'être trahis si ils savent qu(au prochain tour c'est la situation inverse qui se produira, un certain nombre des tours initiaux étant consacré à l'établissement de la méta-coopération.
- La prise en compte d'aspects topologiques sur la recontre des agents : ie le développement d'un modele de graphe sur lesquel les agents se répartissent, chaque noeud correspondant à une communauté, les arcs correspondant à des liens entre les communautés. Cette approche va permette d'étudier des simulations particulières en reflechissant notamment au rôle de la topologie dans les évolutions. Cette approche rejoint la thématique des topologies "small-world" notamment.[6][7]
Sur la théorie des jeux
BINMORE K. Jeux et théorie des jeux. ed. De Boeck Université 1999.
GIBBONS R. A Primer in Game Theory. ed. Pearson Education 1992.Sur la simulation comportementale informatique
[1] AXELROD. The Evolution of Cooperation. New York, USA : Basic Books 1984
[2] BEAUFILS. Dilemme Itéré des prisonniers et Vie artificielle. Rapport de stage de DEA 1995
[3] BEAUFIS. Modèles et simulations informatiques des problèmes de coopération entre agents. Thèse 2000
[4] SMITH J.M. Evolution and the Theory of Games. Cambridge University Press 1982
[5] DELAHAYE, MATHIEU. The Lift Dilemma or How to Establish Meta-Cooperation with your Opponent. Laboratoire d'informatique de Lille 1996.
[6] CASSAR. Coordination and Cooperation in Local, Random and Small World Natworks Technical Report, University of Santa Cruz, California 2002.
[7] WATTS, STROGATZ. Collective Dynamics of Small World' Networkspage 440-442