Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-27T11:46:07.863Z Has data issue: false hasContentIssue false
  • English
  • Français

Search for point in interval, with high–low feedback

Published online by Cambridge University Press:  24 October 2008

Steve Alpern
Steve Alpern
Affiliation:
Department of Mathematics, London School of Economics
Get access Rights & Permissions [Opens in a new window]

Extract

A point H is known to lie on a given bounded interval ℋ. A searcher wishes to locate H by making successive guesses g1, g2, …, each with the knowledge of whether the previous guesses were too high or low, or exactly right. Under these circumstances it is easy to devise a search strategy which ensures the convergence of the gi to H. One such strategy is the ‘halving’ strategy which always guesses the midpoint of the interval on which H is currently known to lie. The problem becomes well defined, and more difficult, if the searcher has to minimize a given cost function which in some way measures the speed of convergence of the gi to H.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 98 , Issue 3 , November 1985 , pp. 569 - 578
Copyright
Copyright © Cambridge Philosophical Society 1985

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.)

References

REFERENCES

[1]Baston, V. J. and Bostock, F. A.. A high-low search game on the unit interval. Math. Proc. Cambridge Philos. Soc. 97 (1985), 345–348.CrossRefGoogle Scholar
[2]Gal, S.. A discrete search game. SIAM J. Appl. Math. 27 (1974), 641–648.CrossRefGoogle Scholar
[3]Gal, S.. A stochastic search game. SIAM J. Appl. Math. 34 (1978), 205–210.CrossRefGoogle Scholar
[4]Gal, S.. Search Games. Vol. 149 in Math, in Science and Engineering (Academic Press, 1980).Google Scholar
[5]Gilbert, E.. Games of identification and convergence. SIAM Rev. 4 (1962), 16–24.CrossRefGoogle Scholar
[6]Glicksberg, I. L.. Minimax theorem for upper and lower semi-continuous payoffs. Rand Corp., Res. Memo. RM-478 (1950).CrossRefGoogle Scholar
[7]Johnson, S. M.. A search game. Advances in Game Theory (Princeton Univ. Press, 1964), 39–48.Google Scholar
[8]Murakami, S.. A dichotomous search with travel cost. J. Oper. Res. Soc, Japan 19 (1976), 245–254.Google Scholar