Game Development Reference

In-Depth Information

of a searcher. In particular in the invisible fugitive case, such games model

the fact that often searchers can see further than just their current position,

for instance using torch lights, but they still cannot see the whole system of

tunnels they are asked to search. Such games, called
domination games
,

were introduced by Fomin et al. [2003]. Kreutzer and Ordyniak [2009] study

complexity and monotonicity of these games and show domination games are

not only algorithmically much harder compared to classical cops and robber

games, they are also highly non-monotone (see Section 7.4.3 below).

Besides graph searching games inspired by applications related to graph

searching, there are also games which fall under the category of graph

searching games but were inspired by applications in logic. In particular,

Berwanger and Gradel [2004] introduce the game of
entanglement
and its

relation to the variable hierarchy of the modal
μ
-calculus.

7.4 Monotonicity of graph searching

As mentioned before, monotonicity features highly in research on graph

searching games for a variety of reasons. In this section we present some

of the most important techniques that have been employed for proving

monotonicity results in the literature.

In Section 7.4.1, we first introduce the concept of
sub-modularity
, which

has been used (at least implicitly) in numerous monotonicity results, and

demonstrate this technique by establishing monotonicity of the visible cops

and robber game discussed above.

Many graph searching games on undirected graphs have been shown to be

monotone. Other games, for instance many games on directed graphs, are

not monotone and examples showing that searchers can be saved by playing

non-monotonic have been given. In some cases, however, at least
approximate

monotonicity
can be retained in the sense that there is a function
f
:

N
→
N

such that if
k
searchers can win by a non-monotone strategy then no more

then
f
(
k
) searchers are needed to win by a monotone strategy. Often
f
is

just a small constant. Many proofs of approximate monotonicity use the

concept of
obstructions
. We will demonstrate this technique in Section 7.4.2

for the case of directed graph searching.

7.4.1 Monotonicity by sub-modularity

The aim of this section is to show that the visible cops and robber game on

undirected graphs is monotone. The proof presented here essentially follows

Search Nedrilad ::

Custom Search