Some Cinderella Ruckle Type Games - Search Theory: A Game Theoretic Perspective - page 83

6.3 Greedy Games

Consider the following scenario. RED wants to hide a quantity of arms or drugs
within a given region which, if not detected within a given time, can be used to fur-
ther RED's interests in the region. BLUE (the authorities within the region) can em-
ploy various measures in an attempt to find the hidden resource and frustrate RED's
ambitions. The benefit to RED of successfully hiding the resource depends on the
amount that has been hidden and circumstances dictate that the larger the amount
RED tries to hide the greater the probability that it will be discovered by BLUE. This
means that RED needs to balance two competing factors; RED would like to hide a
large amount so that RED would derive a substantial benefit if it remains undetected
but, at the same time, not so large that BLUE has a high probability of detecting it. In
modelling this scenario as a game it seems reasonable to set the payoff to RED as q
when an amount q is successfully hidden. The payoff when an amount q is detected
by BLUE is not so clearcut as it may depend on how RED views the situation; we
therefore introduce a parameter If RED

has very large global resources and the scenario is a comparatively minor one for
it, the loss of resource would not be significant and a value of

β ≥ 0 and set the payoff to RED as − β q .

near zero would
be appropriate. On the other hand, if RED has little influence outside the region, a
loss of a sizeable amount of resource could have major consequences for it so that a
comparatively large value of

β

might be appropriate.
The above scenario provides the motivation for our definition of a greedy game.

β

It is a two-person zero-sum game which is played in a compact convex region S with

interior points, of n -dimensional Euclidean space. RED (the maximizer) chooses a member
C from a given class

,

of measurable subsets of S and, without knowing RED's choice,
BLUE (the minimizer) selects B from a given subset

C

B of the power set of S . Letting A

denote the measure of the C chosen by RED and 0 ≤ β , RED gets A if B ∩ C is empty and

loses β A if it is not. Both players know S , C, B and β .

In a number of ways this type of game is a mirror image of the type of game
discussed in Sect. 6.2 . Here, in a particular one-dimensional setting, an interval is
being placed to avoid a point chosen by an opponent whereas, in the Several Interval
Games, intervals are placed in an attempt to include a point chosen by an opponent.
Ruckle solved several greedy games which are played over the unit interval I =

[ In the length greedy game RED can choose any measurable

set and BLUE any set with at most k points whereas, in the interval greedy game ,
RED can choose any interval of I and BLUE an interval of length at most

0 , 1 ] when β = 0 .

In
both games BLUE has an optimal strategy which employs a uniform distribution. In
the first BLUE chooses k points independently using the uniform distribution on I
and, in the second, starts by choosing t

α .

∈ [ 0 , 1 − α ] by the uniform distribution on

[ -optimal strategy

which involves a covering of I in both games. The basic idea underpinning the RED
strategy for the length greedy game is that I is divided into an appropriately large
number n of intervals and then a member is chosen at random from the set of unions

0 , 1 − α ] and then occupies the interval [ t , t + α ] . RED has an ε