Information Technology Reference
In-Depth Information
s 1 , 2
s 1 , 3
s 1 , 4
s 2 , 3
s 2 , 4
s 3 , 4
h 1
1
+
T
1
+
T
1
+
T
1
1
1
h 2
(
3
+
T
) / 2
3
3
/ 2
/ 2
2
+
T
2
+
T
2
A 4 , 2
h 3
3
(
4
+
T
) / 2
(
5
+
T
) / 2
5
=
/ 2
2
/ 2
3
+
T
h 4
3
(
5
+
T
) / 2
5
(
6
+
T
) / 2
(
7
+
T
) / 2
/ 2
2
/ 2
h 4 +
3
5
5
7
/ 2
2
/ 2
/ 2
3
/ 2
By definition, where q represents the vector of searcher probabilities and p the
vector of hider probabilities, both in row form, we have:
p A L , K q T
T L , K (
s
,
h
)=
,
(16.2)
16.4 Some Rudimentary Bounds
We begin by presenting some upper and lower bounds. These bounds are of interest
in their own right, but also serve as a check on our numerical results for large L
and K , especially given that they are substantially easier to compute. First, by con-
sidering the payoff that would result if the hider moves with equal probability in
each of the periods from 1 to L , the folowing can be shown:
Theorem 1. There exists a hider strategy which guarantees the lower bound:
K 3
3 +
K 2
2 +
2
K
6
+ (
L
K
)(
K
+
1
)
T L , K
,
(16.3)
K
(
2 L
K
1
)
(
2 L
K
1
)
Second, consideration of the analogous seacher strategy, where the searcher gives
equal probability to each of their possible strategies, leads to:
Theorem 2. There exists a searcher strategy which guarantees the upper bound:
nK
(
2 K
+
3
n
)
T L , K
max
1 n K + 1 , n N
,
(16.4)
2
+
2 n
(
K
1
)
Note that the parameter L does not influence the value of this bound.
A final bound can be obtained by considering the game as a restricted version of
search on a network structured so that there are K directed (“one-way”) loops from
a central node, i.e. a K -leaf clover. The central node is then taken as the searcher's
ambush point. We will not go into detail, but using existing techniques from the
search game literature it is possible to conclude the following:
Theorem 3. When L
=
, there exists a searcher strategy which guarantees the
upper bound:
T , K
K
+
1
,
(16.5)
 
Search WWH ::




Custom Search