Optimal sets of questions for Twenty Questions

2021/06/03 by Filmus, Yuval, Idan Mehalel, Mehalel, Idan
Computer Science · Engineering · #Algorithms and Data Compression #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Water Systems and Optimization

paper · pdf · doi:10.48550/arxiv.2106.01737

openalex publication_date 2021/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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ⁿ 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).

Related

• Twenty (simple) questions
• Twenty Questions Games Always End With Yes
• The entropy of lies: playing twenty questions with a liar
• Algorithm to Prove Formulas for the Expected Number of Questions in Mastermind Games
• Discussion of Twenty Questions Problem