Playing by searching: Two strategies against a linearly bounded liar (Q1603717)

The searching problem is formulated and analyzed as a two-players game of questioner and responder. The strategy of the responder consists in choosing an integer from a given finite set, the strategy of the questioner is represented by a sequence of questions aiming to determine the chosen value. The number of such questions is predetermined and the responder can lie in an exactly limited number of his responses. The rate of lies under which the questioner may win the game is known from the literature. The main result of the referred paper regards the lower bound of the number of queries needed for the questioner to win the game even if the arbitrary membership queries are allowed. Two questioning strategies for the case where only comparison queries are allowed are suggested, as well. The first one improves the upper bound of the number of needed queries, the second strategy, moreover, makes sure that each query can be formulated in constant time.