Information Technology Reference
In-Depth Information
of precisely
m
members of these intervals where
m
is defined in terms of
For
the interval greedy game the basic idea is simpler; RED divides
I
into an appropriate
number of intervals and chooses one of them suitably modified.
α
and
n
.
β
=
,
=
When
0
the greedy length game in which
k
1 and the interval length
game in which
α
=
0 have a common solution so we now investigate the
point
greedy interval game
Γ
in which RED chooses an interval, BLUE chooses a point
and
In common with Ruckle, we take the interval to be closed so that RED
will in general have only
β
≥
0
.
-optimal strategies although it will be plain that RED
has optimal strategies if open intervals are allowed. The next lemma generalises the
strategies used by Ruckle in the game with
ε
β
=
0 to obtain bounds on what the
players can achieve in the more general game.
Lemma 1.
In the point greedy interval game, BLUE can restrict RED's expectation
to at most
1
/
(
4
(
1
+
β
))
whereas RED can guarantee an expectation of at least
n
2
{
(
−
−
β
)
/
}−
ε
ε
>
max
n
1
where
0
and the maximum is taken over all positive
integers.
Proof.
If BLUE employs the uniform distribution on
I
then BLUE has a probability
of
L
of intersecting with a RED interval of length
L
giving RED an expectation of
(
,
1
−
L
)
L
−
L
β
L
=
L
(
1
−
(
1
+
β
)
L
)
.
Hence the best that RED can do is to choose an
interval of length 1
/
(
2
(
1
+
β
))
and BLUE can restrict RED to a payoff of at most
1
/
(
+
β
))
.
For a positive integer
n
and
4
(
1
η
>
0 small, suppose RED plays one of the intervals
[
1 at random; any pure strategy of BLUE can
intersect at most one of these intervals so RED can ensure an expectation of at least
k
/
n
,
(
k
+
1
)
/
n
−
η
]
,
k
=
0
,
1
,...,
n
−
1
n
−
η
)(
n
−
1
1
n
(
1
n
−
η
)=
n
−
−
β
n
2
1
n
−
1
−
β
(
)
−
β
−
η
n
n
and the lemma follows.
A consequence of the lemma is that, if there is a positive integer
n
such that
n
2
(
then its common value is the value of the game. It
is therefore easy to check that, for all positive integers
n
n
−
1
−
β
)
/
=
1
/
(
4
(
1
+
β
))
,
≥
2
,
thegamehasvalue
1
/
(
.
The formulation of the game requires that the players know the value of
2
n
)
when
β
=(
n
−
2
)
/
2
but,
from a practical view, BLUE in particular may have little idea concerning its precise
value. It can therefore be useful to know that a strategy is reasonably good for a
range of values of
β
even it is not optimal, particularly if that strategy is fairly
simple. The above analysis suggests the uniform distribution is such a strategy; in
particular, it is likely to be effective if the loss of material has serious implications
for RED, that is, when
β
β
is large.
the position is a good deal more complicated.
First of all we should perhaps address the question of whether the games actually
have
a value; we do not wish to go into the details here but they do by an existence
theorem of Alpern and Gal (see [
5
] Theorem A.1 on page 293). In the games in
For general values of
β
∈
[
0
,
1
]
,
Search WWH ::
Custom Search