Playing by searching: two strategies against a linearly bounded liar
The problem of searching in the presence of errors is modeled as a game between a questioner and a responder. The responder chooses an integer x is an element of {1,...,n}, and the questioner has to determine x by asking a predetermined number of queries. The responder can lie at his pleasure, provided that at the end of the game the fraction of lies does not exceed a certain constant r. It is known that the questioner may win the game if and only if r < (1)/(3). Under the latter hypothesis, we state a lower bound on the number Q(n, r) of queries needed by the questioner to win the game, even if he is allowed for arbitrary membership queries. Next, we analyze two questioning strategies for the model where only comparison queries are allowed. The first strategy improves on the known upper bound on Q(n, r); the second one achieves the same value of Q(n, r), but makes also sure that each query can be formulated in constant time. (C) 2002 Elsevier Science B.V. All rights reserved.
comparison query searching game error rate