Information Technology Reference
In-Depth Information
reply BLUE will place as many objects as possible at the points 1 and
n
=
λ
p
+
1
.
As
q
BLUE can put a total of
c
objects at 1 and
n
because an object
must be placed at each point of
≤
n
−
2
+
c
,
[
2
,
n
−
1
]
if objects are put in both 1 and
n
.
Thus a
minimum of
q
−
c
objects must be put in
[
2
,
n
−
1
]
so that RED is assured of a payoff
of at least
(
q
−
c
)
/
λ
.
Now suppose
n
=
λ
p
+
2 for some integer
λ
and RED chooses a member of
{
J
2
(
i
)
:
i
=
0
,
1
,...,
λ
−
1
}
at random. The probability of an
x
satisfying 2
≤
x
≤
λ
whereas each of 1 and
n
occur with
probability 0. Hence, as before, in a best reply BLUE will put as many objects as
possible at the points 1 and
n
but be forced to put at least
q
p
+
1 occurring in the RED strategy is 1
/
λ
−
c
in
[
2
,
n
−
1
]
because
q
)
/
λ
.
The structure of our BLUE strategies is much more complicated so we first look
at a particular example to illustrate the general case.
≤
n
−
2
+
c
.
Thus RED's strategy ensures a payoff of at least
(
q
−
c
Example 1.
The game in which
n
=
λ
p
+
2
=
32
,
p
=
5
,
c
=
2and
q
=
28 has value
26
/
6
=(
q
−
c
)
/
λ
.
Proof.
Consider the BLUE strategy which chooses one of the following pure strate-
gies at random.
1
6
tim
e
s
0
B
1
,
B
1
=(
2
,
2
,
2
,
1
,
1
,
2
,
2
,
2
,
2
,
1
,
2
,
2
,
2
,
2
,
1
,
2
,
,...,
0
)
,
1
6
tim
e
s
0
B
2
B
2
=(
2
,
2
,
2
,
2
,
1
,
2
,
2
,
2
,
1
,
1
,
2
,
2
,
2
,
2
,
1
,
2
,
,...,
0
)
,
,
1
6
tim
es
0
B
3
B
3
=(
2
,
2
,
2
,
2
,
1
,
2
,
2
,
2
,
2
,
1
,
2
,
2
,
2
,
1
,
1
,
2
,
,...,
0
)
,
where
←−−−−−−−
(
x
1
,...,
x
n
)=(
x
n
,...,
x
1
)
.
The points in
{
1
,
2
,
3
,
6
,
7
,
8
,
11
,
12
,
13
,
16
}
each
have an expected capacity of 6/6, those in
{
4
,
9
,
14
}
each have an expected capacity
of 5/6 while those in
{
5
,
10
,
15
}
each have an expected capacity of 3/6. Thus ev-
ery five successive points in
[
1
,
16
]
have an expected capacity of
(
18
+
5
+
3
)
/
6
=
26
/
6
=(
q
−
2
)
λ
.
By symmetry the same holds for every five successive points in
[
. Furthermore every 5 consecutive points containing 16 and 17 must contain
at least 1 of 15 and 18 and at least 1 of 14 and 18 so has an expected capacity of at
most 26/6. Thus the value of the game is at most 26/6.
17
,
32
]
By introducing some notation we can see that the example has a structure which
will be useful in the general case. Let
g
i
(
=
,...,
)
i
1
m
denote sequences of lengths
α
,...,
α
m
respectively, then we use
g
1
⊕
g
2
⊕···⊕
g
m
to denote the sequence of
1
length
m
given by the members of
g
1
in order, followed by the members
of
g
2
in order and so on, finishing up with the members of
g
m
in order. Thus, putting
J
5
(
α
+
···
+
α
1
and letting
m
t
denote the sequence of
tm
's,
B
1
in our example can be written as 2
1
⊕
1
)=(
2
,
2
,
2
,
1
,
2
)
,
J
5
(
2
)=(
2
,
2
,
1
,
1
,
2
)
It is then
clear that
B
2
and
B
3
can be obtained from
B
1
by suitably permuting the
J
5
's in
B
1
.
J
5
(
2
)
⊕
J
5
(
1
)
⊕
J
5
(
1
)
⊕
0
16
.
Search WWH ::
Custom Search