A path guessing game with wagering

DOI10.1017/S0269964810000033zbMATH Open1201.91004arXiv0907.2196OpenAlexW2169325460MaRDI QIDQ3585148FDOQ3585148

Authors: Marcus Pendergrass 

Publication date: 19 August 2010

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

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.

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

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

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)

Cites Work

• Coping with errors in binary search procedures
• Title not available (Why is that?)
• 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)