How to play the one-lie Renyi-Ulam game Academic Article

abstract

• The one-lie Rnyi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n] {colon equals} {1, ..., n}. In each round Paul chooses a subset A [n] and Carole either assigns one lie to each element of A or to each element of [n] {set minus} A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q, n and for both games. 2007 Elsevier B.V. All rights reserved.

authors

• Yan, Catherine

published proceedings

• DISCRETE MATHEMATICS

author list (cited authors)

• Ellis, R. B., Ponomarenko, V., & Yan, C. H.

citation count

• 1

complete list of authors

• Ellis, Robert B||Ponomarenko, Vadim||Yan, Catherine H

publication date

• January 2008

publisher

• Elsevier  Publisher

published in

• Discrete Mathematics  Journal

keywords

• Pathological Liar Game
• Renyi-ulam Game
• Searching With Lies

Digital Object Identifier (DOI)

• 10.1016/j.disc.2007.09.052

start page

• 5805

end page

• 5808

volume

• 308

issue

• 23

URL

• http://dx.doi.org/10.1016/j.disc.2007.09.052