A Halfliar's game

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 2 k as many possibilities as in Ulam's game.

Authors

• Ioana Dumitriu
• Joel Spencer

Keywords

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