Information Technology Reference
In-Depth Information
Y
←
where
members of
η
(
s
−
q
−
2
)
if
k
=
s
,
ρ
(
k
)=
η
(
s
−
q
−
1
)
if
k
=
s
and so at least
λ
q
if
ρ
(
k
)(
s
−
1
)
≥
(
η
+
2
)
.
Hence, using the symmetric result if
J
←
(
W
)
|
=
|
1
,
we have
|B
(
W
)
|≥|W |
if
ρ
(
k
)(
s
−
1
)
≥
(
η
+
2
)
.
For
s
≥
q
+
3
,
ρ
(
k
)(
s
−
1
)
≥
η
(
s
−
1
)
so
|B
(
W
)
|≥|W |
for
η
≥
2andfor
η
=
1
and
s
≥
4
.
However
η
=
1and
s
<
4gives
s
=
3and
q
=
0
.
By Remark
1
we only
need to consider the case
b
=
1
/
3and
a
=
1
/
λ
q
.
Because
η
=
1
,
λ
q
≤
5
.
It is easy
Y
←
so
to see that
B
(
W
)
contains at least 6
>
λ
q
members of
|B
(
W
)
|≥|W |.
Using the Remarks, we have therefore shown that, for all
W ⊆ B
which are
needed for the proof of the theorem
|B
(
W
)
|≥|W |.
Thus, for all relevant
B, B
has
a set of distinct representatives by Hall's Theorem. Thus
B
i
)
∈X
→
gives rise to
(
j
a pure Defender strategy with intervals
B
i
(
j
)
and
A
where
A
∈ Y
is the representa-
B
i
; we say that
A
is the correspondent of
B
i
tive of
(
j
)
(
j
)
.
Pure Defender strate-
gies involving
B
i
(
j
)
are obtained similarly. Thus we have a total of 2
(
s
λ
q
−
q
λ
s
)
Y ∪X
→
∪X
←
occurs in precisely one of
them. Let
S
denote the Defender strategy which selects one of these pure strate-
gies at random. We show that, for
w
pure strategies and every member of
∈
[
,
]
,
(
−
λ
+
λ
−
)
0
1
S
has at least 2
s
q
pure
s
q
.
strategies which have intervals containing
w
Now
λ
s
s
B
i
A
i
(
j
)
∪
(
j
)
j
=
1
,...,
λ
q
−
q
i
=
1
i
=
1
λ
q
q
λ
s
B
i
A
i
A
i
(
j
+
λ
q
−
q
)
∪
(
j
+
λ
q
−
q
)
∪
(
j
)
j
=
1
,...,
s
−
λ
s
i
=
1
i
=
1
i
=
1
+
λ
s
are coverings of
and so are the above expressions with the arrows reversed.
Denote the set of these coverings by
[
0
,
1
]
Y ∪X
→
∪X
←
C.
Note that every member of
occurs in precisely one member of
C .
For
w
∈
[
0
,
1
]
,
a covering
C
∈ C
has a (unique) first interval
I
C
(
w
)
containing
w
,
by which we mean that the left-hand endpoint of
I
C
(
w
)
is strictly less than the left-
hand endpoint of any other interval of
C
containing
w
.
Note that
I
C
(
w
)
starts strictly
to the left of
w
if
w
is in precisely one of the pure strategies of
S
for any
w
so we can define a mapping of
=
0
.
Now
I
C
(
w
)
C
into the pure strategies of
S
by mapping
C
to the pure strategy containing
I
C
(
We show that this mapping is an injection.
Suppose two different coverings
C
1
and
C
2
map into the same pure strategy. This
pure strategy therefore comprises the intervals
I
C
1
(
w
)
.
w
)
and
I
C
2
(
w
)
,
one of which is
of length
b
and the other (its correspondent) is of length
a
.
Because an interval of
length
b
does not contain its correspondent,
w
>
0
.
Hence
I
C
1
(
w
)
and
I
C
2
(
w
)
have an
interval
(
w
−
ε
,
w
]
in common for some
ε
>
0
.
Thus, by the definition of the
B
i
(
j
)
,
the interval of length
b
must be of the form
B
i
or
B
i
(
j
)
(
j
)
where
i
∈{
q
,
s
}
for
some
j
and the interval of length
a
of the form
A
λ
i
(
or
A
λ
i
(
j
1
)
j
1
)
respectively where
If
B
i
contains
w
so must
B
i
Similarly, if
A
λ
i
(
i
∈{
q
,
s
}
for some
j
1
.
(
j
)
(
j
1
)
.
j
1
)
Search WWH ::
Custom Search