Game Development Reference
In-Depth Information
( V ( C )
a strong component of G
\
( Z
Y )). So we can safely remove all cops
( V ( C )
from the board except for those on ( Z
Y ). But by construction of
V ( C )
Z ,
k and therefore there are at most k +1+ k =2 k + 1 cops
on the board. Furthermore, V ( C )
|
Y
|≤
. Hence, the robber
space has become strictly smaller. We can therefore continue in this way to
define a monotone winning strategy for the cops unless at some point we
have found a haven of order k . This concludes the proof of Theorem 7.27 as
the existence of a haven of order k means that the robber wins against k
cops.
W as Z
W
=
Further examples
Similar methods as in this example can be employed in a variety of cases.
For instance, for the Robber and Marshal Game on hypergraphs presented
in Section 7.3.6, Adler [2004] gave examples showing that these games are
non-monotone. But again, using a very similar technique as in the previous
proof, Adler et al. [2005] showed that if k Marshals have a winning strategy
on a hypergraph then 3 k + 1 Marshals have a monotone winning strategy.
Open problems
We close this section by stating an open problem. Consider the visible directed
reachability game on a directed graph G as defined in Section 7.3.5. The
question of whether this game is monotone has been open for a long time.
Kreutzer and Ordyniak [2008] have exhibited examples of games where 3 k
1
cops have a wining strategy but at least 4 k
2 cops are needed for a monotone
strategy, for all values of k . We have seen an example for the special case of
k = 2 in Section 7.3.5 above.
Similarly, they give examples for the invisible inert directed reachability
game where 6 k cops have a winning strategy but no fewer than 7 k cops have
a monotone winning strategy, again for all values of k .
However, the problem of whether these games are at least approximately
monotone has so far been left unanswered.
Open Problem 7.29 Are the directed visible reachability and the inert
invisible directed reachability game approximately monotone?
7.4.3 Games which are strongly non-monotone
We close this section by giving an example for a class of games which is not
even approximately monotone. Recall the definition of domination games
given in Section 7.3.7. Domination games are played on undirected graphs.
Search Nedrilad ::

Custom Search