Minimum Guesswork with an Unreliable Oracle
share
We study a guessing game where Alice holds a discrete random variable X, and Bob tries to sequentially guess its value. Before the game begins, Bob can obtain side-information about X by asking an oracle, Carole, any binary question of his choosing. Carole's answer is however unreliable, and is incorrect with probability ϵ. We show that Bob should always ask Carole whether the index of X is odd or even with respect to a descending order of probabilities -- this question simultaneously minimizes all the guessing moments for any value of ϵ. In particular, this result settles a conjecture of Burin and Shayevitz. We further consider a more general setup where Bob can ask a multiple-choice M-ary question, and then observe Carole's answer through a noisy channel. When the channel is completely symmetric, i.e., when Carole decides whether to lie regardless of Bob's question and has no preference when she lies, a similar question about the ordered index of X (modulo M) is optimal. Interestingly however, the problem of testing whether a given question is optimal appears to be generally difficult in other symmetric channels. We provide supporting evidence for this difficulty, by showing that a core property required in our proofs becomes NP-hard to test in the general M-ary case. We establish this hardness result via a reduction from the problem of testing whether a system of modular difference disequations has a solution, which we prove to be NP-hard for M≥ 3.
READ FULL TEXT