Jeux entre programmes : la ruliologie de la compétition

Article original

La configuration de base

Qu’il s’agisse de biologie, d’économie, de politique ou d’une foule d’autres domaines, il est chose commune de rencontrer des situations qui peuvent être modélisées comme impliquant deux agents qui s’affrontent de manière répétée. On imagine qu’à chaque étape, chaque agent peut choisir l’une des actions d’un ensemble donné, et que, selon les principes classiques de la théorie des jeux, chaque agent (ou « joueur ») reçoit un certain « gain » fixe en fonction de l’action qu’il entreprend et de celle qu’entreprend son adversaire. Mais comment les agents décident-ils de l’action entreprendre ? Nous imaginons que chaque agent dispose d’une certaine procédure fixe, ou « stratégie », pour prendre ses décisions. Et nous imaginons que l’entrée de chacune de ces décisions est la séquence des actions passées que l’agent et son adversaire ont entreprises.
Beaucoup de travail a été accompli au cours de près d’un siècle quant aux choix particuliers des stratégies. Mais quelque chose qui m’intrigue depuis longtemps, c’est ce qui se passe si l’on considère systématiquement toutes les stratégies possibles. Et si nous considérons les stratégies comme des programmes, cela devient une question à laquelle nous pouvons immédiatement appliquer des méthodes ruliologiques. C’est ce que je vais faire ici.
Pour être plus précis au sujet de la configuration, supposons qu’à chaque étape, chaque agent effectue l’une des deux actions possibles, indiquées par
et
. Et pour l’instant, prenons les gains comme étant ceux du jeu classique des « correspondances » (« Jeu de l’appariement des pièces ») dans lequel le joueur 1 reçoit le gain le plus élevé lorsqu’il y a correspondance, et le joueur 2 reçoit le gain le plus élevé lorsqu’il n’y a pas correspondance :
Alors, que se passe-t-il lorsque des agents jouent à ce jeu à plusieurs reprises ? Eh bien, cela dépend de leurs stratégies. Voici quelques exemples concernant plusieurs choix différents stratégiques de chaque agent :
En traçant les gains cumulés des deux agents (représentés par
et
) dans chacun de ces cas, nous obtenons :
Souvent, nous considérerons que « l’agent gagnant » est celui qui a le gain cumulatif numériquement le plus élevé (c’est-à-dire qui finit par être en tête dans ces tracés) après un certain nombre d’étapes. Et avec un critère comme celui-ci, nous pourrons classer différents programmes les uns par rapport aux autres, et, de manière générale, explorer la ruliologie de la compétition.
Avec la configuration de base que nous utilisons, nous pouvons représenter toutes les séquences possibles des actions par un graphe multivoie :
In[]:=
[◼]
MultiwayGameHistory

[◼]
$Games
["MatchingPennies"],3
Pour toute séquence d’actions donnée, il existe alors un gain cumulatif pour chaque agent dans notre jeu des correspondances :
Si chaque agent adopte une stratégie particulière, cela définira un chemin particulier à travers le graphe multivoie. Pour les stratégies utilisées dans les exemples ci-dessus, les chemins sont :
Que faut-il pour avoir une stratégie gagnante ? Dans ce qui suit, nous examinerons des stratégies fondées sur plusieurs types différents de programmes. Mais une question fondamentale que nous pouvons toujours nous poser est de savoir si les stratégies qui se révèlent gagnantes tendent à être fondées sur des programmes plus compliqués ou moins compliqués, ou à montrer un comportement plus compliqué ou moins compliqué.
En d’autres termes, si vous voulez gagner, devriez-vous généralement essayer de construire quelque chose de compliqué ? Ou devriez-vous plutôt vous attendre à pouvoir trouver une « astuce toute simple » qui vous permettra de « déjouer le jeu » et, du moins la plupart du temps, vous permettre de gagner ? En effet, nous demandons si la compétition tend à conduire à la complexité, ou à la simplicité.
J’ai récemment examiné des modèles minimaux à la fois de l’évolution biologique et de l’apprentissage automatique, dans lesquels on fait évoluer de manière adaptative des programmes afin de maximiser une certaine fonction d’aptitude imposée de l’extérieur. Et ce que j’ai constaté, c’est que même lorsque la fonction d’aptitude utilisée est simple, le comportement des programmes qui la maximisent est normalement assez complexe. En d’autres termes, l’évolution adaptative tendra à faire en sorte que même un objectif simple et fixe soit atteint d’une manière compliquée.
Alors, que se passe-t-il si, au lieu d’avoir un objectif fixe imposé de l’extérieur, notre but est simplement, de façon générale, de gagner contre d’autres agents ? Une telle compétition, potentiellement ouverte, nous conduit-elle à un comportement plus complexe (ou à des programmes plus complexes), ou non ? C’est le type de question que nous allons pouvoir explorer ici en examinant la ruliologie de la compétition.

Stratégies issues des machines à états finis

Les machines à états finis peuvent être considérées comme définissant des programmes extrêmement simples (qui pourraient modéliser des voies en biologie, des processus de décision en économie, etc.). Et pour commencer notre étude de la ruliologie de compétition, nous allons examiner des stratégies définies par des machines à états finis.
Voici un exemple typique d’une machine à états finis (ici avec 3 états) :

L’espace des machines à états finis possibles

Machines à 2 états

Dans le cas des machines à 2 états, les 22 machines distinctes sont :

Machines à 3 états

Remarque : qu’entendons-nous par « en moyenne » ?

La complexité de la victoire

et comme suit :

Compétitions entre des machines de différentes tailles

Évolution adaptative des machines à états finis

La machine finale obtenue

Qu’en est-il du dilemme du prisonnier ?

L’espace de tous les jeux possibles

Stratégies des automates cellulaires

L’idée est alors d’exécuter l’automate cellulaire avec ceux-ci comme conditions initiales

Les automates cellulaires par rapport aux machines à états finis

Évolution adaptative des stratégies d’automate cellulaire

Stratégies des machines de Turing

Discussion

Notes historiques et personnelles

Remerciements