Optimal strategies against a liar (Q1978508): Difference between revisions

We consider the following scenario: There are two individuals, say \(Q\) (Questioner) and \(R\) (Responder), involved in a search game. Player \(R\) chooses a number, say \(x\), from the set \(S={1,\dots,M}\). Player \(Q\) has to find out \(x\) by asking questions of type: ``which one of the sets \(A_{1},A_{2},\dots,A_{q}\), does \(x\) belong to?'', where the sets \(A_{1},\dots,A_{q}\) constitute a partition of \(S\). Player \(R\) answers ``\(i\)'' to indicate that the number \(x\) belongs to \(A_{i}\). We are interested in the least number of questions player \(Q\) has to ask in order to be always able to correctly guess the number \(x\), provided that \(R\) can lie at most \(e\) times. The case \(e=0\) obviously reduces to the classical \(q\)-ary search, and the necessary number of questions is [\(\log_{q} M]\). The case \(q=2\) and \(e\geqslant 1\) has been widely studied, and it is generally referred to as Ulam's game. In this paper we consider the general case of arbitrary \(q\geqslant 2\). Under the assumption that player \(R\) is allowed to lie at most twice throughout the game, we determine the minimum number of questions \(Q\) needs to ask in order to successfully search for \(x\) in a set of cardinality \(M=q^{i}\), for any \(i\geqslant 1\). As a corollary, we obtain a counterexample to a recently proposed conjecture of \textit{M. Aigner} [J. Comb. Theory, Ser. A 74, 43-56 (1995; Zbl 0846.90149)] for the case of an arbitrary number of lies. We also exactly solve the problem when player \(R\) is allowed to lie a fixed but otherwise arbitrary number of times \(e\), and \(M=q^{i}\), with \(i\) not too large with respect to \(q\). For the general case of arbitrary \(M\), we give fairly tight upper and lower bounds on the number of the necessary questions.