Abstract
The -round Renyi-Ulam pathological liar game with lies on the set is a 2-player perfect information zero sum game. In each round Paul chooses a subset and Carole either assigns 1 lie to each element of or to each element of . Paul wins if after rounds there is at least one element with 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 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 to be the minimum such that Paul can win the -round pathological liar game with lies and initial set , we find and exactly. For fixed we prove that is within an absolute constant (depending only on ) of the sphere bound, ; this is already known to hold for the original Renyi-Ulam liar game due to a result of J. Spencer.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.