search
Twenty questions with a liar
It is a problem old as parlor games but sharpened to a blade: identify a hidden object using only yes/no questions, when up to two of the answers you receive may be lies — and you don't know which. Each honest answer halves the possibilities, but each possible lie forces you to keep redundancy in reserve, so the liar's mere possibility inflates how many questions you need. Find the optimal questioning strategy and pin down its exact limits — how many questions are necessary and sufficient to defeat two lies. Get it wrong and you trust a corrupted answer and finish confidently wrong, or hedge so heavily you waste questions — this is the pure form of extracting reliable information per query from an adversarial channel.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
This is Erdos's problem in the most literal sense available in this roster: Erdos and Renyi's 1963 paper 'On two problems of information theory' analyzes searching with lies, founding the tradition the puzzle names (Renyi's and Ulam's versions interweave with it). The solution's two halves are both signature Erdos: the lower bound is a counting/sphere-packing argument — each candidate must remain distinguishable under every pattern of up to two lies, inflating the required question volume — and the upper bound is an exactly balanced adaptive strategy of the weight-function kind, the sort of potential argument he and his collaborators (Spencer, whose two-lie 'Ulam' analysis is squarely in the Erdos school) wielded constantly. Combinatorial games, exact thresholds, adversary arguments: his entire method, aimed at a problem he personally helped originate. The problem's own Win line names him first, correctly.
This problem sits squarely on Yao's home ground. Query complexity — how many questions of a restricted form are necessary and sufficient — is the exact genre of his decision-tree work, and Yao's minimax principle (1977) is the canonical tool for proving the lower bound: exhibit a hard distribution over hidden objects and lie patterns, and every deterministic questioner is forced to spend the extra questions. His communication-complexity framework (1979) formalizes information-per-query against an adversarial partner, which is this problem stripped to essentials. The upper bound needs a constructive strategy — weight functions tracking candidates at each lie level, in the Berlekamp tradition — and Yao's combinatorial fluency covers that too. He postdates the Erdos-Renyi origins of the problem, meaning the literature is available to him. Few carriers fit a problem this precisely.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
71 figures are scored on this problem. Draw it in a battle to see where you land.