Coordination and correlation in multi-player sequential games

Computing game-theoretic solution concepts is fundamental to describing the behavior of rational agents taking part in strategic interactions. The large majority of equilibrium-finding techniques are only suited for two-player, zero-sum games, where it is possible to compute strong solutions in theory and in practice. In this thesis, we make a step in the direction of solving more general problems, by focusing on multi-player, general-sum, extensive-form games. In many real-world problems, agents may exploit some form of communication to achieve coordinated behaviors. We mainly focus on the problem of reaching coordination under minimal communication requirements, that is by assuming agents can communicate only before the beginning of the game. We identify three different settings in which communication facilitates coordinated behaviors, and study each of them from a computational perspective. First, we study problems where teams of agents interact against an opponent. In doing so, we define the appropriate solution concepts, and classify their computational complexity and inefficiencies. We study how to compute an optimal solutions in each of these settings. Then, we focus on the case in which only preplay communication is permitted, and develop the first scalable algorithm to learn an approximate solution for the problem. The second problem we investigate is computing correlated equilibria and coarse correlated equilibria in multi-player, general-sum, sequential games. We characterize the computational complexity of computing optimal and approximate solutions for these problems, providing both positive and negative results. Then, we describe algorithmic results, and adapt a state-of-the-art regret minimization technique for the two-player, zero-sum setting to find an approximate coarse correlated equilibrium in our setting. The last problem we study is how to coordinate agents’ behavior through the strategic provision of payoff-relevant information. We study information-structure design problems in which multiple agents can interact in a sequential game. We propose a novel notion of persuasive signaling scheme, and characterize its computational complexity.

La capacità di calcolare strategie di equilibrio è fondamentale per descrivere il comportamento di agenti razionali che si confrontano in interazioni strategiche. La maggior parte delle tecniche attualmente disponibili per la risoluzione di questi problemi richiede che siano presenti esattamente due giocatori, con obiettivi opposti. Scenari di questo tipo possono essere risolti in maniera efficiente, ma rimangono molto restrittivi. Questa tesi pone le basi per lo studio di modelli più flessibili e generali, andando a trattare problemi con un numero arbitrario di agenti, funzioni di utilità generiche, ed interazioni sequenziali. In molti problemi reali, gli agenti possono sfruttare determinate forme di comunicazione per coordinare le proprie azioni. Questa tesi pone l’accento su come sia possibile raggiungere comportamenti coordinati dei giocatori quando questi ultimi possono scambiare messaggi solo prima dell’inizio del gioco. Si presentano risultati di natura computazionale per tre diversi scenari in cui la possibilità di comunicare induce comportamenti coordinati tra i giocatori. Il primo scenario è quello in cui squadre di agenti devono interagire contro un avversario. Vengono definite nozioni di equilibrio appropriate per questi problemi, e se ne studia le relative complessità computazionali e inefficienze. Successivamente, si studia come calcolare soluzioni ottime e approssimate per ciascuno degli equilibri definiti in precedenza. Il secondo problema è relativo al calcolo di equilibri correlati e equilibri coarse correlati in scenari con un numero arbitrario di giocatori, funzioni di utilità generiche, e interazioni sequenziali. Si presenta una caratterizzazione computazionale del calcolo di soluzioni ottime e approssimate per questi equilibri. Questi risultati vengono arricchiti dallo studio di algoritmi scalabili basati su tecniche di regret-minimization. Il terzo scenario è quello in cui un agente può condizionare il comportamento dei rimanenti giocatori attraverso la condivisione strategica di informazioni. La tesi estende il modello classico di Bayesian persuasion a setting di maggiore complessità, in cui molteplici agenti, sulla base delle informazioni ricevute, devono stabilire come interagire in un gioco sequenziale.