The solution to an open problem for a caching game

DOI10.1002/NAV.21674zbMATH Open1337.91026arXiv1507.08425OpenAlexW2963974074MaRDI QIDQ2808489FDOQ2808489

Authors: Endre Csóka, Thomas Lidbetter 

Publication date: 23 May 2016

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

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$.

Full work available at URL: https://arxiv.org/abs/1507.08425

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

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)

Cites Work

• Title not available (Why is that?)
• Search games and other applications of game theory
• Inspection games in arms control
• A generalized inspection game
• Accumulation games. I: Noisy search
• On Ruckle's Conjecture on Accumulation Games
• A proof of the Kikuta-Ruckle conjecture on cyclic caching of resources
• Accumulation games on graphs
• Continuous accumulation games in continuous regions
• New results on a Ruckle problem in discrete games of ambush
• Title not available (Why is that?)
• On a ruckle problem in discrete games of ambush
• Continuous accumulation games on discrete locations
• Title not available (Why is that?)

Cited In (4)

• 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
• 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)