Detecting errors in searching games

AbstractWe consider two-person searching games handling erroneous information. The Responder selects a number from {1, …, n}, unknown to the Questioner, who has to find it asking yes-no questions. The Responder may lie up to k times during the entire search. In the first game the Questioner wins if he finds the unknown number or if he can prove that some answers were false. In the second game he also needs to determine the number of lies, if they occurred. We study Optimal winning strategies of the Questioner and determine their lengths. The results are compared to those about the minimal length of a k-error detecting code of given size