All or Nothing Caching Games with Bounded Queries

DOI10.1142/S0219198917500232MaRDI QIDQ4608745zbMATHOpenAlexFDO

Authors Dömötör Pálvölgyi

Publication date 28 March 2018

Published in International Game Theory Review (Search for Journal in Brave)

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

zbMATH Keywords

search theoryAlpern's caching game

Mathematics Subject Classification ID

Search theory (90B40) Applications of game theory (91A80) 2-person games (91A05)

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 $$ if each treasure is at a different location and $$ if each location might hide several treasures for large enough $n$. Our work builds on some results by Cs'oka 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 $$ for integer $k$ and large enough $n$.

Recommendations

• The solution to an open problem for a caching game
• A Caching Game with Infinitely Divisible Hidden Material
• Randomized competitive algorithms for generalized caching
• An \(O(\log k)\)-competitive algorithm for generalized caching
• An \(O(\log k)\)-competitive algorithm for generalized caching
• Competitive algorithms for restricted caching and matroid caching
• Cache me if you can: capacitated selfish replication games
• Near optimality of the discrete persistent access caching algorithm

Cites work

• Accumulation games. I: Noisy search
• How to Poison Your Mother-in-Law, and Other Caching Problems
• On the graph limit question of Vera T. Sós
• The solution to an open problem for a caching game

Cited in

(3)

• A Caching Game with Infinitely Divisible Hidden Material
• Limits of some combinatorial problems
• The solution to an open problem for a caching game

This page was built for publication: All or Nothing Caching Games with Bounded Queries

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