Trading Probability for Fairness

Marcin Jurdzinski, Orna Kupferman, and Thomas A. Henzinger

Behavioral properties of open systems can be formalized as objectives in two-player games. Turn-based games model asynchronous interaction between the players (the system and its environment) by interleaving their moves. Concurrent games model synchronous interaction: the players always move simultaneously. Infinitary winning criteria are considered: Buechi, co-Buechi, and more general parity conditions. A generalization of determinacy for parity games to concurrent parity games demands probabilistic (mixed) strategies: either player 1 has a mixed strategy to win with probability 1 (almost-sure winning), or player 2 has a mixed strategy to win with positive probability.

This work provides efficient reductions of concurrent probabilistic Buechi and co-Buechi games to turn-based games with Buechi condition and parity winning condition with three priorities, respectively. From a theoretical point of view, the latter reduction shows that one can trade the probabilistic nature of almost-sure winning for a more general parity (fairness) condition. The reductions improve understanding of concurrent games and provide an alternative simple proof of determinacy of concurrent Buechi and co-Buechi games. From a practical point of view, the reductions turn solvers of turn-based games into solvers of concurrent probabilistic games. Thus improvements in the well-studied algorithms for the former carry over immediately to the latter. In particular, a recent improvement in the complexity of solving turn-based parity games yields an improvement in time complexity of solving concurrent probabilistic co-Buechi games from cubic to quadratic.

Proceedings of the International Conference for Computer Science Logic (CSL), Lecture Notes in Computer Science 2471, Springer, 2002, pp. 292-305.

Download inofficial, sometimes updated PostScript / PDF document. © 2002 Springer.