Adversarial team games : a computational perspective

The study of multi-agents systems in which multiple rational and autonomous agents interact in a strategic setting is gathering increasing attention in the Artificial Intelligence community. It is particularly interesting to describe the scenario in which a team of agents with the same goals has to cooperate in order to achieve them, in the presence of an attacker that tries to minimize their payoff. In order to model this problem we resort to tools from Game Theory and, specifically, we consider the class of adversarial team games. The most natural solution concept for this type of games is the team-maxmin equilibrium, which describes the scenario in which team members are able to reach only partial coordination. We first analyze the theoretical properties of the equilibrium by studying the classical inefficiency indexes and introducing a new measure that characterizes the loss due to the inability of reaching full coordination. Next, we analyze the computational complexity of determining the equilibrium. We devise, along with the exact algorithm to compute the equilibrium, three approximation algorithms, paying particular attention to their scalability and experimentally evaluating each of them. The team-maxmin equilibrium is then applied to the specific setting of security games. We address the problem of computing multi-resource defensive strategies in response to an alarm signal, when patrolling an environment at risk. This scenario is described by a specific class of games and, by knowing its structure, we adapt the previously presented algorithms to reach better performances. We provide an experimental analysis for each of the new algorithms by testing them over game instances that mimic real-world patrolling problems.

Lo studio delle modalità di interazione di molteplici agenti autonomi in scenari strategici sta ricevendo notevole attenzione all’interno della comunità dell’Intelligenza Artificiale. Risulta di particolare interesse determinare un modello che descriva come gruppi di agenti con gli stessi obbiettivi possano cooperare per raggiungerli, in presenza di un attaccante che cerca di minimizzare il loro payoff finale. Per modellare questo problema utilizziamo gli strumenti della Teoria dei Giochi e, più specificatamente, prendiamo in considerazione la classe di giochi denominata adversarial team games. L’equilibrio più appropriato per questo tipo di gioco è il team-maxmin equilibrium, che descrive lo scenario in cui i membri del team possano coordinarsi solo in maniera parziale. In primo luogo ci concentriamo sulle proprietà del team-maxmin equilibrium, analizzandone gli indici di inefficienza classici ed introducendone uno nuovo, che caratterizzi la perdita dovuta alla mancanza di una coordinazione completa. In seguito analizziamo la complessità computazionale associata all’equilibrio. Vengono presentati, oltre all’algoritmo per raggiungere in maniera esatta il team-maxmin equilibrium, alcuni algoritmi approssimati, ponendo particolare attenzione alla scalabilità delle soluzioni proposte e verificandone la qualità anche in via sperimentale. Successivamente viene presentata un’applicazione del team-maxmin equilibrium a problemi di sicurezza. In particolare analizziamo come sia possibile, durante il pattugliamento di un sito a rischio, determinare strategie difensive multi-agente a fronte di un segnale d’allarme. Questo scenario viene descritto attraverso una specifica classe di giochi, la cui struttura consente di modificare gli algoritmi presentati in precedenza per ottenere un miglioramento nelle loro performance. Anche in questo caso le soluzioni proposte vengono testate su istanze che ricalcano potenziali problemi di pattugliamento reali.