Combinatorics, Probability and Computing

Research Article

Three Thresholds for a Liar

Joel Spencera1 and Peter Winklera2

a1 NYU-Courant Institute, 251 Mercer St., New York, NY 10012

a2 Bellcore, 445 South St., Morristown, NJ 07962-1910

Abstract

Motivated by the problem of making correct computations from partly false information, we study a corruption of the classic game “Twenty Questions” in which the player who answers the yes-or-no questions is permitted to lie up to a fixed fraction r of the time. The other player is allowed q arbitrary questions with which to try to determine, with certainty, which of n objects his opponent has in mind; he “wins” if he can always do so, and “wins quickly” if he can do so using only O(log n) questions.

It turns out that there is a threshold value for r below which the querier can win quickly, and above which he cannot win at all. However, the threshold value varies according to the precise rules of the game. Our “three thresholds theorem” says that when the answerer is forbidden at any point to have answered more than a fraction r of the questions incorrectly, then the threshold value is r = ½; when the requirement is merely that the total number of lies cannot exceed rq, the threshold is ⅓; and finally if the answerer gets to see all the questions before answering, the threshold drops to ¼.

(Received September 17 1991)

(Revised November 08 1991)

Footnotes

† Author's net address: spencer@cs.nyu.edu

‡ Author's net address: pw@bellcore.com