The solution to an open problem for a caching game

DOI10.1002/NAV.21674MaRDI QIDQ2808489zbMATH OpenOpenAlexFDO

Authors Endre Csóka, Thomas Lidbetter

Publication date 23 May 2016

Published in Naval Research Logistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.08425, http://eprints.lse.ac.uk/64724/1/__lse.ac.uk_storage_LIBRARY_Secondary_libfile_shared_repository_Content_Lidbetter%2C%20T_Lidbetter_Solution%20to%20open%20problem_2015_author.pdf

zbMATH Keywords

zero-sum gamesearch gameaccumulation gamecaching game

Mathematics Subject Classification ID

Search theory (90B40) 2-person games (91A05) Other game-theoretic models (91A40) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: In a caching game introduced by Alpern et al., a Hider who can dig to a total fixed depth normalized to $1$ buries a fixed number of objects among $n$ discrete locations. A Searcher who can dig to a total depth of $h$ searches the locations with the aim of finding all of the hidden objects. If he does so, he wins, otherwise the Hider wins. This zero-sum game is complicated to analyze even for small values of its parameters, and for the case of $2$ hidden objects has been completely solved only when the game is played in up to $3$ locations. For some values of $h$ the solution of the game with $2$ objects hidden in $4$ locations is known, but the solution in the remaining cases was an open question recently highlighted by Fokkink et al. Here we solve the remaining cases of the game with $2$ objects hidden in $4$ locations. We also give some more general results for the game, in particular using a geometrical argument to show that when there are $2$ objects hidden in $n$ locations and $nightarrowinfty$, the value of the game is asymptotically equal to $h/n$ for $hgen/2$.

Recommendations

• A Caching Game with Infinitely Divisible Hidden Material
• All or Nothing Caching Games with Bounded Queries
• Search games with multiple hidden objects
• scientific article; zbMATH DE number 1023202
• Publication:3204351

Cites work

• scientific article; zbMATH DE number 4209901 (Why is no real title available?)
• scientific article; zbMATH DE number 3823533 (Why is no real title available?)
• scientific article; zbMATH DE number 1323112 (Why is no real title available?)
• A generalized inspection game
• A proof of the Kikuta-Ruckle conjecture on cyclic caching of resources
• Accumulation games on graphs
• Accumulation games. I: Noisy search
• Continuous accumulation games in continuous regions
• Continuous accumulation games on discrete locations
• Inspection games in arms control
• New results on a Ruckle problem in discrete games of ambush
• On Ruckle's Conjecture on Accumulation Games
• On a ruckle problem in discrete games of ambush
• Search games and other applications of game theory

Cited in

(5)

• A search problem on a bipartite network
• A proof of the Kikuta-Ruckle conjecture on cyclic caching of resources
• A Caching Game with Infinitely Divisible Hidden Material
• Limits of some combinatorial problems
• All or Nothing Caching Games with Bounded Queries

This page was built for publication: The solution to an open problem for a caching game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808489)