Deux stratégies révolutionnaires en théorie des jeux (2/2)

monopolyLa semaine dernière, je vous ai raconté comment un petit malin avait réussi à hacker un jeu télé basé sur le principe du dilemme du prisonnier (ici). L’histoire était amusante mais difficilement généralisable.

Cette semaine, nous allons voir comment récemment, deux chercheurs ont véritablement réussi à hacker le dilemme du prisonnier, et ce d’une manière totalement inattendue [1].

Ils ont en effet mis en évidence des stratégies nouvelles aux résultats assez incroyables. Tellement incroyables d’ailleurs, que je n’y ai pas cru ! Et j’ai dû les programmer moi-même dans une rapide simulation pour me convaincre qu’elles marchaient vraiment comme annoncé.

Le dilemme du prisonnier répété

Pour comprendre ces stratégies découvertes par William Press et Freeman Dyson [1], il faut tout d’abord planter un peu le décor du problème qu’ils ont étudié. Il s’agit de ce qu’on appelle le dilemme du prisonnier répété.

Deux joueurs participent à un grand nombre de tours de jeu, et doivent à chaque tour choisir s’il collaborent ou trahissent. Le gain de chaque joueur dépend des choix effectués. Pour avoir une situation de dilemme du prisonnier classique, on prend par exemple les valeurs suivantes :

  • S’ils collaborent tous les deux, ils gagnent chacun 3 points;
  • Si l’un trahit et l’autre collabore, le traître gagne 5 et l’autre 0;
  • Si les deux trahissent, ils gagnent 1 chacun.

Pour maximiser leurs gains sur le long terme, les joueurs doivent mettre en place une stratégie qui favorise la collaboration, tout en punissant l’autre joueur si celui-ci s’avise de trop souvent trahir.

Puisque le jeu est répété, à chaque tour un joueur peut prendre en compte ce qu’il s’est passé dans les tours précédents pour décider de son coup. Cela permet en principe des stratégies très sophistiquées, mais Press et Dyson se sont placés dans le cas le plus simple : celui où les joueurs ne prennent en compte que ce qu’il s’est passé au tour précédent (je reviendrai plus loin sur cette apparente limitation.)

En pratique, avec ces hypothèses, la stratégie d’un joueur est complètement caractérisée par la donnée de 4 probabilités p1, p2, p3 et p4, telles que :

  • si au tour précédent les deux ont collaboré, le joueur collaborera avec une probabilité p1;
  • s’il a collaboré et l’autre a trahi, il collaborera avec une probabilité p2;
  • s’il a trahi et l’autre a collaboré, il collaborera avec une probabilité p3;
  • si les deux ont trahit, il collaborera avec une probabilité p4.

La magie du déterminant nul

Voici planté le cadre. Nous avons donc un premier joueur (appelons le « A ») dont la stratégie est décrite par des probabilités p1, p2, p3 et p4, et un deuxième joueur « B » dont la stratégie est différente et donnée par q1, q2, q3 et q4. La question que chacun se pose est donc : comment choisir au mieux ces 4 nombres ?

C’est là qu’intervient la découverte incroyable de Press et Dyson. Appelons G_A le gain moyen du joueur A après un grand nombre de tours, et G_B le gain moyen du joueur B. Prenons 3 nombres \alpha, \beta, \gamma quelconques, les deux auteurs ont démontré qu’il existait une relation

\alpha G_A + \beta G_B - \gamma = \Delta

\Delta est le déterminant d’une matrice 4×4, matrice qui dépend de \alpha, \beta, \gamma et des probabilités p_i et q_i choisies par les 2 joueurs.

La belle affaire, vous allez me dire !

Mais là où ça devient croustillant, c’est qu’il est possible de rendre nul ce déterminant, en jouant uniquement sur les 4 nombres p1, p2, p3 et p4. Imaginons que le joueur A choisisse effectivement des probabilités permettant d’annuler \Delta, on a alors :

\alpha G_A + \beta G_B - \gamma = 0

Cela veut dire que le joueur A, à lui tout seul, est capable d’imposer une relation linéaire entre son gain et celui du joueur B. Et rappelez vous : \alpha, \beta, \gamma peuvent être quelconques, donc A est en mesure d’imposer n’importe quelle relation linéaire ! … ou presque, voyons dans le détail ce qu’il est réellement possible de faire avec ces stratégies dites « de déterminant zéro ».

Contrôler le gain de l’adversaire

Reprenons le calcul précédent. Imaginons que l’on choisisse \alpha=0 et qu’on calcule p1,…,p4 pour annuler le déterminant. Cela veut dire qu’on impose la relation

G_B = \gamma/\beta

En clair, le joueur A, en agissant uniquement sur sa propre stratégie est capable de fixer le gain moyen du joueur B. Relisez bien ça car c’est pour moi incroyable : quelle que soit la stratégie de B, quelles que soient les probabilités q1, …, q4 qu’il choisisse, son gain est entièrement sous le contrôle du joueur A ! J’ai dû le programmer moi-même pour le croire, et ça marche !

En pratique toutefois, le joueur A ne peut pas faire complètement n’importe quoi. Il peut toujours choisir p1, … p4 qui annulent le déterminant, mais la solution n’est pas toujours telle que les 4 nombres soient entre 0 et 1. Si on fait le calcul dans le détail, on trouve qu’il existe des solutions telles que A peut imposer à B n’importe quel score entre 1 et 3 (c’est-à-dire entre le gain de la trahison mutuelle et celui de la collaboration mutuelle).

Le joueur A peut donc contrôler le gain du joueur B, très bien; mais est-ce qu’il ne pourrait pas plutôt essayer de contrôler son propre gain ? Ce qui serait quand même plus intéressant. Malheureusement ça ne marche pas ! Dans le cas général il n’existe pas de solutions p1,…,p4 entre 0 et 1 qui permettent à A de fixer son propre gain. Dommage !

Un inconvénient de cette stratégie, c’est donc qu’on contrôle le gain de l’adversaire mais pas le sien, et qu’on peut donc se retrouver à gagner moins que lui ! Heureusement il existe une solution : l’extorsion.

Extorquer l’adversaire

Si on reprend la formule faisant intervenir le déterminant, on peut aussi choisir les 3 nombres \alpha, \beta, \gamma de manière à imposer que le gain de A soit strictement supérieur au gain de B. En pratique, Press et Dyson ont montré que pour tout nombre \chi, le joueur A pouvait toujours choisir ses probabilités de manière à imposer :

G_A-1 = \chi (G_B-1)

Le nombre \chi est appelé facteur d’extorsion. Le -1 vient du fait que 1 est le en quelque sorte le minimum syndical correspondant au gain en cas de trahison mutuelle, mais tout ce qui est au-delà, le joueur A peut l’extorquer avec un facteur \chi.

Là aussi, il faut le voir pour le croire : ça marche ! Quoi que B choisisse de faire, son gain (au-delà de 1) sera toujours inférieur à celui de A d’un facteur \chi ! En pratique, les choix de B vont quand même fixer le niveau global des gains, mais le ratio entre les deux est totalement contrôlé par A.

Axelrod revisité

Si vous connaissez un peu le dilemme du prisonnier répété, vous savez peut-être qu’on considère traditionnellement que la meilleure stratégie est celle du « donnant-donnant », qui consiste simplement à répéter le coup de l’adversaire au tour précédent. Il a collaboré au tour précédent ? Vous collaborez. Il vous a trahit ? Vous trahissez !

axelrodCette stratégie est notamment fameuse pour avoir gagné le tournoi informatique organisé par Robert Axelrod dans les années 80, et qui faisait s’affronter tout un tas de stratégies proposées par différents spécialistes. (voir mon billet détaillé sur le tournoi d’Axelrod).

La stratégie « donnant-donnant » est à la fois très simple et intrinsèquement juste : elle ne trahit pas si l’autre collabore, et elle punit la trahison de l’autre mais sans rancœur, puisque sa mémoire ne va pas au-delà du tour précédent. La découverte de cette stratégie comme étant la meilleure a donc fait dire que finalement pour réussir, il valait mieux être juste et bienveillant que fourbe et manipulateur.

Eh bien figurez vous que deux chercheurs ont répété le tournoi d’Axelrod en incluant des stratégies de déterminant nul [2], et l’une d’elles (ZDGTFT-2) a battu toutes les autres, y compris « donnant-donnant » (TFT), voir le tableau ci-contre extrait de [2]. Cette stratégie gagnante est une stratégie d’extorsion généreuse, mais une stratégie d’extorsion quand même ! Morale de l’histoire : être machiavélique est quand même finalement plus lucratif !

Kramer contre Kramer

Tel que je l’ai décrit jusqu’ici, A fait un peu ce qu’il veut de B. Oui mais le jeu est symétrique ! Que se passe-t-il si B décide lui aussi de jouer une stratégie du déterminant nul ?

Première possibilité, les joueurs essayent mutuellement de fixer le gain de l’autre. Eh bien dans ce cas il n’y a pas de contradiction : le gain de A est entièrement déterminé par B, et celui de B entièrement déterminé par A ! C’est même une situation fort intéressante, car les deux joueurs peuvent passer un traité et se fixer mutuellement leurs gains à une valeur identique et maximale. Ce qu’il y a de bien, c’est qu’un joueur n’a aucune incitation à ne pas respecter le traité, puisqu’en le violant cela n’aurait aucune incidence sur son propre gain !

Autre cas de figure, les deux joueurs décident chacun d’extorquer l’autre d’un facteur \chi. Là évidemment, ça coince. Si on regarde le détail, on voit que dans ce cas les deux joueurs vont vers leur ruine mutuelle. En effet selon les calculs de Press et Dyson, la stratégie d’extorsion nécessite de fixer p4=0. C’est-à-dire que si j’ai trahi et l’autre aussi, au tour suivant je choisirai systématiquement de trahir. Vous voyez que si les deux joueurs appliquent cette stratégie, il vont rapidement se trouver dans une spirale infernale de trahison mutuelle.

Cela transforme le jeu de manière intéressante. Si le joueur A commence à appliquer une stratégie d’extorsion et que le joueur B s’en rend compte, il n’a que deux options : jouer le jeu et se laisser extorquer, ou faire de même et entraîner les deux dans la ruine mutuelle. Ce principe ramène le dilemme du prisonnier à ce qu’on appelle un jeu de l’ultimatum. Si le joueur B suit son propre intérêt uniquement, il doit accepter l’injustice pour maximiser son score; mais il a la possibilité de s’infliger lui-même des pertes, dans le seul but de faire pression sur A pour qu’il change de stratégie. Comme le font remarquer Press et Dyson, cela dépend si A a effectivement la possibilité de changer de stratégie, ou bien s’il a programmé sa stratégie et est parti ailleurs manger ou jouer au foot…

Billets reliés


Pour aller plus loin…

Si vous êtes curieux je vous invite à aller lire le papier directement. Un premier point intéressant à mentionner concerne le fait qu’avec cette stratégie on peut toujours manipuler un joueur « évolutionnaire », que les auteurs définissent comme un joueur capable de modifier sa stratégie (donc ses probabilités q1, …, q4) mais uniquement en fonction de son propre intérêt (c’est-à-dire en maximisant son gain, mais sans tenir compte de celui de l’adversaire).

Le second point à remarquer concerne l’apparente limitation à des stratégies n’ayant la mémoire que d’un seul tour. Press et Dyson (au fait, c’est bien le physicien Freeman Dyson !) montrent que même si un joueur A possède une stratégie élaborée prenant en compte les 42 tours précédents, alors si son adversaire B ne regarde lui que le dernier tour, tout se passe comme si A jouait une stratégie plus simple ne considérant que le dernier tour. En gros, le joueur ayant la mémoire la plus courte fixe les stratégies possibles. Rien ne sert d’avoir la mémoire longue si votre adversaire a la mémoire courte ! Je ne suis pas sûr de comprendre complètement leur démonstration, mais cela revient à dire que se limiter aux stratégies à mémoire à un tour…n’est pas une limitation !

Enfin pour ceux qui – comme moi – ont du mal à croire au fait que les stratégies de déterminant nul marchent vraiment, je vous invite à coder ça rapido. Ci-dessous mon bout de code Python…

Références

[1] Press, William H., and Freeman J. Dyson. « Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent. » Proceedings of the National Academy of Sciences 109.26 (2012): 10409-10413.

[2] Stewart, Alexander J., and Joshua B. Plotkin. « Extortion and cooperation in the Prisoner’s Dilemma. » Proceedings of the National Academy of Sciences 109.26 (2012): 10134-10135.

Crédits

Billets de monopoly, Anil Mohabir, Flicker CC

17 réflexions sur “Deux stratégies révolutionnaires en théorie des jeux (2/2)

  1. j’y comprends rien, mais c’est passionnant de voir comment des êtres de la même espèce que moi manipulent ces données, je suis admiratif, bon je reste sur le « marquage à la culotte » le jeu de mon adversaire au tour précédent…

  2. Bravo pour cette vulgarisation d’un sujet qui me paraît fondamental.
    Pas sûr que je vais me lancer tout de suite dans l’exploration Python du sujet, mais la tentation est grande et les références sont là … Merci !

  3. Pingback: Deux stratégies révolutionnaires ...

  4. C’est absolument hallucinant ! Merci pour cet article.
    Peut-être pourrait-on appliquer cette théorie du jeu à l’économie ?
    On dirait en ce moment qu’on va vers la ruine mutuelle, il va falloir changer de stratégie et mettre un déterminant nul, afin de maximiser les gains de tout le monde !

  5. Jean-Paul Delahaye a consacré un article à ce sujet dans le Pour la Science de janvier dernier (ici) et se montre très critique sur le résultat. En effet, remarque-t-il, il n’y a rien de remarquable à battre « donnant-donnant »: la plupart des stratégies un peu agressives y parviennent facilement. Or le but d’une stratégie n’est pas de battre ses adversaires,en combat individuel, mais de les contraindre à coopérer le plus possible! Et à ce jeu, les stratégies Extorqueurs sont très faiblement performantes lorsqu’elles sont face à elles-mêmes par exemple.

    Quand on les mélange à plein d’autres stratégies dans un « pool évolutif » où chaque stratégie s’affronte aux autres et se multiplie au rythme de ses gains, les stratégies Extoriqueurs dominent toutes les autres (elles gagnent chaque match individuel)… et disparaissent rapidement du jeu car leur score total est bien plus faible que donnant-donnant ou d’autres stratégies plus coopératives. C’est finalement une belle illustration de la « sélection de groupe »…

    En fin d’article se trouve une longue bibliographie qui s’accorde à trouver l’idée de Freeman et Dyson ingénieuse, mais pas aussi révolutionnaire qu’ils le pensaient…

    • Je viens de lire l’article de Delahaye, et j’avoue ne pas avoir compris initialement…car ce qu’il affirme est contradictoire avec le tournoi réalisé dans le papier [2] dont je cite les résultats : il existe des stratégies de déterminant nul qui battent bien « Donnant-donnant ».

      Il m’a fallu creuser pour trouver la supercherie !

      Évidemment, au dilemme du prisonnier en tournoi, le but n’est pas de gagner le plus de duels possible, mais bien d’amasser le plus de points en moyenne. Comme indiqué dans le tableau que j’ai recopié, les stratégies qui gagnent plein de duels (WINS, colonne de droite) sont en général celles qui gagnent le moins de points (SCORE, colonne de gauche). La stratégie « Toujours trahir » (ALLD) étant le cas extrême.

      Ce que montrent les auteurs du papier [2] (publié en accompagnement du papier de Dyson et Press), c’est que la stratégie EXTORT-2 est effectivement du même genre que « Toujours trahir », c’est-à-dire qu’elle gagne ses duels mais perd en score moyen. Et Delahaye l’a bien expliqué.

      Mais les auteurs de [2] affirment que la stratégie ZDGTFT-2 fait exactement le contraire ! Elle ne gagne aucun duel mais bat tout le monde en moyenne, y compris « Donnant-Donnant » ! (voir la colonne de gauche) C’est ce que je décris dans le paragraphe « Axelrod revisité ». Exactement le contraire de ce que dit JP Delahaye !

      Mais alors d’où vient le problème ? Il m’a fallut relire le papier [2] pour trouver la faille qui est bien cachée. La stratégie ZDGTFT-2 est bien une stratégie de déterminant nul, et les auteurs font comme si c’était une stratégie d’extorsion imposant la relation

      (G_A – R) = 2 (G_B – R)

      où R est le gain de la coopération mutuelle (dans le cas usuel, R=3)

      Donc on a envie de croire qu’il s’agit d’une extorsion d’un facteur 2 de tout gain qui dépasse 3. Sauf qu’il est impossible que le gain moyen des deux joueurs dépasse 3 !! Donc dans le cas général on a G_A<3 et G_B<3, donc il faut réécrire la formule ci-dessus en retournant les termes :

      (R – G_A) = 2 (R – G_B)

      C'est à dire que cette stratégie jouée par A impose que le gain de A soit toujours strictement inférieur à celui de B . C’est donc le contraire d’une stratégie d’extorsion, c’est une stratégie de sacrifice ! On fait en sorte de s’assurer que notre « adversaire » gagne plus que nous, et plus il se rapproche du score maximal, plus l’écart est faible entre nous deux.

      Et ça change complètement ma conclusion : pour gagner au dilemme du prisonnier, il ne faut pas être machiavélique et égoïste, mais machiavélique dans la générosité !

      • Oui je crois que tu as raison, c’est la conclusion de plusieurs articles. Celui-ci par exemple) conclut « les stratégies d’extortion ont d’excellentes performances en face à face, mais sont très médiocres lorsqu’elles sont incorporées à de grandes populations qui évoluent. En revanche nous avons identifié des stratégies très proches mais généreuses, qui coopèrent avec les autres et pardonnent les trahisons, et qui contrairement aux stratégies d’extorsion deviennent dominantes dans de larges populations. Ce résultat permet de mieux comprendre l’émergence de la coopération. »

        C’est drôle comme on passe d’un résultat déprimant à une conclusion radicalement optimiste! Personnellement j’en conclus surtout qu’il faut se méfier des tentatives qui tentent de dériver directement des comportements sociaux de maths pures 😉

      • Rien compris. Pour moi si la stratégie gagne ne gagne qu’entre un et trois alors elle joue le même coup que l’adversaire. C’est impossible à prévoir. De plus elle obtient les mêmes gains.

      • C’est amusant : je suis étudiant en écologie-évolution et cette stratégie, même si je n’ai pas tout compris, me rappelle beaucoup la sélection de parentèle, une théorie absolument passionnante qui a notamment expliqué l’apparition des comportement sociaux chez certains insectes (termites, fourmis, abeilles, etc…).

        Dans le cas de l’évolution, il faut se placer du point de vue du gène et le gain correspond au nombre de copie du gène, donc au nombre de descendants portant cette copie ET au succès reproducteur des descendants eux-mêmes.

        La sélection de parentèle nous dit alors qu’il peut être plus avantageux pour un parent d’optimiser la survie (et donc la probabilité de reproduction) de ses enfants plutôt que sa propre survie !
        Notez que dans le cas des hyménoptères (abeilles, guêpes, fourmis etc…) sociaux, l’altruisme est extrême puisque les individus sont stériles et optimisent la survie et le succès d’un seul individu, la reine !

        Voilà, petite contribution du biologiste ! Je note que cette découverte est relativement récente et, je ne sais pas si ça a été fait à l’époque, il aurait été intéressant au moment de la découverte de la sélection de parentèle (1964) d’avoir une collaboration entre théoriciens des jeux et biologistes de l’évolution, peut-être les solutions trouvées auraient pu être intuitées plus vite ! 🙂

        Mais bon j’ai peut-être rien compris et ma comparaison est donc totalement inappropriée ^^

  6. mais, est-e que ça n’implique pas que A soit capable de déterminer précisément les probabilités qi de B ? Et que ces dernières soit fixes ?

    Je veux dire, si l’on met en place un dilemme du prisonnier avec deux humains, et qu’ils jouent, mettons 30 fois d’affilée, est-ce que cette stratégie est applicable ? Ou bien n’est-ce que théorique ?

    Car la stratégie dont vous parliez la semaine dernière, est immédiatement applicable, elle (tu me trahis, je te punis, tu collabores, je collabores).

    • Non pour choisir ses probabilités p_i qui annulent le déterminant, le joueur A a juste besoin de connaître la matrice des gains. Donc la stratégie est applicable dès le début (voir l’exemple Python que je donne, où j’utilise la formule donnée dans le papier pour calculer les p_i, qui ne dépend pas des q_i).

      En revanche on voit que pour converger vers le score moyen, cela prend un certain nombre de tours. Ce qui n’est pas clair pour moi, c’est ce qu’il se passe si le joueur B fait bouger ses probabilités sur une échelle de temps caractéristique inférieure au temps qu’il faut pour converger…mais je dois pouvoir faire l’expérience !

      • Le joueur A a juste besoin de connaître la matrice des gains. Mais ne suppose-t-on pas que cette matrice de gain reflète la manière de jouer de B jusqu’à maintenant ? Et ainsi, des q_i ?

        Si B change de stratégie pour un tour donné, que se passe t-il ?

  7. Bonjour, je me suis permis de prendre votre code pour tester, et j’ai remarqué 2 petites erreurs.

    La première, c’est lorsque vous faites « total1/(n+1) » et « total2/(n+1) ». Si vous laissez comme ça, vous obtenez des entiers comme résultat (la machine tronque le résultat). Pour éviter cela, on peut mettre : « float(total1)/(n+1) » (de même pour total2)
    On obtient ainsi la bonne moyenne.

    La deuxième est la suivante : « prevDefect = curDefect » (dans la boucle for)
    Si vous copiez vos vecteurs comme cela, vous les « liez ». C’est à dire que lorsqu’à la boucle suivante vous modifier curDefect[0], cela modifie instantanément prevDefect[0] aussi.
    Pour éviter cela, on peut le remplacer par : « preDefect = list(curDefect)  »

    J’ai remarqué le second problème lorsque j’ai fait s’affronter notre méthode avec un « donnant-donnant » (ie: q1,q2,q3,q4 = 1,0,1,0). Le « donnant-donnant » répliquait directement et non au tour suivant.

  8. Pingback: Une stratégie infaillible au poker | Science étonnante

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s