On optimal strategies for searching in presence of errors

We consider the following game between Paul and Carole modeling the problem of searching a discrete domain in presence of errors. Paul searches for an unknown element e in a set S of n elements using w queries. Each query is a partition of S into q parts. Carole is the Oracle who in response to each query points out the part containing e. She is permitted to lie, though not more than k times. We provide a strategy for Paul to determine the unknown element using at most one query more than that necessary against an adversarial Carole. Our result holds for k, the maximum number of lies, nearly doubly logarithmic in w, the total number of queries. Previous results either work for a fixed k and/or use a constant multiplicative factor more queries than that needed. Our work involves the analysis of a related chip game. Our exposition here is in terms of the classical defective coins problem which is that of identifying the single defective coin from amongst n coins using an equal arms balance. The defective coin is heavier than the others, all of which are of equal weight. This problem is the q - way search problem above for q = 3.