The Renyi-Ulam pathological liar game with a fixed number of lies

preprint2010arXivOpen access

Abstract

The qq-round Renyi-Ulam pathological liar game with kk lies on the set [n]:={1,...,n}[n]:=\{1,...,n\} is a 2-player perfect information zero sum game. In each round Paul chooses a subset A⊆[n]A\subseteq [n] and Carole either assigns 1 lie to each element of AA or to each element of [n]∖A[n]\setminus A. Paul wins if after qq rounds there is at least one element with kk or fewer lies. The game is dual to the original Renyi-Ulam liar game for which the winning condition is that at most one element has kk or fewer lies. We prove the existence of a winning strategy for Paul to the existence of a covering of the discrete hypercube with certain relaxed Hamming balls. Defining Fk∗(q)F^*_k(q) to be the minimum nn such that Paul can win the qq-round pathological liar game with kk lies and initial set [n][n], we find F1∗(q)F^*_1(q) and F2∗(q)F^*_2(q) exactly. For fixed kk we prove that Fk∗(q)F_k^*(q) is within an absolute constant (depending only on kk) of the sphere bound, 2q/(q≤k)2^q/\binom{q}{\leq k}; this is already known to hold for the original Renyi-Ulam liar game due to a result of J. Spencer.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.