Algorithm for subgame solving in Adversarial Team Games

The field of Algorithmic Game Theory studies optimal decision-making scenarios through mathematical tools known as games. In a game, a certain number of agents interact with an environment receiving a reward based on their behaviour. The goal of each agent is to find the optimal behaviour that maximizes its reward. The growing interest in these problems has led to the development of efficient and scalable techniques, especially in the case of two-player games. In this thesis, we focus on solving Adversarial Team Games, a scenario less studied in the literature in which a team of agents competes against an adversary team to maximize the overall gain. Existing techniques for solving these games mainly rely on linear programming methods, which do not scale when the size of the problem instance becomes exponentially large. This thesis presents a technique to effi- ciently solve Adversarial Team Games by exploiting subgame solving techniques already known in the two-player case. In this approach, a coarse strategy for the team, called a blueprint, is found by solving a simplified version of the original game. The blueprint strategy is iteratively refined by solving reduced portions of the original game. Finally, we test the performances achieved by our algorithm by solving standard benchmark games.

Nel campo di della Teoria dei Giochi Computazionale si studiano scenari di decisione ottima attraverso strumenti matematici noti come giochi. In un gioco, un certo numero di agenti interagisce con un ambiente ricevendo una ricompensa in base al loro comporta- mento. L’obbiettivo di ogni agente è di trovare il comportamento ottimo che massimizza la sua ricompensa. Il sempre più crescente interesse verso questi problemi ha portato allo sviluppo di tecniche efficienti e scalabili, soprattutto nel caso specifico dei giochi a due gio- catori. In questa tesi ci concentriamo sulla risoluzione di giochi a squadre avversarie, uno scenario meno studiato in letteratura, in cui una squadra di agenti compete contro una squadra avversaria al fine di massimizzare il guadagno complessivo. Le tecniche esistenti per risolvere questa tipologia di giochi, basandosi principalmente sulla programmazione lineare, non sono in grado di scalare per giochi di grandi dimensioni. In questo lavoro, presentiamo una tecnica scalabile per risolvere i giochi a squadre avversarie sfruttando tecniche di subgame solving, già note nel caso a due giocatori. In questo approccio si trova una strategia grezza per la squadra, denominata blueprint, risolvendo una versione semplificata del gioco originale. La blueprint viene raffinata durante il gioco risolvendo iterativamente porzioni ridotte del gioco originale. Infine, mostriamo i risultati ottenuti con il nostro approccio su alcuni giochi di esempio.