Games with a Weak Adversary

We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coali-tion of the first and second players against the third player is undecidable in gen-eral, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the sec-ond player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the prob-lem is decidable for safety and reachability objectives. From our results we derive new complexity results for partial-observation stochastic games