← All problems
Unverified

Strong subgame perfect equilibria

A kk-player (turn-based) game is given by a directed graph G=(V,E)G = (V, E) with each vertex owned by one of the kk players, and an objective Wi⊆VωW_i \subseteq V^\omega for each player ii. A strategy profile σˉ=(σ1,…,σk)\bar{\sigma} = (\sigma_1, \ldots, \sigma_k) 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 σˉ\bar{\sigma} produces a losing outcome for player ii, then Player ii cannot deviate to a different strategy σi′\sigma_i' 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 kk-player games with ω\omega-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 kk-player games with ω\omega-regular objectives? If yes, can we compute a maximal SSPE?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu