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

interval where, in each case, the payoff to RED is the measure of the intersection of
the sets chosen by the players:

Γ ( α , β ) . RED chooses a set of measure at most α and BLUE chooses a set of measure

MM

at least β .

Γ ( α , β ) . RED chooses an interval of length at most α and BLUE chooses a set of measure IM

at least β .

Γ ( α , β ) . RED chooses a set of measure at most α and BLUE chooses an interval of length MI

at least β .

The next result shows that Γ MM is easy to solve using the ideas we have developed.

Proposition 1. The value of Γ MM is αβ .

Proof. Firstly suppose both α and β are rational, say a 1 / a 2 and b 1 / b 2 respectively.

x ∗ where m is an integer and 0 x ∗ < For each real number x , let x = m + ≤ 1 . Given

x ∗ , x ∗ + γ ] γ ∈ [ 0 , 1 ) and x a real non-negative number, I γ ( x ) is defined as the interval [

if x ∗ + γ ≤ x ∗ , x ∗ − if x ∗ + γ >

1andthepairofintervals [ 1 ] ∪ [ 0 , γ + 1 ] 1 . For rational

γ = c 1 / c 2 say, let

I γ = { I γ ( x ) : x = μγ for μ = 0 , 1 ,..., c 2 − 1 },

then I γ covers [ 0 , 1 ] precisely c 1 times. Thus, if RED chooses a member of I α

at random, RED can guarantee an expectation of β ( c 1 ) / c 2 )= βα whatever set of

measure β BLUE chooses. Similarly, if BLUE chooses a member of I β at random,

RED's expectation can be restricted to αβ . Hence the Proposition holds for rational

α and β .

Clearly the expectation to RED does not decrease as the value of α increases

or the value of β decreases. The result therefore follows for general α and β be-

γ ,

< γ > γ

cause, given any irrational number there are rational numbers r 1 and r 2

γ .

arbitrarily close to

The proof of Proposition 1 tells us that, provided a player can split the allowed
measure between two intervals, he gets no benefit from being able to choose a mea-
surable set.
Although, in general the games Γ MI are more difficult to analyse, some

easy deductions can be made. Because BLUE's strategy space in

Γ IM and

Γ IM contains
BLUE's strategy space in the Interval Overlap Game and RED's strategy space is
the same in both games, the value of Γ IM is less than or equal to the value of the

Interval Overlap Game. Furthermore the RED strategy in the proof of Proposition 1
ensures that the value of I MI is at least Γ MI

is greater than or equal to the value of the Interval Overlap Game and Blue can en-
sure the value of I IM is not more than

αβ . By similar arguments, the value of

Although one suspects that the following
problem is not so difficult as many of the others in this chapter, it still may not be
easy.

αβ .

Problem 2. Solve Γ MI and Γ IM .