# Twenty (simple) questions

arXiv: https://arxiv.org/abs/1611.01655 · HTML: https://mlsanity.com/paper/1611.01655/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2016.

## Built on by (most cited first, 1 of 1)

- [GuessingGame: Measuring the Informativeness of Open-Ended Questions in Large Language Models](https://mlsanity.com/paper/2509.19593/) (2025)

## Abstract (arXiv)

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,ldots,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 Omega(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)Theta(1/r) questions are necessary and sufficient.