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

La théorie des jeux est un domaine des mathématiques qui étudie … les jeux ! Enfin certains types de jeux. Cette discipline a été inventée à l’origine non pas pour s’amuser, mais pour comprendre la manière dont des individus aux objectifs différents pouvaient se mettre à collaborer (ou pas).

On pensait depuis longtemps que l’on avait fait le tour des questions intéressantes concernant les jeux les plus simples, et que plus rien ne restait à découvrir. Eh bien ça n’est pas le cas !

Dans ce billet et le suivant, je vais vous parler de deux stratégies révolutionnaires pour « gagner » à ce jeu qu’on appelle le dilemme du prisonnier. La première est assez anecdotique et nous vient d’un jeu télévisé. La deuxième est beaucoup plus sérieuse et pourrait bien être en train de bouleverser le domaine.

Golden Balls

Non, Golden Balls n’est pas le nom du prochain James Bond Austin Powers, mais celui d’un jeu télévisé diffusé en Grande Bretagne entre 2007 et 2009. Le jeu est composé de plusieurs phases, mais la plus intéressante est la dernière : il ne reste que deux joueurs qui doivent se partager un magot, qui vaut en général quelques dizaines de milliers de £.

Pour effectuer le partage, chaque candidat dispose de deux boules : sur l’une est inscrit « SPLIT » (partager) et sur l’autre « STEAL » (voler). Chacun des candidats choisit secrètement une de ses deux boules :

• Si les deux choisissent SPLIT, le magot est partagé équitablement entre eux deux;
• Si l’un choisit SPLIT et l’autre STEAL, celui qui a choisit STEAL (voler) prend tout le magot (et l’autre se retrouve Gros-Jean comme devant)
• Si les deux choisissent STEAL, ils repartent tous les deux les mains vides

Bien sûr en moyenne, il vaudrait mieux que les joueurs collaborent et choisissent SPLIT tous les deux. Mais il y a la tentation de trahir pour empocher tout le magot !

Le plus drôle dans l’affaire, c’est qu’avant de faire leur choix, les joueurs disposent de quelques minutes pour discuter. Évidemment, chacun essaye de convaincre l’autre qu’il va choisir SPLIT. Les candidats jurent leurs grands dieux, ou sur la tête de leur caniche, que jamais ô grand jamais il ne vont trahir et choisir STEAL. De temps en temps, ça fonctionne et les deux choisissent de partager, mais ça arrive régulièrement que l’un entube l’autre, comme sur l’exemple ci-dessous :

[youtube=http://www.youtube.com/watch?v=p3Uos2fzIJ0&start=160]

Une nouvelle stratégie

Tout cela 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)

[youtube=http://www.youtube.com/watch?v=S0qjK3TWZE8&start=280]

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 ?

Les jeux à somme non-nulle

La phase finale de Golden Balls est un cas de ce qu’on appelle « les jeux à somme non-nulle« . Un jeu normal (comme disons le poker) est un jeu à somme nulle en ce sens que tout ce qui est gagné par X est perdu par Y et réciproquement. Il n’y a donc pas d’intérêt à collaborer. Dans la phase finale de Golden Balls, la somme d’argent totale distribuée dépend des choix respectifs des joueurs, il y a donc intérêt à s’entendre pour collaborer.

Les jeux de ce genre ont été très étudiés par les mathématiciens, les économistes et même les biologistes, car ils permettent de mieux comprendre dans quelles circonstances les individus peuvent se mettre à collaborer, ou au contraire à avoir un comportement égoïste.

Le jeu le plus classique s’appelle le dilemme du prisonnier (voir mon billet sur le sujet pour l’explication) et ressemble très fortement à Golden Balls. Mais dans les détails, 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.

Le dilemme du prisonnier répété

Dans Golden Balls, on ne joue évidemment qu’une seule fois. Là où les jeux comme le dilemme du prisonnier deviennent véritablement intéressants, c’est quand on joue plusieurs tours d’affilé, voire un grand nombre de tours, ce qu’on appelle le dilemme du prisonnier répété (ou itéré). C’est en effet ainsi qu’on peut voir dans quelle mesure les gens se font confiance, se trahissent, se punissent sur le long terme, et mettent en place des stratégies de coopération.

C’est dans ce contexte que la théorie des jeux a été largement étudiée par les biologistes, et notamment les spécialistes de l’évolution qui se demandaient comment des individus d’une même espèce pouvaient se mettre à collaborer, si trahir l’autre était toujours plus avantageux à court terme.

C’est ainsi que dans les années 80, Robert Axelrod a organisé un grand tournoi informatique pour faire s’affronter des stratégies du dilemme du prisonnier répété (voir mon billet détaillé sur le sujet) A la surprise générale, la stratégie gagnante s’est révélée extrêmement simple. Elle s’appelle « Donnant-Donnant », et consiste simplement à jouer la même chose que ce que votre adversaire a joué au tour précédent : s’il vous a trahi au tour précédent, vous le punissez en trahissant; s’il a collaboré au tour précédent, vous collaborez.

En moyenne, cette stratégie a battu toutes les autres. C’est intéressant car elle montre que la collaboration peut être avantageuse par rapport à des comportements strictement égoïstes. Et elle est d’autant plus séduisante qu’elle est juste et bienveillante : on n’essaye pas d’entuber l’autre s’il joue le jeu. Notez aussi que c’est une stratégie basée sur le pardon et l’absence de rancune : si l’autre m’a trahi 10000 fois mais qu’il se met à collaborer, je collabore !

Bref cela fait plus de 30 ans que la stratégie « Donnant-Donnant » semble l’indéboulonnable gagnante pour le jeu du dilemme du prisonnier. Mais tout cela est tombé à l’eau il y a quelques mois, avec la découverte d’une toute nouvelle stratégie qui montre que finalement, mieux vaut être machiavélique et manipulateur que juste et bienveillant…Je vous en parlerai la semaine prochaine !

Billets reliés, ici ou ailleurs

• Le dilemme du prisonnier : qu’est-ce que c’est et pourquoi on l’appelle comme ça
• Le tournoi d’Axelrod sur l’évolution de la coopération
• Ce billet est très largement inspiré de l’émission « What’s left when you’re right ? » de Radiolab

Crédits

• Jetons de poker, i-screame
• Split or Steal ? Extrait de la première vidéo