Minimum number of queries for an adaptive liar search game with small sets

摘要

To detect an unknown element x* from a finite set S = {1, 2, ..., n} by asking group-testing queries is a classical combinatorial optimization problem. We consider a variation of the problem, what we call the liar search game with small sets [n, e, ≤ k] and formulate it as follows: two players, say Paul and Carole, fix integers k ≥ 1, m > 0 and e ≥ 0 beforehand. Paul asks size restricted queries to find x*: "Is x* in A?", where A ? S and ≤ k. Carole answers them with "Yes" or "No" to tell whether x* belongs to A or not. Carole is permitted to lie at most e times. Paul wins ifhe finds x* within m rounds; otherwise Carole wins. Our goal is to determine the minimum value of m to assure Paul to win. Let f(n, e, ≤ k) = min{m|Paul wins the game [n, e, ≤ k] for the given integer m}. In this paper, we consider the sequential algorithms of the above game and obtain a tight bound L_(upper)(n, 1, ≤ k) such that f(n, 1, ≤ k) ≤ L_(upper)(n, 1, ≤ k) ≤ f(n, 1, ≤ k) + 1, and the exact value off(n, 1, ≤ k) for (1) n ≤ 2k+ 1 and (2) n ≥ k~2 except for the case n = 15 and k = 3. Moreover, in the end of this paper, we conjecture the exact value of f (n, 1, ≤ k) for general case and verify its correctness for k = ∞.