La révolution émergente dans la théorie des jeux

Le monde de la théorie des jeux est actuellement en feu. En mai, Freeman Dyson à l'Université de Princeton et William Press à l'Université du Texas ont annoncé qu'ils avaient découvert une stratégie jusqu'alors inconnue pour le jeu du dilemme du prisonnier qui garantit à un joueur un meilleur résultat que l'autre.

C'est une surprise monumentale. Les théoriciens ont étudié le dilemme du prisonnier pendant des décennies, l'utilisant comme modèle pour l'émergence de la coopération dans la nature. Ce travail a eu un impact profond sur des disciplines telles que l'économie, la biologie évolutive et, bien sûr, la théorie des jeux elle-même. Le nouveau résultat aura un impact dans tous ces domaines et plus encore.

Le jeu est le suivant : imaginez qu'Alice et Bob ont commis un crime et sont arrêtés. La police offre à chacun un pactole et vous êtes libre pendant que votre ami fait 6 mois de prison. Si Alice et Bob font un vif d'or, ils écopent tous les deux de 3 mois de prison. S'ils gardent tous les deux le silence, ils écopent tous les deux d'un mois de prison pour une infraction moindre.

Que doivent faire Alice et Bob ?

S'ils coopèrent, ils ne passent tous les deux qu'un mois en prison. Néanmoins, dans un seul jeu, la meilleure stratégie est de moucharder car cela garantit que vous n'obtenez pas la peine de prison maximale.

Cependant, le jeu devient plus intéressant lorsqu'il est joué en tours répétés, car les joueurs qui ont été trahis au cours d'un tour ont la possibilité de se venger lors de l'itération suivante.

Jusqu'à présent, tout le monde pensait que la meilleure stratégie dans le dilemme itératif du prisonnier était de copier le comportement de vos adversaires au tour précédent. Cette approche du tac au tac garantit que vous passez tous les deux le même temps en prison.

Cette conclusion était basée sur des décennies de simulations informatiques et une certaine foi aveugle dans la symétrie de la solution.

Ainsi, la nouvelle qu'il existe d'autres stratégies permettant à un joueur non seulement de battre l'autre, mais aussi de déterminer sa durée de vie en prison, est tout simplement révolutionnaire.

La nouvelle approche est appelée la stratégie du déterminant zéro (car elle implique le processus de mise à zéro d'un objet mathématique appelé déterminant).

Il s'avère que l'approche du tac au tac est un cas particulier de la stratégie à déterminant zéro : le joueur utilisant cette stratégie détermine que le temps de prison de l'autre joueur est égal au sien. Mais il existe toute une série d'autres stratégies qui font que l'autre joueur passe beaucoup plus de temps en prison (ou beaucoup moins si vous vous sentez généreux).

La seule mise en garde est que l'autre joueur ne doit pas savoir qu'il est manipulé. S'ils découvrent la ruse, ils peuvent jouer une stratégie qui se traduit par le temps de prison maximum pour les deux joueurs : c'est-à-dire que les deux souffrent.

Les théoriciens des jeux appellent cela le jeu Ultimatum. Cela équivaut à donner 100 £ à Alice et à lui demander de le partager entre elle et Bob. Bob peut accepter la division ou la refuser s'il pense que la division est injuste, auquel cas les deux joueurs n'obtiennent rien. Le refus est la façon dont Bob punit Alice pour sa cupidité.

La chose intéressante ici est que lorsque les deux joueurs sont conscients de la ruse déterminante zéro, le dilemme du prisonnier se transforme en un jeu différent.

La découverte de Press et Dyson a poussé les théoriciens des jeux à se dépêcher d'en comprendre les implications. Ils ont utilisé le dilemme du prisonnier pour avoir un aperçu de tout, de la politique de la guerre froide et des négociations sur le changement climatique à la psychologie et, bien sûr, à l'origine évolutive de la coopération elle-même.

Aujourd'hui, nous voyons l'un des premiers articles à étudier ces implications en détail. Christoph Adami et Arend Hintze de l'Université d'État du Michigan à East Lansing étudient si les stratégies à déterminant zéro sont stables sur le plan de l'évolution.

C'est une question intéressante. Il pose la question suivante : si une population entière d'individus joue tous des stratégies à zéro déterminant, une autre stratégie pourrait-elle se répandre dans la population et prendre le relais ? Sinon, les stratégies à zéro déterminant sont évolutivement stables.

Adami et Hintze montrent que les stratégies à déterminant zéro ne sont pas évolutivement stables. La raison en est qu'ils ne fonctionnent pas bien les uns contre les autres et cela laisse la porte ouverte à d'autres stratégies pour se faufiler et prendre le relais.

Les stratégies à déterminant zéro ne sont pas stables d'une autre manière. Adami et Hintze montrent que si les stratégies du joueur évoluent, les changements qui se produisent entre une génération et la suivante assurent que la nouvelle stratégie n'est généralement pas zéro déterminant. La stratégie ne peut donc pas survivre.

Cependant, il existe un scénario dans lequel Adami et Hintze disent que la nouvelle stratégie devrait être stable. C'est à ce moment que les joueurs déterminant zéro peuvent déterminer si d'autres joueurs utilisent la même stratégie ou non. Dans ce cas, ils peuvent éviter les pertes qui surviennent lorsqu'ils jouent contre les leurs tout en exploitant des joueurs ignorants.

Ainsi, pour être stables, les stratégies zéro déterminant nécessitent des informations supplémentaires sur leurs adversaires. Ces informations leur confèrent un avantage certain mais probablement seulement temporaire. Un tel avantage est voué à être de courte durée car des stratégies opposées évoluent pour contrecarrer la reconnaissance, disent-ils.

En d'autres termes, les autres joueurs devraient développer une sorte de camouflage qui les empêche d'être repérés et exploités.

Cela peut expliquer pourquoi personne n'a trouvé d'exemples de stratégies zéro déterminant dans la nature : dans la plupart des cas, elles ne seront pas stables et même si elles le sont, la situation risque d'être de courte durée. Comme Adami et Hintze l'ont dit dans le titre de leur article : gagner n'est pas tout.

Cela ne veut pas dire qu'il n'y a pas d'exemples prêts à être trouvés. Au contraire. Ce type de course aux armements évolutif a été et sera observé dans toute la biosphère, disent Adami et Hintze.

Bien sûr, ce n'est que le début d'une approche entièrement nouvelle de la théorie des jeux qui a de profondes implications. Suggestions pour savoir où cela pourrait avoir le plus d'impact dans la section commentaires s'il vous plaît.

Réf : arxiv.org/abs/1208.2666 : Gagner n'est pas tout : stabilité évolutive des stratégies Zéro Déterminant

cacher