Abstract
In his 1961 monograph on Game Theory, Melvin Dresher considered a high-low guessing game on N numbers. The game was solved for N ≤ 11 by Selmer Johnson but solutions for higher values of N have never been reported in the literature. In this paper we derive an asymptotic formula for the value of the game as N → ∞ and we present an algorithm that allows us to numerically solve the game for N ≤ 256.
Chapter PDF
Similar content being viewed by others
References
Alpern, S.: Search for point in interval, with high-low feedback. Math. Proc. Cambr. Phil. Soc. 98, 569–578 (1985)
Alpern, S., Gal, S.: The theory of search games and rendezvous. Kluwer Academic Publishers (2003)
Alpern, S., Reyniers, D.: Spatial dispersion as a dynamic coordination problem. Theory and Decision 53(1), 29–59 (2002)
Alpern, S., Snower, D.J.: High-low search in product and labor markets. American Economic Review 78, 356–362 (1988)
Baston, V.J., Bostock, F.A.: A high-low search game on the interval. Math. Proc. Cambr. Phil. Soc. 97, 345–348 (1985)
Crawford, V.P., Heller, H.: Learning How to Cooperate: Optimal Play in Repeated Coordination Games. Econometrica 58, 571–595 (1990)
Dantzig, G., Wolfe, P.: Decomposition principle for linear programs. Operations Res. 8, 101–111 (1960)
Dresher, M.: The Mathematics of Games of Strategy. Dover Publications (1981)
Ferguson, T.S.: Game theory, part II, http://www.math.ucla.edu/~tom/Game_Theory
Gal, S.: A discrete search game. SIAM J. Appl. Math. 27(4), 641–648 (1974)
Garnaev, A.Y.: Search games and other applications of game theory. Springer, Heidelberg (2000)
Gilbert, E.: Games of identification and convergence. SIAM Rev. 4(1), 16–24 (1962)
Gottinger, H.W.: On a problem of optimal search. Z. Operations Res. 21(5), 223–231 (1977)
Grabner, P.: Searching for losers. Random Struct. Algor. 4, 99–110 (1993)
Johnson, S.: A search game. In: Dresher, M., Shapley, L.S., Tucker, A.W. (eds.) Advances in Game Theory. Annals of Mathematics Studies, vol. 52, pp. 39–48 (1964)
Konheim, A.: The number of bisecting strategies for the game (N). SIAM Rev. 4(4), 379–384 (1962)
Pelc, A.: Searching games with errors, fifty years of coping with liers. Theor. Comput. Sci. 270(1-2), 71–109 (2002)
Raghavan, T.E.S.: Zero-sum two-person games. In: Aumann, R.J. (ed.) Handbook of Game Theory with Economic Applications, vol. 2, pp. 735–757. North Holland Publishers (1995)
Reyniers, D.J.: A dynamic model of collective bargaining. Comp. Economics 11(3), 205–220 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fokkink, R., Stassen, M. (2011). An Asymptotic Solution of Dresher’s Guessing Game. In: Baras, J.S., Katz, J., Altman, E. (eds) Decision and Game Theory for Security. GameSec 2011. Lecture Notes in Computer Science, vol 7037. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25280-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-25280-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25279-2
Online ISBN: 978-3-642-25280-8
eBook Packages: Computer ScienceComputer Science (R0)