Information Technology Reference
In-Depth Information
Although the technical details are somewhat involved, the basic idea in the proof
of the next theorem is quite simple. Two sets of intervals
X
and
Y
are defined with
all the members of
X
having length
b
and all the members of
Y
having length
a
.
For each interval
J
in
X
the set of all those sets in
Y
which are disjoint from
J
is
denoted by
B
.
It is shown that
B
J
has a set of distinct representatives so that the
J
representative of
J
together with
J
can be interpreted as a Defender pure strategy.
The strategy which chooses one of these pure strategies at random enables the result
to be established.
B
∈
Λ
+
(
∈
Λ
−
(
Theorem 3.
Let
2
b
<
1
,
s
a
,
b
)
and q
a
,
b
)
,
then Defender can restrict
Infiltrator to at most
1
−
G
(
s
,
q
)
where G
(
s
,
q
)
is given by (
9.4
).
∈
Λ
+
,
∈
Λ
−
.
X
→
and
Y
←
by
Proof.
Let 2
b
<
1
,
s
and
q
Define
X
→
=
{
B
i
(
j
)
:1
≤
i
≤
q
,
1
≤
j
≤
s
−
λ
s
+
λ
q
−
q
}
B
i
∪{
(
j
)
:
q
+
1
≤
i
≤
s
,
1
≤
j
≤
λ
q
−
q
}
and
Y
←
=
{
A
i
(
j
)
:1
≤
i
≤
λ
s
,
1
≤
j
≤
s
−
λ
s
+
λ
q
−
q
}
A
i
∪{
(
j
)
:
λ
s
+
1
≤
i
≤
λ
q
,
1
≤
j
≤
s
−
λ
s
}
X
←
and
Y
→
have the directions of the arrows reversed. It is
Definitions for
easy to see that
|X
→
|
=
|X
←
|
=
λ
s
=
|Y
→
|
=
|Y
←
|.
s
λ
q
−
q
B
1
B
s
A
λ
s
,
A
λ
s
−
1
(
A
1
Note that, for 1
≤
j
≤
λ
q
−
q
,
(
j
)
,...,
(
j
)
,
j
)
,...,
(
j
)
is not
in general a chain in the sense of Sect.
9.4
because the definition of
λ
s
in (
9.2
)
means that
B
s
can have interior points in common. However it is
easy to generate a chain from it by moving the
A
i
(
j
)
and
A
λ
s
(
j
)
(
j
)
s an appropriate distance to the
right. Similar comments apply to
B
1
B
q
A
λ
q
,
A
λ
q
−
1
(
A
1
(
j
)
,...,
(
j
)
,
j
)
,...,
(
j
)
.
This
B
q
B
s
Y
→
∪Y
←
=
Y
motivates the definitions for
(
j
)
and
(
j
)
below. Putting
let, for each
B
i
)
∈X
→
,
and denoting the interior of an interval
I
by int
I
,
(
j
:
B
i
{
A
∈ Y
(
j
)
∩
int
A
=
0
}
if
i
∈{
q
,
s
}
B
i
(
j
)=
(9.6)
A
λ
i
(
or
B
i
{
∈ Y
=
)
(
)
∩
=
}
∈{
,
}.
A
:
A
j
j
int
A
0
if
i
q
s
B
i
The
are defined by reversing the directions of the arrows.
We will obtain the existence of a mixed optimal strategy by taking pure strate-
gies comprising
B
i
(
j
)
(respectively
B
i
B
i
(
j
)
(
j
)
) and a member of
(
j
)
(respectively
B
i
(
j
)
). To do this, we will show that, for most cases, the family
B
of all the
B
i
B
i
has a set of distinct representatives; by Remarks
1
and
2
these
cases will be sufficient to prove the theorem. It is easy to see that
(
j
)
and
(
j
)
|B|
=
2
(
s
λ
q
−
q
λ
s
)
.
Search WWH ::
Custom Search