On some conditions for the existence of strong Nash equilibrium for multiplayer game

• Main Authors: Lee, Seonah, Kim, Jaemin
• Format: text
• Language: English
• Published: Animo Repository 2016
• Subjects: Game theory; Algorithms; Game Design; Mathematics; Theory and Algorithms
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/14924
• Institution: De La Salle University

The Nash equilibrium (NE) is known to be a very important solution concept in game theory. However, it is strictly used in a non-cooperative games where no cooperation among the players is allowed. On the other hand, strong Nash equilibrium (SNE) is an appealing solution concept in cooperative games where the players can form coalitions. An SNE must be a Nash equilibrium and at the same time considered to be a Pareto optimal of the game. In this paper, we discuss three conditions for the existence of the strong Nash equilibrium: two necessary conditions and one sufficient condition. Forcing an SNE to be resilient to pure multilateral deviations is one of the necessary conditions. By applying the Karush-Kuhn-Tucker conditions, we provide another necessary but not sufficient condition. Lastly, an NE to be a Pareto efficient with respect to coalition correlated strategies is a sufficient but not necessary condition. Then we introduce the spatial branch-and-bound algorithm for SNE finding which finds a candidate solution and then verifies the candidate whether it is a strong Nash equilibrium or not. An application of the algorithm is also presented to validate the algorithm and to show how it works in the specific game. All of the three discussions are based on the article Algorithms for Strong Nash Equilibrium with More than Two Agents by Gatti, Rocco, and Sandholm [5].