← All problems
Unverified

Positional Nash Equilibria

We consider multi-player infinite duration games on graphs. A game is given by a directed graph, with vertices partitioned in kk sets; Player ii controls vertices in the ith set. Edges are coloured with colours in a set CC, and each player has an objective Wi⊆CωW_i \subseteq C^\omega. A strategy profile is an array of kk strategies, σˉ=(σ1,…,σk)\bar{\sigma} = (\sigma_1,\dots, \sigma_k), one for each player. It is a Nash equilibrium if no player has an incentive to change their strategy, that is: If σˉ\bar{\sigma} produces a losing outcome for Player ii, then Player ii cannot modify his strategy and obtain a winning outcome. It is known that, under some mild hypothesis on the objectives WiW_i, every game admits some Nash equilibrium. The proofs for this fact usually build a NE where strategies use infinite memory, even for games with very simple objectives. Question: Do all reachability/Büchi/parity games admit a Nash equilibrium in which all strategies are positional?

Coming soon

Organizer

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