Information Technology Reference
In-Depth Information
The structure is as follows. In Sect.
9.2
we introduce the notation we require
and give a summary of Woodward's results for the two barrier game
After
analysising an illustrative example in Sect.
9.3
, these results are used in Sect.
9.4
to obtain a lower bound for the value of
Γ
(
a
,
b
)
.
This is achieved by proving that
Defender has an optimal strategy of a particular form and then showing by linear
programming that a strategy of this form cannot restrict Infiltrator to less than a
certain quantity. A second example is introduced in Sect.
9.5
to illustrate the ideas
used in Sect.
9.6
to demonstrate that a Defender strategy can be constructed which
achieves the lower bound obtained in Sect.
9.4
. In the final section we comment on
and give some consequences of our result.
Γ
(
a
,
b
)
.
9.2 Notation and Woodward's Results
We will always assume that
a
and
b
are positive real numbers with
a
≤
b
<
1
,
Γ
(
a
,
b
)
is the game defined in the Introduction and
v
(
a
,
b
)
is the value of
Γ
(
a
,
b
)
.
Apart from
the final section we will also assume that
b
<
1
/
2; as we shall see, our expression
for the value of
2
for which it does not. As Baston and Bostock [
2
] have completely solved the case
b
Γ
(
a
,
b
)
applies for
b
<
1
/
2 but there are some cases with
b
≥
1
/
≥
this exception is not a problem, just something of a curiosity.
As mentioned previously, Woodward [
13
]hasshownthat
1
/
2
,
Γ
(
a
,
b
)
is equivalent
to a finite game
Γ
F
(
a
,
b
)
which is similar to
Γ
(
a
,
b
)
but one in which the strategy
spaces of the players are finite subsets of
[
0
,
1
)
.
In
Γ
F
(
a
,
b
)
Defender's strategy space
is
Z
×
Z
where
Z
=
{
μ
b
+
ρ
a
∈
[
0
,
1
)
:
μ
and
ρ
non-negative integers
}
(
,
)
∈
×
so that
Z
represents the strategy that places the left-hand endpoints
of the intervals with lengths
a
and
b
at the points
w
1
and
w
2
w
1
w
2
Z
.
This result is crucial to
the proof of our theorem in Sect.
9.4
but, for technical reasons, we take the Defender
strategy space as
Z
∗
×
Z
∗
where
Z
∗
=
Z
∪{
1
}.
Let
z
0
=
0
,
z
1
=
a
,
z
2
,...,
z
|
Z
|−
1
,
z
|
Z
|
=
1
(9.1)
be the elements of
Z
∗
in increasing order. We do not need to consider the strategy
space for Infiltrator in
in detail but, for the information of the reader, it
comprises of a set of points obtained by taking, for each
z
Γ
F
(
a
,
b
)
∈
Z
,
a point just to the
right of
z
the distance past
z
being larger the farther
z
is to the right of the interval.
In Sect.
9.6
a Defender strategy in
,
will be defined using a number of
coverings of [0,1] with intervals of lengths
a
and
b
and it is reasonable to expect
that, for an optimal strategy, these coverings will be minimal in some sense. This is
the motivation for the following notation.
Given
a
and
b
,define
Γ
F
(
a
,
b
)
λ
1
/
b
=
0
,
where
1
/
b
denotes the least integer greater
than or equal to 1
/
b
,
and, for
i
=
0
,
1
,...,
1
/
b
−
1
,
λ
i
by the integer such that
Search WWH ::
Custom Search