Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-11T01:39:37.618Z Has data issue: false hasContentIssue false
  • English
  • Français

A PATH GUESSING GAME WITH WAGERING

Published online by Cambridge University Press:  23 April 2010

Marcus Pendergrass
Marcus Pendergrass
Affiliation:
Department of Mathematics and Computer Science, Hampden-Sydney CollegeE-mail: mpendergrass@hsc.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a two-player game in which the first player (the Guesser) tries to guess, edge-by-edge, the path that second player (the Chooser) takes through a directed graph. At each step, the Guesser makes a wager as to the correctness of her guess and receives a payoff proportional to her wager if she is correct. We derive optimal strategies for both players for various classes of graphs, and we describe the Markov-chain dynamics of the game under optimal play. These results are applied to the infinite-duration Lying Oracle Game, in which the Guesser must use information provided by an unreliable Oracle to predict the outcome of a coin toss.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 24 , Issue 3 , July 2010 , pp. 375 - 396
Copyright
Copyright © Cambridge University Press 2010

References

1.Koether, R. & Osoinach, J. (2005). Outwitting the Lying Oracle. Mathematics Magazine 78: 98–109.CrossRefGoogle Scholar
2.Koether, R., Pendergrass, M. & Osoinach, J. (2009). The Lying Oracle with a biased coin. Journal of Applied Probability 41: 1023–1040.CrossRefGoogle Scholar
3.Lancaster, P. & Tismenetsky, M. (1985). The theory of matrices, 2nd ed.New York: Academic Press.Google Scholar
4.Minc, H. (1988). Nonnegative matrices, New York: Wiley.Google Scholar
5.Ravikumar, B. (2005). Some connections between the lying oracle problem and Ulam's search problem, In Ryan, J., Manyem, P., Sugeng, K. & Miller, M., (eds.). Proceedings of AWOCA 2005, the sixteenth Australasian workshop on combinatorial algorithms, Ballarat, 18–21 September 2005, Bollarat, Australia: University of Ballarat.Google Scholar
6.Rivest, R.L., Mayer, A.R., Kleitman, D., Winklemann, K. & Spencer, J. (1980). Coping with errors in binary search procedures. Journal of Computer and System Sciences 20(2): 396–404.CrossRefGoogle Scholar