Learning coarse correlated equilibria in constrained normal form and extensive form games

In the past decades, the field of Algorithmic Game Theory (AGT), driven by the confluence of Game Theory (GT) and Theoretical Computer Science (TCS), has witnessed a remarkable surge in research. This convergence has been further propelled by the outburst of Machine Learning (ML) techniques, which have revolutionized AGT by overcoming classical computational limitations. This thesis explores the intersection of AGT with constrained games, where players confront deterministic costs associated with their actions. These constraints can take the form of hard physical limitations or soft budgetary restrictions. In the proposed setting, the costs incurred by a player depend solely on that player's strategy, independent of the actions taken by others. This characteristic distinguishes these constrained games from classical AGT settings and opens up new avenues for research. The primary objective of this thesis is to develop algorithms capable of converging to defined equilibrium concepts in such constrained game scenarios. This work provides a theoretical foundation by precisely defining the elements essential for understanding the problem. Subsequently, it proposes innovative algorithms for finding equilibria in both constrained Normal Form Games (NFGs) and constrained Extensive Form Games (EFGs). The theoretical correctness of these algorithms is proven, and some insights into regret and violation bounds are provided. Lastly, the proposed algorithms are extensively tested across various game configurations. The experiments confirm the correctness of the algorithms and offer valuable insights into their efficiency, particularly in terms of execution time. The research presented here promises to advance decision-making processes in resource allocation, security games, budget management, and other domains where constrained games with individual cost dependencies play a pivotal role.

Negli ultimi decenni, il campo dell'Algorithmic Game Theory (AGT), spinto dall'unione della Teoria dei Giochi e dell'Informatica Teorica, ha assistito a una notevole crescita nella ricerca. Questa convergenza è stata ulteriormente accelerata dall'esplosione delle tecniche di Machine Learning, che hanno rivoluzionato l'AGT superando le classiche limitazioni computazionali. Questa tesi esplora l'intersezione tra l'AGT e i giochi vincolati, in cui i giocatori affrontano costi deterministici associati alle loro azioni. Questi vincoli possono assumere la forma di limitazioni fisiche rigide o restrizioni di bilancio più flessibili. Nel contesto proposto, i costi sostenuti da un giocatore dipendono esclusivamente dalla strategia di quel giocatore, indipendentemente dalle azioni intraprese dagli altri. Questa caratteristica distingue questi giochi vincolati dai contesti classici dell'AGT e apre nuove strade per la ricerca. L'obiettivo principale di questa tesi è sviluppare algoritmi capaci di convergere a concetti di equilibrio definiti in scenari di giochi vincolati. Questo lavoro fornisce una base teorica definendo con precisione gli elementi essenziali per comprendere il problema. Successivamente, propone algoritmi innovativi per trovare equilibri sia in Giochi in Forma Normale Vincolati (NFG) che in Giochi in Forma Estesa Vincolati (EFG). La correttezza teorica di questi algoritmi è dimostrata, e vengono fornite alcune intuizioni sui limiti superiori del regret e delle violazioni ai vincoli. Infine, gli algoritmi proposti sono stati testati su varie configurazioni di gioco. Gli esperimenti confermano la correttezza degli algoritmi e offrono preziose intuizioni sulla loro efficienza, in particolare in termini di tempo di esecuzione. La ricerca presentata promette di far progredire i processi decisionali nell'allocazione di risorse, nei giochi di sicurezza, nella gestione del budget e in altri settori in cui i giochi vincolati con dipendenze di costo individuali svolgono un ruolo fondamentale.