A simulator for non-cooperative games

This dissertation describes the theoretic work and the practical design choices which brought to the realization of a non-cooperative game simulator. It also reports some theoretic results achieved from the formal analysis of a class of games called Replication games. It finally depicts the outcomes of an analysis of that particular class of games, obtained through the utilization of the simulator in question. The simulator offers all the instruments to efficiently represent whichever game with finite action sets and to play it, following the learning rules mostly studied in the literature. Its completely modular architecture allows, among everything else, to easily add specific checks on the learning process, permitting to verify generic properties coming for example from theoretic results. Additionally, its capability to exploit hardware parallelism, together with the ability to take advantage of independent game actions, allows to perform particularly efficient simulations. In the formal part of the dissertation is reported the proof of the equivalence of some particular subclasses of the Replication games to the class of Player-Specific Congestion games and the class of Matroid Congestion games. Follows a literature study to collect the theorems which hold also for this subclass. The results show that, under certain conditions, some fundamental properties like the finite improvement and the weakly acyclicity hold. The formal analysis suggests also the absence of cycles in some other subclasses of the Replication games, but this has not been proved yet.

Questa tesi specialistica descrive il lavoro teorico e le scelte di progettazione che hanno portato alla realizzazione di un simulatore di giochi non cooperativi. Il lavoro include inoltre diversi risultati teorici raggiunti grazie all’analisi formale di una classe di giochi conosciuti come Replication games. Questo report descrive infine i risultati dello studio relativo a questa particolare classe di giochi, ottenuti usando il simulatore in questione. Il simulatore offre tutti gli strumenti che permettono di rappresentare in modo efficiente qualunque gioco che abbia insiemi delle strategie finiti, e di simularlo seguendo i processi di apprendimento più studiati in letteratura. La sua architettura completamente modulare permette, tra le altre cose, di aggiungere facilmente particolari controlli sul processo di apprendimento, consentendo di verificare proprietà generiche risultanti, ad esempio, da studi teorici. Inoltre, la sua capacità di sfruttare architetture hardware parallele, congiuntamente con la possibilità di definire computazioni indipendenti, permette di portare a termine simulazioni in modo particolarmente efficiente. Nella parte formale della tesi è riportata la dimostrazione di equivalenza di alcune particolari sottoclassi dei Replication games con la classe dei Player-Specific Congestion games e dei Matroid Congestion games. Segue una revisione della letteratura effettuata con lo scopo di riunire i teoremi validi anche per questa sottoclasse. I risultati dimostrano che, imponendo alcuni vincoli, è possibile attribuire ai Replication games proprietà come l’ aciclicità debole o quella degli incrementi finiti. L’analisi formale fa supporre inoltre la totale assenza di cicli in alcune altre sottoclassi dei Replication games, ma tale risultato non è ancora stato provato.