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

ball B of radius b and RED closed balls R 1 ,..., R k of radii r 1 ,..., r k where all the closed

∩ i = 1 R i = balls have their centres in S . The payoff (to RED) is 1 if S ∩ B /0and0otherwise.

Note that the Hide in a Disc Game is equivalent to one in which BLUE chooses
a closed disc of radius r B and RED a closed disc of radius c − r B . Thus, when the

topology is given by the Euclidean metric, special cases of Γ S ( b ; r 1 ,..., r k ) include:

• Hide in a Disc Game where S is the unit disc, b = r b , k = 1and r 1 = c − r B ;

• Several Intervals Game where S is the unit interval, the closed balls are closed

intervals and b = 0;

•

Several Intervals Game Variation in which BLUE chooses an interval of length
b instead of a point.
So far research on Ruckle-type games has almost exclusively concerned itself
with problems in which the Euclidean topology is employed but, from a games
that people do not play standpoint, there is no reason why other topologies should
be ignored. In particular the Euclidean topology is a special case ( p = 2) of the

topology given by the distance function

n
i = 1 ( | x i − y i | )

p 1 / p

|| x − y || p =( )

where x =( x 1 ,..., x n ) , y =( y 1 ,..., y n ) and p ≥ 1 . When p = 1 , we have the Manhat-

tan, or taxicab, topology whereas the limit as p → ∞ gives the Chebyshev topology

which is represented by the distance function Note

that closed balls in R 2 takes the shape of a square in the Chebyshev topology and
the shape of a diamond in the Manhattan topology. A closed ball in R 1

|| x − y || ∞ = max 1 ≤ i ≤ n | x i − y i |.

is a linear

segment for all p .

In contrast to the Euclidean version, the Chebyshev Hide in a Disc Game, even
in its n -dimensional form, is easy to solve; it can be stated as follows:
Play takes place in I n where I denotes the unit interval. BLUE chooses a point and RED a
n -cube of side 2 r 1 and the payoff to RED is 1 if BLUE's point is in RED's cube and zero
otherwise.

be a minimum cover of I n Let G by cubes of side 2 r 1 then, if RED chooses a

member of G at random, RED's expectation is at least 1 /|G|. Let m be the posi-

tive integer such that 2 mr 1 < 1 ≤ 2 mr 1 + 1 , δ satisfy 0 < δ < ( 1 − 2 mr 1 ) / m and

P ( i )= 2 i ( r 1 + δ ) . If BLUE selects one of the points B = { ( P ( i 1 ) ,..., P ( i n )) : i j =

0 , 1 ..., m for j = 1 ,..., n } at random, then

|| ( P ( i ) , P ( j )) − ( P ( s ) , P ( t )) || = max {| 2 ( s − i )( r 1 + δ ) |,| 2 ( t − j )( r 1 + δ ) |}

1

≥ ( + δ ) .

2 r 1

Thus any closed ball of radius r 1 contains at most one point of B so BLUE can

2

restrict RED's expectation to at most 1 / ( m + 1 ) . But, taking S ( i , j ) to denote the

closed ball with centre at the point (( 2 i + 1 ) r 1 , ( 2 j + 1 ) r 1 + 1 ) and radius r 1 , { S ( i , j ) :

2 members so RED can expect at

0 ≤ i , j < m } is a cover of I × I containing ( m + 1 )

2 and the game is solved.

least 1 / ( m + 1 )