Three Thresholds for a Liar

Joel Spencer, Peter Winkler

Research output: Contribution to journalArticlepeer-review

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 ¼.

Original languageEnglish (US)
Pages (from-to)81-93
Number of pages13
JournalCombinatorics, Probability and Computing
Volume1
Issue number1
DOIs
StatePublished - Mar 1992

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Three Thresholds for a Liar'. Together they form a unique fingerprint.

Cite this