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

  • 1
    $\begingroup$ The numbers are required to be integers, I hope. $\endgroup$ Jan 12, 2012 at 0:35
  • $\begingroup$ @HenningMakholm Yes, the numbers must be integers $\endgroup$
    – Bob
    Jan 12, 2012 at 0:36
  • 1
    $\begingroup$ The question you linked to in your edit has the same problem that it never says what the objectives of A and B are. It does say "at most" several times, which seems to imply that A is trying to minimize the number of guesses in the worst case (so we don't need to know anything about how B acts). It would help if you could clarify whether this is also the case for your game, and if not, what the objectives are. As I stated in my answer, it's based on the premise that A is trying to minimize the number of guesses and B is trying to maximize it. $\endgroup$
    – joriki
    Jan 12, 2012 at 2:09

2 Answers 2


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


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.

  • $\begingroup$ Wow! What a thorough response! $\endgroup$ Jan 12, 2012 at 3:31

I would like to say that Joriki's approach is the right one, but that the answer he has given in the n = 3 case is incorrect. Specifically, he says "From symmetry, we can expect the last four to have the same probability p at equilibrium". That is wrong. 2 is not like 1 and 3, and 2 appears after fewer questions in the sequence 123 than in 132, so you would not automatically expect those sequences to have the same probability.

Indeed, if you give binary search probability 3/5 and 132 and 312 probability 1/5 each (giving probability 0 to 123 and 321), you'll find that the expected payoff is 9/5, which is less than 13/7.

  • $\begingroup$ You're right, thanks! I was thinking that once $1$ has been asked, there is then symmetry between $2$ and $3$, but that's of course wrong because that symmetry doesn't hold at the time when $B$ chooses a number. I'll try to find time to fix my answer. (By the way, I saw this by chance; if you'd written a comment under the answer I would have been notified.) $\endgroup$
    – joriki
    Jun 23, 2018 at 10:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .