All or Nothing Caching Games with Bounded Queries

Dömötör Pálvölgyi ()
Additional contact information
Dömötör Pálvölgyi: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, UK

International Game Theory Review (IGTR), 2018, vol. 20, issue 01, 1-9

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 kd n d if each treasure is at a different location and kd 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 kd n+d−1 d for integer k and large enough n.

Keywords: Search theory; Alpern’s caching game (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198917500232
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:igtrxx:v:20:y:2018:i:01:n:s0219198917500232

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198917500232

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().