La percée de l’IA résout le problème épineux de la théorie des jeux

Pixabay / Pexels

Source: Pixabay / Pexels

Dans une récente percée de l’apprentissage automatique de l’intelligence artificielle (IA) dans la théorie des jeux, les chercheurs résolvent un problème persistant avec l’applicabilité dans le monde réel – pour le mieux. Lors de la 34e Conférence sur les systèmes de traitement de l’information neuronale (NeurIPS 2020) le mois dernier, des chercheurs de Politecnico di Milano et de l’Université Carnegie Mellon ont présenté un nouvel algorithme d’IA qui permet une approche plus nuancée de la résolution des problèmes de théorie des jeux – une solution qui a un impact potentiel sur le monde réel en économie, industrie, élaboration des politiques et science.

La théorie des jeux est la science de la stratégie qui a été lancée par le mathématicien de Princeton John Von Neumann (1903-1957) avec la publication en 1928 de sa théorie des jeux de société intitulée «Zur Theorie der Gesellschaftsspiele». Il s’agit d’une approche mathématique de la modélisation du comportement.

Mentionner la «théorie des jeux» et le concept d’équilibre de Nash, l’un des théorèmes décisionnels les plus importants de la théorie des jeux, peut venir à l’esprit des économistes, mathématiciens, scientifiques, programmeurs informatiques, PDG, décideurs politiques, entrepreneurs, analystes financiers, et les technophiles. Le mathématicien américain John Forbes Nath Jr. (1928-2015) est récipiendaire du prix Abel, du prix Nobel Memorial en sciences économiques et du prix John von Neumann Theory, parmi de nombreux autres prix et distinctions.

L’équilibre de Nash met en avant le concept que le résultat optimal d’un jeu est quand il n’y a aucune incitation pour les joueurs à s’écarter de leur stratégie initiale après avoir considéré le choix de l’adversaire – qu’un équilibre existe si on donne un nombre fini de joueurs et de mouvements.

En science des données, l’équilibre de Nash suppose une interaction entièrement décentralisée entre les joueurs, il s’agit donc d’une distribution sur l’espace stratégique non corrélé.

Pour illustrer ce concept, considérons un jeu hypothétique dans lequel deux enfants ont le choix entre deux stratégies, «get-cookie» ou «perd-cookie». Choisissez la stratégie de get-cookie et recevez un délicieux cookie aux pépites de chocolat. Choisissez la stratégie perdant-cookie et renoncez à une friandise savoureuse. Il s’ensuit logiquement que les deux enfants poursuivent pour recevoir un cookie aux pépites de chocolat et choisissent la stratégie de get-cookie. Même si l’un des enfants a révélé la sienne ou sa stratégie à l’autre, cela n’a pas d’incidence sur le comportement de l’autre enfant. En d’autres termes, les enfants ne sont pas incités à s’écarter de leur stratégie initiale de get-cookie – il suffit de demander à n’importe quel parent d’enfants gourmands.

A lire aussi  Comment utiliser les récompenses et les punitions pour obtenir le résultat souhaité

La théorie des jeux standard suppose homo economicus (homme économique), une vision selon laquelle les gens agissent comme des agents rationnels et intéressés qui recherchent des résultats qui maximisent l’utilité. Ce point de vue n’est pas populaire parmi les sociologues, les psychologues, les anthropologues et les économistes comportementaux car de nombreux facteurs peuvent avoir un impact sur les décisions tels que des informations imparfaites, des changements de préférence, des préférences sociales individuelles (équité, altruisme, réciprocité, etc.), etc. les raisons.

Une théorie des jeux commune qui illustre l’équilibre de Nash est le dilemme des prisonniers, où les procureurs manquant de preuves pour condamner, offrent à deux prisonniers des informations imparfaites (chacun est détenu dans une cellule d’isolement séparée sans capacité de communiquer avec l’autre), le choix soit de témoigner contre l’autre ou garder le silence. Si aucun des deux ne s’avoue, les deux purgeront un an de prison. Si l’un trahit l’autre et que l’autre se tait, le traître est entièrement libéré tandis que l’autre purge 10 ans de prison. Si les deux trahissent l’autre, chacun purge cinq ans de prison. L’équilibre de Nash dans le dilemme des prisonniers est que les deux prisonniers trahissent l’autre.

Dans des situations complexes du monde réel où tout n’est pas si arbitrairement noir et blanc, il n’est pas rare de trouver des lacunes dans l’équilibre de Nash. Dans ces scénarios, le concept d’équilibre corrélé (EC) mis en avant en 1974 par le mathématicien Robert J. Aumann, lauréat du prix Sveriges Riksbank en sciences économiques à la mémoire d’Alfred Nobel 2005, offre une approche plus générale et flexible.

A lire aussi  Que se passe-t-il après la fin de la relation thérapeutique ?

«Une stratégie corrélée est une distribution générale sur des profils d’action commune et elle est généralement modélisée via un médiateur externe de confiance qui tire un profil d’action de cette distribution et recommande en privé à chaque joueur son composant», a écrit l’équipe de recherche d’Andrea Celli, Alberto Marchesi, Gabriele Farina et Nicola Gatti.

Les chercheurs citent de nombreuses faiblesses potentielles dans le concept d’équilibre de Nash où l’équilibre corrélé peut atténuer. En reprenant l’exemple précédent, imaginons que la maman des enfants, un médiateur externe de confiance, fournisse une recommandation à chaque enfant en privé pendant le jeu.

«La plupart des travaux de la communauté d’apprentissage par renforcement multi-agents étudient soit des contextes entièrement compétitifs, où les agents jouent de manière égoïste pour atteindre un équilibre de Nash, soit des scénarios entièrement coopératifs dans lesquels les agents ont exactement les mêmes objectifs», ont expliqué les chercheurs dans l’étude. «Notre travail pourrait permettre des techniques qui se situent entre ces deux extrêmes: les agents ont des objectifs arbitraires, mais coordonnent leurs actions vers un équilibre avec certaines propriétés souhaitées.

L’équilibre corrélé de forme étendue (EFCE) élargit l’équilibre corrélé de forme stratégique d’Aumann; les recommandations aux joueurs sont révélées progressivement à un joueur lorsqu’il atteint d’éventuels nouveaux ensembles d’informations, points de décision, au moment où le mouvement peut être exécuté. Si le joueur s’écarte de l’action recommandée à n’importe quel point de décision, le joueur ne recevra aucune recommandation à l’avenir.

Pour modéliser l’équilibre corrélé de forme extensive, les chercheurs ont créé un algorithme appelé Internal Counterfactual Regret Minimization (ICFR) qui minimise les regrets des agents déclencheurs grâce à la décomposition des regrets au niveau de chaque ensemble d’informations. En d’autres termes, l’algorithme est un moyen de minimiser les regrets de sous-arbre laminaire.

A lire aussi  10 questions à poser avant de commencer une collaboration

Le chercheur a évalué la convergence de leur algorithme en utilisant des jeux de référence standard de quatre jeux multijoueurs, Kuhn poker, Leduc poker, Goofspiel et Battleship.

«Nous montrons qu’il est possible d’orchestrer la procédure d’apprentissage afin que, pour chaque ensemble d’informations, l’utilisation d’un minimiseur de regret par tour ne compromet pas la convergence globale de l’algorithme», ont écrit les chercheurs.

Les chercheurs du Politecnico di Milano et de l’Université Carnegie Mellon figuraient parmi les lauréats des prestigieux prix NeurIPS 2020 Best Paper.

«Cet article montre l’existence de tels algorithmes minimisant les regrets qui convergent vers l’EC dans une classe de jeux beaucoup plus large: à savoir les jeux de forme extensive (ou arborescente)», ont écrit les présidents du programme NeurIPS 2020 dans le blog de la conférence. «Ce résultat résout un problème ouvert de longue date à l’interface de la théorie des jeux, de l’informatique et de l’économie et peut avoir un impact substantiel sur les jeux qui impliquent un médiateur, par exemple sur le routage efficace du trafic via des applications de navigation.»

«Nous avons fourni des preuves empiriques que le CIIF calcule des équilibres qui atteignent un bien-être social« pas trop loin »de l’optimum», ont rapporté les chercheurs. «Cela pourrait avoir un impact sociétal sans doute positif lorsqu’il est appliqué à de réels problèmes économiques.»

Copyright © 2021 Cami Rosso Tous droits réservés.