Title: All or Nothing Caching Games with Bounded Queries,
Abstract: We determine the value of some search games where our goal is to find all of
some hidden treasures using queries of bounded size. The answer to a query is
either empty, in which case we lose, or a location, which contains a treasure.
We prove that if we need to find $d$ treasures at $n$ possible locations with
queries of size at most $k$, then our chance of winning is $\frac{k^d}{\binom
nd}$ if each treasure is at a different location and
$\frac{k^d}{\binom{n+d-1}d}$ if each location might hide several treasures for
large enough $n$. Our work builds on some results by Csóka who has studied a
continuous version of this problem, known as Alpern's Caching Game; we also
prove that the value of Alpern's Caching Game is $\frac{k^d}{\binom{n+d-1}d}$
for integer $k$ and large enough $n$.