Randomized Binary and Tree Search under Pressure

We study a generalized binary search problem on the line and general trees. On the line (e. g. , a sorted array), binary search finds a target node in O (n) queries in the worst case, where n is the number of nodes. In situations with limited budget or time, we might only be able to perform a few queries, possibly sub-logarithmic many. In this case, it is impossible to guarantee that the target will be found regardless of its position. Our main result is the construction of a randomized strategy that maximizes the minimum (over the target position) probability of finding the target. Such a strategy provides a natural solution where there is no apriori (stochastic) information of the target's position. As with regular binary search, we can find and run the strategy in O (n) time (and using only O (n) random bits). Our construction is obtained by reinterpreting the problem as a two-player (seeker and hider) zero-sum game and exploiting an underlying number theoretical structure. Furthermore, we generalize the setting to study a search game on trees. In this case, a query returns the edge's endpoint closest to the target. Again, when the number of queries is bounded by some given k, we quantify a the-less-queries-the-better approach by defining a seeker's profit p depending on the number of queries needed to locate the hider. For the linear programming formulation of the corresponding zero-sum game, we show that computing the best response for the hider (i. e. , the separation problem of the underlying dual LP) can be done in time O (n² 2^2k), where n is the size of the tree. This result allows to compute a Nash equilibrium in polynomial time whenever k=O (n). In contrast, computing the best response for the hider is NP-hard.