Paper Info
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 k(d)/((n)(d)) if each treasure is at a different location and k(d)/((n+d-1)(d)) if each location might hide several treasures for large enough n. Our work builds on some results by Csoka 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 k(d)((n+d-1)(d)) for integer k and large enough n.
Year
DOI
Venue
2018
10.1142/S0219198917500232
INTERNATIONAL GAME THEORY REVIEW
Keywords
DocType
Volume
Search theory, Alpern's caching game
Journal
20
Issue
ISSN
Citations 
1
0219-1989
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Dömötör Pálvölgyi120229.14