Csóka, Endre and Lidbetter, Thomas (2016) The solution to an open problem for a caching game. NAVAL RESEARCH LOGISTICS, 63 (1). pp. 23-31. ISSN 0894-069X
|
Text
Cs_ka_et_al_2016_Naval_Research_Logistics_NRL_u.pdf Download (93kB) | Preview |
Abstract
In a caching game introduced by Alpern et al. (Alpern et al., Lecture notes in computer science (2010) 220-233) 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. (Fokkink et al., Search theory: A game theoretic perspective (2014) 85-104). 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 n→∞, the value of the game is asymptotically equal to h/n for h≥n/2. © 2016 Wiley Periodicals, Inc.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Game theory; HIDDEN OBJECTS; Game-theoretic perspectives; Fixed numbers; Discrete location; LOCATION; ALUMINUM; Zero-sum game; SEARCH; caching; accumulation game |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 03 Jan 2017 15:31 |
Last Modified: | 03 Jan 2017 15:31 |
URI: | http://real.mtak.hu/id/eprint/44192 |
Actions (login required)
![]() |
Edit Item |