Learning optimal equilibria and mechanisms under information asymmetry

Multi-agent environments represent a ubiquitous case of application for game-theoretic techniques. The default game model involves the presence of a large number of agents with asymmetric information on the environment that sequentially interact between them. Algorithmic Game Theory starts from particular notions of equilibria, i.e., sets of strategies for the players such that no one has incentive to deviate from her strategy, and studies the development of algorithms for computing or approximating those. The milestones achieved by researchers in the field over the last decades made it clear how, in order to obtain successful deployments of such game-theoretic techniques in complex real-world settings, it is of uttermost importance to leverage the formulation of learning algorithms for finding approximately optimal solutions of the games. Most of the research has been focused on the design of learning algorithms for simple scenarios, e.g., two-players games, but algorithms for more general cases are still far from reaching adequate performances. The goal of this thesis is to advance the research in this sense. In particular, we investigate different multi-agent scenarios, which we differentiate based on the role of the players holding information on the environment, focusing on the definition of suitable learning algorithms for finding optimal players' strategies. In the first part of the thesis, we study cases in which the agents holding information are active, i.e., they can leverage their information to take informed actions in the game. In this context, we tackle two distinct cases: team games, which model cases in which two teams of agents compete one against the other, as well as the broader class of general-sum games, in which we do not make any particular assumption on the players. For team games, we define a simple transformation that uses a correlation protocol based on public information for obtaining a compact formulation of the teams' strategy sets. The transformation yields an equivalent two-players zero-sum game, which can be naturally used to obtain the first no-regret learning-based algorithm for computing equilibria in team games. Then, inspired by previous literature, we lay the ground for the formulation in the context of team games of popular techniques that proved crucial for achieving strong performances in two-players games, i.e., stochastic regret minimization and subgame solving. For general-sum games, instead, we observe that the mainstream approach that is being used, which consists in the use of decentralized and coupled learning dynamics for approximating different types of correlated equilibria, suffers from major drawbacks as it does not offer any guarantee on the type of equilibrium reached. To mitigate this issue, we take the perspective of a mediator issuing action recommendations to the players and design a centralized learning dynamic that guarantees convergence to the set of optimal correlated equilibria in sequential games. The second part of the thesis is devoted to the study of cases in which the agents holding information are passive, i.e., they cannot directly take actions in the game, but can only report their information (possibly untruthfully) in order to influence the behavior of another uninformed party. This setting corresponds to the case of information acquisition, in which we take the perspective of the uninformed agent (which we call the principal) that is interested in gathering information from the agents, incentivizing their behavior by means of mechanisms composed by an action policy and/or payment functions. In this context, we separately study the cases in which the principal's mechanisms are composed exclusively by action policies and payment schemes and, for both cases, we provide algorithms for learning optimal mechanisms via interactions with the agents.

Gli ambienti con molteplici agenti rappresentano un caso molto diffuso di applicazione per tecniche di teoria dei giochi. Il modello base di gioco prevede la presenza di un gran numero di agenti che dispongono di informazioni asimmetriche riguardo lo stato dell'ambiente e che interagiscono tra loro in maniera sequenziale. La teoria dei giochi algoritmica, partendo da particolari concetti di equilibrio (ovvero strategie tali per cui nessun agente ha incentivo a cambiare la propria strategia), studia lo sviluppo di algoritmi per il calcolo o l'apprendimento di tali equilibri. Analizzando i principali risultati scientifici degli ultimi anni in questo campo di ricerca, ci si può facilmente rendere conto di come, al fine di permettere l'utilizzo di tali tecniche in complessi scenari reali, sia di fondamentale importanza la formulazione di algoritmi di apprendimento. La gran parte della ricerca fino ad ora si è focalizzata sullo sviluppo di tali algoritmi solo in semplici scenari, come giochi a due giocatori, ma algoritmi per casi più generali sono ancora lontani dal raggiungere delle adeguate performance. Lo scopo che questa tesi si pone è quello di avanzare la ricerca in questa direzione. In particolare, studiamo diversi ambienti con molteplici giocatori, differenziandoli in base al ruolo degli agenti che possiedono informazioni sullo stato dell'ambiente. In questo contesto, ci focalizziamo sullo sviluppo di appropriati algoritmi di apprendimento volti all'approssimazione dei diversi concetti di equilibrio relativi ai diversi tipi di ambiente considerati. Nella prima parte della tesi studiamo casi in cui gli agenti che hanno informazioni sull'ambiente sono attivi, ovvero possono utilizzare tali informazioni per eseguire delle azioni all'interno del gioco. Più nello specifico, ci occupiamo di due casi distinti: giochi a team, i quali modellano scenari in cui due team di agenti competono l'uno contro l'altro, e la classe di giochi general-sum, in cui non viene fatta alcuna assunzione sui giocatori. Per i giochi a team definiamo una semplice trasformazione che utilizza un protocollo di correlazione basato sull'informazione pubblica e che permette di ottenere una formulazione compatta del set di strategie correlate del team. Come output di tale trasformazione, otteniamo un gioco a due giocatori strategicamente equivalente al gioco originale, da cui è poi possibile ricavare in maniera diretta il primo algoritmo di apprendimento no-regret per il calcolo di equilibri in giochi a team. In seguito, seguendo quello che è stato fatto in passato nel contesto dei giochi a due giocatori, forniamo una formalizzazione per i giochi a team di due tecniche che si sono dimostrate fondamentali per giochi a due giocatori, ovvero subgame solving e minimizzazione stocastica del regret. Per quanto riguarda i giochi general-sum, invece, osserviamo dapprima che l'approccio comunemente usato in letteratura, ovvero l'utilizzo di dinamiche di apprendimento decentralizzate per l'approssimazione di equilibri, soffre di differenti problematiche, in quanto non offre garanzie sulla bontà dell'equilibrio raggiunto. Per risolvere questo problema, assumiamo il punto di vista di un mediatore che invia delle raccomandazioni ai diversi giocatori riguardo le azioni da giocare e definiamo una dinamica di apprendimento centralizzata che permette di apprendere equilibri correlati ottimi in giochi sequenziali. La seconda parte della tesi si occupa di studiare casi in cui gli agenti che possiedono informazioni sull'ambiente sono passivi, ovvero non possono compiere delle azioni direttamente, ma possono comunicare le proprie azioni in modo strategico al fine di influenzare il comportamento di un agente non informato. Questo scenario corrisponde allo scenario di information acquisition, in cui assumiamo il punto di vista dell'agente non informato (chiamato principal) il quale è interessato ad ottenere informazioni dagli agenti, incentivando i loro comportamenti tramite l'utilizzo di meccanismi che si compongono di strategie di azioni e schemi di pagamento. Più in dettaglio, studiamo separatamente i due casi in cui i meccanismi del principal sono costituiti da policy che legano informazione ricevuta ad azione, o funzioni di pagamento. In entrambi i casi forniamo algoritmi per l'apprendimento di meccanismi ottimi tramite interazione sequenziale con gli agenti.