A basic combinatorial interpretation of Shannon's entropy function is via the "20 questions" game. This cooperative game is played by two players, Alice and Bob: Alice picks a distribution π over the numbers {1, . . . , n}, and announces it to Bob. She then chooses a number x according to π , and Bob attempts to identify x using as few Yes/No queries as possible, on average. An optimal strategy for the "20 questions" game is given by a Hu man code for π : Bob's questions reveal the codeword for x bit by bit. This strategy nds x using fewer than H (π ) + 1 questions on average. However, the questions asked by Bob could be arbitrary. In this paper, we investigate the following question: Are there restricted sets of questions that match the performance of Hu man codes, either exactly or approximately? Our rst main result shows that for every distribution π , Bob has a strategy that uses only questions of the form "x < c?" and "x = c?", and uncovers x using at most H (π )+1 questions on average, matching the performance of Hu man codes in this sense. We also give a natural set of O (rn 1/r ) questions that achieve a performance of at most H (π ) + r , and show that Ω(rn 1/r ) questions are required to achieve such a guarantee. Our second main result gives a set Q of 1.25 n+o (n) questions such that for every distribution π , Bob can implement an optimal strategy for π using only questions from Q. We also show that 1.25 n−o (n) questions are needed, for in nitely many n. If we allow a small slack of r over the optimal strategy, then roughly (rn) Θ(1/r ) questions are necessary and su cient.
Dagan et al. REF give a strategy, using only comparison and equality queries, which asks at most H(µ) + 1 questions on average.
Twenty (simple) questions
STOC 2017
Mathematics Computer Science