How to Poison Your Mother-in-Law, and Other Caching Problems - Search Theory: A Game Theoretic Perspective - page 153

The computation in our proof, which is essentially a double counting argument,
seems to work more or less by coincidence. To check the validity of the Kikuta-
Ruckle conjecture, other sets of parameters need to be tested. The case n < 2 k seems

to be a logical next step.

10.3 Alpern's Caching Games

The Kikuta-Ruckle conjecture presents a combinatorial problem, it is not a game.
It be turned into a game by adding some geometry. Suppose that a hider places n
objects on a graph and that the searcher wins if and only if he retrieves k of these
objects, but he is not allowed to search the entire graph. This is a difficult game to
solve, even for relatively simple graphs. Elementary examples suggest that if the
searcher is allowed to search a large part of the graph, then the hider wants to put all
the objects in a single place, hoping that the searcher won't find them. If the searcher
can only search a small part of the graph, then the hider spreads out the objects, so
that they become out of the searcher's reach. If the game parameter changes to his
advantage, the hider spreads out. This should be compared to the poisoning problem,
in which the poisoner distributes poison over ever more biscuits if the parameter h
changes to his advantage.

Consider the following search game. The hider can place two objects on the line,
at positions x 1 and x 2 . The hider starts from the origin and has to dig a tunnel, so
it takes an effort to place these objects. The hider cannot carry on forever. He can
only dig a tunnel of unit length. This could be a tunnel that goes one way only, from
0to1,orfrom0to

− 1. It can also be a tunnel that goes both ways, from − x to 1 − x

for some 0 1. The hider places the two objects somewhere in the tunnel, and

after he is done, he fills up the tunnels again. One should imagine that the hider is a
squirrel that buries nuts, caching them for later use. Steve Alpern, who first thought
of these games, has coined the term caching game .

< x <

Fig. 10.2 The searcher's dilemma in the caching game

After the hider is done, the searcher looks for these two objects, looks for these
two objects, facing the dilemma that is illustrated in Fig. 10.2 . He is at least as
powerful as the hider and can dig a tunnel of total length h ≥ 1. The searcher wins

if he retrieves both objects, otherwise the hider wins. If h ≥ 2 then the searcher