*Luca de Alfaro and
Thomas A. Henzinger*

We consider two-player games which are played on a finite state space for an
infinite number of rounds. The games are *concurrent*, that is, in each
round, the two players choose their moves independently and simultaneously;
the current state and the two moves determine a successor state. We consider
*omega-regular* winning conditions on the resulting infinite state
sequence. To model the independent choice of moves, both players are allowed
to use randomization for selecting their moves. This gives rise to the
following *qualitative* modes of winning, which can be studied without
numerical considerations concerning probabilities: *sure-win* (player 1
can ensure winning with certainty), *almost-sure-win* (player 1 can
ensure winning with probability 1), *limit-win* (player 1 can ensure
winning with probability arbitrarily close to 1), *bounded-win* (player 1
can ensure winning with probability bounded away from 0), *positive-win*
(player 1 can ensure winning with positive probability), and *exist-win*
(player 1 can ensure that at least one possible outcome of the game satisfies
the winning condition).

We provide algorithms for computing the sets of winning states for each of
these winning modes. In particular, we solve concurrent Rabin-chain games in
*n^O(m)* time, where *n* is the size of the game structure and
*m* is the number of pairs in the Rabin-chain condition. While this
complexity is in line with traditional *turn-based* games, where in each
state only one of the two players has a choice of moves, our algorithms are
considerably more involved than those for turn-based games. This is because
concurrent games violate two of the most fundamental properties of turn-based
games. First, concurrent games are not determined, but rather exhibit a more
general duality property which involves multiple modes of winning. Second,
winning strategies for concurrent games may require infinite memory.

*Proceedings of the
15th Annual Symposium on Logic in Computer Science*
(LICS), IEEE Computer Society Press, 2000, pp. 141-154.

Download inofficial, sometimes updated PostScript / PDF document. © 2000 IEEE.