M.Sc Student Dagan Yuval Twenty Questions Game Using Restricted Sets of Questions Department of Computer Science Dr. Yuval Filmus

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 \pi over the numbers \{1,\ldots,n\}, and announces it to Bob. She then chooses a number x according to \pi, 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
\pi: Bob's questions reveal the codeword for x bit by bit. This strategy finds x using fewer than H(\pi) 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
\pi, Bob has a strategy that uses only questions of the form "x < c?" and "x = c?", and uncovers x using at most H(\pi) questions on average, matching the performance of Huffman codes in this sense. We also give a natural set of O(rn^{1/r})questions that achieve a performance of at most H(\pi), and show that \Omega(rn^{1/r}) questions are required to achieve such a guarantee.
Our second main result gives a set
\mathcal{Q} of 1.25^{n(n)} questions such that for every distribution \pi, Bob can implement an optimal strategy for \pi using only questions from \mathcal{Q}. We also show that 1.25^{n-o(n)} questions are needed, for infinitely many n. If we allow a small slack of r over the optimal strategy, then roughly (rn)^{\Theta(1/r)} questions are necessary and sufficient.