Game Development Reference
In-Depth Information
of whether val ( v )=1is P -complete (see Chatterjee et al. [2004b], de Alfaro
and Henzinger [2000]).
Rabin-chain (parity). In turn-based stochastic games with Rabin-chain
(parity) payoffs, both players still have optimal MD strategies (see McIver and
Morgan [2002], Chatterjee et al. [2004b]). The problem of whether val ( v )
for a given rational
[0 , 1] is in NP coNP , and this is currently the
best upper bound also for the problem of whether val ( v ) = 1 (see Chatterjee
et al. [2004b]).
Rabin and Street. In turn-based stochastic games with Rabin payoffs,
player has an optimal MD strategy (see Chatterjee et al. [2005]). This
does not hold for player ♦, as demonstrated by the following simple example:
u a
u b
v
Consider the Rabin condition
{
( a, b ) , ( b, a )
}
, where ν ( u a )=
{
a
}
, ν ( u b )=
{
b
}
,
and ν ( v )=
. Obviously, val ( v ) = 0, but an optimal minimising strategy
must ensure that both u a and u b are visited infinitely often, which is not
achievable by a MD strategy.
Consequently, the problem of whether val ( v )
is in NP for Rabin payoffs.
Since the problem of whether val ( v )=1is NP -hard (see Emerson and
Jutla [1988]), both problems are NP -complete. Since the Street acceptance
condition is dual to Rabin, this also implies coNP -completeness of the two
problems for Street payoffs.
Muller. In turn-based stochastic games with Muller payoffs, both players
have optimal FD strategies, and the memory cannot be traded for randomness
(i.e., the players do not necessarily have MR optimal strategies). To see
this, consider the following game, where ν ( u a )=
{
a
}
, ν ( v )= ν ( u )=
,
ν ( u b )=
{
b
}
, ν ( u c )=
{
c
}
, and the Muller condition is
{{
b
}
,
{
a, c
}
,
{
a, b, c
}}
(the example is taken from Chatterjee et al. [2004a]):
u b
u a
v
u
u c
It is easy to check that val ( v ) = 1, and player
has a FD optimal strategy
which in every state wv selects either v
u , depending on
whether the last vertex of w is u c or not, respectively. It is also easy to see
that player
u a or v
does not have a MR optimal strategy.
For
Muller
payoffs,
the
problem
of
whether
val ( v )
is