DILEMME ITÉRÉ DES PRISONNIERS


Le but de ce site est de collectionner les informations à propos du Dilemme Itéré des Prisonniers, et plus largement sur la représentation, l'étude, et les connaissances de la coopération (et de l'évolution de la coopération) entre agents.

Les informations présentées ici ont été rassemblées par l'équipe SMAC, appartenant au LIFL, dans le cadre d'un projet nommé PRISON. Le but de ce projet étant l'utilisation des outils informatiques afin de rassembler et d'étudier des données permettant de comprendre comment la coopération entre agents peut s'instaurer et être maintenue.

Sur ce site vous trouverez une présentation du Dilemme Itéré des Prisonniers Classique (DIP, ou CIPD), les articles publiés par les membres de l'équipe SMAC, des bibliographies à propos du dilemme des prisonniers, des logiciels de simulation, téléchargeables ou utilisables en ligne, ainsi que des liens vers des sites autour de ce sujet.

Mots clés : Dilemme (Itéré) des Prisonniers, Coopération, Vie Artificielle, Évolution, Théorie des Jeux, Système Multi-Agents


Sommaire

Nouvelles du site

[2004/11/02]
Nous sommes en complet désaccord avec la manière dont la compétition sur le dilemme du prisonnier a été faite lors de la conférence CEC'2004 et la manière dont cette compétition va être renouvelée lors de la conférence CIG'2005. Vous pouvez lire et signer notre position sur le concours et la manière dont certains s'attribuent et diffusent les résultats de cette compétition.
[1999/11/09]
Un concours sur le dilemme du prisonnier est organisé pour la conférence CEC'2000. Nous vous encourageons vivement à y participer !
[1998/11/26]
Ajout des sources des classes Java dans les distributions de jprison.
[1998/11/20]
Ajout du paquetage jprison.
Ajout des trois premières applets utilisant jprison.
[1998/11/19]
Ajout de la description de stratégies de bases.
[1998/09/25]
Le site est ouvert à la nouvelle adresse.
[1998/07/01]
La première version des applets est disponible.

[Retour au sommaire]

Le Dilemme Itéré des Prisonniers Classique

Un modèle formel de la coopération

Soit deux agents rationnels ayant le choix entre deux comportements :

Ils jouent l'un contre l'autre, de manière synchrone, de telle sorte qu'ils ne peuvent pas savoir ce que l'autre va jouer. Ils obtiennent alors un score dépendant de la situation de jeu :

La distribution classique des scores est (le score du joueur de ligne est donné en premier) :

CoopérationTrahison
Coopération R = 3
R = 3
S = 0
T = 5
Trahison T = 5
S = 0
P = 1
P = 1

Pour qu'il y est dilemme, la tentation doit payer plus que la coopération mutuelle, qui doit rapporter plus que la punition, qui doit être plus valorisante que la duperie. Ceci est formalisé par :

T > R > P > S

Comme la version en un coup du Dilemme des Prisonniers n'est pas très intéressante (le choix le plus rationnel est de trahir), le jeu est répété un nombre inconnu de fois.
Le jeu est dit itéré.
Le score final d'un joueur est la somme de ses scores à chaque itération.
Comme aucun des deux joueurs ne sait quand la partie va se terminer, il est alors possible d'étudier la stratégie de chaque agent, pour étudier, par exemple, comment ils essaient d'installer la coopération.

De façon à favoriser la coopération, i.e. l'intérêt commun face à l'intérêt individuel, l'inéquation suivante est respectée :

2 R > T + S

Avec cette restriction, les stratégies n'ont plus d'intérêt à alternativement coopérer puis trahir. Pour étudier le comportement des stratégies, deux types d'évaluations peuvent être faites.

[Retour au sommaire]

Quelques stratégies

Une description des quelques stratégies de base utilisées dans nos simulations ainsi que dans la littérature est donnée ici :
gentille
Coopère toujours. [c]*
méchante
Trahit toujours. [d]*
donnant_donnant
La stratégie donnant_donnant a été introduite par Anatole Rapoport. Elle commence par coopérer, puis joue ce que son adversaire a joué au coup précédent.
rancunière
Elle coopère jusqu'à ce que son adversaire ait trahi, après quoi elle trahit toujours.
majo_mou
Joue le coup majoritairement joué par l'adversaire, coopère en cas d'égalité. Le premier coup est considéré comme une égalité.
per_ttc
Joue périodiquement : [d,d,c]*
per_cct
Joue périodiquement : [c,c,d]*
méfiante
Trahit, puis joue ce que son adversaire a joué au coup précédent.
per_ct
Joue périodiquement [c,d].
pavlov
La stratégie gagne-reste/perd-change a été introduite par Martin Nowak and Karl Sigmund. Elle coopère puis coopère si et seulement si les deux joueurs ont joué la même chose au coup précédent.
tf2t
Coopère sauf si l'adversaire a trahi deux fois de suite.
tft_dur
Coopère sauf si l'adversaire a trahi au moins une fois dans les deux dernièrs coups.
tft_lent
Joue [c,c], puis si l'adversaire joue deux fois de suite la même chose alors joue le coup de l'adversaire sinon répète le coup précedent.
majo_dur
Joue le coup majoritairement joué par l'adversaire, trahit en cas d'égalité. Le premier coup est considéré comme une égalité.
lunatique
Coopère avec une probabilité de 1/2.

[Retour au sommaire]

L'équipe de SMAC

Aujourd'hui notre équipe est composée de chercheurs travaillant dans l'équipe SMAC du LIFL :

D'autres personnes sont, ou ont été, impliquées dans le developpement de nos travaux :

[Retour au sommaire]

Références

Les articles publiés par SMAC

Voici une liste exhaustive des articles écrits, et publiés par des membres notre équipe. Ils présentent nos idées, et résultats à propos de la coopération au travers du modèle du DIP. g

Articles en anglais

Articles en français

[Retour au sommaire]

Bibliographies

Bibliographie de SMAC

Une bibliographie complète de tous les livres et articles que nous avons est générée automatiquement chaque semaine, et est disponible ici.

Bibliographie d'Axelrod

Une bibliographie annotée sur l'Évolution de la Coopération a été écrite par Robert Axelrod et Lisa D'Ambrosio. Elle est disponible ici.
La version originale est à l'adresse suivante : http://pscs.physics.lsa.umich.edu/RESEARCH/Evol_of_Coop_Bibliography.html.

[Retour au sommaire]

Logiciels

En ligne

Vous pouvez essayez d'apprendre à utiliser et mieux comprendre le modèle en essayant nos applets.

Pour cela assurez-vous que votre navigateur soit capable d'éxécuter les programmes écrits avec le JDK 1.1.x (x > 5) et qu'il soit capable de dessiner les objets AWT.
Par exemple les navigateurs de Netscape ne sont capables de cela que depuis la version 4.06, de telle manière que nos applets ne fonctionneront pas avec des version plus anciennes.

Aujourd'hui vous pouvez essayer trois applets :

  1. La première vous permet simplement d'essayer des rencontres entre deux stratégies jouant au Dilemme Itéré des Prisonniers Classiques, de manière à apprécier le comportement des stratégies. Cliquer ici pour l'essayer.
  2. La seconde vous permet de tester des stratégies, jouant toujours au Dilemme Itéré des Prisonniers Classique, via des tournois, ou championnats, de telle sorte que vous comprendrez la méthode de base d'évaluation d'une stratégie. Cliquer ici pour l'essayer.
  3. La troisième vous permet de tester l'évolution de population d'agents jouant à n'importe quel jeu à deux joueurs que vous puissiez imaginer et définir par sa matrice de gain. Vous pouvez choisir la taille de chaque population, voir les résultats du tournoi ainsi qu'une représentation graphique de l'évolution de la population. Cliquer ici pour l'essayer.

[Retour au sommaire]

Autres produits

Nous avons produit de nombreux logiciels de simulations depuis le début de nos études sur le dilemme.

Voici une description de chacun de ces projets :
WINPRI
  • Ce programme se veut être une manière conviviale d'étudier le Dilemme Itéré des Prisonniers. Le but est de permettre à tous genres d'utilisateurs de faire des simulations sur la coopération et l'évolution de la coopération. Les stratégies sont choisies dans un ensemble prédéfinies, ou peuvent être créés en personnalisant des cadres génériques. Cet outil est celui qui doit être utilisés par les non spécialistes, comme par exemple dans le cadre d'un cours sur le dilemme, ou sur un autre jeux à deux joueurs, au sens de la théorie des Jeux.
  • Vous ne pouvez l'utiliser que sous Windows (3.x, 95, ou NT). Le programme est écrit en Visual Basic 3.0, et n'est donc pas aussi rapide que le programme PRISON.
  • Toutes les opérations se font graphiquement à la souris (photo d'écran).
  • Télécharger winpri.zip (315kb):
PRISON
  • Ce programme se veut être une manière optimisée, puissante et efficace de faire de grosses expériences, comme celles que nous faisons, sur le Dilemme Itéré des Prisonniers. Il est écrit entièrement en C, norme ANSI. Il permet d'écrire autant de nouvelles stratégies que ce que permet le langage C. Ne l'utilisez que si vous faites des expériences importantes ou si vous avez besoin de stratégies particulières.
  • Vous pouvez l'utiliser sur n'importe quelle plateforme ayant un compilateur C, norme ANSI, nécessaires pour modifier ou créer les stratégies. Si vous voulez interpréter vos résultats de manière graphique vous aurez besoin de GNUPLOT, avec lequel le programme est interfacé, sinon vous devrez traitez vous mêmes les résultats stockés dans des fichiers textes.
  • Toutes les opérations se font en mode texte et ligne de commande, mais sur les plateformes UNIX utilisant X/Window et le toolkit Xview, vous pourrez utiliser une interface appelée xprison (photo d'écran). Lisez le fichier README avant de télécharger quoique ce soit.
  • Télécharger :
JPRISON
  1. Le but de ce projet est d'offrir un ensemble de classes JAVA permettant de facilement créer des simulations du Dilemme Itéré des Prisonniers. Il est clairement dédié aux programmeurs ayant des connaissance en JAVA, mais est suffisament simple pour pouvoir être utiliser par des débutants. Tous les types de stratégies sont définissables. Les simulations ne sont pas limitées au Dilemme Itéré des Prisonniers Classiques, mais à tout jeu à deux joueurs dont on peut fournir une matrice de ain.Cet outil est celui qui doit être utilisépar ceux qui veulent définir leur propres simulations. Il peut aussi être utile pour des cours de programmation. C'est une librairie et non un programme.
  2. Vous pouvez l'utiliser sur n'importe quelle plateforme ayant une machine virtuelle JAVA. Il a été écrit entièrement en JAVA, et testé sur le JDK 1.1.x, avec x >5, de Sun. La puissance des simulations est directement liée à la puissance de votre machine virtuelle JAVA.
  3. Quelques exemples d'applets sont distribuées dans les archives, et sont disponibles sur le site dans la section précédente. Lisez le fichier README avant de télécharger quoi que ce soit. Les fichiers sources des classes ainsi que la documentation complète de l'API sont également distribuées dans les archives. La documentation est également disponible sur le site ici.
  4. Télécharger :
EVOLUTION
  1. Le but de ce projet est d'aider au calcul d'évolutions écologiques impliquant 3 stratégies à partir de matrices de gains prédéfinies. Les calculs peuvent être faits de 3 manières différentes (avec des nombres entiers, des réels, etc.)
  2. Il s'agit d'un feuille de calcul Micro$oft Excel 2000 utilisant quelques macros.
  3. Toutes les opération se font via l'outil Mico$oft Excel 2000.
  4. Télécharger :

Il est à noter qu'un nouveau programme, basé sur les idées de WinPri, et utilisant les classes de jprison est en cours de développement. Sa mise à disponibilité sera faite lors de la remise à jour du site. Connectez-vous donc fréquemment sur ce site pour rester informer.

[Retour au sommaire]

Contacts

Vous pouvez nous joindre par email à : prison@lifl.fr.

Vous pouvez également nous joindre par courrier à l'adresse suivante :

Philippe Mathieu - Responsable du projet PRISON
Laboratoire d'Informatique Fondamentale de Lille
Université des Sciences et Technologies de Lille
UFR IEEA - Bât M3
59655 Villeneuve d'Ascq Cedex
FRANCE

Nous pouvons également être joints par téléphone ou par télécopie à ces numéros :

Téléphone Télécopie
P. Mathieu :
03 20 43 45 04
B. Beaufils :
03 20 43 69 02
03 20 43 65 66

[Retour au sommaire]

Liens

Quelques liens sur le sujet sont regroupés ici.

[Retour au sommaire]

Financeurs

Le projet PRISON est soutenu par :

[Back to contents]

Cette page a été lue fois depuis
Valid HTML 4.0!

Copyright © 1998 by LIFL, <prison@lifl.fr>
Last modified: 1999/11/12 - 11:25