An Improved Liar Game Strategy From a Deterministic Random Walk
Robert Ellis
Department of Applied Mathematics
Illinois Institute of Technology
A liar game is a 2-person perfect information played by Paul and Carole in which Paul uses Yes-No questions to find a distinguished element known by Carole, and Carole is allowed to lie a prescribed number of times. Liar games were introduced by Renyi and Ulam, and in an equivalent form, by Berlekamp. In the pathological variant, Paul plays to preserve possibilities for the distinguished element, while Carole plays to disqualify all possibilities. The original and pathological variants are equivalent to adaptive error-correcting and adaptive covering codes, respectively. We introduce a deterministic random walk called the "linear machine," compare its behavior to the simple random walk on the integers, and use the result to improve the best-known strategy for Paul in the pathological variant when the number of lies is a constant fraction of the total number of questions. Included in this talk is an overview of liar games and deterministic random walks.