Information Technology Reference
In-Depth Information
Theorem 4 (Alpern).
The value V of the find-and-fetch game on a tree is
V
=
μ
+
D
/
ρ
,
(2.3)
where D
is the mean distance from O to the leaf nodes of Q, weighted
according to the EBD distribution.
=
D
(
Q
)
To illustrate how
D
is calculated, consider the network in Fig.
2.1
. The probabil-
ities that the hider is at nodes
A
,
B
and
B
are 2/15, 3/15 and 10/15, respectively, and
the distances of these nodes from
O
are 3, 4 and 3. Hence
D
=
2
/
15
(
3
)+
3
/
15
(
4
)+
5
/
15
(
3
)=
11
/
5. For
ρ
=
1
/
2, the value
V
of the find and fetch game played on the
tree in Fig.
2.1
is
V
tends to infinity so
that the searcher can return instantaneously to the root after finding the hider, the
value
V
in (
2.3
) tends to
=
9
+(
11
/
5
)
/
(
1
/
2
)=
10
.
1. Note that as
ρ
, Gal's classic result (Theorem
2
).
A different model of search is given in [
6
], in which the authors suppose that
the searcher can use an
expanding search
. This is defined as a sequence of unit
speed paths on a network
Q
, starting at
O
, each of which starts from a point already
reached by the searcher. Another way to think of expanding search is as a family of
connected subsets of
Q
starting with
O
and expanding at unit speed. To differentiate
expanding search from the type of search used in Gal's model, we call the latter
pathwise search. Expanding search provides a model of mining, in which the time
taken to recommence mining from a location already reached in small compared to
the time taken up by the mining itself. As before, the hider simply picks a point on
Q
and the searcher picks an expanding search. The search time is the time taken for
the searcher to reach the hider.
Again, if
Q
is a tree it turns out that the EBD distribution is optimal for the hider,
and the searcher's optimal strategy is a branching strategy. The authors show that
μ
Theorem 5 (Alpern and Lidbetter).
The value V of the expanding search game on
atreeis
=
/
(
μ
+
)
,
V
1
2
D
(2.4)
The variable
D
is defined as above. In the case of the network in Fig.
2.1
where
D
6.
In [
6
] the expanding search game is also solved for 2-arc-connected networks.
These are networks that cannot be disconnected by the removal of fewer than two
arcs. The authors show that on these networks it is optimal for the hider to hide
uniformly, and for the searcher to make an equiprobable choice of a reversible ex-
panding search and its reverse. A reversible expanding search is simply one whose
reverse is also an expanding search, analogous to an Eulerian circuit in Gal's model.
The authors show that such a search always exists on a 2-arc-connected network,
and the randomized choice of this search and its reverse ensures that the searcher
finds the hider in expected time no greater than
=
11
/
5and
μ
=
9, the value is
V
=
1
/
2
(
9
+
11
/
5
)=
5
.
2, which is the value of the game.
For example, the 3-arc network depicted in Fig.
1.1
in Chap.
1
is 2-arc-connected,
and hence has value
μ
/
μ
/
2
=
3
/
2.
Search WWH ::
Custom Search