Strong Nash equilibrium : smoothed computational complexity and algorithms for games with three or more players

The most important solution concept in game theory is the Nash equilibrium (NE). However, this solution concept fails when agents can form coalition, even in the case of two--agent games. Strong Nash equilibrium (SNE) is an appealing solution concept that refines NE to capture such a case. An SNE must simultaneously be a NE and the optimal solution of multiple non-convex optimization problems. This makes even the derivation of necessary and sufficient equilibrium constraints in a mathematical programming fashion difficult. Moreover it is known that finding an SNE is a NP-complete problem. In the first part of this work we study the properties of mixed-strategy SNEs in bimatrix game, providing two main contributions. We show that if there exists an SNE in a bimatrix game, then the payoffs of the actions in the SNE support must lay on the same line in agents' utilities space. Furthermore, we show that finding an SNE is a problem in smoothed-P, admitting a deterministic support-enumeration algorithm with smoothed polynomial running time. In the second part of the work we derive different sets of conditions for a strategy to be an SNE. We show that forcing an SNE to be resilient only to pure strategy deviations by coalitions, unlike for NEs, is only a necessary condition. We also show that the application of Karush-Kuhn-Tucker (KKT) conditions leads to another set of necessary conditions that are not sufficient. Finally we can show that forcing the Pareto efficiency of a NE for each coalition with respect to coalition correlated-strategies is sufficient but not necessary. In the end we develop a tree search algorithm for SNE finding which, at each node, calls an oracle to suggest a candidate SNE and then verifies the candidate. We show that our necessary conditions can be leveraged to make the oracle more powerful. Experiments show that the new conditions reduce search tree size compared to using NE conditions alone, however it is necessary to use an incomplete nonlinear solver, which affects the soundness and the completeness of the whole algorithm.

La ricerca degli equilibri di Nash (NE) è un problema di grande importanza nel campo dell'intelligenza artificiale. Tuttavia, il concetto di NE è valido solo quando gli agenti non possono formare coalizioni. L'equilibrio di Nash forte (SNE) estende il concetto di NE in modo da catturare proprio queste situazioni. Uno SNE deve essere contemporaneamente un NE e la soluzione di diversi problemi non convessi di ottimizazione. Questo rende difficile derivare un insieme finito di vincoli necessari e sufficienti affinché una strategia sia uno SNE. Inoltre è noto che trovare uno SNE è un problema NP-completo. Nella prima parte di questa tesi vengono studiate le proprietà degli SNE e vengono forniti due contributi principali. Dapprima viene mostrato che se esiste uno SNE in un gioco a due giocatori, allora i payoff delle azioni nel supporto dell'equilibrio devono essere allineati nello spazio dell’utilità degli agenti. In secondo luogo viene mostrato che trovare uno SNE in un gioco a due giocatori è un problema che ha classe di complessità smoothed–P. Nella seconda parte di questa tesi vengono derivati diversi insiemi di condizioni affinché una strategia sia uno SNE. Si dimostra che è possibile ricavare un insieme di condizioni necessarie, ma non sufficienti, o imponendo ad una strategia di essere robusta rispetto a deviazioni multilaterali in strategie pure, o utilizzando le condizioni di Karush-Kuhn-Tucker. Inoltre si dimostra che imporre la Pareto efficienza di un NE in strategie correlate, per ogni possibile coalizione, è una condizione sufficiente ma non necessaria. Per concludere viene sviluppato un algoritmo branch–and–bound per la ricerca di uno SNE che, ad ogni iterazione, utilizza un oracolo per generare un candidato e verifica se tale candidato è uno SNE. Viene mostrato che utilizzando gli insiemi di condizioni necessarie individuati si ottengono degli oracoli più performanti, infatti si riduce in maniera significativa il numero di branch rispetto all'uso di oracoli che genereano candidati che sono NE. Tuttavia si rende necessario l'utilizzo di un risolutore non lineare e non completo, il che ha un impatto sulla completezza e la correttezza dell'algorimo.