Published online by Cambridge University Press: 01 July 2016
The lying oracle problem is a problem of finding the optimal strategies in a two-person game where an oracle predicts the outcomes of coin flips and a player bets on the outcomes. The oracle announces whether the coin will land heads or tails, but may at times lie. We analyze the variant of the game which uses a biased coin, where the probability p that the coin lands heads is common knowledge. We determine optimal strategies for both the oracle and player, and we give an explicit expression for the expected payoff to the player when the coin is flipped n times and the oracle may lie at most k times.