Un chercheur résout un dilemme de la théorie des jeux vieux de près de 60 ans

Dejan Milutinovic, professeur de génie électrique et informatique à l’UC Santa Cruz, a longtemps travaillé avec des collègues sur le sous-ensemble complexe de la théorie des jeux appelé jeux différentiels, qui concerne les joueurs en mouvement. L’un de ces jeux s’appelle le jeu de poursuite au mur, un modèle relativement simple pour une situation dans laquelle un poursuivant plus rapide a pour objectif d’attraper un évadé plus lent qui est confiné à se déplacer le long d’un mur.

Depuis que ce jeu a été décrit pour la première fois il y a près de 60 ans, il y a eu un dilemme dans le jeu – un ensemble de positions où l’on pensait qu’aucune solution optimale de jeu n’existait. Mais maintenant, Milutinovic et ses collègues ont prouvé dans un nouvel article publié dans la revue Transactions IEEE sur le contrôle automatique que ce dilemme de longue date n’existe pas réellement, et a introduit une nouvelle méthode d’analyse qui prouve qu’il existe toujours une solution déterministe au jeu de la poursuite du mur. Cette découverte ouvre la porte à la résolution d’autres défis similaires qui existent dans le domaine des jeux différentiels et permet de mieux raisonner sur les systèmes autonomes tels que les véhicules sans conducteur.

La théorie des jeux est utilisée pour raisonner sur le comportement dans un large éventail de domaines, tels que l’économie, les sciences politiques, l’informatique et l’ingénierie. Dans la théorie des jeux, l’équilibre de Nash est l’un des concepts les plus communément reconnus. Le concept a été introduit par le mathématicien John Nash et il définit des stratégies de jeu optimales pour tous les joueurs du jeu afin de terminer le jeu avec le moindre regret. Tout joueur qui choisit de ne pas jouer sa stratégie optimale de jeu se retrouvera avec plus de regrets, par conséquent, les joueurs rationnels sont tous motivés à jouer leur stratégie d’équilibre.

Ce concept s’applique au jeu de poursuite au mur — une paire de stratégies d’équilibre de Nash classique pour les deux joueurs, le poursuivant et l’esquive, qui décrit leur meilleure stratégie dans presque toutes leurs positions. Cependant, il existe un ensemble de positions entre le poursuivant et l’évadé pour lesquelles l’analyse classique ne parvient pas à fournir les stratégies de jeu optimales et conclut à l’existence du dilemme. Cet ensemble de positions est connu comme une surface singulière – et pendant des années, la communauté des chercheurs a accepté le dilemme comme un fait.

Mais Milutinovic et ses co-auteurs ne voulaient pas accepter cela.

“Cela nous a dérangés parce que nous pensions que si l’évadé sait qu’il y a une surface singulière, il y a une menace que l’évadé puisse aller à la surface singulière et en abuser”, a déclaré Milutinovic. “L’esquive peut vous forcer à aller à la surface singulière où vous ne savez pas comment agir de manière optimale – et nous ne savons tout simplement pas quelle serait l’implication de cela dans des jeux beaucoup plus compliqués.”

Milutinovic et ses co-auteurs ont donc proposé une nouvelle façon d’aborder le problème, en utilisant un concept mathématique qui n’existait pas lorsque le jeu de poursuite au mur a été conçu à l’origine. En utilisant la solution de viscosité de l’équation de Hamilton-Jacobi-Isaacs et en introduisant une analyse du taux de perte pour résoudre la surface singulière, ils ont pu découvrir qu’une solution optimale de jeu peut être déterminée dans toutes les circonstances du jeu et résoudre le dilemme.

La solution de viscosité des équations aux dérivées partielles est un concept mathématique qui était inexistant jusque dans les années 1980 et offre une ligne de raisonnement unique sur la solution de l’équation de Hamilton-Jacobi-Isaacs. Il est maintenant bien connu que le concept est pertinent pour raisonner sur les problèmes de contrôle optimal et de théorie des jeux.

L’utilisation de solutions de viscosité, qui sont des fonctions, pour résoudre des problèmes de théorie des jeux implique l’utilisation de calculs pour trouver les dérivées de ces fonctions. Il est relativement facile de trouver des solutions optimales de jeu lorsque la solution de viscosité associée à un jeu a des dérivées bien définies. Ce n’est pas le cas pour le jeu de poursuite au mur, et ce manque de dérivées bien définies crée le dilemme.

Généralement, lorsqu’un dilemme existe, une approche pratique consiste à ce que les joueurs choisissent au hasard l’une des actions possibles et acceptent les pertes résultant de ces décisions. Mais c’est là que réside le hic : s’il y a une perte, chaque joueur rationnel voudra la minimiser.

Ainsi, pour trouver comment les joueurs pourraient minimiser leurs pertes, les auteurs ont analysé la solution de viscosité de l’équation de Hamilton-Jacobi-Isaacs autour de la surface singulière où les dérivées ne sont pas bien définies. Ensuite, ils ont introduit une analyse du taux de perte à travers ces états de surface singuliers de l’équation. Ils ont constaté que lorsque chaque acteur minimise son taux de pertes, il existe des stratégies de jeu bien définies pour leurs actions sur la surface singulière.

Les auteurs ont constaté que non seulement ce taux de minimisation des pertes définit les actions optimales du jeu pour la surface singulière, mais qu’il est également en accord avec les actions optimales du jeu dans tous les états possibles où l’analyse classique est également capable de trouver ces actions.

“Lorsque nous prenons l’analyse du taux de perte et l’appliquons ailleurs, les actions optimales de jeu de l’analyse classique ne sont pas affectées”, a déclaré Milutinovic. “Nous prenons la théorie classique et nous l’augmentons avec l’analyse du taux de perte, donc une solution existe partout. C’est un résultat important montrant que l’augmentation n’est pas seulement une solution pour trouver une solution sur la surface singulière, mais une contribution fondamentale à la théorie des jeux.

Milutinovic et ses coauteurs sont intéressés à explorer d’autres problèmes de théorie des jeux avec des surfaces singulières où leur nouvelle méthode pourrait être appliquée. Le document est également un appel ouvert à la communauté des chercheurs pour qu’ils examinent de la même manière d’autres dilemmes.

“Maintenant, la question est, quel genre d’autres dilemmes pouvons-nous résoudre?” dit Milutinovic.