The interval liar game

with Benjamin Doerr, Johannes Lengler. ISAAC 2006, Electr. Notes Discr. Math. 28 (2007).

PDF

abstract

We regard the problem of communication in the presence of faulty transmissions. In contrast to the classical works in this area, we assume some structure on the times when the faults occur. More realistic seems the “burst error model”, in which all faults occur in some small time interval. Like previous work, our problem can best be modelled as a two-player perfect information game, in which one player (“Paul”) has to guess a number $x$ from $\{1, \ldots, n\}$ using Yes/No-questions, which the second player (“Carole”) has to answer truthfully apart from few lies. In our setting, all lies have to be in a consecutive set of $k$ rounds. We show that (for big $n$) Paul needs roughly $\log n+\log \log n+k$ rounds to determine the number, which is only $k$ more than the case of just one single lie.