Giochi infiniti: da Conway agli Ipergiochi

The aim of this thesis is to study possibly infinite games. We start form showing some general results of Game Theory and, in particular, some useful ways to display and represents different kind of games. Then we dive deep in Conway Theory, where only finite combinatorial 2-player games are modelled, in a way that highlights some interesting algebraic properties, unlike classical approach. We also talk about how these Conway games generalizes numbers, and how impartial games have an important role in this theory. Then, following the research of Furio Honsell and Marina Lenisa, we study hypergames: a generalization of Conway games that also includes never ending ones. In order to describe such objects we need to leave the usual ZFC Set Theory and embrace the Actzel Set theory, where the axiom of Foundation is replaced with an "Anti" Foundation Axiom, which allows infinite descending chains of membership relations between sets, and also loops. Within this theory we manage to define hypergames using technical tools from Category Theory and finally show how these objects extend the idea of Conway games, and their algebraic properties. Finally we introduce a new way to represent hypergames, by "splitting" them in two different objects depending on which player is currently playing them. Over such objects, called P-hypergames, we define and study some relations, such as the pre-order relation of being "reachable" or the equivalence relation of being "mutually reachable", when played. Important results are given about the properties of some P-hypergames of being recursive and some computational limit of such a theory. One of the main topics that appears throughout the entire thesis is the concept of Winning Strategy, along with the more general Non-losing Strategy. We descrive a lot of results about the conditions for the extistence of such startegies, and we translate these concepts also for P-Hypergames.

L'obbiettivo di questa tesi è studiare i giochi infiniti. Si parte da alcuni concetti e risultati fondamentali della teoria dei Giochi classica, mostrando, in particolare, alcuni modi per rappresentare graficamente differenti tipi di giochi. In seguito entreremo in dettaglio nella Teoria di Conway, dove vengono modellizzati soltanto giochi combinatori finiti a due giocatori. Questo approccio, diversamente da quello classico, evidenzia alcune proprietà algebriche dei giochi che possono essere visti come estensione del concetto di numero. Inoltre viene posto l'accento sui giochi imparziali, che ricoprono un ruolo importante nella teoria di Conway. Dopodiché, guidati da alcuni articoli di Furio Honsell e Marina Lenisa, verranno studiati gli ipergiochi: una generalizzazione dei giochi di Conway che include anche giochi infiniti. Per descrivere questi nuovi oggetti è necessario uscire dalla classica teoria assiomatica degli insiemi di Zermelo Freankel e spostarsi su quella di Aczel, dove l'assioma di fondatezza è rimpiazzato da un assioma di anti-fondatezza, che permette l'esistenza di catene infinite e discendenti di appartenenza, così come di catene cicliche. In questa teoria, e grazie ad alcuni strumenti tecnici propri della teoria delle Categorie, si riuscirà finalmente a definire gli ipergiochi e dimostrare come molte loro proprietà estendono quelle dei giochi di Conway. Infine, verrà introdotto un nuovo modo di rappresentare gli ipergiochi "spezzandoli" in due diversi oggetti, chiamati P-ipergiochi, a seconda del giocatore che li sta giocando. Su questi oggetti verranno definite e studiate interessanti relazioni come quella di pre-ordine che rappresenta la "raggiungibilità" di un gioco quando si gioca a partire da un altro, o la relazione di equivalenza che ne rappresenta la "muta raggiungibiltà". Di questi oggetti verranno inoltre esaminate anche alcune proprietà di ricorsività e si delineeranno alcuni limiti computazionali di questa teoria. Lungo tutti i capitoli di questa tesi, un focus particolare viene dato al concetto di strategia vincente, o della sua estensione di strategia non-perdente, che ricopre un ruolo fondamentale nella teoria dei giochi. Di questi concetti verranno mostrati diversi risultati di esistenza, differentemente coniugati a seconda dei modelli studiati e della teorie affrontate.