The Renyi-Ulam pathological liar game with a fixed number of lies Academic Article uri icon

abstract

  • The q-round Rnyi-Ulam pathological liar game with k lies on the set [n] := {1,..., n} is a 2-player perfect information zero sum game. In each round Paul chooses a subset A [n] and Carole either assigns 1 lie to each element of A or to each element of [n]A. Paul wins if after q rounds there is at least one element with k or fewer lies. The game is dual to the original Rnyi-Ulam liar game for which the winning condition is that at most one element has k or fewer lies. Define Fk*(q) to be the minimum n such that Paul can win the q-round pathological liar game with k lies and initial set [n]. For fixed k we prove that Fk* (q) is within an absolute constant (depending only on k) of the sphere bound, 2q/(kq); this is already known to hold for the original Rnyi-Ulam liar game due to a result of J. Spencer. 2005 Elsevier Inc. All rights reserved.

published proceedings

  • JOURNAL OF COMBINATORIAL THEORY SERIES A

author list (cited authors)

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

citation count

  • 5

complete list of authors

  • Ellis, RB||Ponomarenko, V||Yan, CH

publication date

  • January 2005