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 :

CD
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)
}

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.

2 commentaires:

  1. Salut les gars, comment j'ai retrouvé mon ex-mari, Fast, Dr.Padman a vraiment travaillé sur le lancer des sorts d'amour!
    Mon mari m'a quitté pour une autre femme il y a trois mois et depuis lors, ma vie a été remplie de douleurs, de chagrin et de cœur brisé, car il était mon premier amour avec lequel j'ai passé toute ma vie. Un de mes amis m'a dit avoir vu des témoignages d'un lanceur de sorts appelé Dr.Padman qu'il pourrait ramener son amant dans quelques jours. Je ris et dis que je ne m'intéressais pas mais à cause de l'amour que mon ami m'avait pour moi, elle a consulté le grand prêtre (padmanlovespell@yahoo.com) en mon nom et à ma plus grande surprise après 11 heures plus tard, mon mari m'a appelé pour la première fois après trois mois qu'il me manque et qu'il est désolé pour tout ce qu'il a m'a fait traverser.Il est revenu à moi et maintenant nous sommes heureux ensemble. Je ne peux toujours pas y croire, parce que c’est très incroyable. Merci Dr.Padman d’avoir ramené mon amant et également à mon cher ami qui a intercédé en ma faveur, pour tous ceux qui pourraient avoir besoin de l’aide de ce grand docteur, voici l’adresse email: (padmanlovespell@yahoo.com)

    RépondreSupprimer

  2. Bonjour je me prénomme nadia mère de 3 enfants. Je vivais à briouze avec mon mari, quand en 2018 il

    décida d'aller en voyage d'affaire à Bresil , où il tomba sur le charme d'une jeune vénézuélienne et ne

    semblait même plus rentrer. Ces appels devenaient rares et il décrochait quelquefois seulement et après du

    tout plus quand je l'appelais. En février 2019, il décrocha une fois et m'interdit même de le déranger.

    Toutes les tentatives pour l'amener à la raison sont soldée par l'insuccès. Nos deux parents les proches

    amis ont essayés en vain. Par un calme après midi du 17 février 2019, alors que je parcourais les annonce

    d'un site d'ésotérisme, je tombais sur l'annonce d'un grand marabout du nom ZOKLI que j'essayai toute

    désespérée et avec peu de foi car j'avais eu a contacter 3 marabouts ici en France sans résultât. Le grand

    maître ZOKLI promettait un retour au ménage en au plus 7 jours . Au premier il me demande d’espérer un

    appel avant 72 heures de mon homme, ce qui se réalisait 48 heures après. Je l'informais du résultat et il

    poursuivait ses rituels.Grande fut ma surprise quand mon mari m’appela de nouveau 4 jours après pour

    m'annoncer son retour dans 03 jours. Je ne croyais vraiment pas, mais étonnée j'étais de le voire à

    l'aéroport à l'heure et au jour dits. Depuis son arrivée tout était revenu dans l'ordre. c'est après

    l'arrivé de mon homme que je décidai de le récompenser pour le service rendu car a vrai dire j'ai pas du

    tout confiance en ces retour mais cet homme m'a montré le contraire.il intervient dans les domaines

    suivants

    Retour de l'être aimé
    Retour d'affection en 7jours
    réussir vos affaires , agrandir votre entreprises et trouver de bon marché et partenaires
    Devenir star
    Gagner aux jeux de hasard
    Avoir la promotion au travail
    Envoûtements
    Affaire, crise conjugale
    Dés-envoûtement
    Protection contre les esprits maléfices
    Protection contre les mauvais sorts
    Chance au boulot évolution de poste au boulot
    Chance en amour
    La puissance sexuelle.
    agrandir son pénis
    Abandon de la cigarette et de l'alcool

    voici son adresse mail : maitrezokli@hotmail.com vous pouvez l'appeler directement ou l 'Ecrire sur

    whatsapp au 00229 61 79 46 97

    RépondreSupprimer

Le prix de la baguette de 1954 à 2019

Le sujet n’en finit plus de faire débat : j’ai donc reconstruit une série du prix de la baguette (de 250g) en France (les données concernent...