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.

Three people A,B,C attend the following game: from 0~100, the Host will come up a number with Uniform, but he doesn't tell them the number, the attendee will guess a number and the closes one will win. A choose the number first and tell the number, B will tell another different number based on A's number, C choose another different one based on both A and B.

What number should A,B,C choose to make sure the probability is largest to win the game ?

share|improve this question
    
Is this game iterated or one-off? If it's iterated, then some prisoners'-dilemma considerations come into play. –  user22805 Feb 1 '12 at 4:45
    
This is one-off –  John Feb 2 '12 at 12:08

3 Answers 3

To temporarily avoid problems due to the discreteness of the set $\{0,1,\dots,100\}$, let's pretend that the three people are guessing a real number between 0 and 1. If the first two guesses are $a$ and $b$, say $0<a<b<1$, then C will want to guess

  • a tiny bit less than $a$, if $\max\{a,\frac{b-a}2,1-b\} = a$;
  • anything between $a$ and $b$, if $\max\{a,\frac{b-a}2,1-b\} = \frac{b-a}2$;
  • a tiny bit more than $b$, if $\max\{a,\frac{b-a}2,1-b\} = b$.

Then C's chance of winning will be precisely $\max\{a,\frac{b-a}2,1-b\}$.

Unfortunately, the fact that C's winning move is not unique in one case makes B's strategy undefined: B needs to know how C will choose from among those choices, or what random distribution C will choose from.

share|improve this answer
    
Or else $B$ needs to avoid the situation that gives $C$ a choice. –  Gerry Myerson Feb 1 '12 at 11:48
    
@GerryMyerson - I don't agree. To avoid giving C the choice, B has to pick a number that guarantees him less of a chance than he'd get if he DID give C the choice. I believe that in the case where $a < 0.25$, B's best number is $\frac{a+2}{3}$. But, as Greg correctly pointed out, it's undefined just how good this is for B. –  user22805 Feb 3 '12 at 5:59
    
@David: Under the assumption stated in my answer, the question never comes up, not because B avoids it but because A avoids it. –  joriki Mar 2 '12 at 13:10

Building upon Greg's answer, we can analyze what's best for $B$ then.

C's strategy

As pointed out, depending on $M = \max\{a, (b-a)/2, 1 - b\}$, $C$ will choose $c = a - \gamma$ if $a = M$, $c \in (a,b)$ if $(b-a)/2 = M$ and $c = 1 - b + \gamma$ if $1 - b = M$, for some small value $\gamma$. This is assuming $a < b$, but of course an analogous result holds for $a > b$.

B's strategy

If $A$ chooses $a = 1/2 - \alpha$ for some small $\alpha$, then $B$ can choose $b = 1/2 + \alpha + \beta$ for some small $\beta$, so that $C$'s optimal strategy would be to pick $c = 1/2 - \alpha - \gamma$ for some small $\gamma$. This gives $B$ a winning chance of almost $0.5$, which should be optimal, and $A$'s winning chances will be $(b - c)/2 = \alpha + \beta/2 + \gamma/2$ which will be small for small $\alpha, \beta, \gamma$.

This holds for all sufficiently small $\alpha$, but when $\alpha = 1/4$ and $a = 1/4$ we get a new situation. Then with this strategy $(b - a)/2 = 1/4 + \beta/2 > \{1 - b, a\} = \{1/4 - \beta, 1/4\}$, hence $C$ would choose a number between $a$ and $b$ as pointed out by Greg. Then (for $B$'s worst-case) if $C$ chooses $c$ close to $b$, $B$'s winning chances are reduced to less than $1/4$. Similarly, choosing $b \gg 3/4$ allows $C$ to choose $c = b - \gamma$ further decreasing $B$'s worst-case chances, while $b < 3/4$ will make $C$ choose $c = b + \gamma$ also giving $B$ odds of less than $1/4$. So assuming the worst-case scenario for $B$, $B$ is best off by taking $b = 3/4$ if $a = 1/4$. Then $A$'s worst-case winning chances are always at least $1/4$.

Finally, if $A$ chooses $a < 1/4$, then $B$ can choose $b = a + 2/3(1 - a) + \beta < 3/4$, so that $C$ will choose $c$ between $a$ and $b$, and $B$'s chances are more than $1/4$. In $A$'s worst-case scenario, this will mean that $C$ chooses $c$ close to $a$, so that $A$'s chances will be less than $1/4$.

A's strategy

As we saw above, the worst-case chances of $A$ winning, assuming $B$ maximizes his worst-case chances, are $< 1/4$ for $a \in (1/4, 1/2]$, $\geq 1/4$ for $a = 1/4$ and $< 1/4$ for $a \in (0, 1/4)$. So the best worst-case strategy for $A$ is to pick $a = 1/4$, in which case $B$'s best worst-case strategy is to pick $b = 3/4$, after which $C$ can pick any value $c \in (1/4, 3/4)$.

share|improve this answer

It turns out that under a plausible assumption about C's strategy, the case where B would need to know C's strategy to decide her own strategy doesn't occur because it's bad for A. Under this assumption, all players have a well-defined optimal strategy independent of the other players' strategies.

Let $S_1$ and $S_2$ be two states brought about by the choices of A and B such that in each state C has an interval $[a_i,b_i]$ of options that will lead to the same payoff for C but not for A and B. The assumption about C's strategy is that if $a_1\le a_2$ and $b_1\le b_2$, then $c_1\le c_2$, where $c_i$ is C's choice in $S_i$. This assumption is satisfied for instance if C always favours A, always favours B, always chooses randomly with uniform distribution in the interval, or has a lucky number that he will pick whenever it's in the interval. It is not satisfied, however, if C's strategy is to "punish" or "deter" B by giving B a smaller payoff the smaller B makes C's payoff.

In Greg's second case, B knows that C will play in the middle, so under the assumption made, she can increase her payoff by moving to the left, as this will not cause C to move to the right. This works until $(b-a)/2=1-b$ (where C would start playing just to the right of B), and thus $b=(a+2)/3$, as David pointed out. The payoff for B in this case is known to be at least $1-b=(1-a)/3$, and B will make this move if it is at least preferable to playing just to the left of A with payoff $a$, that is if $(1-a)/3\ge a$, or $a\le1/4$. Then B will have guaranteed payoff $(1-a)/3$, A will have guaranteed payoff $a$, and C will get half of the rest, $(1-a)/3$, and the remaining $(1-a)/3$ will be split between A and B according to C's choice.

On the other hand, if $1/4\lt a\le1/2$, there are two choices for B. While B can't decide between them without knowing more about C's strategy, A knows that whichever choice B makes it will be worse for A. If B plays just to the left of A, C will play just to the right of A, and A's payoff will be $0$. If B plays on the right, at $(a+2)/3$, then the payoff for C if he plays in the middle or just to the right of B, $(1-a)/3\lt1/4$, would be less than the payoff if he plays just to the left of A, namely $a\gt1/4$. Thus C would play just to the left of A, and the payoff of $(b-a)/2=(1-a)/3\lt1/4$ for A would be less than the guaranteed payoff of $1/4$ for $A$ at $a=1/4$.

Thus, under the stated assumption and without making further assumptions about the choices other players will make among options that don't affect their own payoff, A will play at $1/4$, B will play at $3/4$, and C will play at $c$ anywhere between $1/4$ and $3/4$; the payoff will be $1/4$ to C, $1/8+c/2$ to A and $5/8-c/2$ to B.

Returning to the integer case, since $100$ is divisible by $4$, it seems likely that the optimal strategies (under the stated assumption) are $a=25$, $b=75$ and $25\lt c\lt 75$, but I haven't checked that in detail.

It's interesting that C is worst off; I would have thought that choosing last would be to C's advantage, but it turns out that playing earlier allows one to impose a more favourable spacing.

[Update:]

We can also ask what would happen if C did try to set incentives in his strategy. Of course this only works under the assumption that he announces the strategy and the others believe that he will follow it. There are two different versions of this: We could consider strategies under the assumption that C always directly maximizes his own payoff and only uses options to which he is otherwise indifferent to set incentives; or we could also allow him to promise to choose an otherwise suboptimal result. The second case is more complicated, especially if we allow the same for B; whereas the first case is rather straightforward to solve.

So assume that C always chooses an optimal result for himself and reliably announces how he will decide between options to which he is otherwise indifferent. First assume $a\gt1/4$. In this case B can secure herself a payoff of $1/2$ by playing just to the right of $1-a$, which will cause C to play just to the left of $a$, and there is no incentive that C could offer to B to change that. The payoff to A in this case would be $1/2-a\lt1/4$. Since we already know that A can unconditionally secure a payoff of $1/4$ by playing at $a=1/4$, it follows that A will not play at $a\gt1/4$.

Now assume $a=1/4$. Then B can secure a payoff of at least $1/4$ by playing at $3/4$, so C needs to offer her more than that to cause her to play somewhere else. He can offer to play somewhere between $1/4$ and $1/2$ if B plays at $1$, and threaten to play just to the left of B otherwise. This will lead to a payoff of $3/8$ for C, $(1/4+c)/2$ for A and $(1-c)/2$ for B, where the payoffs for A and B both lie between $1/4$ and $3/8$ and depend on the remaining choice by C.

Now assume $a\lt1/4$. Then B can secure a payoff of $(1-a)/3$ by playing at $(a+2)/3$, and C can get her to play at $1$ by offering to play between $a$ and $1-2(1-a)/3=(1+2a)/3$. The payoff for A will be $(a+c)/2$, and this has to be just more than $1/4$, so C can offer to play at $1/2-a$. This is compatible with offering an incentive to B as long as $1/2-a\lt(1+2a)/3$, that is $a\gt1/10$. Thus, by offering to play at $2/5$, he can get A to play at $1/10$ and B to play at $1$, and the payoffs will be $1/4$ to A, $3/10$ to B and $9/20$ to C. (The incentives can be made arbitrarily small, and I didn't include any $\epsilon$s for them so as not to clutter the results.)

Thus, while C is worst off if he plays a simple strategy such as favouring A, favouring B or choosing randomly among options with equal payoff for himself, he is best off and gets almost half the payoff if he puts the indeterminacy in his options to strategic use.

For the integer problem, this would correspond to A choosing $10$, B choosing $40$ and C choosing $100$. However, in this case the incentives can't be made arbitrarily small, so B might have to allow A to play at $11$; this can't be analysed in detail since the question doesn't say what happens in case of a tie.

share|improve this answer
    
"all players have a well-defined optimal strategy independent of the other players' strategies" - If $a = 0.2$ and $b = 0.8$ then for $C$ it does not matter whether he chooses $c = 0.3$ or $c = 0.7$: his chances of winning are always $0.3$. So although for $C$ it does not matter whether he picks $0.3$ or $0.7$, for the others it does. So the probability of $B$ winning in this scenario depends on how $C$ makes a decision when it does not matter for his own chances. If $B$ knows $C$'s decision-function, it could turn out that $B$ is better off choosing $b = 0.99$ in that case. –  TMM Mar 2 '12 at 12:06
    
@TMM: You're right in the sense that if C can have an arbitrary decision function that may lead to C moving closer to B when B moves closer to the middle, e.g. to punish B, then B's choice does depend on C's strategy. I should have said more precisely that the result doesn't depend on C's strategy for more plausible strategies of C such as favouring A, favouring B, or choosing $a+r(b-a)$ with $r\in(0,1)$ a random number. I'll edit to restrict my claim to such cases. –  joriki Mar 2 '12 at 12:15
    
I agree that in most sensible cases B's strategy will be to pick $b$ at two-thirds of $(a, 1)$, but as you mentioned $C$ could "punish" $B$ for making such a good choice, in which case $B$ would be better off making a bad choice. –  TMM Mar 2 '12 at 12:32
    
@TMM: My apologies for portraying your worst-case assumptions as unnecessary in the original version of my answer. You're right that it's not possible to do entirely without assumptions, and that "punishing" B is also a possible strategy. Nevertheless it's interesting that one can get by with a relatively mild assumption and the result is independent e.g. of C favouring A or B. I've edited the answer to specify the required assumption. –  joriki Mar 2 '12 at 13:09

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.