# Avons nous toujours besoin de stochasticité pour la simulation évolutionnaire ?

Philippe Mathieu, Jean-Paul Delahaye

► To cite this version:

Philippe Mathieu, Jean-Paul Delahaye. Avons nous toujours besoin de stochasticité pour la simulation évolutionnaire ?. Trente-deuxièmes journées francophones sur les systèmes multi-agents (JFSMA), Nov 2024, Cargese (Corse), France. pp.171-180, 10.5802/roia.57.pdf. hal-04777147

HAL Id: hal-04777147

https://hal.science/hal-04777147v1

Submitted on 12 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Avons nous toujours besoin de stochasticité pour la simulation évolutionnaire ?

Philippe Mathieuª

Jean-Paul Delahayeª

philippe.mathieu@univ-lille.fr

jean-paul.delahaye@univ-lille.fr

ªUniv. Lille, CNRS, Centrale Lille, UMR 9189, CRISTAL, F-59000 Lille, France

## Résumé

Pour évaluer et comparer des stratégies au dilettre itéré du prisonnier diverses méthodes sont utilisées. Il existe trois catégories principales : les méthodes par tournois, les méthodes évolutionnaires déterministes, et les méthodes évolutionnaires stochastiques. La question que nous abordons ici est de savoir si les méthodes stochastiques sont vraiment utiles et si elles permettent une meilleure modélisation du monde réel conduisant à un classement plus fin des stratégies comparées. Nous mettons en œuvre trois méthodes stochastiques différentes et montrons qu'aucune ne conduit à des résultats sensiblement différent des méthodes déterministes, et donc qu'il est inutile de les utiliser. Une série de courbes et de graphiques prouvent visuellement notre conclusion, qui est renforcée par un calcul massif conduisant à un dendrogramme où apparaît nettement la grande proximité des classements entre méthodes déterministes et méthodes stochastiques à la fois dans le cas individualiste et dans le cas communautaire. Onze méthodes de classement sont comparées que le dendrogramme regroupe en trois catégories bien nettes, chacune contenant au moins un modèle déterministe représentatif de la catégorie.

**Mots-clés** : Jeux itérés, Evaluation, Stratégies d'agents, comportements

## Abstract

Various methods are used to evaluate and compare strategies to the iterated prisoner's diletternum methods, deterministic evolutionary methods and stochastic evolutionary methods. The main question we address is whether stochastic methods are really useful, and whether they provide a better model of the real world, leading to a more refined ranking of the strategies. We implement three different stochastic methods and show that none of them leads to significantly different results from deterministic methods, and that there is therefore no point in using them. A series of curves and graphs visually prove our conclusion, which is reinforced by a mas-

sive calculation leading to a dendrogram where the great proximity of rankings between deterministic and stochastic methods is clearly apparent in both the individualistic and community cases. Eleven ranking methods are compared, and the dendrogram groups them into three clear-cut categories, each containing at least a deterministic model representative of the category.

**Keywords:** Iterated games, Evaluation, Agent's Strategy, Behavior

## 1 Introduction

L'évaluation du comportement des agents dans un SMA et la classification de leurs performances est un problème fondamental dans la communauté. Nous l'étudions ici dans le cadre formel de la théorie des jeux itératifs et plus précisément dans le cadre du dilemme itéré du prisonnier (DIP). Ce modèle a fait l'objet de nombreuses études et de travaux de recherche dont le point de départ est l'article de Robert Axelrod et William Hamilton [4]. Sans chercher à être exhaustif on peut mentionner [1, 2, 3, 5, 8, 9, 10, 11, 17, 18]). Cet article fait suite à [6, 7]<fnref n="1" /> dont nous adopterons les notations et conventions.

Dans ces deux articles nous proposions 4 méthodes de classement pour un ensemble de stratégies donné<fnref n="2" />.

* la méthode par tournoi individualiste ClaT(Ind). Une rencontre généralisée est opérée entre toutes les stratégies de l'ensemble considéré conduisant chaque stratégie à gagner des points, dont on tire un classement.

* la méthode par tournoi communautaire ClaT(Com). Une rencontre généralisée est opérée entre toutes les stratégies de l'ensemble considéré mais en ne faisant pas se rencontrer les stratégies de la même catégorie (ce qui rendient à modéliser l'idée que les stratégies en

<footnote n="1">1. https://roia.centre-mersenne.org/item/10.5802/roia.57.pdf</footnote>

<footnote n="2">2. Les simulations numériques de ces expériences peuvent être reproduites à l'aide du code https://github.com/cristal-smac/ipd</footnote>
compétition se regroupent en communautés s'opposant les unes aux autres). On obtient à nouveau un classement.

* la méthode évolutionnaire individualiste déterministe *Det(Ind)*. La population initiale de stratégies subit une évolution où génération après génération les stratégies de la génération N ont un nombre de descendants proportionnels au nombre de points gagnés lors d'un tournoi individualiste entre les stratégies de la génération N, ce qui fixe les effectifs de la génération N+1. À l'issue de l'évolution, on obtient des effectifs pour chaque type de stratégies (c'est-à-dire pour chaque communauté) dont on tire un classement.

* la méthode évolutionnaire communautaire déterministe *Det(Com)*. Même principe que précédemment en remplaçant individualiste par communautaire.

Une autre méthode déterministe sera considérée ici :

* la méthode par tournoi-victoires (Vict). Une rencontre généralisée est opérée entre toutes les stratégies de l'ensemble considéré conduisant chaque stratégie à gagner des points qui sont donnés par la règle : +1 si victoire ; -1 si défaite ; 0 en cas d'égalité. On en tire un classement.

Les conclusions de l'étude étaient que :

1. les méthodes par tournoi ne donnent pas de résultats très satisfaisants car elles favorisent les stratégies très agressives qui ne sont pas robustes en cas d'interactions prolongées;

2. les méthodes évolutionnaires sont bien meilleures et produisent des résultats significatifs, conformément aux résultats classiques (dont ceux d'Axelrod[4, 2]);

3. les méthodes déterministes évolutionnaires individualistes conduisent presque toujours à des situations de coopération généralisée;

4. les méthodes déterministes évolutionnaires communautaires convergent le plus souvent vers des points fixes où les stratégies survivantes ne coopèrent pas nécessairement les unes avec les autres (ce qui est plus conforme que la coopération généralisée à ce qu'on peut observer dans le monde réel).

Le but du présent article est d'étudier si l'introduction de méthodes stochastiques dans les simulations évolutionnaires produit des résultats essentiellement différents et en particulier des classements éloignés de ceux obtenus par les cinq méthodes déterministes étudiés auparavant. Si c'était le cas, cela signifierait qu'il faut

absolument les mettre en œuvre pour obtenir des classements pertinents au sein d'une famille de stratégies. Notre travail a été suggéré par l'article [9] qui présentait des simulations évolutionnaires stochatiques utilisant la méthode de Moran.

Nous avons non seulement étudié la méthode de Moran, mais aussi celle par rencontres aléatoires Encounter, et la méthode de Fermi. Pour chacune de ces trois méthodes stochastiques nous avons distingué le modèle individualiste FIGURE 1 et 2 et le modèle communautaire FIGURE 3 et 4. Cela nous a donné 6 méthodes évolutionnaires stochatiques : Enc(Ind), Enc(Com), Mor(Ind), Mor(Com), Fer(Ind), Fer(Com).

La comparaison des 11 méthodes de classement a été opérée d'une part en réalisant des schémas de trajectoires et des courbes mettant en évidence visuellement les regroupements des méthodes évolutionnaires en deux catégorie principales. Nous avons confirmé ces résultats par un calcul massif où nous avons évalué les distances mutuelles entre les 11 méthodes en prenant en comptes plusieurs familles de stratégies. Cela nous a donné un tableau de distances que nous avons exploité pour créer un dendrogramme où apparaît clairement la façon dont se regroupent les méthodes et où on constate finalement que les méthodes stochastiques produisent des résultats assez proches des méthodes déterministes.

## 2 Simulations évolutionnaires stochastiques

Rappelons que la "fitness" d'une stratégie S dans un environnement composé d'un ensemble de stratégies E mesure l'adaptation de S à E, c'est-à-dire le nombre de points que remporte S quand il rencontre chaque stratégie de E, ce nombre étant normalisé pour que la somme des fitness de toutes les stratégies de E soit égale à 1.

Nous avons envisagé 6 modèles stochastiques évolutionnaires qui se fondent sur trois idées simples : (a) l'idées de rencontres aléatoires uniformes, les scores tirés de chaque rencontre déterminent le nombre des nouveaux individus ajoutés aux effectifs des stratégies concernées ; (b) l'idée d'une l'évolution résultant directement du "fitness" des individus pour en créer des nouveaux ; (c) l'idée des rencontres aléatoires en favorisant par l'usage du "fitness" les meilleures stratégies. Pour chacune des méthodes après chaque ajout, on retire autant d'individus qu'on
<figure><img src="image_2.png" /><figcaption>FIGURE 1 – Chaque figure représente 18 trajectoires évolutives de la méthode individualiste en utilisant la représentation barycentrique. Quelle que soit la méthode, et quels que soient les effectifs de départ, les trajectoires arrivent toutes sur l’axe gradual - tft de coopération généralisée. Voir les précisions section 2.4.</figcaption></figure>
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

FIGURE 2 – Cette figure illustre l’évolution des effectifs de 6 stratégies pour les méthodes individuelles. Quelle que soit la méthode, seules deux types de stratégies survivent gradual et tft dont tous les membres coopèrent, donnant un état de coopération généralisée.

en a ajouté (au hasard uniformément) pour maintenir un effectif total stable.

Les modifications des effectifs de l'arène d'une génération à la suivante sont maintenant bien moins importantes que dans les modèles déterministes *Det(Ind)* et *Det(Com)*. Il en résulte qu'il faut suivre l'évolution de l'arène sur un nombre de générations bien plus grands (200 000 par exemple) avant d'arriver à un état de stabilisation satisfaisant. Pour obtenir des résultats reproductibles, il faut aussi éviter que "par malchance" une stratégie disparaisse rapidement, ce qui conduit à prendre dans l'arène initiale des effectifs importants de chaque stratégie : par exemple une centaine de fois plus que la variation d'effectif qu'une étape d'évolution peut provoquer. En respectant ces précautions les évolutions conduisent à des états sensiblement équivalents d'une simulation à l'autre. La comparaison entre les résultats produits par les méthodes stochastiques et les méthodes déterministes (voir plus loin) confirme qu'une fois bien stabilisées, les méthodes stochastiques produisent des dynamiques évolutives significatives donnant des classements entre familles de stratégies ne dépendant plus du hasard et équivalents aux classements donnés par les méthodes déterministes.

## 2.1 Idée 1. Rencontres aléatoires entre deux individus.

L'idée est que les individus d'une arène circulent aléatoirement dans l'arène et que parfois deux individus se rencontrent et engagent une partie, dont le résultat en points détermine l'augmentation du nombre d'individus des stratégies associées aux individus qui se sont affrontées.

### Simulation par rencontres aléatoires individuelles (encounter) *Enc(Ind)*.

* On choisit deux individus *a* et *b* aléatoirement uniformément, ce qui signifie que s'il y a *N* individus dans l'arène, chacun a une probabilité de $1/N$ d'être choisi.

* L'individu *a* qui joue la stratégie *A* rencontre l'individu *b* qui joue la stratégie *B*.

* Les scores obtenus font varier les effectifs des stratégies *A* et *B* :
  Effectif *A* = Effectif *A* + points gagnés par *a*,
  Effectif *B* = Effectif *B* + points gagnés par *b*.

* On retire uniformément autant d'individus qu'on vient d'en ajouter.
**Simulation par rencontres aléatoires communautaires (encounter) Enc(Com).** Le procédé de calcul est le même, mais on choisit nécessairement un couple d'individus a et b jouant des stratégies différentes.

## 2.2 Idée 2. Processus de Moran.

Pour simuler un processus évolutionnaire [14, 15] proposent de prendre en compte le fitness (c'est-à-dire l'adaptation au milieu) des individus en compétition en donnant plus de chances de se reproduire à ceux ayant le meilleur fitness. Dans [12] le processus est décrit ainsi : "Consider a homogeneous population of size N. At each time step an individual is chosen for reproduction with a probability proportional to its fitness. The offspring replaces a randomly chosen individual. In this so-called Moran process, the population size remains constant."

L'idée est tout à fait naturelle. Nous l'appliquons de la façon suivante dans le cas d'un ensemble de stratégies pour le dilemme du prisonnier.

Pour chaque état de l'arène, la distribution des fitness entre stratégies définit une probabilité sur l'ensemble des stratégies que l'on souhaite classer. On l'utilise pour incrémenter l'effectif d'une stratégie, puis on retire une stratégie au hasard uniformément (chaque individu a la même probabilité d'être retirée, y compris celle qu'on vient d'ajouter). On recommence, etc.

L'évolution se fait aléatoirement, mais les bonnes stratégies d'une arène —celles qui ont des fitness élevés— ont une plus grande probabilité instantanée d'accroître leur effectif, ce qui simule de manière naturelle un processus de sélection.

**Simulation aléatoire individualiste à la Moran, Mor (Ind).** Dans le cas individualiste l'idée générale devient :

* On calcule le fitness individualiste des individus puis des stratégies (voir [7] ou [6]) relativement à l'arène : $FitnessI(Ind)[a], FitnessS(Ind)[s]$.

* On choisit une stratégie s selon la distribution de probabilité définie par $FitnessS(Ind)[s]$ sur l'ensemble des stratégies.

* On incrémente d'une unité l'effectif de la stratégie choisie.

* On enlève un individu de l'arène au hasard uniformément.

* On recommence après avoir recalculé les fitness

**Simulation aléatoire communautaire à la Moran, Mor (Com).** Le calcul est le même, mais avec le fitness communautaire $FitnessS(Com)$.

## 2.3 Idée 3. Processus de Fermi

L'idée des rencontres aléatoires et du processus de Moran peuvent être fusionnées. C'est le "processus de Fermi" [13, 19].

L'idée reprend celle des simulations Encounter (Enc(Ind), Enc(Com)), sauf qu'on considère maintenant que les stratégies qui se rencontrent ne sont pas choisies aléatoirement uniformément, mais en fonction de leur fitness. Les stratégies performantes ont maintenant un double avantage dans le processus évolutionnaire : (a) elles vont plus fréquemment au combat que les autres ; (b) quand elles y vont, elles gagnent en général plus de points que leur adversaire ce qui augmente leur effectif plus que celui de leur adversaire.

L'idée modélisée est celle de la prudence : si vous êtes faibles et que vous en avez conscience, vous évitez de multiplier les combats, vous vous cachez de vos prédateurs, parfois même vous les fuyez.

**Simulation aléatoire individualiste à la Fermi, Fer(Ind).** La méthode consiste à opérer de la façon suivante :

* On calcule le fitness individualiste des stratégies $FitnessS(Ind)[s]$.

* On choisit deux individus a et b qui jouent deux stratégies A et B selon la distribution de probabilité $FitnessS(Ind)[s]$.

* L'individu a qui joue la stratégie A rencontre l'individu b qui joue la stratégie B.

* Les scores obtenus font varier les effectifs des stratégies A et B :
  Effectif A = Effectif A + points gagnés par a,
  Effectif B = Effectif B + points gagnés par b.

* On retire uniformément autant d'individus qu'on vient d'en ajouter.

On recommence après avoir recalculé les fitness.

**Simulation aléatoire communautaire à la Fermi, Fer(Com).** Le calcul est le même, mais avec le fitness communautaire $FitnessS(Com)$.

## 2.4 Représentation barycentrique

Les quatre parties de la FIGURE 1 utilisent la méthode de représentation barycentrique des évolutions d'un ensemble de stratégies. Son principe est le suivant :
<figure><img src="image_7.png" /><figcaption>FIGURE 3 – Pour comparer les méthodes communautaires le principe est le même que pour les méthodes individualistes de la FIGURE 1. Les 18 trajectoires de chaque sous-figure convergent vers un même point fixe attracteur. On observe comme pour la FIGURE 1, que les trajectoires des méthodes stochastiques sont moins lisses mais équivalentes à celles des méthodes déterministes.</figcaption></figure>
<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /><figcaption>FIGURE 4 – Le principe est le même que pour la FIGURE 2, sauf que les méthodes utilisées sont communautaires plutôt qu’individualistes.</figcaption></figure>

Pour *k* stratégies, nous plaçons *k* points sur un cercle aux sommets d'un polygone régulier à *k* sommets. Chaque sommet représente une stratégie. La répartition des effectifs d'une génération détermine un point à l'intérieur du polygone qui est le barycentre des *k* sommets affectés des effectifs respectifs des stratégies. En joignant les points successifs obtenus lors d'une simulation évolutionnaire, la variation des effectifs de l'arène de génération en génération produit une courbe à l'intérieur du polygone. Il s'agit d'une projection en dimension 2 d'une courbe dans un espace de dimension *k*. S'il y a stabilitation la courbe s'arrête en un point intérieur au polygone ou à sa frontière, qui est marqué par un rond. Dans un tel schéma, on peut dessiner plusieurs trajectoires évolutives correspondant à plusieurs distributions initiales différentes des effectifs. On voit alors en observant les trajectoires dessinées et leurs points d'arrivée, si l'état stabilisé est unique, ou s'il y en a plusieurs. La position des points d'arrêt des courbes donne des informations sur les états stables finaux. Dans la FIGURE 1a, nous avons considéré six types de stratégies appelées bag6 par la suite : allD, allC, prober, gradual, tft, mistrust. En utilisant la méthode de représentation barycentrique, nous avons dessiné 18 trajectoires évolutives pour des

arènes initiales différentes, l'évolution se faisant par la méthode de simulation évolutionnaire déterministe individualiste Det(Ind). Toutes les trajectoires convergent vers un état de coopération généralisée qui est un mélange de gradual et de tft. Les 18 configurations initiales sont les suivantes : effectifs de 30 pour toutes les stratégies sauf une avec effectif de 1000, ce qui donne 6 trajectoires ; même chose en remplaçant 30 par 50 (6 trajectoires) ; même chose en remplaçant 30 par 100 (6 trajectoires). Pour la FIGURE 1b, nous avons procédé de la même façon, mais utilisant la méthode de simulation évolutionnaire individualiste stochastique Encounter : Enc(Ind). Même chose pour la FIGURE 1c avec Mor(Ind), et pour la FIGURE 1d avec Fer(Ind). Chacune des évolutions (que ce soient les 18 déterministes, les 18 encounter, les 18 Moran ou les 18 Fermi) conduit à une coopération généralisée où ne survivent que des stratégies Gradual et TFT. Les trajectoires des méthodes stochastiques sont moins lisses, mais essentiellement identiques aux trajectoires lisses obtenues avec la méthode déterministe.
<table><caption>TABLE 1 – Matrice des distances entre les 11 méthodes (3h00 de calcul sur un i9 8 cœurs)</caption><thead><tr><th></th><th>VicT</th><th>ClaT(I)</th><th>ClaT(C)</th><th>Det(I)</th><th>Det(C)</th><th>Enc(I)</th><th>Enc(C)</th><th>Fer(I)</th><th>Fer(C)</th><th>Mor(I)</th><th>Mor(C)</th></tr></thead><tbody><tr><td>VicT</td><td>0.0</td><td>0.68</td><td>0.653</td><td>2.823</td><td>1.914</td><td>2.882</td><td>1.902</td><td>2.782</td><td>1.769</td><td>2.538</td><td>1.623</td></tr><tr><td>ClaT(Ind)</td><td>0.68</td><td>0.0</td><td>0.08</td><td>2.453</td><td>1.455</td><td>2.528</td><td>1.44</td><td>2.412</td><td>1.315</td><td>2.171</td><td>1.161</td></tr><tr><td>ClaT(Com)</td><td>0.653</td><td>0.08</td><td>0.0</td><td>2.491</td><td>1.441</td><td>2.561</td><td>1.43</td><td>2.451</td><td>1.303</td><td>2.208</td><td>1.149</td></tr><tr><td>Det(Ind)</td><td>2.823</td><td>2.453</td><td>2.491</td><td>0.0</td><td>1.925</td><td>0.513</td><td>1.841</td><td>0.267</td><td>1.94</td><td>0.535</td><td>1.915</td></tr><tr><td>Det(Com)</td><td>1.914</td><td>1.455</td><td>1.441</td><td>1.925</td><td>0.0</td><td>2.045</td><td>0.33</td><td>1.914</td><td>0.376</td><td>1.761</td><td>0.455</td></tr><tr><td>Enc(Ind)</td><td>2.882</td><td>2.528</td><td>2.561</td><td>0.513</td><td>2.045</td><td>0.0</td><td>1.955</td><td>0.617</td><td>2.04</td><td>0.809</td><td>2.026</td></tr><tr><td>Enc(Com)</td><td>1.902</td><td>1.44</td><td>1.43</td><td>1.841</td><td>0.33</td><td>1.955</td><td>0.0</td><td>1.83</td><td>0.281</td><td>1.649</td><td>0.408</td></tr><tr><td>Fer(Ind)</td><td>2.782</td><td>2.412</td><td>2.451</td><td>0.267</td><td>1.914</td><td>0.617</td><td>1.83</td><td>0.0</td><td>1.925</td><td>0.513</td><td>1.901</td></tr><tr><td>Fer(Com)</td><td>1.769</td><td>1.315</td><td>1.303</td><td>1.94</td><td>0.376</td><td>2.04</td><td>0.281</td><td>1.925</td><td>0.0</td><td>1.728</td><td>0.295</td></tr><tr><td>Mor(Ind)</td><td>2.538</td><td>2.171</td><td>2.208</td><td>0.535</td><td>1.761</td><td>0.809</td><td>1.649</td><td>0.513</td><td>1.728</td><td>0.0</td><td>1.673</td></tr><tr><td>Mor(Com)</td><td>1.623</td><td>1.161</td><td>1.149</td><td>1.915</td><td>0.455</td><td>2.026</td><td>0.408</td><td>1.901</td><td>0.295</td><td>1.673</td><td>0.0</td></tr></tbody></table>

## 3 Relations entre les 11 méthodes.

Pour obtenir des informations sur les onze méthodes de classement, nous utilisons une méthode qui produit un tableau de distances entre méthodes, qui lui-même produit un dendrogramme synthétisant sous forme graphique ces distances.

Pour comparer les onze méthodes un seul ensemble de stratégies n'est pas suffisant c'est pourquoi nous avons utilisé les ensembles de stratégies suivants : bag5, bag6, bag11, bag20, bag20+bagDyson, Mem11 détaillées dans [6] et dans l'ANNEXE 5.

Pour chacun d'eux et chacune des 11 méthodes, nous avons calculé la distance entre les résultats fournis en procédant de la manière suivante :

1. Pour chacune des méthodes et chaque ensemble de stratégies nous avons construit un vecteur de résultat normalisé $V$. Pour les méthodes de tournoi, on calcule $V$ en prenant le vecteur des scores de chaque stratégie dont on divise chaque composante par la somme des composantes du vecteur. Cela donne un vecteur dont la somme des composantes vaut 1, assimilable à un vecteur de pourcentage mesurant la force respective des stratégies. Dans le cas de VicT pour avoir des coefficients positifs, nous avons remplacé les points attribués (-1, 0, +1), par (0, 1, 2) respectivement pour (perdu, ex-aequo, gagné). Pour les méthodes évolutionnaires, le vecteur est obtenu en normalisant les effectifs moyens du dernier quart de l'évolution.

2. Pour chaque ensemble de stratégies, à partir des vecteurs normalisés associé à chacune des 11 méthodes, nous avons calculé une matrice de distance. La distance entre deux vecteurs est la distance euclidienne usuelle entre vecteurs : $d((x_1, ..., x_n)(y_1, ..., y_n) = \sqrt{\sum(x_i - y_i)^2}$

En faisant la somme des matrices obtenues pour chacun des six ensembles de stratégies considérés, nous avons obtenu une matrice de distance entre les 11 méthodes considérées (Table 1).

On y voit par exemple que les méthodes les plus proches de Det(Ind) sont Enc(Ind), Fer(Ind) et Mor(Ind), et que les méthodes les plus proches des Det(Com) sont Enc(Com), Fer(Com) et Mor(Com). Il y a regroupement des méthodes individualistes les unes avec les autres, et de même pour les communautaires.

Le dendrogramme qu'on en tire est représenté à la FIGURE 5. Il confirme ce qu'on voyait dans les figures précédentes. Les méthodes individuelles sont regroupées comme les méthodes communautaires, et les méthodes par tournois.

On en tire la conclusion que les méthodes sto-chastiques sont peu utiles puisqu'elles donnent des résultats que les méthodes déterministes anticipent.

Puisque les méthodes par tournois ne sont pas bien adaptées pour repérer et comparer des stratégies robustes et performantes, il faut privilégier les deux méthodes Det(Ind) et Det(Com).

## 4 Conclusion

Le dilemme itéré du prisonnier (IPD) a fait l'objet de multiples études et travaux de recherche conduisant à de nombreuses surprises, en particulier quand les chercheurs ont voulu identifier les stratégies les plus performantes. La première des surprises fut la découverte de la robustesse de tft mais elle fut suivie de bien d'autres.

La comparaison et le classement des stratégies de jeu pose cependant une série de problèmes délicats. Bien évidemment, il ne peut pas exister de classement absolu et objectif s'appliquant à l'in-finité des stratégies possibles car la performance
<figure><img src="image_12.png" /></figure>

FIGURE 5 – Le dendrogramme construit à partir de la matrice du tableau 1 permet de visualiser clairement ce qui apparaît déjà quand on analyse les coefficients de la matrice donnant les distances entre méthodes. Les méthodes par tournois se regroupent et ne donnent jamais des résultats anticipant ce que donnent les méthodes évolutionnaires. C'est là un résultat conforme aux conclusions générales bien établies depuis Axelrod et Hamilton[4]. De plus, le dendrogramme montre de manière très nette le regroupement de toutes les méthodes évolutionnaires individualistes (qu'elles soient déterministes ou stochastiques) et le regroupement de toutes les méthodes évolutionnaires communautaires (qu'elles soient déterministes ou stochastiques), les deux regroupements étant bien séparés l'un de l'autre.

d'une stratégie dépend de l'environnement dans laquelle elle se trouve. Il faut se limiter à la recherche de méthodes d'évaluation et de classement entre stratégies de familles finies fixées.

Les travaux sur le Dilemme du Prisonner utilisent plusieurs méthodes produisant de tels classements. Nous considérons ici qu'il est important de travailler à comparer ces méthodes, et à réfléchir à leur bien fondé.

Les méthodes de tournois sont les plus simples, il y en a trois au moins. Avec les deux méthodes évolutionnaires déterministes : la méthode individualiste *Det(Ind)* et la méthode communautaire *Det(Com)* cela donne 5 méthodes déterministes naturelles de classement. Contrairement à ce qu'on espérait peut-être, les méthodes fournissent des résultats sensiblement différents.

En y ajoutant les 6 méthodes stochastiques de

la section 2 on obtient onze méthodes que le dendrogramme FIGURE 5 regroupe.

À partir de la matrice de distance, les deux méthodes les plus proches en distance euclidienne sont fusionnées pour former une nouvelle catégorie dont le vecteur associé est constitué de la moyenne des deux vecteurs des méthodes fusionnées. Le processus est ensuite itéré. Voir [16] ou le package *scipy.cluster.hierarchy*.

Ce dendrogramme met clairement en évidence que les tournois produisent des résultats qui n'anticipent que très médiocrement ce que donnent les méthodes évolutionnaires. Or, on doit préférer les méthodes évolutionnaires car elles fournissent des classements plus robustes et correspondant mieux à des situations compétitives dynamiques comme on en rencontre dans les écosystèmes, la vie sociale et économique.

Les deux méthodes déterministes évolutionnaires *Det(Ind)* et *Det(Com)* sont naturelles et simples. On a, semble-t-il, accordé jusqu'à présent assez peu d'importance à la seconde qui possède pourtant l'avantage de conduire bien plus fréquemment à des équilibres stables où persistent des stratégies agressives (qui prennent l'initiative de trahir). Ces équilibres stables complexes correspondent pourtant à ce qu'on observe dans le monde vivant. Par ailleurs l'idée naturelle que les individus d'une même famille ne sont pas ennemis est prise en compte uniquement par *Det(Com)*.

La dynamique très fréquemment observée pour les simulations évolutionnaires individualistes *Det(Ind)* est la convergence vers un état de coopération généralisée. Ce n'est pas vrai pour les simulations évolutionnaires communautaires *Det(Com)* qui produisent majoritairement des attracteurs correspondant à de subtils équilibres entre stratégies qui ne sont pas des situations de coopération généralisée.

Les méthodes stochastiques de simulations évolutionnaires les plus naturelles dérivent de trois idées de base décrites à la section 2. Elles donnent 6 méthodes de simulations évolutionnaires. Nous avons montré par les dynamiques créées que les 6 méthodes se classent en trois méthodes fournissant des résultats semblables à *Det(Ind)* et trois méthodes fournissant des résultats semblables à *Det(Com)*. Les figures barycentriques mettent en évidence ces regroupements. Pour confirmer et consolider ce résultat nous avons mené des calcul massifs aboutissant à des matrices de distances entre les onze méthodes
envisagées et un dendrogramme. Ces nouveaux résultats corroborent de manière claire les regroupements anticipés par l'observation des dynamiques.

L'analyse menée montre donc que seules deux méthodes principales déterministes *Det(Ind)* et *Det(Com)* doivent être retenues et distinguées selon ce qu'on cherche à modéliser : (a) des compétitions entre individus ; ou (b) des compétitions entre familles d'individus formant des groupes qui s'opposent sans que dans un groupe les individus se combattent.

L'article [6] avait montré l'importance des compétitions communautaires qui avaient été négligées. Cette fois, nous montrons en plus l'utilité des simulations évolutionnaires stochastiques. Reste à étudier si ces résulats, obtenus dans le cadre formel du IPD, se retrouvent aussi dans le cas d'autres modèles multi-agents.

# 5 Annexe

Les six stratégies qui constituent bag6

1. all_c : Je coopère toujours.

2. all_d : Je trahis toujours.

3. tft : Je coopère au premier coup, puis à chaque tour *n* je joue ce que mon adversaire a joué au tour *n* − 1.

4. mistrust : Je trahis au premier coup, puis à chaque tour *n* je joue ce que mon adversaire a joué au tour *n* − 1.

5. gradual : Je coopère au premier tour et lorsque la règle suivante n'est pas appliquée : à chaque fois que mon adversaire me trahit, je compte le nombre *n* de ses trahisons passées et je trahis *n* fois consécutivement suivies de deux coopérations.

6. prober : Je joue Trahir-Coopérer-Coopérer (d c c) durant les 3 premies tours ; puis si mon adversaire n'a pas trahi aux tours 2 et 3, je trahis toujours. Sinon je joue tft.

Pour la composition exacte des ensembles de stratégies utilisés dans le calcul du dendrogramme, voir https://github.com/cristal-smac/ipd.

# Références

[1] Ethan Akin. The iterated prisoner's dilemma: good strategies and their dynamics. *Ergodic Theory, Advances in Dynamical Systems*, pages 77–107, 2016.

[2] Robert Axelrod. *The evolution of cooperation : revised edition*. Basic books, 1984, 2006.

[3] Robert Axelrod. *The complexity of cooperation : Agent-based models of competition and collaboration*, volume 3. Princeton University Press, 1997.

[4] Robert Axelrod and William Donald Hamilton. The evolution of cooperation. *science*, 211(4489):1390–1396, 1981.

[5] Bruno Beaufils, Jean-Paul Delahaye, and Philippe Mathieu. Our meeting with gradual, a good strategy for the iterated prisoner's dilemma. In *Proceedings of the Fifth International Workshop on the Synthesis and Simulation of Living Systems (ALIFE'5)*, pages 202–209. The MIT Press/Bradford Books, 1996.

[6] Jean-Paul Delahaye and Philippe Mathieu. Coopération généralisée et attracteurs au dilemme itéré du prisonnier. In *Journées Francophones sur les Systèmes Multi-Agents (JFSMA)*, 2021.

[7] Jean-Paul Delahaye and Philippe Mathieu. Être ou ne pas être individualiste, quelles conséquences ? *Revue Ouverte d'Intelligence Artificielle*, 4(2):67-95, 2023.

[8] Jeffrey A Fletcher and Martin Zwick. Unifying the theories of inclusive fitness and reciprocal altruism. *The American Naturalist*, 168(2):252-262, 2006.

[9] Nikoleta E Glynatsi and Vincent A Knight. A meta analysis of tournaments and an evaluation of performance in the iterated prisoner's dilemma. *arXiv preprint arXiv:2001.05911*, 2020.

[10] Graham Kendall, Xin Yao, and Siang Yew Chong. *The Iterated Prisoners' Dilemma: 20 Years on*. World Scientific Publishing Co., Inc., 2007.

[11] Vincent Knight, Marc Harper, Nikoleta E Glynatsi, and Owen Campbell. Evolution reinforces cooperation with the emergence of self-recognition mechanisms: An empirical study of strategies in the moran process for the iterated prisoner's dilemma. *PloS one*, 13(10):e0204981, 2018.

[12] Erez Lieberman, Christoph Hauert, and Martin A Nowak. Evolutionary dynamics on graphs. *Nature*, 433(7023):312–316, 2005.

[13] Xuesong Liu, Mingfeng He, Yibin Kang, and Qiuhui Pan. Fixation of strategies with the moran and fermi processes in evolutionary games. *Physica A: Statistical Mechanics and its Applications*, 484:336-344, 2017.

[14] Patrick Alfred Pierce Moran. Random processes in genetics. In *Mathematical proceedings of the cambridge philosophical society*, volume 54, pages 60–71. Cambridge University Press, 1958.

[15] Patrick Alfred Pierce Moran et al. The statistical processes of evolutionary theory. *The statistical processes of evolutionary theory*, 1962.

[16] Daniel Müllner. Modern hierarchical, agglomerative clustering algorithms. *arXiv preprint arXiv:1109.2378*, 2011.

[17] Martin Nowak and Karl Sigmund. Chaos and the evolution of cooperation. *Proceedings of the National Academy of Sciences*, 90(11):5091–5094, 1993.

[18] Karl Sigmund. *The calculus of selfishness*. Princeton University Press, 2016.

[19] Arne Traulsen, Jorge M Pacheco, and Martin A Nowak. Pairwise comparison and selection temperature in evolutionary game dynamics. *Journal of theoretical biology*, 246(3):522–529, 2007.