Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-12-03T19:09:30.406Z Has data issue: false hasContentIssue false
  • English
  • Français

A hide–search game

Published online by Cambridge University Press:  14 July 2016

Eduardo J. Subelman
Eduardo J. Subelman*
Affiliation:
University of California, Los Angeles
*
∗Postal address: Department of System Science, School of Engineering and Applied Science, University of California, Los Angeles, CA 90024, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a game in which one player hides a ball in one of n boxes and the other player is allowed to search for it. There are known probabilities that the searcher will overlook the ball if he searches the correct box. The hider wishes to minimize and the searcher to maximize the probability that the ball will be found in m or fewer searches. We exhibit a procedure which allows efficient computation of optimal strategies for both players without solving the game as a linear program. The results are extended to a non-zero-sum game where the searcher's objective is to minimize the expected time until the ball is found.

Keywords

SEARCH THEORYOPTIMAL HIDINGTWO-PERSON GAMES
Type
Research Papers
Information
Journal of Applied Probability , Volume 18 , Issue 3 , September 1981 , pp. 628 - 640
Copyright
Copyright © Applied Probability Trust 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research partially supported by the Office of Naval Research under contract number N00014–78–C–0428.

References

[1] Beck, A. and Newman, D. J. (1970) Yet more on the linear search problem. Israel J. Math. 8, 419–429.CrossRefGoogle Scholar
[2] Bram, J. (1963) A 2-player N-region search game. Report OIRM 31, Center for Naval Analyses. (NTIS No. AD402914.) Google Scholar
[3] Fox, B. L. (1967) Discrete optimization via marginal analysis. Management Sci. 13, 210–216.CrossRefGoogle Scholar
[4] Gal, S. (1974) Minimax solutions for linear search problems. SIAM J. Appl. Math. 27, 17–30.CrossRefGoogle Scholar
[5] Gal, S. and Chazan, D. (1976) On the optimality of the exponential functions for some minimax problems. SIAM J. Appl. Math. 30, 324–348.CrossRefGoogle Scholar
[6] Gittins, J. C. and Roberts, D. M. (1979) The search for an intelligent invader concealed in an arbitrary number of regions. Naval Res. Logist. Quart. 26, 651–666.CrossRefGoogle Scholar
[7] Murty, K. G. (1976) Linear and Combinatorial Programming. Wiley, New York.Google Scholar
[8] Norris, R. C. (1962) Studies in search for a conscious evader. MIT Lincoln Laboratory Technical Report No. 279.Google Scholar
[9] Roberts, D. M. and Gittins, J. C. (1978) The search for an intelligent invader: strategies for searcher and evader in the two-region problem. Naval Res. Logist. Quart. 25, 95–106.CrossRefGoogle Scholar
[10] Stone, L. D. (1975) Theory of Optimal Search. Academic Press, New York.Google Scholar