Solving imperfect-recall games : new representations and algorithms

This thesis focuses on non-cooperative game theory problems. Specifically, it studies games with imperfect recall. Games with imperfect recall are a powerful model of strategic interactions that allows agents to forget less important details of the past. Nevertheless, the computational treatment of imperfect-recall games is largely unexplored so far, and even the problem of finding strategy representations that can be effectively used by algorithms is open. In this work, we focus on general imperfect-recall games without absentmindedness, and we study how to produce a perfect-recall representation of these games using personalities. In particular, a valid personality assignment is a decomposition of an imperfect-recall player such that she does not exhibit memory losses within the same personality. Given a valid personality assignment, we can build an auxiliary team game where a team of perfect-recall players--- i.e. players sharing the same objectives---replaces a player with imperfect recall. Our primary goal is the construction of a compact representation in terms of the number of personalities. We study the (iterated) inflation operation as a way to simplify a game with imperfect recall by splitting certain information sets of a player, and potentially leading to a player with perfect recall. We show that the complete (i.e., maximal) inflation of a game tree can be found in polynomial time. We also show that finding the valid personality assignment minimizing the number of personalities is NP-hard, and also hard to approximate, unless P=NP, even in a completely inflated game tree. Finally we devise a new pruning technique that can be employed within state-of-the-art techniques to compute Nash equilibria in imperfect-recall games. This technique makes use of additional information that is derived from the perfect-recall refinement of the original imperfect-recall game.

In questa tesi studiamo problemi non cooperativi nell'ambito della teoria dei giochi e, nello specifico, giochi imperfect-recall. Questi ultimi sono modelli che rappresentano interazioni strategiche nelle quali è possibile che gli agenti si dimentichino certi dettagli del passato. Lo studio, dal punto di vista computazionale, dei giochi imperfect-recall è ancora ampiamente inesplorato, come anche il problema di trovare una rappresentazioni delle strategie dei giocatori che possano essere effettivamente usate negli algoritmi. In questo lavoro ci concentriamo su giochi imperfect-recall con struttura generica, senza absentmindedness, e proponiamo un metodo per produrre una rappresentazione perfect-recall di tali giochi utilizzando il concetto di personalità. In particolare, un'assegnazione di personalità valida consiste nella scomposizione di un giocatore imperfect-recall in modo tale che non ci siano perdite di memoria all'interno di una stessa personalità. Data un'assegnazione valida di personalità, possiamo costruire un team game ausiliario nel quale un team di giocatori perfect-recall -- i.e., giocatori che condividono gli stessi obiettivi -- sostituisce il giocatore imperfect-recall. Il nostro obiettivo primario consiste nella creazione di una rappresentazione compatta in termini di numero di personalità. Per questo motivo, studiamo l'operazione di inflation, e mostriamo come applicarla iterativamente al fine di semplificare un gioco imperfect-recall spezzando alcuni information sets di un giocatore, e portando potenzialmente tale giocatore ad essere perfect-recall. Spieghiamo inoltre come sia possibile trovare la complete inflation (i.e., inflation massimale) di un albero di gioco in tempo polinomiale. Successivamente, dimostriamo che trovare un'assegnazione valida che minimizzi il numero di personalità è NP-hard, ed è anche difficile da approssimare, a meno che P=NP, anche in un albero di gioco completely inflated. Infine, descriviamo un oracolo di best response per giocatori imperfect-recall che fa uso di una nuova tecnica di pruning. L'algoritmo può essere impiegato all'interno di tecniche già esistenti usate per calcolare equilibri di Nash ottimi in giochi imperfect-recall. La nostra tecnica sfrutta informazioni addizionali derivate dal perfect-recall refinement del gioco imperfect-recall originale.