Information Technology Reference
In-Depth Information
would be sufficient for our purposes but, to make full use of symmetry, we will take
α
=
We will be able to restrict attention to two particular types of chain, one in
which all the intervals of length
b
precede all the intervals of length
a
and the other
in which all the intervals of length
a
precede all the intervals of length
b
2
.
.
As the number of intervals of length
b
equals the number of intervals of length
a
correspondences between them. Each correspondence
f
can be
used to define a Defender strategy
S
,
there are
(
1
−
1
)
(
)
by choosing one of the intervals of length
b
at random together with the interval of length
a
corresponding to it. We shall see
in the proof of the next theorem that, by setting up an appropriate correspondence
f
f
is given by (
9.4
). To
prove the existence of an appropriate correspondence, we need Hall's theorem ([
1
]
or see [
5
] p. 89) on systems of distinct representatives.
A system of distinct representatives
of not necessarily distinct subsets
C
1
,
,
S
(
f
)
restricts Infiltrator to at most 1
−
G
(
s
,
q
)
where
G
(
s
,
q
)
C
2
,
...,
C
n
of a set
X
is an
n
-tuple
(
c
1
,
c
2
,...,
c
n
)
such that
c
i
∈
C
i
for
i
=
1
,...,
n
and
c
i
=
.
For a subset
J
c
j
if
i
=
j
⊆{
1
,
2
,...,
n
},
define
C
(
J
)=
∪
j
∈
J
C
j
where
C
(
0
)=
0
.
Theorem 2 (Hall's Theorem).
The family C
1
,
C
2
,...,
C
n
has a system of distinct
representatives if and only if
|
C
(
J
)
|≥|
J
|
for all subsets J of
{
1
,
2
,...,
n
}.
For positive integers
i
and
j
let
A
i
B
i
(
j
)=[(
i
−
1
)
a
,
ia
]
,
(
j
)=[(
i
−
1
)
b
,
ib
]
,
B
i
and
A
i
Although
B
i
(
j
)=[
1
−
ib
,
1
−
(
i
−
1
)
b
]
(
j
)=[
1
−
ia
,
1
−
(
i
−
1
)
a
]
.
(
j
1
)
and
B
i
(
j
2
)
are equal as sets, we will want to look on them as different entities when
Similar remarks apply to the other entities. To avoid unwieldy notation we
effectively treat these entities as multisets and adopt the following convention.
j
1
=
j
2
.
B
→
,
A
←
,
B
←
,
A
→
},
Convention.
For
X
,
Y
∈{
we consider
X
i
1
(
j
1
)=
Y
i
2
(
j
2
)
if and
only if
X
j
2
.
If Defender can restrict Infiltrator's payoff to at most
v
with intervals of lengths
b
and
a
=
Y
,
i
1
=
i
2
and
j
1
=
,
he can clearly restrict Infiltrator's payoff to at most
v
with intervals of lengths
b
and
a
where
b
≥
b
and
a
≥
.
We will use this fact for some particular cases in
the proof of the next theorem which gives an upper bound for
v
a
(
a
,
b
)
in terms of an
∈
Λ
+
(
∈
Λ
−
(
s
a
,
b
)
and a
q
a
,
b
)
.
These cases use the following remarks.
we can decrease the value of
a
to
a
∗
Remark 1.
When
λ
s
=
0and
qb
+
λ
q
a
>
1
,
+
λ
q
a
∗
=
where
qb
1 and just prove the theorem for the case when
λ
s
=
0and
we can decrease
b
to
b
∗
where
qb
+
λ
q
a
=
1
.
Furthermore, if we also have
q
=
0
,
sb
∗
=
1 and just prove the theorem for
b
∗
=
1
/
s
and
a
=
1
/
λ
q
.
Remark 2.
When
q
=
0and
sb
+
λ
s
a
>
1where
λ
s
>
0
,
we can decrease
b
to
b
−
=
a
;if
b
−
=
we can then further
decrease the values of
b
−
and
a
together until they equal
b
∗
where
sb
∗
+
λ
s
b
∗
=
max
{
b
1
,
b
2
}
where
sb
1
+
λ
s
a
=
1and
b
2
=
b
2
,
1
λ
0
b
∗
≥
(note that
(
s
+
λ
s
−
1
)
a
≤
sb
+(
λ
s
−
1
)
a
<
1
≤
λ
0
a
so
s
+
λ
s
≤
λ
0
giving
1).
Hence when
q
=
0and
λ
s
>
0 we need only prove the theorem for the case when
q
=
0and
sb
+
λ
s
a
=
1
.
Search WWH ::
Custom Search