Dependency Matrices: Multi-player Delay Games

Players in a game take their decisions with respect to their knowledge of what the other players do, or have done or even in some cases, will do. The study of temporal dependencies requires specific formalism through Delay games: two players play a classical Gale-Stewart game but the moves of one player are delayed. In this presentation, we propose a formalism generalizing Delay games, Dependency Matrices, for a multi-player setting. We solve the problem of the existense of a winning uniform strategy when all delays are finite and show that this problem is undecidable when delays may be infinite. We then propose a fragment to recover decidability that we call perfectible information. We solve the problem on this fragment by unifying Büchi automaton complemention and parity-game resolution.

Authors

• Dylan Bellier

Keywords

No keywords are indexed for this paper.