The Interval Liar Game

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 model that 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, ..., 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 large n, Paul needs roughly log n + log log 2 n + k rounds to determine the number, which is only k more than the case of just one single lie. Our main theorem (1.1) gives precise upper and lower bounds which differ only by a (small) constant.