Information Technology Reference
In-Depth Information
6.4 Area Greedy Games
In the previous section we concentrated attention on greedy games played on the
unit interval so we will now look at generalizations of the Area Greedy game which
was given as a problem in Ruckle's topic. In this two person zero-sum game played
over the unit square
S
,
RED (the maximizer) chooses a rectangular subset with edges
parallel to
S
and BLUE (the minimizer) selects a path in
S
which is the graph of a
continuous function from
BLUE wants the path to intersect RED's
rectangle and, if it does, RED gets nothing. On the other hand RED gets the value
of the area of the chosen rectangle if BLUE's path does not intersect it. The game
has the flavour of a needle in a haystack game but, in this game, RED can choose
the size of the rectangle as well as its position whereas the hider in a needle in a
haystack game hides a needle of fixed length.
It is straightforward to see that Ruckle's game has a simple solution. By choosing
the function
f
n
defined by
[
0
,
1
]
to
[
0
,
1
]
.
2
(
nt
−
i
)
if
i
≤
nt
≤
i
+
1
/
2
f
n
(
t
)=
1
−
2
(
nt
−
i
−
1
/
2
))
if
i
+
1
/
2
≤
nt
≤
i
+
1for
i
=
0
,
1
...,
n
−
1
.
/
BLUE can ensure that every RED rectangle with horizontal length of at least 1
n
/
.
is intersected so that RED's payoff is at most 1
Thus, by choosing
n
sufficiently
large, RED's payoff can be made arbitrarily small and the value of the game is
therefore zero. Note that the same is true if RED has the freedom to choose any
convex subset of
S
n
not just rectangles.
To particularise the general definition of greedy game given in the previous sec-
tion and stay within the spirit of the area greedy game of Ruckle, we define an
area
greedy game
as a two person zero-sum game played over a compact region
S
,
,
with
interior points, of two-dimensional Euclidean space of the following type.
RED (the maximizer) chooses a member from a class
of convex subsets of
S
and, without
knowing RED's choice, BLUE (the minimizer) selects a path from a set of paths
C
P
,allof
length at most
L
Letting
A
denote the area of the set chosen by RED, RED gets
A
if
BLUE's path does not intersect it and loses
,
in
S
.
β
A
if it does. Both players know
S
, C, P,
L
and
β
.
Ruckle's original game is easy to solve because BLUE is allowed to choose a
path that has no restrictions on its length. In fact every one of our area greedy games
(and also some more general ones) has value zero if BLUE is allowed a completely
free choice of path. This follows from Lemma 3.39 of Alpern and Gal [
5
]which
ensures that, given
there is a (closed) path in the two-dimensional compact
convex set
S
such that every point of
S
has distance less than
ε
>
0
,
from the path. Hence
a natural restriction to impose on BLUE's paths is that they should have length
bounded by a positive real number, L say.
Notice that there are connections between the point greedy interval game anal-
ysed in the previous section and a number of area greedy games on the unit square
when BLUE has to choose a path which is the graph of a constant function. In the
ε
Search WWH ::
Custom Search