A path guessing game with wagering

DOI10.1017/S0269964810000033MaRDI QIDQ3585148zbMATH OpenOpenAlexFDO

Authors Marcus Pendergrass

Publication date 19 August 2010

Published in Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.2196

zbMATH Keywords

game on a directed graphLying Oracle GameMarkov-chain dynamics of the gameUlam's Liar Game

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) 2-person games (91A05) Probabilistic games; gambling (91A60)

Abstract: 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 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.

Recommendations

• The lying oracle game with a biased coin
• The infinite duration lying oracle game
• Guessing Games
• How to play the one-lie Rényi-Ulam game
• Optimal strategies against a liar

Cites work

• scientific article; zbMATH DE number 3889718 (Why is no real title available?)
• Coping with errors in binary search procedures
• Outwitting the lying oracle
• The lying oracle game with a biased coin

Cited in

(3)

• The infinite duration lying oracle game
• Outwitting the lying oracle
• The lying oracle game with a biased coin

This page was built for publication: A path guessing game with wagering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3585148)