Positional Nash Equilibria
We consider multi-player infinite duration games on graphs. A game is given by a directed graph, with vertices partitioned in sets; Player controls vertices in the ith set. Edges are coloured with colours in a set , and each player has an objective . A strategy profile is an array of strategies, , one for each player. It is a Nash equilibrium if no player has an incentive to change their strategy, that is: If produces a losing outcome for Player , then Player cannot modify his strategy and obtain a winning outcome. It is known that, under some mild hypothesis on the objectives , 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?
