Le dilemme du prisonnier répété, une introduction

Si vous ne savez pas ce qu’est un dilemme du prisonnier, une rapide mise à niveau s’impose. Supposez, que deux joueurs qui ne se connaissent pas et n’ont aucun moyen de communiquer entre eux se voient proposer de participer à un jeu dans lequel ils ont le choix entre collaborer (C) entre eux ou faire défaut (D) sachant que :

• S’ils collaborent tous les deux, ils gagnent tous les deux $r$ points (mettons $r=3$) ;
• S’ils font défaut tous les deux, ils gagnent chacun $p$ points (mettons $p=1$) ;
• Si l’un des joueurs fait défaut tandis que l’autre collabore, il gagne $t$ points ($t=5$) tandis que son adversaire ne gagnera que $s$ points (par exemple, $s = 0$).

Si $t>r>p>s$ (ce qui est le cas dans l’exemple donné ci-dessus), nous avons un dilemme du prisonnier. Pour bien comprendre, on peut représenter le problème avec une matrice des paiements :

	C	D
C	[3,3]	[0,5]
D	[5,0]	[1,1]

Supposez que vous ayez à choisir une ligne entre collaborer (C) et faire défaut (D) et que, dans le même temps, votre adversaire va aussi choisir une colonne (C ou D) :

• Si vous choisissez tous les deux de collaborer (ligne C et colonne C), vous gagnez tous les deux 3 points ([3,3]) ;
• Si vous choisissez tous les deux de faire défaut (ligne D et colonne D), vous gagnez tous les deux 1 point ([1,1]) ;
• Si vous décidez de collaborer (ligne C) tandis que votre adversaire fait défaut (colonne D), il gagne 5 points et vous rien du tout ([0,5]) ;
• Dans le cas contraire, si vous faites défaut tandis que l'autre collabore, c'est vous qui gagnez 5 points et lui 0 ([5,0])

Ceci étant donné, considérez ceci : vous ne savez pas ce que va faire votre adversaire mais ce que vous savez, en revanche, c’est que quoiqu’il fasse vous avez matériellement intérêt à faire défaut. S’il choisit de collaborer (colonne C), vous gagnez 5 points en faisant défaut contre seulement 3 si vous collaborez aussi. Si, en revanche, il a décidé de faire défaut (colonne D), vous gagneriez 1 point en faisant également défaut contre 0 en collaborant. En théorie des jeux, on dit de la stratégie qui consiste à faire défaut dans un dilemme du prisonnier qu’elle est dominante : quels que soient les futurs états possibles du monde, vous avez matériellement intérêt à faire ça.

Ça, c’est la (triste) réalité quand on ne joue qu’une seule fois. La défection mutuelle est le seul équilibre de Nash possible (aucun joueur n’a intérêt à changer unilatéralement de stratégie) et rien ne permet d’espérer atteindre la situation optimale au sens de Pareto (une collaboration réciproque — [3,3] — qui permettrait d'atteindre un état dans lequel il est impossible de faire gagner plus à l’un des deux sans détériorer la situation de l’autre.)

Mais si le jeu est répété plusieurs fois avec les deux mêmes joueurs qui gardent en mémoire les coups joués précédemment, les choses deviennent plus intéressantes (et aussi beaucoup plus optimistes !).

Le dilemme répété

Pour bien comprendre, l'idéal c'est de simuler des stratégies et de voir comment elles s'en sortent si on répète le jeu plusieurs fois. Pour faire simple, je ne vais ici utiliser que des stratégies très simples — en l’occurrence celles évoquées par Nicky Case sur cet extraordinaire site que je vous recommande chaudement.

Pour donner un peu de substance à ce que je vous raconte, j’ai codé chacun de ces algorithmes sous forme de fonction R (si vous ne comprenez pas ce que je fais, voyez les notes en fin d'article) en respectant la structure suivante :

foo = function(p, o) {
 # faire quelque chose...
 return(res)
}

Où foo est le nom de la fonction (c'est-à-dire de l'algorithme, de la stratégie) considérée, p est la liste des coups joués par foo depuis le début de la partie (c'est une vecteur de logical ou booléens — c'est-à-dire une suite de TRUE pour coopération et de FALSE pour défaut), o est l'historique des coups joués par l'adversaire de foo durant cette partie (même format) et res est le coup joué par foo étant donné p et o (TRUE s'il coopère ou FALSE s'il fait défaut).

Commençons par alld, la stratégie dominante du dilemme du prisonnier joué une seule fois, celle qui consiste à faire systématiquement défaut (Always Cheat sur le site de Nicky Case) :

alld = function(p, o) {
 return(FALSE)
}

Évidemment, ça n’est pas très compliqué et les arguments (p et p) passés à ma fonction ne servent à rien puisque, par définition, alld fait tout le temps défaut, quoi qu’il arrive. Symétriquement, allc (a.k.a Always Cooperate), qui coopère tout le temps, s’écrit :

allc = function(p, o) {
 return(TRUE)
}

À peine plus compliquée, grudger, c’est la stratégie rancunière : elle coopère tout le temps jusqu’à ce que son adversaire la trahisse ; auquel cas elle fait défaut systématiquement jusqu’à la fin de la partie. Sous R, c’est très facile :

grudger = function(p, o) {
 res <- all(o)
 return(res)
}

Tit-for-Tat (a.k.a Copycat) commence par coopérer (quand la longueur de p est égale à 0, c’est-à-dire au premier round) puis, se contente de reproduire le coup précédent de son adversaire :

tft = function(p, o) {
 res <- ifelse(length(p) == 0, TRUE, tail(o, 1))
 return(res)
}

Tit-For-Two-Tats (a.k.a. Copykitten) est une variante de Tit-for-Tat qui coopère deux fois puis, ne fait défaut que si son adversaire a lui-même fait défaut lors des deux coups précédents (elle lui « pardonne » un défaut) :

tf2t = function(p, o) {
 r <- length(p)+1
 res <- TRUE
 if(r > 2) res <- ! all(! tail(o, 2))
 return(res)
}

Le « détective » est à peine plus compliqué : il coopère, fait défaut, coopère et coopère puis, si son adversaire ne se venge pas au 3ème tour, fait systématiquement défaut ou, dans le cas contraire, joue à Tit-For-Tat :

detect = function(p, o) {
 r <- length(p)+1
 if(r < 5) {
  res <- as.logical(r != 2)
 } else {
  res <- ifelse(o[3], FALSE, o[r-1])
 }
 return(res)
}

Win-Stay-Lose-Shift (a.k.a Simpleton or Pavlov) commence par coopérer puis, si son adversaire coopère à son tour, répète son dernier coup et change de stratégie dans le cas contraire :

wsls = function(p, o) {
 r <- length(p)+1
 if(r == 1) {
  res <- TRUE
 } else {
  res <- ifelse(tail(o, 1), tail(p, 1), !tail(p, 1))
 }
 return(res)
}

Enfin, pour mettre un peu de folie dans le jeu, voici Random qui coopère ou fait défaut de façon aléatoire avec une probabilité de 1/2 :

rand = function(p, o) {
 res <- sample(c(TRUE, FALSE), 1)
 return(res)
}

Ce qui nous fait donc 8 candidats que nous allons faire jouer les uns contre les autres lors de dilemmes du prisonnier répétés — mettons 10 fois pour commencer. Par exemple, si nous organisons une rencontre entre alld (Always Cooperate) et allc (Always Cheat), voici ce qu'il va se passer (si vous voulez vous amusez avec, voyez les notes à la fin)  :

> .match(alld, allc, 10)$S
       alld allc
 [1,] FALSE TRUE
 [2,] FALSE TRUE
 [3,] FALSE TRUE
 [4,] FALSE TRUE
 [5,] FALSE TRUE
 [6,] FALSE TRUE
 [7,] FALSE TRUE
 [8,] FALSE TRUE
 [9,] FALSE TRUE
[10,] FALSE TRUE

Forcément, alld fait tout le temps défaut et allc coopère systématiquement ce qui fait que, lors de ce match et en retenant la matrice des paiements données plus haut le premier gagne $5\times10=50$ points tandis que notre pauvre allc ne gagne rien. C'est le match le plus extrême dans l'univers des possibles.

Autre exemple, detect (le détective) contre grudger (le rancunier) :

> .match(detect, grudger, 10)$S
      detect grudger
 [1,]   TRUE    TRUE
 [2,]  FALSE    TRUE
 [3,]   TRUE   FALSE
 [4,]   TRUE   FALSE
 [5,]  FALSE   FALSE
 [6,]  FALSE   FALSE
 [7,]  FALSE   FALSE
 [8,]  FALSE   FALSE
 [9,]  FALSE   FALSE
[10,]  FALSE   FALSE

Ici, vous voyez le petit test de detect au second round — il fait défaut pour voir comment son adversaire réagit — et, en l'espèce, il n'est pas déçu puisqu'en face c'est grudger qui ne pardonne rien et se met immédiatement à faire défaut systématiquement. Résultat des courses : detect gagne $14$ points mais grudger l'emporte avec 19 points.

Enfin, dernier exemple, un des nombreux matches possibles entre tft (Tit-for-Tat ou Copycat) et rand (celui qui fait n'importe quoi) :

> .match(tft, rand, 10)$S
        tft  rand
 [1,]  TRUE FALSE
 [2,] FALSE  TRUE
 [3,]  TRUE FALSE
 [4,] FALSE FALSE
 [5,] FALSE FALSE
 [6,] FALSE  TRUE
 [7,]  TRUE FALSE
 [8,] FALSE  TRUE
 [9,]  TRUE FALSE
[10,] FALSE  TRUE

Ici, ils arrivent à égalité (22 points partout) mais vous pouvez surtout voir la stratégie de Tit-for-Tat à l’œuvre : il commence par coopérer mais, comme rand fait défaut, il lui répond dès le second tour et ainsi de suite.

Tournois

Et si, maintenant, nous organisions un tournois dans lequel chacun de nos algorithmes rencontrera tous les autres de telle sorte que nous puissions déterminer celui qui, en moyenne gagne le plus de points ? Commençons par un tournois en 10 rounds : chaque algo est confronté à chacun des autres lors d'un dilemme du prisonnier répété 10 fois.

Au premier tirage, voici le nombre de points moyen obtenu par chaque algo :

rand	20.429
allc	20.571
tf2t	23.000
detect	24.000
alld	24.857
wsls	25.286
tft	25.571
grudger	25.857

C'est donc grudger qui l'emporte devant Tit-for-Tat (tft) et, comme vous pouvez le voir, Always Cheat (alld), stratégie dominante dans le dilemme de base, n'arrive que 4ème. Pourquoi ? Eh bien tout simplement parce qu’il n’y a pas que ce pauvre Always Cooperate (allc) dans le jeu : il y a aussi des joueurs qui ne se laissent pas faire comme, justement tft ou grudger qui vont s’empresser de sanctionner ceux ne coopérèrent pas. Du coup, pour allc, ça se traduit par un maximum de matchs où il ne gagne qu’une misère.

Mais que ce passera-t’il si on augmente le nombre de rounds ? Qui va l’emporter dans un tournois où le dilemme du prisonnier est répété 20, 30 ou 40 fois ? Eh bien ce qu’il se passe, c’est que Tit-for-Tat, dans un dilemme du prisonnier répété, c’est comme l’Allemagne au foot : à la fin, c’est lui gagne. Avec ces concurrents-là, il est ultra-dominant dès une quinzaine d’itérations et il devient littéralement invincible quand on approche des 40 rounds. À part grudger et, dans une moindre mesure, Win-Stay-Lose-Shift (wsls), qui parviennent à remporter quelques tournois quand le nombre de rounds n’est pas trop élevé, les autres algorithmes de font étriller.

Qu’est ce qui explique le succès de Tit-for-Tat ? Eh bien il a 3 caractéristiques essentielles : (i) c’est une stratégie coopératrice (face à allc, grudger, tf2t et wsls, c’est une longue suite de coopérations sans la moindre anicroche), (ii) il n’est, pour autant, ni naïf (comme allc) ni trop gentils ( tf2t ) et (iii) il sait pardonner (contrairement à grudger). Et ça, manifestement, c’est une très bonne stratégie.

Notes

Principales fonctions R utilisées

La fonction all renvoie TRUE si tous ses arguments sont TRUE et FALSE dans le cas contraire :

> all(c(TRUE, TRUE, TRUE))
[1] TRUE
>

Mais :

> all(c(TRUE, FALSE, TRUE))
[1] FALSE
> 

La fonction ifelse renvoie sont 2ème argument si le premier est TRUE ou le 3ème dans le cas contraire :

> ifelse(TRUE, 1, 2)
[1] 1
>

Mais :

> ifelse(FALSE, 1, 2)
[1] 2
>

La fonction as.logical transforme son argument en vecteur logique (TRUE ou FALSE) :

> as.logical(0)
[1] FALSE
> as.logical(1)
[1] TRUE
>

Pour votre information :

> as.logical(15)
[1] TRUE
>

La fonction tail renvoie les n derniers membres de son premier argument :

> x <- 1:5
> tail(x, 3)
[1] 3 4 5
>

Et :

> head(x, 3)
[1] 1 2 3
>

La fonction sample sélectionne aléatoirement n membres de son premier argument :

> x <- 1:5
> sample(x, 3)
[1] 2 1 3
>

Par défaut, chaque élément a autant de chance d’être sélectionné que les autres mais vous pouvez aussi utiliser l’argument prob pour modifier ça.

Enfin ! indique la négation :

> !TRUE
[1] FALSE
> FALSE == !TRUE
[1] TRUE
>

Ma libraire sur Github

Tous les algos cités ci-dessus (et mêmes d'autres) ainsi que les fonctions .match (pour faire un match) et .tournament (pour organiser un tournois) sont disponibles sur Github.

Vous voulez jouer ?

Si c'est le cas, j'organise une petite compétition. Tous les détails sont sur Github (attention : je risque de modifier encore deux ou trois petites choses) et pour soumettre vos œuvres, utilisez ce lien.