Chercheur résout problème théorie des jeux 60 ans
Chercheur résout problème théorie des jeux 60 ans. Pour comprendre la navigation des véhicules autonomes dans des scénarios routiers complexes, les chercheurs utilisent souvent la théorie des jeux, un modèle mathématique représentant le comportement stratégique d’agents rationnels pour atteindre leurs objectifs.
Dejan Milutinovic, professeur de génie électrique et informatique à l’UC Santa Cruz, s’est concentré sur les jeux différentiels, une sous-section complexe de la théorie des jeux traitant des joueurs en mouvement. Un de ces jeux est le jeu de la poursuite murale, un modèle simple impliquant un poursuivant plus rapide cherchant à attraper un évadé plus lent contraint à un chemin le long d’un mur.
Chercheur résout un problème de théorie des jeux vieux de 60 ans : IEEE Transactions on Automatic Control
Pendant près de 60 ans, un dilemme persistait dans ce jeu, où plusieurs positions semblaient manquer d’une solution optimale. Cependant, Milutinovic et son équipe ont récemment prouvé, dans un article publié dans IEEE Transactions on Automatic Control, que ce dilemme n’est pas valable. Ils ont introduit une nouvelle approche analytique démontrant qu’une solution déterministe existe toujours pour le jeu de la poursuite murale. Cette découverte pourrait aider à résoudre des défis similaires dans les jeux différentiels et améliorer la réflexion sur les systèmes autonomes, comme les véhicules sans conducteur.
Ainsi, la théorie des jeux trouve des applications dans divers domaines, notamment l’économie, la politique, l’informatique et l’ingénierie, pour comprendre de manière exhaustive les comportements. L’équilibre de Nash, proposé par le mathématicien John Nash, signifie des stratégies optimales minimisant les regrets pour tous les joueurs. Ce concept s’étend au jeu de la poursuite murale, où les joueurs rationnels adoptent leur stratégie d’équilibre pour éviter les regrets accrus.
L’analyse classique de ce jeu échoue pour un ensemble spécifique de positions, appelé surface singulière, conduisant à l’acceptation du dilemme. Cependant, Milutinovic et ses collègues ont élaboré une nouvelle approche, en utilisant un concept mathématique qui n’était pas disponible lors de la conception du jeu. En intégrant la solution de viscosité de l’équation de Hamilton-Jacobi-Isaacs et une analyse de perte pour la surface singulière, ils ont déterminé qu’une solution optimale existe pour toutes les circonstances du jeu, résolvant ainsi le dilemme.
Équation de Hamilton-Jacobi-Isaacs
Le concept de solution de viscosité dans les équations aux dérivées partielles, apparu dans les années 1980, offre une perspective nouvelle pour résoudre des équations telles que l’équation de Hamilton-Jacobi-Isaacs. Ce concept est particulièrement pertinent pour les problèmes de contrôle optimal et de théorie des jeux. Il implique l’utilisation du calcul pour trouver les dérivées des fonctions, ce qui est simple lorsque les dérivées sont bien définies, mais pas dans des cas comme le jeu de la poursuite murale.
Dans les situations où il n’y a pas de dérivée bien définie, les joueurs choisiraient généralement au hasard des actions et accepteraient les pertes résultantes. Cependant, les joueurs rationnels cherchent à minimiser les pertes. Pour résoudre ce problème, les chercheurs ont minutieusement analysé la solution de viscosité autour des points avec des dérivées non définies. Par la suite, ils ont introduit une analyse du taux de perte, ce qui a conduit à l’émergence de stratégies optimales bien définies pour ces points.
Cette analyse résout de manière cruciale le dilemme de la surface singulière tout en restant cohérente avec l’analyse classique dans les états pertinents. Cette percée a des implications plus larges pour la théorie des jeux. Par conséquent, Milutinovic et son équipe visent à appliquer cela à d’autres dilemmes et encouragent la communauté de recherche à faire de même.
Lire l’article original sur sciencedaily.
Lire la suite : Utiliser le jeu Squid pour enseigner l’économie
