Algorithms for verification and computation of strong Nash equilibria

Computing equilibria of situation of conflict and cooperation, usually called games in mathematical literature, is central in artificial intelligence. In games theory there are different solution concepts, each specifics for a certain type of game. The most studied solution concept is Nash equilibrium (NE), in which each player is assumed to know the equilibrium strategies of the other players and no player has anything to gain by changing only their own strategy. However, NE can be used only when coalitions are not an issue. When instead agents can communicate and form coalitions, an appropriate solution concept is strong Nash equilibrium (SNE). Differently from NE, a SNE may not exist. In this thesis we study algorithms for finding SNE when the number of players is arbitrary and we evaluate their computational complexity. We achieve an efficient algorithm for verifying that a NE is strong by using global optimization tools and we use such algorithm to design an algorithm for finding SNEs. We achieve another algorithm for finding SNE, based on the enumeration of players' strategies. Finally, we experimentally evaluate and compare our algorithms for the verification and computation on games synthetically generated by the main testbed available in literature and by a testbed we implemented.

In intelligenza artificiale il problema della ricerca di soluzioni per problemi di interazione strategica, comunemente detti giochi in letteratura matematica, è di grande importanza. Un aspetto cruciale è che in teoria dei giochi non esiste un unico concetto di soluzione, ma molteplici concetti, ed ognuno di essi è specifico per una situazione di gioco. Il concetto più famoso è l'equilibrio di Nash (NE), che cattura la situazione in cui i giocatori giocano la miglior risposta alle strategie degli avversari e nessun giocatore ha interesse ad essere l'unico a cambiare la propria strategia. Il NE però fallisce ogni qual volta sia possibile la comunicazione tra giocatori. In tutti questi casi, l'equilibrio di strong Nash (SNE) è invece appropriato. A differenza di un NE, uno SNE può non esistere in un gioco. In questa tesi ci siamo occupati di studiare algoritmi per la ricerca degli SNE quando il numero di giocatori è arbitrario e di valutarne la complessità. Abbiamo realizzato un algoritmo efficiente per la verifica che un equilibrio di Nash sia strong utilizzando strumenti di ottimizzazione globale e lo abbiamo utilizzato per progettare un algoritmo per la ricerca degli SNE. Abbiamo realizzato un secondo algoritmo di ricerca degli SNE, basato sull'enumerazione delle strategie dei giocatori. Infine abbiamo valutato e confrontato sperimentalmente i nostri algoritmi di verifica e ricerca su giochi generati in modo sintetico da generatori noti in letteratura e da un generatore da noi implementato.