In the "guess-my-number" game, one player (player A) makes guesses at another player's (player B) secret number. All games would follow the following procedure:
-
Player B decides on a number between a known, set limit (for
example, he/she may only choose a number between 1 and 100), this
will become the player's "secret number" (the secret number must be an integer) -
Player A then guesses an initial number
-
Player B responds by (honestly) declaring Player A's response to be
either too high, too low, or correct -
The process repeats, Player A guesses a number based on previous
feedback, and Player B responds, until Player A guesses correctly
Anyways, I've heard that the most efficient method for Player A to guess player B's number would be the binary search, as it takes logarithmic time. First of all, I want to confirm that this is true, but I have another part to my question…
What if the game was modified so that Player B lied on occasion, under the following, known circumstances:
-
Player B only lies one-third of the time
-
Player B does not lie twice in a row
-
Player B only lies when the guess is too high, if the guess is too low or correct, Player B will not lie
- When Player B lies, the lie is guaranteed to be that the guess is too low
Would it still be most efficient to perform a binary search, and if so, how would I modify it to fit this situation more precisely? Alternatively, what other algorithm would be most efficient?
edit: related: Twenty questions against a liar
Best Answer
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.