Dans cette thèse, nous avons étudié des jeux dans lesquels une équipe d’agents affronte plusieurs adversaires indépendants. De tels jeux se retrouvent dans des applications cruciales telles que la lutte anti-braconnage, où une équipe de gardes forestiers protège une zone forestière contre des braconniers planifiant des incursions indépendantes. Nous nous sommes intéressés au calcul efficace des équilibres de Nash dans ces jeux, c’est-à-dire des stratégies pour chaque joueur desquelles aucun agent n’a intérêt à dévier. Ces équilibres reflètent l'état stable du jeu, dans lequel chaque agent a une attente correcte quant au comportement des autres joueurs et agit de manière rationnelle en s’appuyant sur ces informations. L’hypothèse centrale est que si ces comportements d’équilibre ne peuvent pas être calculés efficacement, on ne peut pas s’attendre à ce que des agents réels découvrent de tels comportements en situation réelle.
Nous avons tout d’abord présenté le cadre des jeux d’équipe multi-adversaires (Multi-Adversarial Team Games, MATG), qui généralise le cadre des jeux d’équipe adverses (Adversarial Team Games, ATG) à des scénarios impliquant plusieurs adversaires indépendants. Notre première contribution a consisté à montrer que l’algorithme MATG Gradient Descent Max calcule un équilibre de Nash approché d’un MATG en un temps polynomial par rapport aux paramètres naturels du jeu et à l'inverse de la précision requise.
Dans un deuxième temps, nous avons proposé d’étendre les MATG au cadre markovien à horizon fini, définissant les jeux markoviens d’équipe multi-adversaires à horizon fini (FH-MATMG). Nous avons démontré qu'un calcul d’équilibre efficace n'est pas possible dans le cas multi-adversaires général, car PPAD-difficile, mais qu’il devient possible lorsqu’il n’y a qu’un seul adversaire, ou lorsque les transitions sont additives (dans les AT-FH-MATMG). Pour ce faire, nous avons établi que des variantes de l’algorithme Nash Value Iteration peuvent être utilisées pour calculer des équilibres de Nash approchés dans ces situations.
Enfin, nous avons étendu le modèle FH-MATMG au cadre de l'observabilité partielle (PO-FH-MATMG). Nous avons démontré que le calcul de politiques optimales pour l’équipe dans ces jeux est NEXP-difficile. C’est ce qui motive notre approche, qui repose sur des méthodes empiriques basées sur l’apprentissage par renforcement multi-agents (MARL) afin de trouver de bonnes politiques dans ces jeux. Nous avons donc modélisé le problème de la lutte anti-braconnage en tant que FH-MATMG partiellement observable, et avons fourni une implémentation de ce jeu sous la forme de l’environnement Anti-Poaching Environment (APE). APE illustre ainsi l'importance des PO-FH-MATMG en tant qu’outil de modélisation, tout en fournissant un benchmark essentiel pour cette classe de jeux.
Des bibliothèques de code pour l'ensemble des modèles et algorithmes développés pendant cette thèse sont également disponibles, accompagnées d'évaluations empiriques par rapport à l'état de l'art. |
In this thesis, we study games where a team of agents plays against multiple, independent adversaries. Such games arise in critical applications such as anti-poaching, where a team of rangers protects a conservation area against poachers planning independent incursions. We focus on the efficient computation of Nash equilibria in these games—strategies where no agent has an incentive to deviate. These equilibria capture the steady state of the system, where each agent holds correct expectations about the behavior of others and acts rationally based on this information. Our core hypothesis is that if these equilibria cannot be computed efficiently, real-world agents cannot be expected to discover such behaviors in practice.
We first introduce the Multi-Adversarial Team Games (MATG) framework, generalizing the Adversarial Team Games (ATG) framework to scenarios involving multiple independent adversaries. As a first contribution, we show that MATG Gradient Descent Max computes an approximate Nash equilibrium of an MATG in time polynomial in the game's natural parameters and in the inverse of the required precision.
In our second contribution, we extend MATGs to the finite-horizon Markov setting, defining Finite-Horizon Multi-Adversarial Team Markov Games (FH-MATMGs). We prove that equilibrium computation is intractable (PPAD-hard) in the general case, but becomes tractable either when there is a single adversary or when transitions are additive (AT-FH-MATMGs) in the general multi-adversarial case. We establish this tractability by proving that variants of Nash Value Iteration can compute approximate Nash equilibria for these settings.
Finally, we introduce the Partially Observable FH-MATMG (PO-FH-MATMG), extending the model to environments with partial observability. We show that computing optimal policies for the team in this class of games is NEXP-hard. This complexity motivates our deployment of empirical methods based on Multi-Agent Reinforcement Learning (MARL) to find high-quality policies. Consequently, we model the anti-poaching problem as a PO-FH-MATMG and provide an implementation of this game as the Anti-Poaching Environment (APE). APE serves both to illustrate the modeling power of PO-FH-MATMGs and to provide a challenging benchmark for this class of games.
We also provide reusable libraries for all models and algorithms developed in this thesis, alongside empirical evaluations against the state of the art. |