Information Technology Reference
In-Depth Information
Proof.
From Lemmas 1 and 2 and Theorem 3 in [
13
], Defender and Infiltrator have
optimal strategies contained in finite strategy spaces which are subsets of the strat-
egy spaces of
As stated in Sect.
9.2
we need only be specific about the
Defender strategy space which, for technical reasons, we take to be
Z
∗
×
Γ
(
a
,
b
)
.
Z
∗
where
Z
∗
=
and
Z
is given by (
9.1
). The only feature of the finite Infiltrator strategy
space that is relevant here is that it can be taken so that it is contained in
Z
∪{
1
}
As
the payoffs in the finite game are rational, a theorem of Weyl (see [
12
]) ensures that
the game value is rational and that each player has an optimal strategy in which the
probability of playing any pure strategy is also rational. Hence we may make the
following assumptions.
[
0
,
1
)
.
Assumption 1
There is a Defender optimal strategy S
0
made up of k (not necessar-
ily distinct) pure strategies in Z
∗
×
Z
∗
each played with probability
1
/
k
.
Assumption 2
If the intervals in one of the pure strategies in S
0
intersect within
[0,1], then they do so only at a point of Z
∗
.
For instance, if a pure strategy
places the two intervals
[
w
1
,
w
1
+
a
]
and
[
w
2
,
w
2
+
b
]
such that w
1
<
w
2
and
w
1
+
a
∈
(
w
2
,
w
2
+
b
)
then it can be replaced by the strategy placing the intervals
at
because every Infiltrator strategy which is
intercepted by the former pair of intervals is intercepted by the latter pair.
[
w
1
,
w
1
+
a
]
and
[
w
1
+
a
,
w
1
+
a
+
b
]
Assumption 3
In the set of all strategies satisfying Assumptions
1
and
2
S
0
is one
with a maximal number of pure strategies having the interval of length b preceding
the interval of length a
.
Because there are precisely
k
Defender strategies, it is clear that the value of the
game
v
(
a
,
b
)
must take the form
(
k
−
m
)
/
k
for some positive integer
m
.
For each
i
=
1
,...,|
Z
|
Infiltrator can choose a point of
(
z
i
−
1
,
z
i
)
so there must be at least
m
of
the
k
members of
S
0
which contain
z
i
)
.
Note also that the intervals in the pure strategies of
S
0
all start at a point of
Z
∗
and thus terminate at a point in
Z
∗
∪
(
(
z
i
−
1
,
1
,
1
+
b
]
.
CLAIM 1: An optimal strategy
S
∗
can be obtained from
S
0
using an inductive
argument with the property that, for
i
S
∗
has precisely
m
pure
=
1
,...,|
Z
|,
strategies having intervals which contain
(
z
i
−
1
,
z
i
)
.
The inductive hypothesis is stated as follows. Suppose, for some
j
satisfying
S
j
is an optimal Defender strategy which selects at random a member
from a multiset
K
j
of
k
pure strategies in
Z
∗
×
0
≤
j
< |
Z
|,
Z
∗
and which satisfies the following
conditions:
(
α
)
the intervals in a member of
K
j
intersect in [0,1] (if at all) only at a point of
Z
∗
,
(β
)
for each
i
=
1
,...,|
Z
|,
there are at least
m
members of
K
j
which have intervals contain-
ing
(
z
i
−
1
,
z
i
)
,
(γ ) for each
i
=
1
,...,
j
there are precisely
m
members of
K
j
which have intervals containing
(
z
i
−
1
,
z
i
)
.
Search WWH ::
Custom Search