Trembling-hand perfection in extensive form correlated equilibria

Since the definition of the concept of Nash equilibrium, the study of its main refinements and generalizations has been central in the field of Game Theory and has allowed to develop very useful tools for practical applications related to Artificial Intelligence. The main refinement of Nash equilibrium is the Perfect Equilibrium defined by Selten, which strengthens the equilibrium re- quirements obtained by identifying those equilibria that remain stable even if some of the players may make a mistake. One of the main results that generalizes Nash’s work is the Correlated Equilibrium defined by Aumann, which introduces the figure of a trustworthy moderator who prescribes the actions to be performed to reach an equilibrium. In this work, these two concepts are jointly analyzed, specifically for games in extensive form, by inserting the concept of perfection in the context of correlated games, with the aim of providing a refinement of the Correlated equilibrium. In this way, after a study on the nature of the perturbations that can occur when playing games with a mediator, we formulate the definition of Extensive Form Perfect Correlated Equilibrium (EFPCE), which definitively combines the two concepts described above. From a computational perspective, we formulate the problem of finding an EFPCE in sequence form for two-player games, showing the existence of a solution to this problem independently from the chosen perturbation scheme (similarly to what happens for the per- fect equilibrium). Finally, we are interested in the relationships between the various kinds of equilibria with particular attention to the one just defined. Therefore, we obtain a complete taxonomy involving the most important solution concepts available for games in extensive form, which shows how, given that the Extensive Form Correlated equilibrium (EFCE) is a general- ization of the Nash equilibrium (NE), also the EFPCE is a generalization of the Extensive Form Perfect Equilibrium (EFPE). Furthermore, it is shown and proved that the intersection between the NE and EFPCE sets is exactly the set of EFPEs.

Sin dalla definizione del concetto di equilibrio di Nash, lo studio dei suoi prin- cipali raffinamenti e delle sue generalizzazioni `e stato centrale nell’ambito della Teoria dei Giochi e ha permesso di sviluppare strumenti molto utili nelle applicazioni pratiche legate all’Intelligenza Artificiale. Il principale raf- finamento dell’equilibrio di Nash `e il Perfect Equilibrium definito da Selten, che irrobustisce i risultati ottenuti identificando quegli equilibri che riman- gono stabili anche se qualcuno dei giocatori commette un errore. Uno dei principali risultati che generalizzano il lavoro di Nash `e il Correlated Equi- librium definito da Aumann, che introduce la figura di un moderatore del quale i giocatori hanno convenienza a fidarsi e che prescrive loro le azioni da eseguire per raggiungere un punto di equilibrio. Nel presente lavoro si affrontano questi due concetti congiuntamente e specificatamente per i giochi in forma estesa, inserendo il concetto di perfezione nel contesto dei giochi correlati, con l’obiettivo di fornire un irrobustimento del Correlated equilibrium. In tal modo, dopo uno studio sulla natura delle perturbazioni che si possono verificare quando si giocano giochi correlati, si arriva alla definizione di Extensive Form Perfect Correlated Equilibrium (EFPCE), che coniuga definitivamente i due concetti sopra esposti. Per fornire poi anche una implementazione, si arriva alla definizione del problema della ricerca di un EFPCE formulato in forma sequenza per giochi a due giocatori, di- mostrando l’esistenza di una soluzione al problema indipendentemente dalla perturbazione scelta (analogamente a quanto succede per il perfect equi- librium). Infine, ci si interessa dei rapporti che intercorrono tra i vari tipi di equilibrio con particolare attenzione a quello appena definito. Ci`o che si ottiene `e pertanto una tassonomia completa dei piu` importanti solution concepts disponibili per i giochi in forma estesa che dimostra come, dato che l’Extensive Form Correlated equilibrium (EFCE) `e una generalizzazione del Nash equilibrium (NE), anche l’EFPCE sia una generalizzazione dell’ Exten- sive Form Perfect Equilibrium (EFPE). Inoltre, si dimostra che l’intersezione tra gli insiemi NE e EFPCE `e esattamente l’insieme degli EFPE.