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

on it. Section 6.7 looks at its symmetrization and asks whether there are optimal
strategies in this symmetrization which are probability distributions over a finite
number of points.

Section 6.8 shows that some of our games can be thought of as special cases of a
general game and Sect. 6.9 details come conclusions.

6.2 The Several Intervals Game

Probably the game in Ruckle's topic which has since received the most attention in
the literature is the Several Intervals Game. In it BLUE chooses a single point b in
[0,1] and RED chooses the union of several closed intervals R = J 1 ∪...∪ J k where,

for each i R and zero

otherwise. Ruckle obtained solutions by trial and error for two special cases when
k

, the length of J i is at most α i . The payoff to RED is one if b ∈

2 and, as a result, ventured that the solution for general k may be difficult; he
therefore made a more modest proposal of solving it for k

=

2or3.Evenforthis
more limited objective progress has been slow and, to adapt Churchill's description
of Attlee, workers on it have a lot to be modest about. However, after 20 years,
Woodward in a doctoral thesis [ 5 ] managed to come up with what can be regarded
as a complete solution for k

=

We will indicate the processes that enabled him to
arrive at this solution as they may provide ideas that can be used to solve the case
k

= 2 .

3 which, as we shall see, still presents a challenge.
In essence Woodward's approach was straightforward but the devil remained in
the detail. Firstly it was shown that the game for general k is equivalent to a corre-
sponding finite game meaning that a complete solution could be obtained for any
given set of interval lengths using linear programming. Although theoretically use-
ful, little immediate value was obtained from the computer results for k

=

2 due to
the sheer volume of data and the vast number of different strategies. In particular
vastly different strategies could be produced for games which had the same game
values and very similar

=

Also RED strategies proved particularly awk-
ward as the computer did not find symmetric ones. This meant that the approach
was throwing up interesting computing problems because it was important that a
coherent set of solutions be produced for a theoretical analysis to be undertaken. By
perturbing interval positions, swapping intervals from one strategy to another and
other techniques, strategies were found which were valid for all cases with the same
value; in many instances the resulting strategies showed very little resemblance to
the original strategies generated by the computer. It was then possible to detect the
pattern which enabled a theoretical analysis to be made. This analysis is contained
in Woodward's thesis of almost 300 pages but recently new arguments (see Chap. 9 )
have been found which enable the treatment to be shortened.
Woodward also managed to generate a number of results for k

α 1 and α 2 .

3bythesame
methods and we give an account of his findings. He produced expressions for the
game value which cover all the cases when 1

=

/ 3 ≤ α 1 < 1 / 2and α 3 ≥ 1 / 5 . It might