Information Technology Reference
In-Depth Information
weighted with respect to the EBD distribution, which is equal to 2
D
(
Q
)
/
ρ
. Hence
by (
2.5
), the value is
V
=
1
/
2
(
2
μ
+
2
D
/
ρ
)
=
μ
+
/
ρ
,
D
as given in (
2.3
).
We now return to the expanding search model played on a tree
Q
. Suppose we
form a new network
Q
by replacing each arc of
Q
of length
λ
with an asymmetric
arc with forward travel time (away from
O
)of
and backward travel time 0. Then a
depth-first pathwise search on
Q
is equivalent to an expanding search on
Q
. It can
be shown that it is optimal to use a depth-first search in the expanding search game,
so that the two models are equivalent. The total tour time of the new network is the
length
λ
of the original network, and the height of a leaf node in the new network is
the distance from that node to
O
in the old network, so
μ
Q
)=
Δ
(
D
(
Q
)
. Hence, by
(2), the value is
V
=
1
/
2
(
μ
+
D
)
,
as given in (
2.4
).
2.7 Conclusion
We have seen how an idea in [
14
] sparked a field of research which has produced
many elegant results, and continues to develop and expand. We have focused here
on search games on a network with an immobile hider, but search games are not
limited to this paradigm. Much has been achieved in the field of search games with
a mobile hider (also originally motivated by Isaacs [
14
]), as well as many other
variations on the classic models. The connected field of search games in unbounded
domains, initiated independently by Bellman [
8
] and Beck [
7
], has also been ex-
tensively studied. Many unanswered questions in search games remain and new
problems arise, capturing the imaginations of those who have taken the childhood
game of hide-and-seek to its mathematical extreme.
References
1.
Alpern, S. (2010). Search games on trees with asymmetric travel times. SIAM J. Control
Optim. 48, no. 8, 5547-5563.
2.
Alpern,
S.
(2011).
Find-and-fetch
search
on
a
tree.
Operations
Research
59
(2011):
1258-1268.
3.
Alpern, A., Baston, V. and Gal, S. (2008). Network Search Games with an immobile hider
without a designated searcher starting point, Int. J. Game Theory 37, 281-302.
4.
Alpern S. and Gal S. (2003). The Theory of Search Games and Rendezvous (Kluwer Interna-
tional Series in Operation Research and Management Sciences, Kluwer, Boston).
Search WWH ::
Custom Search