Apprendimento e coordinazione in sistemi multi-agente nella teoria dei giochi

This thesis focuses on the study of learning and coordination strategies in multi-agent systems, which are a set of agents located in a certain environment and interacting with each other, through the theory of iterated games. In particular, a learning algorithm called Fictitious Play Modified is covered. This is based on the algorithm of Fictitious Play, which is a powerful tool for learning equilibria in multiplayer games, but as the size of the game increases it entails computational and communication costs between players too high and unsustainable. The innovative approach that is adopted in the Modified Fictitious Play analyzes the situation in which each player has access only to the empirical average of the distributions of all the other players without having to search the empirical distribution of every single player, considerably simplifying the choice of Best Reply. It is also shown that the Modified Fictitious Play converges to a set of "Consensus Equilibria", which is a subset of the Nash Equilibria.

Questa tesi si concentra sullo studio di strategie di apprendimento e coordinazione in sistemi multi-agente, ovvero un insieme di agenti situati in un certo ambiente ed interagenti tra loro, mediante la teoria dei giochi iterati. Viene trattato in particolare un algoritmo di apprendimento chiamato Fictitious Play Modificato. Quest’ultimo è una variante dell’algoritmo del Fictitious Play, il quale è un potente strumento per l’apprendimento di equilibri in giochi multiplayer, ma che con l’aumentare delle dimensioni del gioco comporta costi computazionali e di comunicazione tra i giocatori troppo elevati ed insostenibili. L’approccio innovativo che viene adottato nel Fictitious Play Modificato analizza la situazione in cui ogni giocatore ha accesso solamente alla media empirica delle distribuzioni di tutti gli altri giocatori senza dover ricercare la distribuzione empirica di ogni singolo giocatore, semplificando in maniera considerevole la scelta della Best Reply ad ogni round del gioco. Si dimostra inoltre che il Fictitious Play Modificato converge ad un insieme di “Equilibri di consenso”, il quale è un sottoinsieme degli Equilibri di Nash.