A Halfliar's game

Ioana Dumitriu; Joel Spencer

doi:10.1016/j.tcs.2002.09.001

A Halfliar's game

Ioana Dumitriu, Joel Spencer

Research output: Contribution to journal › Conference article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	353-369
Number of pages	17
Journal	Theoretical Computer Science
Volume	313
Issue number	3
DOIs	https://doi.org/10.1016/j.tcs.2002.09.001
State	Published - Feb 19 2004
Event	Algorithmic Combinatorial Game Theory - Dagstuhl, Germany Duration: Feb 1 2002 → Feb 1 2002

Keywords

Combinatorial game theory
Liar games
Two-person games

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2002.09.001

Cite this

@article{9fce4f774a4c4f74971e884525fdc235,

title = "A Halfliar's game",

abstract = "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.",

keywords = "Combinatorial game theory, Liar games, Two-person games",

author = "Ioana Dumitriu and Joel Spencer",

year = "2004",

month = feb,

day = "19",

doi = "10.1016/j.tcs.2002.09.001",

language = "English (US)",

volume = "313",

pages = "353--369",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "3",

note = "Algorithmic Combinatorial Game Theory ; Conference date: 01-02-2002 Through 01-02-2002",

}

TY - JOUR

T1 - A Halfliar's game

AU - Dumitriu, Ioana

AU - Spencer, Joel

PY - 2004/2/19

Y1 - 2004/2/19

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

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

KW - Combinatorial game theory

KW - Liar games

KW - Two-person games

UR - http://www.scopus.com/inward/record.url?scp=0842329859&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0842329859&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2002.09.001

DO - 10.1016/j.tcs.2002.09.001

M3 - Conference article

AN - SCOPUS:0842329859

SN - 0304-3975

VL - 313

SP - 353

EP - 369

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

T2 - Algorithmic Combinatorial Game Theory

Y2 - 1 February 2002 through 1 February 2002

ER -

A Halfliar's game

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this