Learning correlation in multi-player general-sum games with regret minimization

Game Theory is a very powerful tool to model strategic interaction between agents with conflicting interests. In recent years, there has been an increasing attention to solution concepts that embed some form of correlation and coordination among agents, since they can lead to socially better outcomes with respect to totally uncoupled solution concepts as Nash Equilibria, and can be reached effectively through online learning dynamics in a decentralized fashion. In this thesis, we focus on the computation of Coarse Correlated Equilibria, both in the general class of multi-player games, as well as in the more specific class of multi-player extensive-form games. The goal of this thesis is to develop a set of algorithmic tools for embedding Regret Minimization in the computation of Coarse Correlated Equilibria for multi-player games, and to demonstrate their effectiveness by applying them to extensive-form games. To this end, we introduce a Regret Minimization Framework and we apply it to derive two novel algorithms: CFR-S and CFR-Jr. We give theoretical results on the soundness of both algorithms and on their computational complexity. Moreover, we give a wide set of experimental results that show that our algorithms are able to consistently outperform the prior state of the art, and that they are able to compute a Coarse Correlated Equilibrium for game instances that are several orders of magnitude larger than what was possible before.

La Teoria dei Giochi è un potente strumento per modellare l'interazione strategica tra agenti con interessi contrastanti. Negli ultimi anni vi è stata un crescente attenzione per concetti di soluzione che incorporino forme di correlazione e di coordinamento tra gli agenti, in quanto possono portare a risultati socialmente migliori rispetto a concetti di soluzione totalmente disaccoppiati come gli equilibri di Nash, e possono essere efficacemente raggiunti attraverso dinamiche di apprendimento online in modo decentralizzato. Questa tesi si concentra sul calcolo di equilibri Coarse-Correlati, sia nella classe generale dei giochi a più giocatori, sia nella classe più specifica dei giochi a più giocatori in forma estesa. L'obiettivo della tesi è quello di sviluppare un insieme di strumenti algoritmici per sfruttare il concetto di minimizzazione del regret per il calcolo di equilibri Coarse-Correlati per giochi a più giocatori, e di dimostrare la loro efficacia applicandoli a giochi in forma estesa. A questo scopo, viene introdotto un framework di minimizzazione del regret, che viene poi applicato per ricavare due nuovi algoritmi: CFR-S e CFR-Jr. La tesi contiene risultati teorici sulla correttezza di entrambi gli algoritmi e sulla loro complessità computazionale. Inoltre, viene fornita un'ampia serie di risultati sperimentali che mostrano come i due nuovi algoritmi siano in grado di superare consistentemente le performance degli algoritmi allo stato dell'arte, e che sono in grado di calcolare un equilibrio Coarse-Correlato per istanze di gioco che sono diversi ordini di grandezza più grandi di quanto non fosse possibile in precedenza.