Public information representation for adversarial team games

Nowadays, the push for automatic decision making tools is driven by the extraordinary results obtained by Artificial Intelligence (AI) techniques. In this work, we focus on a team of agents playing a sequential game against a single adversary. The presence of asymmetric information among the members of the team makes the problem of computing a solution hard even with zero-sum payoffs. A number of ad hoc algorithms available in the literature tackle this problem resorting to Linear Programming. Our novel approach consists in using a procedure to convert the game to a classical two-player zero-sum game. In this converted game, the team is transformed into a single coordinator player which only knows information common to the whole team and prescribes to the players an action for any possible private state. We call this procedure Public Team Conversion, and its result is an extensive-form game maintaining most of the structure of the original game. Our conversion allows one to adopt the highly scalable and performant techniques already developed for two-players zero sum games, including techniques for generating automated abstractions. However, our procedure produces a game which may be exponentially larger than the original one, but this is unavoidable due to the NP-hard nature of the problem. To cope with the computational issues due to the size of the converted game, we provide two pruning techniques able to considerably reduce the increase in size. We also present experimental results obtained by applying our technique to standard benchmarks in the field, Kuhn Poker and Leduc Poker. We also apply state of the art equilibrium computation algorithms on the resulting game, showing the effectiveness of our approach.

Al giorno d’oggi, l’interesse verso strumenti decisionali automatizzati è spinto dagli straordinari risultati ottenuti dall’uso di tecniche di intelligenza artificiale. In questo lavoro, ci focalizziamo sul caso in cui un team di agenti gioca sequenzialmente contro un avversario. La presenza di informazione asimmetrica tra i membri della squadra rende difficile il calcolo di una soluzione anche nel caso di payoff a somma zero. Gli algoritmi ad hoc disponibili in letteratura affrontano questo problema utilizzando tecniche di Programmazione Lineare. L’approccio che proponiamo in questo lavoro consiste invece nell’usare una procedura per convertire il gioco in un altro a due giocatori e somma zero. Nel gioco convertito, il team è trasformato in un singolo coordinatore, a conoscenza solo dell’informazione comune a tutti i membri del team, e che prescrive ai giocatori un’azione per ogni possibile stato privato. Chiamiamo questa procedura Public Team Conversion, e il suo risultato è un gioco in forma estesa che mantiene la maggior parte della struttura del gioco originale. La nostra conversione permette di adottare le tecniche scalabili e performanti già sviluppate per i giochi a due giocatori e somma zero, includendo anche tecniche per la generazione automatica di astrazioni. Tuttavia, questa procedura produce un gioco che potrebbe essere esponenzialmente più grande dell’originale, ma questo non è evitabile a causa della natura NP-hard del problema. Per risolvere parte delle difficoltà computazionali dovute alla grandezza del gioco convertito, abbiamo sviluppato due tecniche di pruning, capaci di diminuire considerevolmente l’aumento di dimensione. Presentiamo anche risultati sperimentali ottenuti applicando la nostra conversione a benchmark standard nell’ambito, Kuhn Poker e Leduc Poker. Applicando algoritmi stato dell’arte per la computazione di equilibri sul gioco risultante, mostriamo l’efficacia del nostro approccio.