Information Technology Reference
In-Depth Information
16.5.3 The Game with an Infinite Number of Periods
In the case where
L
is infinite, the above solution for the value of the single cell
simplifies to:
T
∞
,
1
=
,
2
(16.28)
If
q
n
and
p
n
represents the a priori probability of the hider and searcher electing to
move or search, respectively, in the
n
-th period, we also find that
q
n
=
n
.
This calculation assumes continuity in the limit of equation (
16.27
); this can be
shown to be reasonable through an alternate (and much simpler) solution technique,
namely directly solving the following 2
p
n
=(
1
/
2
)
×
2matrix:
Search
Ambush
Move
1
+
T
∞
,
1
1
Stay
1
1
+
T
∞
,
1
This formulation models the hider and searcher as making a decision at the
beginning of each period, rather than each round. This is possible since, as noted,
in the infinite one-cell game the hider cannot have any information about the pro-
portion of the space searched, nor is anything gained by knowing what time period
they are in (since there is always an infinite number of periods remaining). This is
not the case for games with higher values of
K
or finite
L
.
16.6 AmbushinTwoCells
Once we move into the more complex set of games where
K
1, the situation
is complicated by the rapid growth in the number of strategies available to the
searcher.
3
>
, rather than
attempting to derive an explicit equation for the value of the game under finite
L
,as
we did for the case where
K
For the case of
K
=
2, we restrict ourselves to setting
L
=
∞
1. This is not to say that such an equation is impos-
sible; indeed, any game with
K
=
2 and finite
L
should theoretically be explicitly
solveable. The solutions, though, tend to involve large sums of high-order polyno-
mial equations, and, given the awkwardness involved in their manipulation, and the
=
3
As an aside, note that when
L
is infinite, we can take every searcher strategy from the case where
K
1, which involved searching in a particular period, and associate it with the subset of searcher
strategies when
K
=
2 that search for the first time in that same period. That is, we can associate
s
1
=
s
1
,
2
s
1
,
3
s
1
,
4
,
s
2
s
2
,
3
s
2
,
4
s
2
,
5
with
{
,
,
...}
with
{
,
,
...}
, and so on. Thus every searcher strategy when
K
0
.The
set of searcher strategies when
K
=
1 is of cardinality ℵ
0
; the set of all searcher strategies when
K
=
2 is thus of cardinality ℵ
0
×
ℵ
0
=
ℵ
0
. An inductive argument demonstrates that for any
K
,
the set of searcher strategies is always of countable cardinality: very briefly, given that the searcher
strategy space for
K
−
1 is countable, the addition of a new cell to search in allows each strategy in
the previous space to be associated with a countably infinite subset of strategies (note these subsets
need not be non-intersecting with one another).
=
1 can be associated with a subset of searcher strategies when
K
=
2 of cardinality
ℵ
Search WWH ::
Custom Search