Information Technology Reference
In-Depth Information
More generally let
J
p
(
w
)
denote the sequence
(
x
1
,...,
x
p
)
with
x
i
=
1for
p
−
w
≤
i
≤
p
−
1and
x
i
=
2 otherwise; in particular
J
p
(
0
)=
2
p
.
For
w
i
satisfying
0
≤
w
i
≤
p
−
2
,
let
(
,...,
w
μ
)=
⊕
(
)
⊕···⊕
(
w
μ
)
⊕
.
H
p
w
1
2
1
J
p
w
1
J
p
0
μ
p
+
1
=
(
,
,
)
,
=
(
,
,
)
=
(
,
,
)
.
Thus, in the example,
B
1
H
5
2
1
1
B
2
H
5
1
2
1
and
B
3
H
5
1
1
2
(
,...,
w
μ
)
Note that
H
p
w
1
represents a BLUE strategy in the game in which
i
n
=
2
μ
p
+
2
,
c
=
2and
q
=
2
(
μ
p
+
1
)
−
∑
1
w
i
as does
H
p
(
w
)
,...,
w
σ
(
μ
)
)=
σ
(
1
=
H
p
(
σ
w
)
(abusing notation) where
σ
is any permutation of
{
1
,...,
μ
}.
Given
w
=
(
w
1
,...,
w
μ
)
,
let
σ
∈ I
(
μ
)
}∪{
←−−−−−
H
(
w
)=
{
H
p
(
σ
w
)
:
H
p
(
σ
w
)
:
σ
∈ I
(
μ
)
}
p
I
(
μ
)
{
,
,...,
μ
}
where
denotes the set of permutations of
1
2
Theorem 2.
Fo r p
>
2
,
n
=
2
μ
p
+
2
,
c
=
2
and q satisfying
μ
(
p
+
2
)+
2
≤
q
≤
2
μ
p
+
1
,
the value of the game is
(
q
−
c
)
/
(
2
μ
)
.
Proof.
RED can ensure an expectation
by Lemma
2
so we only need
to show that BLUE can restrict RED to that expectation. Take any
w
(
q
−
c
)
/
(
2
μ
)
=(
w
1
,...,
w
μ
)
i
=
1
w
i
=
satisfying 0
≤
w
i
≤
p
−
2and
2
(
μ
p
+
1
)
−
q
;sucha
w
exists because
∑
1
≤
2
(
μ
p
+
1
)
−
q
≤
μ
(
p
−
2
)
.
Suppose BLUE adopts the strategy which picks
amemberof
H
μ
(
w
)
at random, then
x
1
,
x
2
∈
[
1
,
μ
p
+
1
]
satisfying
x
1
−
x
2
=
0
(
mod
p
)
have the same expected allocation. Thus, if the RED strategies starting at
1
,...,
p
all have expectation at most
(
q
−
c
)
/
(
2
μ
)
,
then so does every RED strategy
contained in
[
1
,
μ
p
+
1
]
.
Put
ρ
w
(
m
)=
|{
i
:
w
i
≥
m
}|,
then the expected allocation of
j
∈
[
1
,
p
]
is
(
2
−
ρ
w
(
p
+
1
−
j
)
/
μ
)
/
2 which is a decreasing function of
j
.
Hence ev-
p
j
ery RED strategy contained in
[
1
,
μ
p
+
1
]
has an expected allocation of
p
−
∑
ρ
w
=
1
(
p
+
1
−
j
)
/
(
2
μ
)
.
Let
t
m
=
|{
j
:
w
j
=
m
}|,
then
μ
i
=
1
w
i
=
p
m
=
1
mt
m
=
p
m
=
1
m
(
ρ
w
(
m
)
−
ρ
w
(
m
+
1
)) =
p
m
=
1
ρ
w
(
m
)
.
2
(
μ
p
+
1
)
−
q
=
Thus every RED strategy contained in
[
1
,
μ
p
+
1
]
,
and by symmetry, every RED
strategy contained in
[
μ
p
+
2
,
n
]
,
has an expected allocation of
(
q
−
2
)
/
(
2
μ
)
.
Suppose a RED strategy contains both
λ
p
+
1and
λ
p
+
2
.
By symmetry the
expected allocations of
2
and, from the above, we know that these allocations are increasing functions of
j
λ
p
+
1
−
j
and
λ
p
+
2
+
j
are the same for
j
=
1
,...,
p
−
.
Hence every RED strategy containing both
λ
p
+
1and
λ
p
+
2 has an expected
[(
μ
−
)
+
,
μ
+
]
allocation of at most that of
1
p
2
p
1
which has the same expected
[
,
+
]
.
(
−
)
/
(
λ
)
.
allocation as
2
p
1
Thus RED has an expectation of at most
q
c
2
Apart from the extreme cases
q
=
2
μ
p
+
1and
q
=
μ
(
p
+
2
)+
2
,
there are several
possibilities for the choice of
in the proof of the previous theorem so
there are in general a number of optimal strategies for BLUE. However the exam-
ples in [
7
] show that there are BLUE optimal strategies which do not follow our
(
w
1
,...,
w
μ
)
Search WWH ::
Custom Search