Strong subgame perfect equilibria
A -player (turn-based) game is given by a directed graph with each vertex owned by one of the players, and an objective for each player . A strategy profile is a tuple of strategies, one for each player. A strategy profile is Nash equilibrium (NE) if no player can benefit by unilaterally changing their strategy, i.e., if produces a losing outcome for player , then Player cannot deviate to a different strategy that would produce a winning outcome. A strategy profile is a subgame perfect equilibrium (SPE) if it is an NE in every possible subgame of the original game. It is well-known that SPE is a more appropriate notion in this setting and well-studied for -player games with -regular objectives. A more robust notion of NE is strong Nash equilibrium (SNE), where no coalition of players can cooperatively deviate in a way that strictly benefits all of its members. Based on SNE, we consider the notion of strong subgame perfect equilibrium (SSPE), which is a strategy profile that is SNE in every subgame. Question: Does it always exists an SSPE in -player games with -regular objectives? If yes, can we compute a maximal SSPE?
