Algorithms for the verification, computation and learning of equilibria in extensive-form games

The study of strategic-interaction situations has recently received increasing attention in artificial intelligence with the aim of designing autonomous software agents able to act optimally. these situations are customarily modeled as games in which the mechanism describes the rules and strategies describe the behavior of the agents. Particular attention is focused on the study of formal methods to theoretically guarantee the optimality of the agents' behavior. Game theory and microeconomics provide mathematical tools to model strategic-interaction situations and characterize the appropriate solution concepts. However, they do not provide computational tools to and solutions. this problem, commonly called equilibrium computation, is instead central in computer science, whose aim includes assessing the complexity of finding an exact or approximate solution, designing exact or approximate algorithms, and evaluating the application of the algorithms in practical settings. In this thesis, we focus on non-cooperative general-sum extensive-form games. Extensive-form games are more suitable to represent real-world situations providing a richer representation than strategic-form games, where the sequential structure of decision-making is described explicitly and each agent is allowed to be free to change her mind as events unfold. While in zero-sum extensive-form games the main problem is to solve games of large dimension (e.g., poker), in general-sum extensive-form games there are other important issues. the most important is the choice of the most suitable solution concept: it depends on the scenario modelled by the game, e.g. the agents' common knowledge, and it depends on its computability, i.e. the amount of time and memory necessary to solve the game. We can identify two main scenarios, characterized through the knowledge available to agents: the case where the agents have common information and the case where they have incomplete information. Interestingly, with common information, the appropriate solution concepts for extensive-form games refine the concept of Nash equilibrium, while, when agents learn, the appropriate solution concepts relax the concept of Nash equilibrium. More precisely, in the first scenario, it is well known that the Nash equilibrium is not suitable, allowing strategies to be non-sequentially rational. the game theoretic literature provides a number of refinements of Nash equilibrium for extensive-form games that are the appropriate solution concepts. For these solution concepts the verification and computation problems can be hard. In this thesis we show that for some solution concepts the verification problem is easy and we design algorithms to and some refinements of Nash equilibrium. When the information is not common every agent needs to have a set of beliefs over the opponents' behaviour. this beliefs are updating during the learning process, i.e. while the agents repeat the game. In this thesis we discuss the suitable solution concepts for this scenario and we develop efficient evolutionary game theory techniques and algorithms that works with the sequence form representation of extensive-form games allowing an exponential reduction of time and space w.r.t. the algorithms presented in literature. Finally, we experimental evaluate each presented algorithm.

Lo studio di situazione di interazione strategica ha recentemente ricevuto un'attenzione crescente nel campo dell'intelligenza artificiale al fine di progettare agenti autonomi capaci di agire ottimamente. Queste situazioni sono comunemente modellate come giochi in cui il meccanismo descrive le regole e le strategie descrivono il comportamento degli agenti. Particolare attenzione è focalizzata sullo studio di metodi formali per garantire teoricamente l'ottimalità del comporta- mento degli agenti. La teoria dei giochi e la microeconomia forniscono gli strumenti matematici per modellare la situazioni di interazione strategica e caratterizzare gli appropriati concetti di soluzione. Comunque, essi non forniscono gli strumenti computazionali per cercare le soluzioni. Questo problema, comunemente chiamato calcolo degli equilibri, è invece centrale in informatica, il cui obiettivo include la valutazione della complessità di trovare una soluzione esatta o approssimata, progettare algoritmi esatti o approssimati, e valutare l'applicabilità degli algoritmi in situazioni reali. In questa tesi, ci focalizziamo sui giochi non cooperativi in forma estesa a somma generale. I giochi in forma estesa sono più adatti a rappresentare le situazioni del mondo reale fornendo una rappresentazione più ricca dei giochi in forma strategica, dove la struttura sequenziale delle decisioni è de- scritta esplicitamente e ogni agente ha la possibilità di cambiare strategia dopo le azioni dell'avversario. Mentre i giochi in forma estesa a somma zero il problema principale è la risoluzione di giochi di grande dimensione (per esempio il poker), nei giochi in forma estesa a somma generale ci sono altri importanti problemi. Il più importante è la scelta del più adatto concetto di soluzione: esso dipende dallo scenario modellato dal gioco, per esempio la conoscenza comune degli agenti, e dipende dalla sua commutabilità, cioè la quantità di tempo e di memoria necessari a risolvere il gioco. Possiamo identificare due scenari principali, caratterizzare dalla conoscenza disponibile agli agenti: il caso in cui gli agenti hanno informazione comune e il caso in cui essi hanno informazione incompleta. È interessante come, con informazione comune, i concetti di soluzione appropriati per i giochi in forma estesa sono i raffinamenti dell'equilibrio di Nash, mente, quando gli agenti devono apprendere, i concetti di soluzione appropriati rilassano il concetto di equilibrio di Nash. Più precisamente, nel primo scenario, è noto che l'equilibrio di Nash non è adatto, permettendo agli agenti di giocare strategie che non sono sequenzialmente razionali. La letteratura di teoria dei giochi fornisce un numero di raffinamenti dell'equilibrio di Nash per giochi in forma estesa che sono i concetti di soluzione appropriati. Per questi concetti di soluzione i problemi di verifica e computazione possono essere difficili. In questa tesi mostriamo che per alcuni concetti di soluzione il problema della verifica è facile e progettiamo algoritmi in grado di trovare alcuni raffinamenti dell'equilibrio di Nash. Quando l'informazione non è comune ogni agente ha bisogno di un insieme di credenze sul comportamento degli avversari. Queste credenze sono aggiornate durante il processo di apprendimento, cioè mentre gli agenti ripetono il gioco. In questa tesi discutiamo i possibili concetti di soluzione per questo scenario e sviluppiamo tecniche di teoria dei giochi evoluzionaria efficienti e algoritmi che si applicano direttamente alla rappresentazione in forma sequenza del gioco in forma estesa permettendo una riduzione esponenziale del tempo e dello spazio rispetto agli algoritmi presenti in letteratura. Infine valutiamo sperimentalmente gli algoritmi presentati in questa tesi.