A caching game with infinitely divisible hidden material

Lidbetter, Thomas (2015) A caching game with infinitely divisible hidden material. SIAM Journal on Control and Optimization, 53 (5). pp. 3040-3056. ISSN 0363-0129
Copy

We consider a caching game in which a unit amount of infinitely divisible material is distributed among $n\geq 2$ locations. A Searcher chooses how to distribute his search effort $r$ about the locations so as to maximize the probability she will find a given minimum amount $\bar{m} =1-m\leq r$ of the material. If the search effort $y_{i}$ invested by the Searcher in a given location $i$ is at least as great as the amount of material $x_{i}$ located there she finds all of it, otherwise the amount she finds is only $y_{i}$. In other words she finds $\min \left\{ x_{i},y_{i}\right\} $ in location $i$. We seek the randomized distribution of search effort that maximizes the probability of success for the Searcher in the worst case, hence we model the problem as a zero-sum win-lose game between the Searcher and a malevolent Hider who wishes to keep more than $m$ of the material. We show that in the case $r=\bar{m}$ the game has a geometric interpretation that for $n=2$ corresponds to a problem posed by W. H. Ruckle in his monograph [Geometric Games and Their Applications, Pitman, Boston, 1983]. We give solutions for the geometric game when $n=3$ for certain values of $m$, and bounds on the value for other values of $m$. In the more general case $r\geq \bar{m}$ we show that for $n=2$ the game reduces to Ruckle's game


picture_as_pdf
subject
Accepted Version

Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads