Information Technology Reference
In-Depth Information
16.5 Ambush in a Single Cell
We
will
now
present
some
analytical
solutions
to
versions
of
the
silent
search-ambush game, starting with the case where
K
1 (that is, there is only a
single cell). In this case, movement by the hider does not involve a meaningful
randomisation of the hider's position from the searcher's point of view, since the
searcher effectively “knows” which cell the hider is occupying at all times. Rather,
a successful move simply allows the hider to evade capture for one additional period.
The “silent searcher” condition retains its meaning in the sense that strategies are
not changed while a round is in progress, though it is no longer even possible for the
hider to be aware of some fraction of the space search having been searched (either
none of the search space has been searched, or the entirety has. In the latter case
the hider has been caught, and, under the predator-prey interpretation, consumed,
rendering the content of the hider's information set a moot issue).
Geometrically, some intuition can be gained by imagining the
K
=
1 case as
a search game on a one-way circular graph that takes unit time to traverse, with
hiding and ambush points placed at antipodean points. If the hider moves while the
searcher inspects, they “chase each other's tails” around the circle, coming back
to their starting points (this is the simplest instance of the
K
-leaf clover network
referenced in Sect.
16.4
).
=
16.5.1 The Game with Two Periods
As before, a strategy for the hider is denoted
h
i
H
. Ignoring
h
L
+
.Wehave
i
∈
∈
. Similarly, a strategy for the searcher will be denoted
s
j
{
1
...
L
}
∈
S
where
j
∈
{
1
...
L
}
represents the period of search. The payoffs are defined as follows:
i
+
2
+
T
L
,
1
if i
=
j
h
i
s
j
T
L
,
1
(
,
)=
,
(16.6)
min
{
i
,
j
}
if
i
=
j
That is, if the hider successfully restarts the game, the payoff is equal to the period
in which this occurred plus the value of the restarted game; otherwise, the payoff is
simply in the period in which either the searcher searches before the hider moves,
or the hider moves while the searcher is ambushing. The simplest possible interest-
ing form of the general game with finite
L
is where
K
=
1,
L
=
2, which we will
consider now.
The relevant payoff matrix is symmetric with the form:
s
1
s
2
h
1
+
1
T
1
A
2
,
1
=
h
2
+
12
T
Search WWH ::
Custom Search