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

Search Nedrilad ::

Custom Search