Les jeux répétés : quand l'avenir rend la coopération possible
Joué une seule fois, le dilemme du prisonnier pousse chacun à trahir. Mais deux voisins, deux entreprises ou deux pays se retrouvent jour après jour : trahir aujourd'hui, c'est risquer la vengeance demain. En 1980, le politologue Robert Axelrod organise un tournoi entre programmes informatiques, et c'est le plus simple, « donnant-donnant », qui gagne. Les théoriciens connaissaient déjà un résultat si répandu qu'on l'appelle le folk theorem, le « théorème du folklore » : quand l'avenir compte assez, presque n'importe quel partage des gains peut être un équilibre. Cette page fait jouer des matchs, reconstitue un tournoi, dessine les gains réalisables, calcule le seuil de patience et trace la région du folk theorem.
Les mots de la répétition
| Mot | Sens |
|---|---|
| Dilemme du prisonnier | Chacun choisit de coopérer (C) ou de trahir (D). Gains d'Axelrod : 3 chacun si les deux coopèrent, 1 chacun si les deux trahissent, 5 pour le traître et 0 pour la victime sinon. |
| Stratégie | Dans un jeu répété, une règle qui dit quoi jouer à chaque tour en fonction de ce qui s'est passé. |
| Facteur d'actualisation δ | Le poids du tour suivant par rapport au tour présent, ou la probabilité que le jeu continue. Plus δ est proche de 1, plus l'avenir compte. |
| Gain minimax | Le gain qu'un joueur peut toujours garantir, quoi que fasse l'autre : ici 1, en trahissant toujours. |
| Folk theorem | Tout gain moyen réalisable qui donne à chacun plus que son minimax peut être obtenu à l'équilibre, si les joueurs sont assez patients. |
Un match répété : deux stratégies face à face
Choisissez deux stratégies et faites-les jouer 200 tours, comme dans le tournoi d'Axelrod. Chaque tour, les deux joueurs choisissent en même temps C ou D, puis découvrent le choix de l'autre. Le bruit fait parfois jouer un coup à la place d'un autre, par erreur : une main qui tremble, un message mal compris. Observez comment une seule erreur peut déclencher une longue querelle entre deux « donnant-donnant ».
Le tournoi d'Axelrod en détail
En 1980, Axelrod invite des spécialistes à envoyer un programme. Quatorze programmes, plus un qui joue au hasard, s'affrontent tous deux à deux en matchs de 200 tours. Le vainqueur est le plus court de tous : donnant-donnant, envoyé par le psychologue Anatol Rapoport. Un second tournoi réunit 62 programmes venus de six pays, en sachant que donnant-donnant avait gagné : il gagne encore. La page reconstitue un tournoi avec douze stratégies classiques (cinq matchs de 200 tours par paire, y compris contre soi-même). Puis elle fait une expérience « écologique » : chaque stratégie se reproduit en proportion de ses points.
Les gains réalisables à long terme
À long terme, ce qui compte est le gain moyen par tour. Si les joueurs répètent un cycle, par exemple trois tours de coopération puis un tour où le joueur 1 trahit seul, le gain moyen est la moyenne des gains du cycle. En dosant les quatre issues possibles, on obtient tous les points d'un quadrilatère : l'ensemble des gains réalisables, dont les sommets sont (3, 3), (0, 5), (5, 0) et (1, 1). Personne n'acceptera pourtant moins que 1, puisqu'il peut toujours l'obtenir en trahissant : seule la partie au-dessus de (1, 1) est individuellement rationnelle.
Le seuil de patience δ
Un tour plus tard, un gain ne vaut plus que δ fois sa valeur : δ mesure la patience, ou la probabilité que la relation continue (Axelrod parle de « l'ombre de l'avenir »). Avec la stratégie rancunière, on coopère tant que l'autre coopère, et on trahit pour toujours dès sa première trahison. Coopérer rapporte R à chaque tour. Trahir rapporte T une fois, puis P pour toujours. La coopération tient si et seulement si δ ≥ (T − R) / (T − P), soit 1/2 avec les gains d'Axelrod. Pour donnant-donnant, il faut aussi résister à l'alternance de trahisons, d'où le seuil max[(T − R)/(T − P) ; (T − R)/(R − S)] = 2/3.
Le folk theorem dessiné dans le plan des gains
Quels gains moyens peut-on obtenir à l'équilibre ? On cherche des accords soutenus par la menace la plus dure : au premier écart, on trahit pour toujours, ce qui ramène chacun à son minimax 1. Les joueurs tirent au sort en public, à chaque tour, l'issue qu'ils vont jouer (par exemple (C, C) avec probabilité 3/4 et (D, C) avec probabilité 1/4). Pour chaque mélange, la page vérifie qu'aucun joueur ne gagne à s'écarter, compte tenu de δ. Quand δ approche de 1, la région remplit toute la zone verte de la planche 3 : c'est le folk theorem, démontré dans sa forme générale par Drew Fudenberg et Eric Maskin en 1986.
Ce qu'il faut retenir
La répétition change tout
La menace de représailles futures peut rendre la coopération rationnelle, même entre égoïstes.
Le seuil de patience
La coopération tient si δ ≥ (T − R)/(T − P) avec une punition éternelle ; plus la tentation est forte, plus il faut de patience.
Le folk theorem
Avec assez de patience, tout gain réalisable qui donne à chacun plus que son minimax est un équilibre : la théorie ne choisit pas.
Pour aller plus loin
Les conventions de la page. Gains d'Axelrod : T = 5, R = 3, P = 1, S = 0. Le tournoi de la planche 2 n'est pas celui de 1980 : c'est une reconstitution avec douze stratégies classiques, certaines présentes en 1980 (donnant-donnant, le rancunier de Friedman, Joss, le hasard), d'autres inventées plus tard (donnant-donnant généreux, Pavlov). Le « Testeur » vient du second tournoi. Dans la planche 5, la région est calculée exactement : pour chaque ensemble d'issues tirées au sort, on prend leur enveloppe convexe et on la coupe par les contraintes d'incitation vi ≥ 1 + (1 − δ)/δ × (gain de l'écart).
Références. R. Axelrod, « Effective choice in the Prisoner's Dilemma » (1980) et The Evolution of Cooperation (1984) ; J. Friedman, « A non-cooperative equilibrium for supergames » (1971) ; D. Fudenberg et E. Maskin, « The folk theorem in repeated games with discounting or with incomplete information » (1986) ; M. Nowak et K. Sigmund, sur donnant-donnant généreux (1992) et Pavlov (1993).
Pages voisines. Le dilemme du prisonnier, les jeux bayésiens, l'histoire de la théorie des jeux.