Krishnendu Chatterjeex, Luca de Alfarox and Thomas A. Henzingeryz
06/13/2008 09:00 AM
Computer Engineering
We consider two-player concurrent games played on graphs, where at each state both players choose moves simultaneously and independently. We consider regular winning conditions specified as parity objectives and study the qualitative winning mode, i.e., whether a player can win with probability arbitrarily close to 1 (limit-winning). We provide an efficient reduction from limit-winning concurrent parity games to winning turn-based parity games, where at each state only one player has a choice of moves. From a theoretical point of view, the reduction shows that for the qualitative winning mode, one can eliminate the concurrent nature of a game, and since turn-based games are well-studied, the reduction improves the understanding of concurrent games. From a practical point of view, the reduction provides algorithms for limit winning concurrent parity games from algorithms for solving turn-based parity games. Every improvement in the latter algorithms will carry over to the former. In particular, using recent results on algorithms for turn-based parity games, we improve the best known time complexity to solve concurrent parity games when the set of available moves at each state is small.
