Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
The numbers are required to be integers, I hope. –  Henning Makholm Jan 12 '12 at 0:35
    
@HenningMakholm Yes, the numbers must be integers –  Bob Jan 12 '12 at 0:36
1  
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. –  joriki Jan 12 '12 at 2:09

1 Answer 1

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.

share|improve this answer
    
Wow! What a thorough response! –  Samuel Reid Jan 12 '12 at 3:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.