Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Fraenkel divides games into two types, games people play (i.e. games that people buy and play) and games that mathematicians play or, in Peter Winkler’s words, games people don’t play. The selection of the games here fall very definitely into the latter category and the hope is that these games will lead to the development of ideas which can be used to unify treatments for a variety of games, in other words, usable methods. Thus the choice has been strongly influenced by two factors. Firstly there needs to be a connection between the games and secondly each game has to provide a stimulus for further research; in most cases this means that the games are used as a starting off point from which attractive open questions can be generated. As a result Sects. 6.2 and 6.8 all include suggestions for further work of varying degrees of difficulty which are intended to encourage more researchers to take an interest in the games. However it does mean that other games associated with Ruckle such as lattice and accumulation games have been ignored. In keeping with the spirit of Ruckle’s book, the games in this chapter are all two-person zero-sum ones and the players are called RED and BLUE with RED being the maximizer. The structure of the chapter is described in the following paragraphs.

The Several Intervals Game is played in the unit interval I with BLUE choosing a point of I and RED simultaneously selecting intervals of given lengths α i in I; the payoff to RED is one if BLUE’s point is in one of the intervals and zero otherwise. Although simply stated, this has proved to be an extremely difficult game to solve and no comprehensive solution has been found when RED can choose more than two intervals. Abbreviated details of the original (unpublished) approach used for the Two Intervals Game and some of the results on the Three Intervals case are given in Sect. 6.2.

Ruckle’s greedy games have not attracted very much attention and are the subject of Sects. 6.3 and 6.4. Many games have the form that RED has the task of deciding where to hide a given amount of material but, in greedy games, RED has the additional decision of determining how much material to hide when facing the prospect that hiding more means a greater probability of discovery. Section 6.3 gives a formal definition of a greedy game and then concentrates attention on games in the unit interval whereas Sect. 6.4 looks briefly at greedy games on the unit square.

In the Number Hides Game RED and BLUE simultaneously choose subintervals of given length in an integer interval with RED getting a payoff equal to the number of integers the subintervals have in common. The game proved more tractable than the other games we consider and it was solved independently by three sets of researchers. Section 6.5 presents some natural variations of the game and Sect. 6.6 discusses the interesting generalization by Zoroa, Fernandez-Saez and Zoroa [7] in which BLUE has to hide a given quantity of objects in an integer subinterval of his choice with the stipulation that at least one object and at most c can be placed at each integer of the subinterval; as before RED chooses a subinterval and receives an amount equal to the number of objects in it. The solution of this game seems to be difficult so, as a first step, it is proposed that the solution of a couple of particular cases extending those of [7] be attempted.

The Hiding in a Disc Game is again easily stated. RED and BLUE simultaneously choose points in the unit disc and RED wins if and only the chosen points are at most a given distance c apart. It was already proving awkward 30 years ago as Ruckle demonstrated that an assertion concerning its value in the American Mathematical Monthly was false and, since then, there seems to have been little work done 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.

2 The Several Intervals Game

Probably the game in Ruckle’s book 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, the length of J i is at most α i . The payoff to RED is one if b ∈ R and zero otherwise. Ruckle obtained solutions by trial and error for two special cases when k = 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 = 2 or 3. Even for this 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 = 2. 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 = 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 corresponding finite game meaning that a complete solution could be obtained for any given set of interval lengths using linear programming. Although theoretically useful, 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 α 1 and α 2. Also RED strategies proved particularly awkward 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 = 3 by the same methods and we give an account of his findings. He produced expressions for the game value which cover all the cases when \(1/3 \leq \alpha _{1} < 1/2\) and α 3 ≥ 1 ∕ 5. It might have been expected that the justification of a RED optimal strategy would prove more troublesome than a BLUE one as it involves triplets of intervals played with certain probabilities whereas a BLUE strategy is simply a probability distribution on [0,1]. However the reverse was true because a RED optimal strategy could be easily verified by showing that each point of [0,1] meets its intervals with a certain probability. In many cases the RED optimal strategies could be derived using three appropriate inequalities of the form \(x_{i1}\alpha _{1} + x_{i2}\alpha _{2} + x_{i3}\alpha _{3} \geq 1\ i = 1,2,3\) where the x ij are non-negative integers; to be appropriate, a necessary condition is that there are positive integers p, q, r satisfying \(px_{i1} + qx_{i2} + rx_{i3} = W\) for each i resulting in the value of the game being \((p + q + r)/W.\) Note that the inequalities represent three different coverings of the unit interval by segments of lengths α 1, α 2 and α 3. This follows a similar pattern to that found in the Two Intervals Game where the RED optimal strategies can mostly be derived from two different coverings of the unit interval.

Although the examples give indications of how the case k = 3 might be treated in general, there are sufficient exceptions to suggest that further ideas are necessary if substantial progress is to be made. For example most have a BLUE optimal strategy which uses each of 0 and 1 with a probability equal to the game value. However no such BLUE strategy was found for the case \(\alpha _{1} = 1/3,\ \alpha _{2} = 1/4\) and \(\alpha _{3} = 1/5.\) Its value is 13/56 but the BLUE optimal strategy obtained used each of 0 and 1 with probability 10/56. This case is interesting in another way as the Red optimal strategy was derived from four covering inequalities rather than the usual three; in addition to the obvious 3α 1 ≥ 1,  4α 2 ≥ 1 and 5α 3 ≥ 1, \(\alpha _{1} + 2\alpha _{2} +\alpha _{3} \geq 1\) is needed. It seems therefore that an interesting challenge on the way to solving the case k = 3 would be to answer the following open question.

Question 1.

What is the value of the Three Intervals Game when the lengths of the intervals are of the form \(\alpha _{1} = 1/u,\alpha _{2} = 1/v\) and \(\alpha _{3} = 1/w\) when u, v and w are positive integers satisfying 3 ≤ u ≤ v ≤ w?

To introduce a note of optimism, Woodward in his work on the Three Intervals Game has taken the length of the largest interval to be at least a third and it could be that the case when the longest interval has length less than a third will have a more unified treatment. After all, in the Two Intervals Game, there is a single expression for the value of the game when the length of the longest interval is less than a half but this expression does not always hold when it is greater than or equal to a half.

Woodward has also obtained some minor results for the n interval case. In particular he has shown that, when α 1 > 1 ∕ 2, the value of the game is one half of the value of the game with n − 1 intervals with lengths having values \(\alpha _{2}/(1 -\alpha _{1}),\ldots, \alpha _{n}/\) (1 − α 1). Also if there are n intervals all of the same length 1 ∕ k where k > n, the value of the game is \(1 - k/n.\)

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 further RED’s interests in the region. BLUE (the authorities within the region) can employ 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 β ≥ 0 and set the payoff to RED as − βq. 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 β 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 \(\mathcal{C}\) of measurable subsets of S and, without knowing RED’s choice, BLUE (the minimizer) selects B from a given subset \(\mathcal{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,\ \mathcal{C},\) \(\mathcal{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 = [0, 1] when β = 0. 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 α. 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 [0, 1 − α] and then occupies the interval [t, t + α]. RED has an ε-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 of precisely m members of these intervals where m is defined in terms of α and n. For the interval greedy game the basic idea is simpler; RED divides I into an appropriate number of intervals and chooses one of them suitably modified.

When β = 0, the greedy length game in which k = 1 and the interval length game in which α = 0 have a common solution so we now investigate the point greedy interval gameΓ in which RED chooses an interval, BLUE chooses a point and β ≥ 0. In common with Ruckle, we take the interval to be closed so that RED will in general have only ε-optimal strategies although it will be plain that RED has optimal strategies if open intervals are allowed. The next lemma generalises the strategies used by Ruckle in the game with β = 0 to obtain bounds on what the players can achieve in the more general game.

Lemma 1.

In the point greedy interval game, BLUE can restrict RED’s expectation to at most \(1/(4(1+\beta ))\) whereas RED can guarantee an expectation of at least \(\max \{(n - 1-\beta )/{n}^{2}\}-\epsilon\) where ε > 0 and the maximum is taken over all positive integers.

Proof.

If BLUE employs the uniform distribution on I, then BLUE has a probability of L of intersecting with a RED interval of length L giving RED an expectation of \((1 - L)L - L\beta L = L(1 - (1+\beta )L).\) Hence the best that RED can do is to choose an interval of length \(1/(2(1+\beta ))\) and BLUE can restrict RED to a payoff of at most \(1/(4(1+\beta )).\)

For a positive integer n and η > 0 small, suppose RED plays one of the intervals \([k/n,(k + 1)/n-\eta ],\ k = 0,1,\ldots, n - 1\) at random; any pure strategy of BLUE can intersect at most one of these intervals so RED can ensure an expectation of at least

$$\displaystyle{( \frac{1} {n}-\eta )(\frac{n - 1} {n} ) -\beta \frac{1} {n}( \frac{1} {n}-\eta ) = \frac{n - 1-\beta } {{n}^{2}} -\frac{n - 1-\beta } {n} \eta }$$

and the lemma follows.  □

A consequence of the lemma is that, if there is a positive integer n such that \((n - 1-\beta )/{n}^{2} = 1/(4(1+\beta )),\) then its common value is the value of the game. It is therefore easy to check that, for all positive integers n ≥ 2, the game has value 1 ∕ (2n) when \(\beta = (n - 2)/2.\)

The formulation of the game requires that the players know the value of β but, from a practical view, BLUE in particular may have little idea concerning its precise value. It can therefore be useful to know that a strategy is reasonably good for a range of values of β even it is not optimal, particularly if that strategy is fairly simple. The above analysis suggests the uniform distribution is such a strategy; in particular, it is likely to be effective if the loss of material has serious implications for RED, that is, when β is large.

For general values of β ∈ [0, 1], the position is a good deal more complicated. First of all we should perhaps address the question of whether the games actually have a value; we do not wish to go into the details here but they do by an existence theorem of Alpern and Gal (see [5] Theorem A.1 on page 293). In the games in which a value has been found (\(\beta = 2/(n - 2)\)), these RED strategies have been derived from coverings of I so it is difficult to see how they can be modified to improve the payoff for other values of β. On the other hand optimal alternatives to the uniform distribution for BLUE abound. For instance, when \(\beta = 1/2,\) the value is 1/6 so BLUE can afford to ignore all points in [0, 1 ∕ 6) and (5 ∕ 6, 1] and concentrate the distribution in an appropriate way in \([1/6,5/6].\)

To illustrate the point we show that the value of the game is \((2-\beta )/9\) when \(1/5 \leq \beta \leq 5/7.\) Notice that \((n - 1-\beta )/{n}^{2}\) equals 1/5 for n = 2 and 3 when \(\beta = 1/5\) and equals 1/7 for n = 3 and 4 when \(\beta = 5/7.\) Thus \(1/5 \leq \beta \leq 5/7\) is likely to be the maximum range of values of β giving the game value \((2-\beta )/9\) because not only does Lemma 1 tell us that RED can guarantee more (namely \((1-\beta )/4\)) if β < 1 ∕ 5 but it also suggests that RED cannot guarantee as much if β > 5 ∕ 7. Let

$$\displaystyle{ F(x) = \left \{\begin{array}{@{}l@{\quad }l@{}} 0 \quad &\text{if}\ \ x < (2-\beta )/9, \\ 1/(1+\beta ) - (2-\beta )/{\bigl (9x(1+\beta )\bigr )}\quad &\text{if}\ \ (2-\beta )/9 \leq x < 1/2, \\ (19\beta + 7)/{\bigl (18(1+\beta )\bigr )} \quad &\text{if}\ \ x = 1/2\\ \quad \end{array} \right . }$$

and \(F(x) = 1 - F(1 - x)\) for 1 ∕ 2 < x ≤ 1. 

As \(x \rightarrow 1/2-,\ F(x) \rightarrow (5 + 2\beta )/(9 + 9\beta ) \leq 1/2\) when β ≥ 1 ∕ 5. Thus F(x) is a probability distribution over I which has a jump at 1/2 when β > 1 ∕ 5 and is strictly concave in the interval \([(2-\beta )/9,1/2).\)

Suppose BLUE employs the strategy F(x). We first show that the properties of F mean that we only need to find the payoff of certain RED intervals in detail in order to find RED’s best reply to F. 

If [a, a + x] and [b, b + x] are two RED intervals with \(F(a + x) - F(a) < F(b + x) - F(b),\) then [a, a + x] gives a better payoff than [b, b + x] so we need only consider [a, a + x]. Therefore any RED interval of the form [a, a + x] with \(0 < a \leq (2-\beta )/9\) gives an inferior payoff than [0, x] and so can be ignored.

Furthermore \(F(a + x) - F(a) < F(b + x) - F(b)\) if \((2-\beta )/9 \leq b < a < a + x < 1/2\) so intervals \([a,a + x] \subseteq [2-\beta )/9, 1/2)\) have an inferior payoff to \([1/2 - x, 1/2).\)

For \(a < 1/2 < a + x,\) \(F(a + x) - F(a)\) has a minimum in a for fixed x at \(a = (1 - x)/2\) so, for intervals having 1/2 as an interior point, it is only necessary to consider those symmetric about 1/2.

Finally the symmetry of F means that we can assume a RED interval starts in [0, 1 ∕ 2). 

Thus, in finding RED’s best reply to F, the analysis is reduced to investigating three types of RED interval, namely (i) [0, x],   (ii) [x, 1 ∕ 2) where \(x > (2-\beta )/9\)   and   (iii) \([1/2 - x,1/2 + x].\)

  1. (i)

    For x < 1 ∕ 2, the payoff for [0, x] is

    $$\displaystyle{ (1 - F(x))x -\beta F(x)x = x(1 - (1+\beta )F(x)) = (2-\beta )/9. }$$

For \(1/2 < x \leq 1 - (2-\beta )/9,\) it is

$$\displaystyle{ x(1 - (1+\beta )(1 - F(1 - x))) = x(1 -\beta + \frac{2-\beta } {9(1 - x)}) }$$

Routine calculations show that this expression has a minimum at \(x = 1 - (1/3)\sqrt{(2-\beta )/(1-\beta )} \leq 1/2\) when β ≥ 1 ∕ 5; it is convex so, in \([1/2,(2-\beta )/9],\) its minimum occurs at 1/2. The payoff is continuous on the right in [0,1] so, for x > 1 ∕ 2, it is at least that of the interval [0,1/2] which is at least the payoff \((2-\beta )/9\) of [0,1/2).

  1. (ii)

    For \((2-\beta )/9 \leq x < 1/2,\) the payoff of the interval [x, 1 ∕ 2) is

    $$\displaystyle{ (1/2 - x)(1 - (1+\beta )(F(1/2-) - F(x))) = (1/2 - x)(1 - (2-\beta )(1 - 2x)/9x). }$$

    The two (main) brackets are decreasing functions of x so the maximum occurs at \(x = (2-\beta )/9\) and is less than \((2-\beta )/9.\)

  2. (iii)

    Now \(F((1 + x)/2) - F((1 - x)/2) = 1 - 2F((1 - x)/2)\) so the expected payoff of \([(1 - x)/2,(1 + x)/2]\) is

    $$\displaystyle{ x(1 - (1+\beta )(1 - 2F((1 - x)/2))) = x(2-\beta )(1 - (4/(9(1 - x))). }$$

    This expression is concave and has a maximum of \((2-\beta )/9\) when \(x = 1/3.\)

Lemma 1 tells us that RED can ensure an expected payoff of at least \((2-\beta )/9\) so we have established the following theorem.

Theorem 1.

The value of the point greedy interval game is \((2-\beta )/9\) when \(1/5 \leq \beta \leq 5/7.\)

This leads to the following conjecture.

Conjecture 1.

The point greedy interval game has value \(\max \{(n - 1-\beta )/{n}^{2}\}\) where the maximum is taken over all positive integers.

Of course there are a legion of further challenges with an obvious one being the case when BLUE is allowed to select more than one point. An alternative approach would be to investigate other forms of payoff. We have introduced the idea of a cost to RED of being discovered so a natural extension would be to allow BLUE to choose the number of points to play but levy a cost on BLUE for them. BLUE would then have to make a judgement about the amount of resource to employ, thus creating a doubly greedy game. This might entail a movement away from zero-sum games but, on the basis that what is good for me is bad for my enemy and vice-versa, might realistically still remain in the zero-sum environment. As mentioned above Ruckle did frame his game in terms of BLUE having at most k points but, in the absence of a penalty for using more points, BLUE does not in fact have to make a judgement call. For the record, in the modified length greedy game Ruckle did introduce a modified payoff to RED of aα − bn where α is the length of RED’s interval, n is the number of points in RED’s interval and a and b are positive constants so this may also be setting off point for allied games.

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 book. 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 [0, 1] to [0, 1]. 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

$$\displaystyle{ f_{n}(t) = \left \{\begin{array}{@{}l@{\quad }l@{}} 2(nt - i) \quad &\text{if}\ \ i \leq nt \leq i + 1/2\\ 1 - 2(nt - i - 1/2))\quad &\text{if} \ \ i + 1/2 \leq nt \leq i + 1\ \ \text{for}\ i = 0,1\ldots, n - 1. \end{array} \right . }$$

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 ∕ n. 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, not just rectangles.

To particularise the general definition of greedy game given in the previous section 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 \(\mathcal{C}\) of convex subsets of S and, without knowing RED’s choice, BLUE (the minimizer) selects a path from a set of paths \(\mathcal{P}\), all of length at most L, in S. Letting A denote the area of the set chosen by RED, RED gets A if BLUE’s path does not intersect it and loses βA if it does. Both players know \(S,\ \mathcal{C},\ \mathcal{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 ε > 0, there is a (closed) path in the two-dimensional compact convex set S such that every point of S has distance less than ε 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 analysed 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 latter games, the crucial factor that determines whether BLUE’s path intersects the convex set C chosen by RED is the projection of C onto the y-axis. In particular, in this restricted form of Ruckle’s area greedy game, in order to play optimally RED will choose a rectangle with base of length one so his choice is effectively to choose the height of the rectangle (which is a line segment) while BLUE is effectively choosing a point (the value of the constant). Perhaps the next natural step is to tackle the following problem.

Problem 1.

Solve the Area Greedy Game on the unit square when BLUE can take any path of length one and RED can choose any compact convex set in the unit square.

5 The Numbers Hides Game

Like the Several Intervals Game the Number Hides Game is a two person zero-sum game which was posed as a problem in [4] with some special cases being solved. Its formulation is particularly simple.

RED and BLUE choose sequences of p and q consecutive integers respectively between 1 and n. The payoff to RED is the number of integers in the intersection of the chosen intervals.

The game has proved more tractable than the Several Intervals Game. When Baston and Bostock submitted their solution to the proceedings of the American Mathematical Society, they were told that Ferguson had also solved it so a three author paper [3] was written in the style of Ferguson which the editors preferred. They subsequently learned that Zoroa, Zoroa and Ruiz had also found a solution [6].

The game is the discrete version of the Interval Overlap Game in which RED and BLUE choose intervals of lengths at most α and at least β respectively in the unit interval I, and RED has a payoff of the measure (length) of the intersection of the chosen intervals; this game was solved in [4]. We have seen in Sect. 6.2 that the Several Intervals Game is essentially equivalent to a corresponding finite game so it is natural to ask whether a similar situation pertains here. Although no formal justification has been given, the answer is probably yes as it was remarked in [3] that the ideas used to solve the Numbers Hide game carry over to the Interval Overlap Game; in fact these ideas enabled a fault in the analysis of BLUE’s optimal strategies in [4] to be corrected. The games where the Number Hides Game is modified so that one or both players are permitted to choose an arbitrary set of integers rather than a set of consecutive integers have been solved in [3] and [7]. The game in which both players can choose an arbitrary set of integers is called the Simple Point Catcher Game. As pointed out in [3], its value is pq ∕ n, when RED chooses at most p integers and BLUE chooses at least q but Ruckle [4] gave a more complicated expression, namely

$$\displaystyle \frac{{}^{q}C{_{1}\ }^{n-q}C_{p-1} + {2\ }^{q}C{_{2}\ }^{n-q}C_{p-2} + \cdots + {r\ }^{q}C{_{r}\ }^{n-q}C_{p-r} + \cdots + {p\ }^{q}C{_{p}\ }^{n-q}C_{0}}{ {}^{n}C_{p}} ; $$

this expression can be rearranged to

$$\displaystyle{ \frac{pq/n} {{n-1}C_{p-1}}W} $$

where

$$\displaystyle{ W {=\ }^{n-q}C_{ p-1} {+ }^{q-1}C{_{ 1}\ }^{n-q}C_{ p-2} + \cdots {+ }^{q-1}C{_{ r-1}\ }^{n-q}C_{ p-r} + \cdots {+ }^{q-1}C_{ p-1} }$$

Because W is the coefficient of x p − 1 in the expansion of \({(1 + x)}^{n-q}{(1 + x)}^{q-1}\) and the denominator is the coefficient of x p − 1 in the expansion of \({(1 + x)}^{n-1},\) they are equal and the expression simplifies to pq ∕ n. Optimal strategies for RED and BLUE are to select the set of p, respectively q, integers from {1, 2, …, n} by simple random sampling.

We now introduce notation which enables us to give alternative optimal strategies in the Simple Point Catcher Game which are more useful as a guide for optimal strategies in the modified Interval Overlap games described below. In fact they are the optimal strategies Ruckle used to solve the Modified Number Hides Game in which the players can choose sequences modulo n. Let n be a fixed positive integer and, for each positive integer x, let \(x =\lambda n + {x}^{{\ast}}\) where λ is an integer and 0 < x  ∗  ≤ n. For positive integers m < n and x, put

$$\displaystyle{ I_{m}(x) = \left \{\begin{array}{@{}l@{\quad }l@{}} [{x}^{{\ast}},{x}^{{\ast}} + m - 1] \quad &\text{if}\ \ {x}^{{\ast}} + m - 1 \leq n, \\ \left[{x}^{{\ast}},n\right] \cup [1,m + {x}^{{\ast}}- n - 1]\quad &\text{if}\ \ {x}^{{\ast}} + m - 1 > n. \end{array} \right . }$$

Thus the sets in

$$\displaystyle{ \mathcal{I}_{m} =\{ I_{m}(x) : x = 1 +\mu m\ \ \text{for}\ \mu = 0,1,\ldots, n - 1\} }$$

cover the integer interval [1, n] precisely m times and every integer y ∈ [1, n] is in precisely m members of \(\mathcal{I}_{m}.\) Hence, if RED chooses one of the members of \(\mathcal{I}_{p}\) at random and BLUE chooses any set of q integers in [1, n], RED has an expectation of pq ∕ n. Similarly, if BLUE chooses one of the members of \(\mathcal{I}_{q}\) at random, RED has an expectation of pq ∕ n whatever set of p integers in [1, n] RED chooses. Thus, taking a member at random from \(\mathcal{I}_{p}\) and \(\mathcal{I}_{q}\) respectively are optimal strategies for RED and BLUE in the Simple Catcher Game. These optimal strategies and the ones mentioned earlier demonstrate that the game has the unusual property that, if the roles are reversed (so that RED loses the number of integers in the intersection of the chosen intervals), a player still has the same optimal strategy.

We now look at the analogous problems on the real interval [0, 1] where one or both players can, instead of choosing an interval of length α, choose a set of (Lebesgue) measure α. This gives rise to the following three games over the unit interval where, in each case, the payoff to RED is the measure of the intersection of the sets chosen by the players:

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

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

Γ MI (α, β). RED chooses a set of measure at most α and BLUE chooses an interval of length 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. For each real number x, let \(x = m + {x}^{{\ast}}\) where m is an integer and 0 ≤ x  ∗  < 1. Given γ ∈ [0, 1) and x a real non-negative number, I γ (x) is defined as the interval [x  ∗ , x  ∗  + γ] if x  ∗  + γ ≤ 1 and the pair of intervals \([{x}^{{\ast}},1] \cup [0,\gamma +{x}^{{\ast}}- 1]\) if x  ∗  + γ > 1. For rational \(\gamma = c_{1}/c_{2}\) say, let

$$\displaystyle{ \mathcal{I}_{\gamma } =\{ I_{\gamma }(x) : x =\mu \gamma \ \ \text{for}\ \mu = 0,1,\ldots, c_{2} - 1\}, }$$

then \(\mathcal{I}_{\gamma }\) covers [0, 1] precisely c 1 times. Thus, if RED chooses a member of \(\mathcal{I}_{\alpha }\) at random, RED can guarantee an expectation of \(\beta (c_{1})/c_{2}) =\beta \alpha\) whatever set of measure β BLUE chooses. Similarly, if BLUE chooses a member of \(\mathcal{I}_{\beta }\) 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 β because, 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 measurable set.

Although, in general the games Γ IM and Γ MI are more difficult to analyse, some easy deductions can be made. Because BLUE’s strategy space in Γ 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 αβ. By similar arguments, the value of Γ MI is greater than or equal to the value of the Interval Overlap Game and Blue can ensure the value of I IM is not more than αβ. 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 . 

6 Relatives of the Number Hides Game

The Simple Point Catcher Game can be interpreted as BLUE having q objects to hide at integer points in [1, p] with the constraint that exactly one object can be hidden at a point and RED being allowed to search p integer points in an attempt to find them. The payoff to RED is the number of objects found. A natural generalization of this game is for BLUE to have q objects to hide and be allowed to choose b points in which to hide them with the constraint that an amount between 1 and c must be placed in each of the chosen points. The game has an affinity with the greedy games covered in Sects. 6.3 and 6.4 because BLUE now has to balance two competing factors; whether to hide objects at a comparatively small number of integers meaning that it is relatively difficult for RED to find them but expensive if he does or to spread the objects over a comparatively large number of integers so that losses are more likely but less painful. N Zoroa, M. J. Fernández-Sáez and P Zoroa introduced these types of game involving capacities into the literature and have been in the forefront of research on them (see [7] and [8]); in particular an interesting general Point Catcher Game is solved in [8]. Although they have obtained many results, interesting and challenging problems remain open and we now detail some of them.

First consider the following generalization of the Numbers Hide Game; in [7] it is called the Hide and Seek Game with Capacities equal to c, but we will call it the Integer Number Hides Game with Capacities to emphasize not only that it has a strong relationship with the Numbers Hides Game but also that it is not an isolated game but one that forms part of a coherent body of work.

BLUE has q indivisible objects to hide in the integer interval L = [1, n] and must choose an interval B of L to do so under the restriction that between 1 and c objects must be allocated to each point of the chosen interval. Simultaneously RED picks an interval R of length p and gets a payoff equal to the number of objects that BLUE allocated to the points of A. 

Two results for this game are given in [7]. Firstly, if p is a divisor of N, then the value of the game is pq ∕ N. Secondly, let \(n =\lambda p + r\) where λ is a positive integer and 0 ≤ r < p, then, provided \(q \leq (c - 1)r + p,\) the value of the game is \(q/(\lambda +1)\) if q ≤ rc and \((q(\lambda +1) - cr)/(\lambda (\lambda +1))\) if q > rc. In addition two particular examples are given which show that the value of the game can equal \((q - c)/\lambda .\) As they had found other examples which had the same expression for the value and in which all RED optimal strategies have a similar structure, they suggested that there may be a general structure for games with value \((q - c)/\lambda .\) Very modest progress on this front when \(n =\lambda p + 2\) and c = 2 is detailed below.

Lemma 2.

Let \(n =\lambda p + 1\) or \(n =\lambda p + 2\) for some integer λ and \(q \leq n - 2 + c,\) then RED can ensure a payoff of at least \((q - c)/\lambda .\)

Proof.

Let \(J_{j}(i) = [ip + j,(i + 1)p + j - 1].\) First suppose \(n =\lambda p + 1\) and RED chooses a member of \(\{J_{1}(i) : i = 0,1,\ldots, \lambda -1\} \cup \{ J_{2}(i) : i = 0,1,\ldots, \lambda -1\}\) at random. The probability of an x satisfying 2 ≤ x ≤ λp occurring in the RED strategy is 1 ∕ λ whereas each of 1 and λp + 1 occur with probability 1 ∕ (2λ). Hence in a best reply BLUE will place as many objects as possible at the points 1 and \(n =\lambda p + 1.\) As \(q \leq n - 2 + c,\) BLUE can put a total of c objects at 1 and n because an object must be placed at each point of [2, n − 1] if objects are put in both 1 and n. Thus a minimum of q − c objects must be put in [2, n − 1] so that RED is assured of a payoff of at least \((q - c)/\lambda .\) □

Now suppose \(n =\lambda p + 2\) for some integer λ and RED chooses a member of \(\{J_{2}(i) : i = 0,1,\ldots, \lambda -1\}\) at random. The probability of an x satisfying 2 ≤ x ≤ λp + 1 occurring in the RED strategy is 1 ∕ λ whereas each of 1 and n occur with probability 0. Hence, as before, in a best reply BLUE will put as many objects as possible at the points 1 and n but be forced to put at least q − c in [2, n − 1] because \(q \leq n - 2 + c.\) Thus RED’s strategy ensures a payoff of at least \((q - c)/\lambda .\)

The structure of our BLUE strategies is much more complicated so we first look at a particular example to illustrate the general case.

Example 1.

The game in which \(n =\lambda p + 2 = 32,\ p = 5,\ c = 2\) and q = 28 has value \(26/6 = (q - c)/\lambda .\)

Proof.

Consider the BLUE strategy which chooses one of the following pure strategies at random.

$$\displaystyle{ B_{1} = (2,2,2,1,1,2,2,2,2,1,2,2,2,2,1,2,\overbrace{0,\ldots, {0}}^{16\mathrm{\;times}}),\ \ \ \ \ \ \ \ \ \ \overleftarrow{B_{ 1}}, }$$
$$\displaystyle{ B_{2} = (2,2,2,2,1,2,2,2,1,1,2,2,2,2,1,2,\overbrace{0,\ldots, {0}}^{16\mathrm{\;times}}),\ \ \ \ \ \ \ \ \ \ \overleftarrow{B_{ 2}}, }$$
$$\displaystyle{ B_{3} = (2,2,2,2,1,2,2,2,2,1,2,2,2,1,1,2,\overbrace{0,\ldots, {0}}^{16\mathrm{\;times}}),\ \ \ \ \ \ \ \ \ \ \overleftarrow{B_{ 3}} }$$

where \(\overleftarrow{(x_{1},\ldots, x_{n})} = (x_{n},\ldots, x_{1}).\) The points in {1, 2, 3, 6, 7, 8, 11, 12, 13, 16} each have an expected capacity of 6/6, those in {4, 9, 14} each have an expected capacity of 5/6 while those in {5, 10, 15} each have an expected capacity of 3/6. Thus every five successive points in [1, 16] have an expected capacity of \((18 + 5 + 3)/6 = 26/6 = (q - 2)\lambda .\) By symmetry the same holds for every five successive points in [17, 32]. Furthermore every 5 consecutive points containing 16 and 17 must contain at least 1 of 15 and 18 and at least 1 of 14 and 18 so has an expected capacity of at most 26/6. Thus the value of the game is at most 26/6. □

By introducing some notation we can see that the example has a structure which will be useful in the general case. Let g i  (i = 1, …, m) denote sequences of lengths α 1, …, α m respectively, then we use g 1 ⊕ g 2 ⊕ ⋯ ⊕ g m to denote the sequence of length \(\alpha _{1} + \cdots +\alpha _{m}\) given by the members of g 1 in order, followed by the members of g 2 in order and so on, finishing up with the members of g m in order. Thus, putting \(J_{5}(1) = (2,2,2,1,2),\ J_{5}(2) = (2,2,1,1,2)\) and letting m t denote the sequence of t m’s, B 1 in our example can be written as 21 ⊕ J 5(2) ⊕ J 5(1) ⊕ J 5(1) ⊕ 016. It is then clear that B 2 and B 3 can be obtained from B 1 by suitably permuting the J 5’s in B 1. 

More generally let J p (w) denote the sequence (x 1, …, x p ) with x i  = 1 for \(p - w \leq i \leq p - 1\) and x i  = 2 otherwise; in particular J p (0) = 2 p . For w i satisfying 0 ≤ w i  ≤ p − 2, let

$$\displaystyle{ H_{p}(w_{1},\ldots, w_{\mu }) = 2_{1} \oplus J_{p}(w_{1}) \oplus \cdots \oplus J_{p}(w_{\mu }) \oplus 0_{\mu p+1}. }$$

Thus, in the example, \(B_{1} = H_{5}(2,1,1),\ B_{2} = H_{5}(1,2,1)\) and B 3 = H 5(1, 1, 2). Note that H p (w 1, …, w μ ) represents a BLUE strategy in the game in which \(n = 2\mu p + 2,\ c = 2\) and \(q = 2(\mu p + 1) -\sum _{i=1}^{\mu }w_{i}\) as does H p (w σ(1), …, w σ(μ)) = H p (σw) (abusing notation) where σ is any permutation of {1, …, μ}. Given w = (w 1, …, w μ ), let

$$\displaystyle{ \mathcal{H}_{p}(w) =\{ H_{p}(\sigma w) :\sigma \in \mathcal{I}(\mu )\}\ \cup \ \{\overleftarrow{ H_{p}(\sigma w)} :\sigma \in \mathcal{I}(\mu )\} }$$

where \(\mathcal{I}(\mu )\) denotes the set of permutations of {1, 2, …, μ}

Theorem 2.

For \(p > 2,\ n = 2\mu p + 2,\ c = 2\) and q satisfying \(\mu (p + 2) + 2 \leq q \leq 2\mu p + 1,\) the value of the game is \((q - c)/(2\mu ).\)

Proof.

RED can ensure an expectation \((q - c)/(2\mu )\) by Lemma 2 so we only need to show that BLUE can restrict RED to that expectation. Take any w = (w 1, …, w μ ) satisfying 0 ≤ w i  ≤ p − 2 and \(\sum _{i=1}^{\mu }w_{i} = 2(\mu p + 1) - q;\) such a w exists because \(1 \leq 2(\mu p + 1) - q \leq \mu (p - 2).\) Suppose BLUE adopts the strategy which picks a member of \(\mathcal{H}_{\mu }(w)\) at random, then x 1,  x 2 ∈ [1, μp + 1] satisfying \(x_{1} - x_{2} = 0 ({\rm mod} p)\) have the same expected allocation. Thus, if the RED strategies starting at 1, …, p all have expectation at most \((q - c)/(2\mu ),\) then so does every RED strategy contained in [1, μp + 1]. Put \(\rho _{w}(m) =\vert \{ i : w_{i} \geq m\}\vert, \) then the expected allocation of j ∈ [1, p] is \((2 -\rho _{w}(p + 1 - j)/\mu )/2\) which is a decreasing function of j. Hence every RED strategy contained in [1, μp + 1] has an expected allocation of \(p -\sum _{j=1}^{p}\rho _{w}\) \((p + 1 - j)/(2\mu ).\) Let \(t_{m} =\vert \{ j : w_{j} = m\}\vert, \) then

$$\displaystyle{ 2(\mu p + 1) -q =\sum _{ i=1}^{\mu }w_{ i} =\sum _{ m=1}^{p}mt_{ m} =\sum _{ m=1}^{p}m(\rho _{ w}(m) -\rho _{w}(m + 1)) =\sum _{ m=1}^{p}\rho _{ w}(m). }$$

Thus every RED strategy contained in [1, μp + 1], and by symmetry, every RED strategy contained in [μp + 2, n], has an expected allocation of \((q - 2)/(2\mu ).\)

Suppose a RED strategy contains both λp + 1 and λp + 2. By symmetry the expected allocations of \(\lambda p + 1 - j\) and \(\lambda p + 2 + j\) are the same for \(j = 1,\ldots, p - 2\) and, from the above, we know that these allocations are increasing functions of j. Hence every RED strategy containing both λp + 1 and λp + 2 has an expected allocation of at most that of \([(\mu -1)p + 2,\mu p + 1]\) which has the same expected allocation as [2, p + 1]. Thus RED has an expectation of at most \((q - c)/(2\lambda ).\)  □

Apart from the extreme cases \(q = 2\mu p + 1\) and \(q =\mu (p + 2) + 2,\) there are several possibilities for the choice of (w 1, …, w μ ) in the proof of the previous theorem so there are in general a number of optimal strategies for BLUE. However the examples in [7] show that there are BLUE optimal strategies which do not follow our structure, illustrating that it may not be easy to home in on particular BLUE optimal structures for other cases. It is probably over-optimistic to hope for a complete solution of the game without further inroads into special subcases being made first. Zoroa, Fernández-Sáez and Zoroa have solved the game when q is relatively small so it would seem that the two subcases that present the best chance of progress on an analytical front are:

Problem 3.

Solve The Integer Number Hides Game with Capacities for comparatively large q. 

Problem 4.

Solve The Integer Number Hides Game with Capacities for c = 2. 

Like the Several Intervals Game, one feels that a comprehensive solution of this game may need the insight given by computer generated solutions where the computer has been programmed to target certain types of solution.

A natural variation of the above game in which BLUE has an amount q, not necessarily an integer, of divisible material to hide was introduced by Zoroa, Fernández-Sáez and Zoroa in [8]. It can be formulated as follows.

BLUE has an amount q, not necessarily an integer, of divisible material to hide in the integer interval I and must choose a subinterval B of I with length at most b in which to do so under the restriction that an amount of at most c is allocated to each point of B. Simultaneously RED picks a subinterval R of length r and gets a payoff equal to the amount of material that BLUE allocated to the points of R. 

It is not easy to give a summary of the theorems obtained in [8] which does justice to them without involving detailed notation so the reader is encouraged to read the paper itself. Although a complete solution appears to be extremely difficult, many open questions regarding partial results suggest themselves. Note that, in this game, BLUE is allowed to put an amount zero at some of the chosen points so it is not totally obvious that there is a close connection between this game and the previous one. Thus it is of interest that [8] points out that there are similarities between the two in some cases.

7 Hiding in a Disc Game

The Hiding in a Disc game is very simple to state and easy to understand but seems difficult to solve. It can be described as follows.

Without knowing each other’s choices, RED and BLUE choose points r and b in a disc D with centre O and radius one. The payoff to RED in this zero-sum game is one if \(\vert r - b\vert \leq c\) and zero otherwise.

When \(1/\sqrt{2} \leq c < 1,\) the value is the ratio of the length of the arc whose chord has length c to the circumference of D; optimal strategies for BLUE and RED are to choose a point according to a uniform distribution on the circumference of D and on the circumference of a circle with centre O and radius \(\sqrt{ 1 - {c}^{2}}\) respectively. What intrigued me when I first read Ruckle’s book was that the solution for \(1/2 < c < 1/\sqrt{2}\) was still open, particularly so because the value when \(c = 1/2\) is known. Ruckle showed that, in the range, RED can guarantee a payoff of at least \((1/\pi )\arccos (1/2c)\) demonstrating that a solution communicated to the American Mathematical Monthly was incorrect. The RED strategy which ensured this payoff seemed an intuitively natural one so all that was needed was to produce a BLUE strategy showing RED could do no better. However the “all” proved elusive and, after prolonged efforts, I gave the problem best. On re-reading Ruckle’s book recently I was curious whether progress had been made on the problem but I have been unable to find references to it.

It is natural to wonder whether a symmetry argument which is standard in the literature might be of use for this game; for a formal group theoretic justification of the following process see [1]. Let \(\mathcal{A}\) denote the set of all rotations about the centre and let Γ denote the symmetized version of the game in which, after RED and BLUE choose strategies r and b respectively, a random (equiprobable) member γ is selected from \(\mathcal{A}\) and the payoff \(P(\gamma r,b) = P(r{,\gamma }^{-1}b)\) is assigned to RED. Observe that either player can ensure that Γ is played by applying a random automorphism to his own strategy so its value must be the same as that of the original game. Hence the Hiding in a Disc game is solved once Γ is solved. We may therefore regard mixed strategies of the players in Γ as distributions over the equivalence classes of \(\mathcal{A}\) so that the strategy spaces are represented by the unit interval. The optimal strategies of the game given in [4] can all be expressed in Γ as probability distributions over a finite number of points in the unit interval. Unfortunately the payoff of the symmetrized game is much more complicated than that for the original game so there may be few practical benefits of symmetrising this particular game. However it does highlight a question that is of interest.

Question 2.

In the symmetrized Hiding in a Disc game, do there always exist optimal strategies for the players which are probability distributions over a finite number of points in the unit interval?

8 A General Ruckle-Type Game

Ruckle proposed the problem of solving the Hiding in a Disc Game played on a set S more general than the circular disc. As that game appears to be still unsolved, it might seem somewhat bizarre to give a game formulation of which it is a special case. However the game we now introduce does show that a number of win-lose Ruckle-type games (payoff 0 or 1) do have a common structure and that there may be interesting research to be done on them in topologies other than the Euclidean one. The reader is reminded that a closed ball with centre c and radius r is the set of points which are at a distance less than or equal to r from c. 

Let Γ S (b; r 1, …, r k ) denote the following two-person zero-sum game played on a convex compact subset S of R n endowed with a topology from a metric. BLUE chooses a closed ball B of radius b and RED closed balls R 1, …, R k of radii r 1, …, r k where all the closed balls have their centres in S. The payoff (to RED) is 1 if S ∩ B ∩ ⋃ i = 1 k R i ≠ ∅ and 0 otherwise.

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 = 1\) and \(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

$$\displaystyle{\vert \vert x - y\vert \vert _{p} = {(\sum _{i=1}^{n}{(\vert x_{ i} - y_{i}\vert )}^{p})}^{1/p}}$$

where \(x = (x_{1},\ldots, x_{n}),\ y = (y_{1},\ldots, y_{n})\) and p ≥ 1. When p = 1, we have the Manhattan, or taxicab, topology whereas the limit as p → ∞ gives the Chebyshev topology which is represented by the distance function \(\vert \vert x - y\vert \vert _{\infty } =\max _{1\leq i\leq n}\vert x_{i} - y_{i}\vert .\) 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 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 2r 1 and the payoff to RED is 1 if BLUE’s point is in RED’s cube and zero otherwise.

Let \(\mathcal{G}\) be a minimum cover of I n by cubes of side 2r 1 then, if RED chooses a member of \(\mathcal{G}\) at random, RED’s expectation is at least \(1/\vert \mathcal{G}\vert .\) Let m be the positive integer such that 2mr 1 < 1 ≤ 2mr 1 + 1, δ satisfy \(0 <\delta < (1 - 2mr_{1})/m\) and \(P(i) = 2i(r_{1}+\delta ).\) If BLUE selects one of the points \(\mathcal{B} =\{ (P(i_{1}),\ldots, P(i_{n})) : i_{j} = 0,1\ldots, m\ \ \mbox{ for}\ \ j = 1,\ldots, n\}\) at random, then

$$\begin{array}{rlrlrl} \vert \vert (P(i),P(j)) - (P(s),P(t))\vert \vert _{1} & =\max \{\vert 2(s - i)(r_{1}+\delta )\vert, \vert 2(t - j)(r_{1}+\delta )\vert \} & & \\ & \geq 2(r_{1}+\delta ). & & \end{array}$$

Thus any closed ball of radius r 1 contains at most one point of \(\mathcal{B}\) so BLUE can restrict RED’s expectation to at most \(1/{(m + 1)}^{2}.\) But, taking S(i, j) to denote the closed ball with centre at the point \(((2i + 1)r_{1},(2j + 1)r_{1} + 1)\) and radius r 1, {S(i, j) : 0 ≤ i, j < m} is a cover of I ×I containing (m + 1)2 members so RED can expect at least \(1/{(m + 1)}^{2}\) and the game is solved.

In addition to problems in the topology given by \(\vert \vert x - y\vert \vert _{p},\) readers who relish the more esoteric problems may like to investigate problems in the topology arising from the distance function \(d(x,y) =\sum _{ i=1}^{n}\vert x_{i} - y{_{i}\vert }^{p}\) where 0 < p < 1; in this topology the closed ball in R 2 is not convex.

9 Conclusions

In this chapter we have investigated only a few of the games proposed by Ruckle in his book but they indicate how the apparently simple games there can provide a challenge in themselves or the foundation for significant generalisations. A common thread running through most of the games is that there are optimal strategies which involve, in some way, coverings of the set the game is played on. Research problems are the lifeblood of any mathematical discipline and it is hoped that it has been shown that Ruckle’s problems are in rude health. However one can also expect the games to evolve in different directions. With the current global financial crisis there is a much greater questioning as to whether projects are affordable so a natural direction would be to incorporate costs into many of Ruckle’s games. For instance the several intervals game has been interpreted as a game in which a defender puts detecting devices (intervals) across a channel in an attempt to detect an infiltrator but little interest has so far been shown in creating scenarios in which the defender has a limited budget and the more efficient the device (the larger the length of the interval) the greater the cost of deployment. Be that as it may, the important aspect of Ruckle’s games from my viewpoint is that they provide one with intellectual fun. His book even includes a game on a Möbius band; definitely a game that people don’t play.