Reducing Guesswork via an Unreliable Oracle

DOI10.1109/TIT.2018.2856190MaRDI QIDQ4559568zbMATH OpenOpenAlexFDO

Authors Amir Burin, Ofer Shayevitz

Publication date 4 December 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Applications of game theory (91A80) Stochastic programming (90C15) Combinatorial probability (60C05)

Abstract: Alice holds an random variable $X$, and Bob is trying to guess its value by asking questions of the form "is $X=x$?". Alice answers truthfully and the game terminates once Bob guesses correctly. Before the game begins, Bob is allowed to reach out to an oracle, Carole, and ask her any yes/no question, i.e., a question of the form "is $XinA$?". Carole is known to lie with a given probability $p$. What should Bob ask Carole if he would like to minimize his expected guessing time? When Carole is always truthful ($p=0$), it is not difficult to check that Bob should order the symbol probabilities in descending order, and ask Carole whether the index of $X$ w.r.t this order is even or odd. We show that this strategy is almost optimal for any lying probability $p$, up to a small additive constant upper bounded by a $1/4$. We discuss a connection to the cutoff rate of the BSC with feedback.

Cited in

(1)

• Logics in Artificial Intelligence

This page was built for publication: Reducing Guesswork via an Unreliable Oracle

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