A Halfliar's game

Ioana Dumitriu, Joel Spencer

Research output: Contribution to journalConference articlepeer-review


In Ulam's game Paul tries to find one of n possibilities with q yes-no questions, while responder Carole is allowed to lie a fixed number k of times. We consider an asymmetric variant in which Carole must say yes when that is the correct answer (whence the halflie). We show that this variation allows Paul to distinguish between roughly 2k as many possibilities as in Ulam's game.

Original languageEnglish (US)
Pages (from-to)353-369
Number of pages17
JournalTheoretical Computer Science
Issue number3
StatePublished - Feb 19 2004
EventAlgorithmic Combinatorial Game Theory - Dagstuhl, Germany
Duration: Feb 1 2002Feb 1 2002


  • Combinatorial game theory
  • Liar games
  • Two-person games

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A Halfliar's game'. Together they form a unique fingerprint.

Cite this