La théorie des jeux

La vidéo du jour est une introduction à la théorie des jeux !

Il y a deux choses que je voudrais ajouter en complément, et qui concernent des stratégies possibles : la première à Golden Balls, et la seconde au dilemme du prisonnier répété.

(PS pour les habitués des lieux : je recycle de vieux billets sur le sujet)

Comment hacker Golden Balls ?

Avec Golden Balls, tout fonctionnait selon le plan prévu (par le producteur TV) jusqu’à ce qu’un petit malin trouve un moyen de hacker le jeu. Ce petit malin s’appelle Nick, et il s’est retrouvé un jour dans la phase finale du jeu contre un autre joueur appelé Ibrahim. Quand la phase de négociation (avant le choix des boules) a commencé, Nick a d’emblée annoncé :

Nick : – Ibrahim, je veux que tu me fasses confiance, à 100%, je vais choisir la boule STEAL (voler)

Ibrahim interloqué : – Pardon ? Tu vas prendre la boule…

Nick : – Je vais prendre la boule STEAL.

Puis Nick explique sa stratégie : – Je vais prendre la boule STEAL, je veux que tu prennes la boule SPLIT, et je te promets que je partagerai l’argent avec toi après.

Ibrahim est incrédule. Le public rigole. Le présentateur TV semble nerveux.

Puis Nick précise son idée. Il soutient mordicus que quoi qu’il arrive, il choisira de toute façon STEAL. Si Ibrahim choisit aussi STEAL ils repartiront tous les deux sans rien. Donc la seule chose raisonnable que puisse faire Ibrahim, c’est de choisir SPLIT, de laisser Nick empocher tout le magot, et de lui faire confiance pour que celui-ci partage après la fin du jeu.

S’ensuit une négociation interminable, et largement coupée au montage, mais qui paraît-il aurait duré 45 minutes.

Et voici ce qui arriva à la fin … (Nick est à droite, Ibrahim à gauche)

Sous la contrainte, Ibrahim a choisi de suivre le raisonnement de Nick, et a choisi SPLIT. Quant à Nick, … il a choisi SPLIT également ! Bien joué, non ?

Un point important à noter toutefois, c’est que Golden Balls n’est pas un véritable dilemme du prisonnier. Si vous comparez avec l’exemple que je donne dans la vidéo, vous verrez qu’il y a une petite différence dans les valeurs des gains. Ainsi si Golden Balls mimait véritablement le dilemme du prisonnier, on devrait avoir quelque chose comme

  • Si les 2 joueurs choisissent SPLIT, ils prennent chacun 50% du magot;
  • Si l’un choisit SPLIT et l’autre STEAL, ce dernier repart avec 80% du magot (et l’autre rien du tout);
  • Si les deux choisissent STEAL, ils repartent chacun avec 10% du magot.

Cette répartition des gains obéit à deux conditions qu’on ne retrouve pas dans Golden Balls : d’une part la collaboration est en moyenne strictement avantageuse (100% du magot est distribué contre 80% en cas de trahison par l’un des deux); d’autre part on gagne plus en faisant deux STEAL (10%) qu’en se faisant entuber (0%).

Je vous laisse y réfléchir, mais vous voyez que ces deux conditions invalident la stratégie de Nick ! Son argumentaire ne tient plus car d’une part le « je prends tout et on partage après » est moins avantageux qu’une collaboration directe; d’autre part si Ibrahim est sûr que Nick va voler, il a intérêt à voler aussi pour au moins repartir avec 10% du magot. La stratégie de Nick fonctionne donc parce que Golden Balls n’est pas un vrai dilemme du prisonnier, mais seulement une forme dite faible. Cette stratégie ne fonctionnerait pas avec la forme normale du jeu.

Les stratégies à déterminant nul

Pour ce deuxième complément, on va passer une vitesse supplémentaire et étudier une nouvelle famille de stratégies assez incroyables, proposée il y a quelques temps par deux chercheurs : William Press et Freeman Dyson (oui, le célèbre physicien !).

Ces stratégies concernent le dilemme du prisonnier dans sa version « répétée », et les auteurs se sont placés dans le cas le plus simple : celui où les joueurs ne prennent en compte que de 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.

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 ?

La magie du déterminant nul

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é

axelrod

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].

Mais un point qui n’était pas du tout clair dans la publication d’origine et que je n’ai exhibé qu’avec l’aide des commentaires d’un billet précédent, c’est le fait que la stratégie ZDGTFT-2 est en fait une stratégie d’anti-extorsion, une stratégie « de sacrifice » où l’on choisit au contraire de s’imposer un gain plus faible que l’adversaire.

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…

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.

20 réflexions sur “La théorie des jeux

  1. j’en suis encore à jouer à pile ou face… mais je suis sidéré de lire une telle analyse, je reste fasciné par le choix de Nick, sa force de persuasion et la réussite de son split ! bravo David.

  2. Pingback: La théorie des jeux — Science étonnante | Charentonneau

  3. Petite question :
    Si on organisait un tournoi (comme Nash si ma mémoire ne me fait pas défaut) où différentes stratégies s’affronteraient sauf que celles-ci joueraient également contre elles même, c’est à dire dans un cas où chaque stratégie serait représentée deux fois, les résultats changeraient sûrement. Et dans ce cas, quelle stratégie serait gagnante ?
    Extrêmement intéressant comme sujet soit dit en passant !

  4. Ne pourrait-on modéliser la lutte des classes comme un jeu à dix joueurs répartis en deux sous-groupes ? :
    – « classe dominée », composée de huit joueurs appliquant le donnant-donnant ;
    – « classe dominante », composée de deux joueurs appliquant le dominant nul, et se fixant mutuellement leurs gains à une valeur identique et maximale.
    La seule façon de supprimer la lutte des classes est de faire en sorte que les joueurs de la classe dominée passent du donnant-donnant au dominant nul, et que l’accord mutuel se réalise à dix.
    Le problème étant que si la règle du donnant-donnant est facile à comprendre, ce n’est par contre pas le cas du dominant nul …

    • Très bonne idée mais qui ne marche que dans un jeux à somme non nulle. Autrement dis, si dans ce cas tout le monde peut sortir gagnant en choisissant leur gains maximum sans que ça n’impacte les autres joueurs, dans la vraie vie, tout ce que tu gagnes, c’est ce que les autres n’auront pas. Les riches sont riches parcequ’il y a des pauvres.
      Le plus juste serait de trouver un équilibre de Nash mondial tel que personne ne pourrait espérer avoir plus que ce qu’il n’a déjà, malheureusement je ne pense pas qu’il existe.

      • Dans le contexte dynamique du développement économique le jeu des rapport de force entre classes n’est-il pas à somme non nulle ?

  5. J’avais un peu peur de visionner cette vidéo…
    La théorie des jeux, comme l’évolution Darwinienne, sont souvent (à tord) évoquées pour justifier les thèses utilitaristes anglo-saxonnes: Comme dirait le docteur House: « tous les humains cachent, sous un vernis altruiste, une profonde nature égoïste ». Ceci est bien connu de chaque téléspectateurs vivant au XIXème siècle.

    Et pourtant c’est faux!

    En étudiants de très jeunes enfants on s’est aperçu (assez récemment) que l’altruisme, la compassion (la gentillesse?) sont profondément ancrés en nous (ref: L’Essentiel Cerveau & Psycho N° 18 – Mai-Juillet 2014 « la morale? inée ou acquise? »). L’égoïsme serait nécessaire à chaque être vivant pour survivre mais la nature a doté certaines forme de vie d’une bonne couche de coopération. En particulier la plupart des humains privilégieraient l’altruisme (« par nature ») avant d’en changer éventuellement (« par culture »).

    Une autre réflexion; la théorie des jeux semble indiquer que les comportements des « joueurs » dépendent grandement des règles du jeu qu’on leur propose. Aussi si les réflexions des politiques n’étaient pas (auto)centré sur leurs intérêts propres mais sur celui de la collectivité (ne riaient pas!) , ne serait-ce pas le b.a.-ba de leur boulot que d’essayer de mettre en place des règles du jeu incitant la population a adopter des comportements vertueux (bénéfiques à tous) ?

    bref… Merci beaucoup pour cette très bonne vidéo!

  6. Merci pour ce billet et cette vidéo, que tout les professeurs d’économie devraient voir.
    Je trouve que la théorie des jeux est très souvent maltraitée dans le ouvrages d’économie….

  7. La manière dont les règles sont présentées n’auraient elle pas une influence significative? Je m’interroge sur le raisonnement de l’individu économique et sociologique. Je crois me souvenir dans un cours d’économie comportemental qu’on nous avait expliqué qu’il arrive souvent que des individus prennent des décisions différentes selon qu’on leur propose un gain ou une perte, quand bien même le résultat final est identique. On aurait donc une limitation assez claire de la théorie du jeu puisque l’influence culturelle et sociale et difficilement modélisable dans toute sa complexité.

    • Voir l’article précédent « risque et incertitude, théorie des perspectives » de notre hôte. Qu’il soit remercié pour le plaisir qu’il nous procure. (nb j’ai acheté son bouquin, le Bison de Higgs, je vous invite à faire de même)

    • Bien d’accord. L’homme possède une large part d’irrationnel en lui, biais cognitifs, influence culturelle…empêche de modéliser mathématiquement son comportement complètement. A la rigueur celui qui est capable de maîtriser au maximum le côté irrationnel et irrationnel de l’être humain possède le maximum de chance de dominer une situation (en commençant par soi), ce qu’arrive à faire ce malin anglais !

  8. Bonjour,
    Bravo pour cette vidéo qui sait mettre au niveau de tous un sujet mathématique pas si simple que ça ..; Mais ce message a aussi pour but de signaler une petite erreur dans la vidéo. Dans la comparaison antre la stratégie « Donnant/Donnant » et la « méchante », le premier coup de « Donnant/Donnant » doit être « C » et non « T » comme dans la vidéo …
    C’est ma petite coopération 😉

  9. Petit éclairage économique, dans le dilemme du prisonnier on oublie que dans le gagnant-gagnant il y a un perdant . tout comme le jeux télévisé. Dans le premier cas le perdant est le policier et dans le deuxième la chaine de télé. Si il y a gain pour l’un il y a cout pour un autre c’est la loi de l’économie. C’est pour ça que l’exemple du prisonnier est plus parlant que le jeux . ce qu’ils risque c’est une perte moindre une grande perte ou l’un une énorme perte pour l’autre rien. En soit c’est un exemple sociétal, en vase clos la coopération réduit la perte de temps, l’individualisme lui produit une absence de perte de temps pour l’un et une énorme perte de temps pour l’autre. Dans le sein d’une cellule familiale ou entrepreneurial la coopération est gage de gain pour le groupes et l’individu seul ça me coute 5 unités de temps en groupe une pour chaqu’un soit 2 unités au total donc un gain pour le groupe de 3 unités. dans le cas ou c’est le temps qui est a gagner la coopération est beaucoup plus évidente.

  10. Bonjour,

    bravo pour cette vidéo, excellente comme d’hab!!!
    Deux petite questions sur les stratégies dans le dilemme du prisonnier.
    D’abord tu dis que la stratégie donnant-donnant a gagné. Mais elle a gagné parmi les stratégies proposées… Est-ce que on a montré que cette stratégie est optimal en général?
    La seconde est peut-on vraiment dire qu’elle est meilleure que les autres? L’efficacité des méthodes proposées doit dépendre des répartitions des points. Si on avait choisit de ne pas trop pénalisé le vol, on aurait sans doute pu obtenir un résultat bien différent, non?

  11. Bonjour David,
    ta vidéo et ton billet m’ont rappelé de bons souvenirs d’un TIPE réalisé dans le prépa de Marc qui m’a d’ailleurs conseillé d’aller voir ton blog pour avoir quelques compléments. C’est mot pour mot le début de mon TIPE ! C’est comme ça que j’ai découvert ton blog que je suis assidûment depuis..!
    Dilemme du prisonnier itéré, Axelrod, évolutions de populations de stratégies, mutations de stratégies, déterminant nul… De bons souvenirs d’un sujet qui me plaît beaucoup et qui m’a valu une très bonne note aux concours !
    Bonne continuation !

  12. Génial, j’avais déjà lu des articles sur le sujet, mais là, la synthèse est complète.
    Une remarque : la stratégie donnant-donnant a un avantage sur la stratégie à déterminant nul : elle est très simple à mettre en œuvre, en particulier dans les situations de tous les jours où il est difficile de réduire les stratégies à un schéma simple, surtout si les situations évoluent vite.

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