Information Technology Reference
In-Depth Information
For trees, the find and fetch model and the expanding search model can both
be encapsulated in a single overarching model. In [
1
] Alpern examines the Search
Game on a network with asymmetric travel times, meaning that the speed it takes
for the searcher to traverse an arc depends on the direction in which he travels. An
equivalent formulation is given in [
5
] in which the searcher moves with a speed that
depends on his direction of travel. We therefore call this the
variable speed
model.
The game is then defined as usual: the searcher picks a path in the network starting
at
O
, the hider picks a point on the network and the payoff is the time taken for the
searcher to reach the hider. The model clearly encompasses Gal's model of networks
with symmetric travel times if the travel times of each arc are set to be the same in
either direction.
For a tree
Q
we can give every point
x
on
Q
a height
, equal to the time taken
to travel from
O
to
x
(along the shortest path) minus the time taken to travel from
x
to
O
. This definition is motivated by the assumption that it is quicker to travel uphill
than downhill. In [
1
] Alpern shows that the EBD is once again optimal for this game
played on a tree, and he gives recursive formulae for the optimal branching strategy
for the searcher. In [
5
], the authors derive a closed form expression for the optimal
searcher strategy as well as a formula for the value
V
of the game:
δ
(
x
)
Theorem 6 (Alpern and Lidbetter).
The value V of the variable speed search
game is
V
=
1
/
2
(
τ
+
Δ
)
,
(2.5)
where
τ
is defined as the time taken for the searcher to tour the network, and
Δ
=
Δ
(
is defined as the mean height of the leaves, weighted with respect to the EBD
distribution.
Q
)
τ
=
If the network is symmetric, then all leaf nodes have height 0, and
2
μ
,
=
μ
=
μ
/
¯
so (
2.5
) reduces to Gal's classic result,
V
2 given in Theorem
2
. In fact, in
the case that the network
Q
is a tree, the variable speed network model also encom-
passes both the find and fetch model and the expanding search model, as we now
explain.
We first consider the find and fetch game, in which the searcher must return to
O
along the shortest path at speed
after finding the hider. It is optimal for the hider to
choose a leaf node
x
, and for any such choice of
x
at shortest distance
d
ρ
(
x
,
O
)
from
O
, the searcher must travel for additional time
d
after finding the hider. We
therefore form a new network
Q
from
Q
by adding an asymmetric arc from
x
to a
new leaf node
x
+
with forward travel time (from
x
to
x
+
)of
d
(
x
,
O
)
/
ρ
(
x
,
O
)
/
ρ
and backward
. The variable speed game played on
Q
is then equivalent to
the find and fetch game played on
Q
: traveling to
x
+
in
Q
is equivalent to traveling
to
x
in the original network and then back to
O
at speed
travel time
−
d
(
x
,
O
)
/
ρ
, and if the hider is not at
x
the extra arc from
x
to
x
+
makes no contribution to the search time. Hence the two
models are equivalent.
The total tour time
ρ
of
Q
is equal to twice the length 2
of
Q
, and in the
Q
the
τ
μ
leaf node
x
+
has height 2
d
Q
)
(
x
,
O
)
/
ρ
,so
Δ
=
Δ
(
is the mean value of 2
d
(
x
,
O
)
/
ρ
,
Search WWH ::
Custom Search