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

To detect an unknown element x∗x∗ from a finite set S={1,2,…,n}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][n,e,≤k] and formulate it as follows: two players, say Paul and Carole, fix integers k≥1,m>0k≥1,m>0 and e≥0e≥0 beforehand. Paul asks size restricted queries to find x∗x∗: “Is x∗x∗ in AA?”, where A⊆SA⊆S and |A|≤k|A|≤k. Carole answers them with “Yes” or “No” to tell whether x∗x∗ belongs to AA or not. Carole is permitted to lie at most ee times. Paul wins if he finds x∗x∗ within mm rounds; otherwise Carole wins. Our goal is to determine the minimum value of mm to assure Paul to win. Let f(n,e,≤k)=min{m|Paul wins the game  [n,e,≤k]  for the given integer m}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 Lupper(n,1,≤k)Lupper(n,1,≤k) such that f(n,1,≤k)≤Lupper(n,1,≤k)≤f(n,1,≤k)+1f(n,1,≤k)≤Lupper(n,1,≤k)≤f(n,1,≤k)+1, and the exact value of f(n,1,≤k)f(n,1,≤k) for (1) n≤2k+1n≤2k+1 and (2) n≥k2n≥k2 except for the case n=15n=15 and k=3k=3. Moreover, in the end of this paper, we conjecture the exact value of f(n,1,≤k)f(n,1,≤k) for general case and verify its correctness for k=∞k=∞.