Optimal sets of questions for Twenty Questions
share
In the distributional Twenty Questions game, Bob chooses a number x from 1 to n according to a distribution μ, and Alice (who knows μ) attempts to identify x using Yes/No questions, which Bob answers truthfully. Her goal is to minimize the expected number of questions. The optimal strategy for the Twenty Questions game corresponds to a Huffman code for μ, yet this strategy could potentially uses all 2^n possible questions. Dagan et al. constructed a set of 1.25^n+o(n) questions which suffice to construct an optimal strategy for all μ, and showed that this number is optimal (up to sub-exponential factors) for infinitely many n. We determine the optimal size of such a set of questions for all n (up to sub-exponential factors), answering an open question of Dagan et al. In addition, we generalize the results of Dagan et al. to the d-ary setting, obtaining similar results with 1.25 replaced by 1 + (d-1)/d^d/(d-1).
READ FULL TEXT