You haven't defined payoffs for the game – you imply that A wants to minimize the number of guesses, but you say nothing about the payoffs for B. If it's a zero-sum game, B will try to maximize the number of guesses. In that case, a pure strategy of always performing binary search will be suboptimal, since B could anticipate it and always choose numbers that are found last in a binary search.
As a simpler example, consider the same game with numbers from $1$ to $3$. If A uses a pure strategy of always performing binary search, the best strategy for B will be to always choose $1$ or $3$, resulting in a payoff of $2$ guesses (first guess $2$, second guess $1$ or $3$). Now if B follows this strategy and A switches to the strategy of first guessing one of $1$ or $3$ with equal probability and then the other one, the expected number of guesses decreases to $1.5$. Since A can improve her payoff by switching strategies, this can't be the Nash equilibrium.
To find the Nash equilibrium, consider all possible pure strategies for A. These are binary search (first guess $2$, then $1$ or $3$ according to the answer), $123$, $132$, $312$ and $321$. From symmetry, we can expect the last four to have the same probability $p$ at equilibrium. Thus a mixed strategy for $A$ will have the form $(1-4p,p,p,p,p)$. B has three strategies, $1$, $2$ and $3$, and by symmetry we can expect the probability $q$ for $1$ and $3$ to be equal at equilibrium. Thus a mixed strategy for B will have the form $(q,1-2q,q)$.
Here's the payoff matrix for the pure strategies:
$$
\begin{array}{c|ccccc}
&\text{binary}&123&132&312&321\\
\hline
1&2&1&1&2&3\\
2&1&2&3&3&2\\
3&2&3&2&1&1\\
\end{array}
$$
Thus the expected payoff is
$$(1-4p)(1-2q+4q)+p(14q+10(1-2q))=1+2q+6p-14pq\;.$$
Setting the derivatives with respect to $p$ and $q$ to $0$ yields the equilibrium at $p=1/7$, $q=3/7$, with the equilibrium strategies given by $(3/7,1/7,1/7,1/7)$ for A and $(3/7,1/7,3/7)$ for B. That is, A should apply binary search $3$ out of $7$ times, and otherwise any of the other strategies with equal probability, and B should pick $2$ one out of $7$ times and otherwise $1$ or $3$ with equal probability. The resulting expected payoff is $1+6/7+6/7-6/7=13/7$, slightly in A's favour compared to pure binary search.
What a lovely question! I'll concentrate on Variant 1.
You are in fact trying to guess two numbers. In the course of $Q$ questions (which I'll number from 1 to $Q$), you are trying to determine:
- The number, between $0$ and $2^n$. That is $n$ bits of information.
- Whichth answer was a lie. This is a number between $1$ and $Q$, plus $Q+1$ to denote "no lie", which makes $Q+1$ possible values, or $\log_2 (Q+1)$ bits of information.
Since the questions each yield 1 bit of information, the best possible number of questions would seem to be $Q=\lceil n+\log_2 (Q+1) \rceil$. Yes, this is a transcendental equation with $Q$ on both sides; but it does look a lot better than the bound you have proposed.
As for the algorithm itself, what I would do is a straightforward binary search, with the understanding that:
- I am searching not only for the number $x$ but also for the number $f$ of the false answer, where (as before) $f=Q+1$ means that there is no false answer.
- At each stage, my aim is to maximise the information extracted by having as many possibilities coming from a "Yes" answer as from a "No" one. But the possibilities to be counted are not possible values of $x$, as they would be in an ordinary binary search, but possible values of $\langle x,f\rangle$. This gives a different choice of question from the traditional "midpoint of the interval" choice.
In what follows, I'll take $n=5$, so that $0\le x\le 31$. Simple guesswork implies that $Q$ will be 9: that is, 5 to guess $x$, plus a bit over 3 to guess $1\le f\le 10$. ($Q=8$ is not enough, because we need to account for the possibility that there is no lie).
By symmetry, the first question is quite clearly the same as in the traditional binary search: "is $x\le 16$?". Without loss of generality, let's assume that the answer is Yes. In that case, the possibilities are:
- $x\le 16$ and $1\lt f \le Q+1$: $16Q$ possibilities.
- $x\gt 16$ and $f=1$: $16$ possibilities.
…so indeed we have chopped the $32(Q+1)$ possibilities in half.
For the second question, we ask "Is $x\le y$?" for some integer $y$. I'm going to neglect the possibility that $y>16$ because it seems too inefficient. There are two possible answers:
Yes
- $x\le y$ and $2\lt f \le Q+1$: $(Q-1)y$ possibilities.
- $y\lt x\le 16$ and $f=2$: $16-y$ possibilities.
No
- $y\lt x \le 16$ and $2\lt f\le Q+1$: $(16-y)(Q-1)$ possibilities.
- $16\lt x\le 32$ and $f=1$: $16$ possibilities.
- $x\le y$ and $f=2$: $y$ possibilities.
…which adds up to $16(Q+1)$, as expected. But the possibilities are divided between $Qy+16$ for Yes and the rest for No, so the most even balance is achieved when $Qy+16$ is as near as possible to $8(Q+1)$: that is, when $y$ is as close as possible to $y=8\frac{Q-1}{Q}$.
With $Q=9$, the target value is $8\times\frac{8}{9}$, which is $7\frac{1}{9}$. So the second question needs to be not "Is $x\le 8$?", as a naive binary search would ask, but "Is $x\le 7$?".
The overall algorithm before asking each question is therefore:
- Note all the $\langle x,f\rangle$ pairs that are still possible given the questions and answers so far.
- Go through all possible values of $y$.
- For each value of $y$, consider how many $\langle x,f\rangle$ pairs match the answer "Yes" to "Is $x\le y$?" and how many match "No".
- Pick the value of $y$ for which the "Yes" and "No" counts are closest together, and ask the question using that value.
Although I assert that a binary search in $\langle x,f\rangle$ space is the best possible algorithm, and although I have given an approximate value for $Q$, I have not actually proved anything.
Best Answer
There is a fairly simple strategy which requires (1 + ε)log(n) + 1/ε + O(1) queries, for any constant ε > 0. I illustrate this strategy below.
First, I ask you whether or not X, the secret number, is n/2. Without loss of generality, suppose you answer "less". I learn nothing at first, because you may be lying; but for the moment I give you the benefit of the doubt.
I next ask you whether X is n/4. If you say "less", I don't know whether or not 0 < X < n/4, but I do know that 0 < X < n/2, because you can't lie twice. Similarly, if I go about a normal binary search, so long as you continue to answer "less", I know that your answer to the preceding query was honest. So we may reduce to the case where you say "more" to my query of whether X is n/4.
If I continue to take you at your word, persue a binary search, and enquire about whether X is 3n/8, you may say either "more" or "less". If you say "more", then I don't know whether X > n/2, but I do know that X > n/4, again because you can't lie twice. So again so long as you continue to answer "more" in my normal binary search, I know that your answer to the preceding query was honest.
More generally: if I consistently guess under the hypothesis that you are being honest, in any "monotonic" sequence of responses, I know that all but (possibly) the last of them are honest. So it might seem as though the worst case scenario is where your responses alternate a lot, as would occur for instance if you had chosen something like X = ⌊ n/3 ⌋. But in the alternating case too, I can be confident of the honesty of some of your answers:
More generally: not only do I know that monotonic subsequences of answers are mostly honest, I know that any time that you answer "more" or "less", your previous answer of the same kind was also honest. So in fact I should be most suspicious, when I encounter long monotonic subsequences in your answers, that the answer previous to that monotonic subsequence was a lie.
What I need is a strategy that will tell me when to revisit an old question, depending on how large n is. Ideally, revisiting old questions would require very little overhead. If I encounter a monotonic sequence of f(n) responses, I revisit the last question before that monotonic sequence started.
If I do a double-check like this every time I encounter a monotonic sequence of length r, I will in the worst case query you about (r+1)log(n)/r = (1 + 1/r)log(n) times. If I catch you in a lie, I will have only "wasted" r queries, and my strategy afterwards can be just a simple binary search without double-checks; so your optimal strategy for maximizing the number of queries I make is actually not to lie at all, or to save your lie for nearly the end of the game to cost me about r additional queries. Here r can be an arbitrarily large integer; thus for any ε, I can achieve a query rate of (1 + ε)log(n) + 1/ε + O(1) by setting r > 1/ε.
Bonus problem #1. Without too much extra work, I think you can improve this to a strategy requiring only log(n) + O(log log(n)) queries, but I'm too lazy to work out the details right now.
Bonus problem #2. Generalize this strategy to the regime where you are allowed to lie to me some fixed number of times L > 0.