On playing “Twenty Questions” with a liar
Aditi Dhagat, Péter Gács, Peter M. Winkler · 1992
We consider a version of the game “Twenty Questions ” played on the set {0, · · · , N − 1} where the player giving answers may lie in her answers. The questioner is allowed Q questions and the responder may lie in up to rQ of the answers, for some fixed and previously known fraction r. Under various models of this game and different question classes, we give precise conditions (i.e. tight bounds on r and, in most cases, optimal bounds on Q) under which the questioner has a winning strategy in the game.