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
- [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.
Soit deux agents rationnels ayant le choix entre deux comportements :
- Coopération, que l'on notera C
- Trahison, que l'on notera T, ou
D de Defection en anglais.
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 :
- S'ils ont tous les deux coopéré, ils obtiennent chacun une
Récompense pour coopération, que l'on
évaluera à R points ;
- S'ils ont tous les deux trahis, ils obtiennent chacun une Punition
pour egoïsme, que l'on évaluera à P
points ;
- Si l'un a choisi de trahir et l'autre de coopérer, alors celui
qui a trahis se voit attribuer le score de la Tentation, que
l'on évaluera à T points, alors que celui qui a
coopéré se voit attribuer le Salaire de la dupe,
que l'on évaluera à S points
La distribution classique des scores est (le score du joueur de ligne est
donné en premier) :
| Coopération | Trahison |
| 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.
- Tout d'abord un simple tournoi, ou
championnat, dans lequel chaque stratégies
rencontrent toutes les autres stratégies. Le score final d'une
stratégie étant alors la somme des scores obtenu dans
chaque confrontation. ã la fin, la qualité de la
stratégie est simplement son rang dans le tournoi.
- Une manière plus complexe est inspirée de la nature :
l'évolution écologique, dans laquelle au
début une population fixe d'agents est divisée en
sous-populations, de taille identiques, chacune représentant une
stratégie. Un tournoi est effectué et les
mauvaises stratégies voient leur population
diminuées au profit des bonnes. La simulation est
répétée jusqu'à ce que la population totale
se soit stabilisée (pas de changement entre deux
générations). C'est de cette manière qu'il a
été découvert que les stratégies
méchantes, celles qui trahissent les premières,
n'étaient pas très stable, parce qu'elles pouvaient se
faire envahir par des gentilles.
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.
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 :
- Y. Leborgne, élève normalien, travaille
sur des recherches mathématiques autour d'une variation du
Dilemme Itéré des Prisonniers que nous avons mis au
point.
- F. Laveine, DESS, a participé à la
construction de l'interface graphique Xview du programme PRISON ;
- F. Grinion, maître ingénieur, a
participé au développement du programme WINPRI ;
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
- L'Altruisme perfectionné [ps.gz]
Jean-Paul DELAHAYE, Philippe MATHIEU
Publication interne du LIFL, numéro IT-249
- Expériences sur le Dilemme Itéré des
Prisonniers [ps.gz]
Jean-Paul DELAHAYE, Philippe MATHIEU
Publication Interne du LIFL, numéro IT-233
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.
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.
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 :
- 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.
- 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.
- 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.
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 :
prison.tar.gz (370kb)
prison.zip (390kb)
- JPRISON
-
- 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.
- 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.
- 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.
- Télécharger :
jprison.tar.gz (116kb)
jprison.zip (202kb)
- EVOLUTION
-
- 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.)
- Il s'agit d'un feuille de calcul Micro$oft Excel 2000
utilisant quelques macros.
- Toutes les opération se font via l'outil Mico$oft Excel 2000.
- 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.
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
|
Quelques liens sur le sujet sont regroupés ici.
Le projet PRISON est soutenu par :
Cette page a été lue (none) fois depuis
(none)
