Abstract | ||
---|---|---|
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 Huffman code for Ï: Bobâs questions reveal the codeword for x bit by bit. This strategy finds 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 Huffman codes, either exactly or approximately?* Our first 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 Huffman codes in this sense. We also give a natural set of O(rn1/r) questions that achieve a performance of at most H(Ï)+r, and show that Ω(rn1/r) questions are required to achieve such a guarantee. Our second main result gives a set Q of 1.25n+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.25nâo(n) questions are needed, for infinitely many n. If we allow a small slack of r over the optimal strategy, then roughly (rn)Î(1/r) questions are necessary and sufficient. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1145/3055399.3055422 | STOC |
Keywords | DocType | Volume |
combinatorial search theory,twenty questions game,binary decision tree,information theory,redundancy | Conference | abs/1611.01655 |
ISSN | Citations | PageRank |
0737-8017 | 0 | 0.34 |
References | Authors | |
23 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuval Dagan | 1 | 0 | 0.68 |
Yuval Filmus | 2 | 275 | 27.33 |
Ariel Gabizon | 3 | 156 | 13.97 |
Shay Moran | 4 | 63 | 27.30 |