Information Technology Reference
In-Depth Information
interpreted as a binary vector of length
L
, where a 1 in the
n
-th position indicates
searching in the
n
-th period, while a 0 indicates ambushing. Thus
s
2
,
4
=
{
0
,
1
,
0
,
1
}
.
A subscript on the
s
represents the relevant vector entry; hence
s
2
,
4
2
1,
s
2
,
4
3
=
=
0.
l
K
. Any pure hider strategy,
h
i
,
could also be represented by a binary vector, but this rarely proves necessary.
Our notation provides us with a natural ordering for the searcher strategies:
concatenate the relevant binary vectors to create binary numbers, then sort in de-
scending numerical order. Under this approach, strategies that emphasise relatively
“early” search will be listed ahead of those that emphasise “late” search.
To provide a compact formula for the expected payoffs, we define the vector
W
m
Our constraint on the searcher requires
1
s
l
=
∑
=
of length
L
,where
W
j
=
m
and 0 otherwise; as an example,
W
3
j
if
j
<
=
W
L
+
1
. The expected time until capture from any combi-
nation of pure hider and searcher strategies is:
.Define
W
L
+
=
{
1
,
2
,
0
,
0
}
i
−
1
−
∑
1
K
sW
i
K
1
s
l
h
i
l
=
T
(
s
,
)=
+
(
Ts
i
+
i
)
,
(16.1)
K
Vector multiplication is assumed to proceed appropriately, producing a scalar in
every case, without introducing notation to distinguish row and column vectors.
The interpretation of this formula is not obvious, so some explication follows.
We will first consider the case where the hider plays the suboptimal stratyegy of not
moving before time
L
,thatis,
i
=
L
+
. In that case the expected time until capture is
1
K
multiplied by the search strategy,
s
, multiplied by
W
, which will just be a vector
of integers counting from 1 to
L
(we will have that
/
i
1
l
=
1
s
l
=
−
K
, so the second term
∑
in the formula is zero). Thus, against the strategy
{
0
,
1
,
0
,
1
}
, the expected capture
1
2
)+
1
2
)=
time in our example game would be 2
3.
Consider another case, where the hider moves before the first period in which the
searcher searches. In that case the first term is zero (as
sW
i
(
4
(
i
1
l
=
−
=
0), while
1
s
l
=
0.
∑
Since in this case
s
i
=
0, the entire equation is simply equal to
i
. If, however, the
hider moves in the first period in which the searcher searches (so that
s
i
=
1), the
payoff is
T
i
,where
T
is the payoff obtained by playing the game again assum-
ing the hider and searcher hold their probability distributions over their strategies
constant.
The remaining and most complex case is thus when the hider moves after some
cells have been searched, but not all of them. In this case the term
+
K
sW
i
represents
the proportion of the expected payoff due to the possibility of capture
before
the
period in which the hider moves.
1
i
−
1
K
−
∑
1
s
l
K
represents the probability that the hider
will not have been captured by time
i
, and thus the probability of obtaining the
payoff
T
l
=
i
(if movement occurs during search) or
i
(if it does not).
Thus: against
+
,
h
1
provides a payoff of 1;
h
2
T
;
h
3
1
2
{
,
,
,
}
+
(
)+
0
1
0
1
of 2
of 2
T
2
.
For a particular game, the payoff matrix is denoted
A
L
,
K
. The searcher is taken as
the column player (with strategies ordered as described previously) while the hider
is the row player. For our example, we have:
1
2
)=
5
1
2
)+(
1
2
)=
2
,and
h
4
of 2
3
(
(
4
+
T
)(
3
+
Search WWH ::
Custom Search