Researches on the calculation of strong Nash equilibria

Computing equilibria of games is an important task in computer science. A large number of results are known for Nash equilibrium. However, Nash equilibrium can be adopted only when coalitions are not an issue. When instead agents can form coalitions, Nash equilibrium is inadequate and an appropriate solution concept is strong Nash equilibrium. This thesis is devoted to the problem of calculating strong Nash equilibrium in general strategic games. We divide the problem of finding a strong Nash equilibrium to sub-problems of finding Nash equilibrium, and finding Pareto efficient strategies. Then we introduced and developed several formulations for both kinds of sub-problem. For Nash equilibrium finding we introduced the state-of-art NLCP and MILP, while for Pareto efficiency we developed one necessary formulation based on Karush-Kuhn-Tucker conditions and one sufficient formulation considering correlated strategies. The exact formulation for Pareto optimality is difficult to obtain, but one can firstly find a Nash equilibrium, then verify the Pareto optimality. Based on this idea we developed a Branch and Bound algorithm and its variant in MILP. We develop a new kind of game class named MISSING to test our algorithm, together with GAMUT classes, we measure the performances of our algorithm.

La ricerca degli equilibri di un gioco è un problema di grande importanza in intelligenza artificiale. Molti risultati noti in letteratura studiano il problema di ricerca di un equilibrio di Nash. Tuttavia, equilibrio di Nash può essere adottato solo quando gli agenti non possono formare coalizioni. Quando invece questa possibilità è percorribile, il concetto di equilibrio di Nash è non appropriato. Il concetto di soluzione che cattura queste situazioni è l’equilibrio di Nash forte (strong Nash equilibrium). Questo tesi è dedicata al problema di ricerca dell’equilibrio di Nash forte. Decomponiamo il problema di ricercare un equilibrio di Nash forte in sotto-problemi di ricercare un equilibrio di Nash, e la verifica di strategie di Pareto efficienti. Diverse formulazioni sono introdotte e sviluppate per entrambi i sotto-problemi. Per trovare equilibrio di Nash sono state utilizzate le tecniche disponibili nello stato dell’arte (NLCP e MILP), mentre per la verifica della Pareto efficienza abbiamo sviluppato una formulazione necessaria sulla base di Karush-Kuhn-Tucker e una formulazione sufficiente basato su analisi delle strategie correlate. Mentre la formulazione esatta per il Pareto ottimalità è difficile da ottenere, si può in primo luogo trovare un equilibrio di Nash, poi verificare l’ottimalità di Pareto. Sulla base di questa idea è sviluppato un algoritmo di Branch and Bound e la sua variante in MILP. È stato sviluppato inoltre una nuova classe di gioco, detta MISSING, per valutare sperimentalmente il nostro algoritmo assieme alle classi di GAMUT.