Strong Nash equilibria in bimatrix games

The tools of game theory are today receiving great importance as they constitute the main instrument for the study of strategic interaction situations. These problems today play a crucial role in many engineering fields: computer science, energy, telecommunications and other areas of interest. The central solution concept in non competitive game theory is Nash equilibrium (NE), but when agents (players) can form coalitions, as it can happen in practice in many applications, it becomes inadequate. An appropriate solution concept in this case is Strong Nash equilibrium (SNE). A strategy profile is a SNE if no coalition of agents can benefit by deviating from it. A SNE must simultaneously be a NE and (weakly) Pareto efficient for every coalition. Even the derivation of necessary and sufficient mathematical equilibrium constraints for SNE is difficult. In this work we characterize the existence of SNEs in 2- player games. More precisely: we prove that only a zero-measure subset of bimatrices admits mixed-strategy SNEs, whereas a positive-measure subset admits pure-strategy SNEs. Furthermore, we demonstrate that necessary condition for a mixed-strategy SNE to exist is that all the payoffs, restricted to the support of the equilibrium, are aligned and therefore that the utility bimatrix contains a sub-bimatrix that is a strictly competitive game, in which all the NE are obviously also SNE. We also conjecture that the result stating that only a zero-measure subset of game instances admits mixed-strategy SNEs extends to the general case of multi-player games with an arbitrary number of players. Our results have important implications for the problem of searching for SNEs in games, showing that the complexity is polynomial when the number of players is given, except for a measure-zero set of instances. Furthermore, our results provide also useful insights for designing algorithms in the case the set of hard zero-measure instances are considered.

Gli strumenti della teoria dei giochi assumono oggi grande importanza in quanto costituiscono il mezzo principale per lo studio delle situazioni di interazione strategica. Questi problemi giocano un ruolo cruciale in molti campi dell'ingegneria: computer science, energia, telecomunicazioni e molti altri ambiti. Il concetto centrale di soluzione nella teoria dei giochi è l'equilibrio di Nash (NE), ma quando i giocatori possono formare coalizioni, come può accadere in pratica in molte applicazioni, esso risulta inadeguato. Un concetto appropriato di soluzione in questo caso è l'equilibrio Strong Nash (SNE). Un profilo di strategie è uno SNE se nessuna coalizione di agenti può beneficiare deviando da esso. Uno SNE deve essere contemporaneamente un NE e (debolmente) Pareto efficiente. Persino la derivazione dei vincoli matematici necessari e sufficienti per l'equilibrio è difficile nel caso di uno SNE. In questo lavoro caratterizziamo l'esistenza degli SNE in giochi a due giocatori. Più precisamente: proviamo che solo un sottoinsieme di misura nulla di bimatrici ammette SNE in strategie miste, mentre un sottoinsieme di misura positiva ammette SNE in strategie pure. Inoltre, dimostriamo che condizione necessaria affinché esista uno SNE in strategie miste è che tutti i payoff, ristretti al supporto dell'equilibrio, siano allineati e quindi che la bimatrice delle utilità contenga una sotto-bimatrice che sia un gioco strettamente competitivo, nel quale tutti gli equilibri di Nash sono ovviamente SNE. Riteniamo infine che il risultato che afferma che solo un sottoinsieme a misura nulla dei giochi a bi-matrice ammette SNE in miste si estenda al caso generale di giochi con un numero arbitrario di giocatori. I nostri risultati hanno importanti implicazioni per il problema della ricerca di SNE nei giochi, perché mostriamo che la complessità è polinomiale quando il numero dei giocatori è dato, eccetto che per un insieme di istanze a misura nulla. In aggiunta, i nostri risultati forniscono informazioni utili per la progettazione di algoritmi nel caso in cui venga considerato l'insieme di istanze difficili a misura nulla.