Optimal Sets of Questions for Twenty Questions

DOI10.1137/21M1424494MaRDI QIDQ6141868zbMATH OpenOpenAlexWikidataFDO

Authors Yuval Filmus

Publication date 23 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.01737

zbMATH Keywords

information theorygamescombinatorial search

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Theory of error-correcting codes and error-detecting codes (94Bxx)

Abstract: In the distributional Twenty Questions game, Bob chooses a number $x$ from $1$ to $n$ according to a distribution $mu$, and Alice (who knows $mu$) 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 $mu$, 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 $mu$, 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)}$.

Cites work

• scientific article; zbMATH DE number 4057247 (Why is no real title available?)
• A Mathematical Theory of Communication
• A Method for the Construction of Minimum-Redundancy Codes
• An Optimal Search Procedure
• Chains, antichains, and fibres
• Elements of Information Theory
• Information Theory and Statistics: A Tutorial
• Information theory, combinatorics, and search theory. In memory of Rudolf Ahlswede
• Maximal Chains and Antichains in Boolean Lattices
• Minimum sized fibres in distributive lattices
• Twenty (short) questions
• Twenty (simple) questions

This page was built for publication: Optimal Sets of Questions for Twenty Questions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6141868)