3
$\begingroup$

Two people play a mathematical game. Each person chooses a number between 1 and 100 inclusive, with both numbers revealed at the same time. The person who has a smaller number will keep their number value while the person who has a larger number will halve their number value. Disregard any draws.

For example, if the two players play 50 and 70, the first player will retain 50 points while the second will only get 35.

There are five turns in total and each person receives a score equal to the sum of their five values.

What is the optimum winning strategy?

Obviously playing 100 each turn is a bad strategy since if the other player plays 70 then they gain 20 points more than you. Similarly, playing 1 is also a bad move since you are guaranteed to receive less points than your opponent.

If we assume that our opponent is a computer that picks numbers from 1 to 100 with equal probability, we can work out the expected value which will maximise our score relative to the computer's. (I have worked out this to be 60 something - I think)

But, if this is true then the computer will realise that it is pointless to play anything less than 30 something so we can further assume the computer will not play such low numbers.

This gives a different optimal number to play each time. Repeating this method will give different values of the 'best' number to play. I'm just wondering what this number is.

Also, the 'five turns' thing is of course irrelevant, but with a human it is interesting to predict the other player's strategy and moves.

So does there exist a number, which will maximise the total expected value? (We can assume our opponent has the same amount of knowledge as us)

$\endgroup$
  • 1
    $\begingroup$ This game is similar in flavor to the traveler's dilemma game. $\endgroup$ – vadim123 Oct 18 '15 at 2:23
  • $\begingroup$ This game can be phrased as a non-cooperative perfect information zero-sum game (assuming you only care about who wins, not how much money they make when they win), and strategies for these games can be found via linear programming. (Presumably the best strategy is to pick certain numbers at random with certain probabilities.) en.wikipedia.org/wiki/Zero-sum_game#Solving $\endgroup$ – Greg Martin Oct 18 '15 at 2:55
  • $\begingroup$ Can you clarify if you care about an absolute value of winning or value relative to the other player? $\endgroup$ – A.S. Oct 19 '15 at 4:32
  • $\begingroup$ What about both? Which number gives the highest chance of winning (assume only one game) and which number will maximise the winning value (assuming more than one game)? $\endgroup$ – John Smith Oct 19 '15 at 5:25
1
$\begingroup$

As @Greg Martin pointed out, you can solve such games using linear programming under the assumption that the goal is to win by the largest margin over the other player.

I used an online zero-sum game solver to find the following solution; I'm not sure if this optimal strategy is unique.

enter image description here

Never choose numbers in $[1,25]$. Choose even numbers in $[26,100]$ with decreasing probability ($P(26)\approx0.0575$; $P(100)=0.\overline{01}=\frac1{99}$) and choose odd numbers in $[27,49]$ even less often ($P(27)\approx0.0166$; $P(49)\approx0.000372$). Never choose odd numbers greater than $49$.

This is a fairly curious result, and perhaps someone else can offer some insight into it.

The strategy above is appropriate when playing over several rounds and the scores accumulate. But if you're playing only one round and care only for winning but not the margin of victory, then the strategy is very different! Simply play either $26$ or $52$ with equal probability and you are guaranteed to win at least half the time. (If your opponent adopts the same strategy, you will tie every single game.) Again, I'm not sure if this strategy is unique.

$\endgroup$
  • $\begingroup$ @A.S. You still haven't explained how either player wins if they are both choosing $26$ or $52$. Furthermore, I believe that the spirit of the problem is indeed about relative final value: "Obviously playing 100 each turn is a bad strategy since if the other player plays 70 then they gain 20 points more than you. Similarly, playing 1 is also a bad move since you are guaranteed to receive less points than your opponent." If we cared about absolute value, then playing $1$ would be a bad move for a different reason, namely that it would only give $1$ point. $\endgroup$ – Théophile Oct 19 '15 at 3:38
  • $\begingroup$ Point noted on the spirit of the problem, though the statement in the beginning is only about absolute value. So it's unclear overall. You are correct that 26/52 strategy results in ties - I simply didn't half the max value. $\endgroup$ – A.S. Oct 19 '15 at 3:43
  • $\begingroup$ Given that, $26/52$ strategy is not unique. Any $k/2k$ for $k\geq 26$ strategy has the same guarantee. $\endgroup$ – A.S. Oct 19 '15 at 3:56
  • $\begingroup$ I got pdf $f(t)=\frac 1 2 t^{-3/2}I(t\in [1/4,1])$ for a continuous game of relative objective on $[0,1]$ which translates to $\frac 1 {200} (t/100)^{-3/2}I(t\in[25,100])$ on $[1,100]$. Can you look at the log-log plot of your data to see if the top line fits a similar curve and check the smaller for the smaller subcurve? $\endgroup$ – A.S. Oct 20 '15 at 3:49
1
$\begingroup$

I will address a continuous version of the problem (since nothing explicitly says that one can only choose whole numbers) on $[0,1]$ and assume that both players maximize absolute payoff (as the last sentence asks) rather than relative payoff.

In that case, let $X\sim F$ be cdf of the first player and $Y\sim G$ be cdf of the second player. Then

$$V_1(X,Y)=\int_0^1 x\big(P(Y>x)+\frac 1 2P(Y<x)\big)dF(x)=\int_0^1\frac 1 2x(1+P(Y>x)-P(Y=x))dF(x)=\frac 1 2\int H(x)dF(x)$$

This shows that $F$ will put no weight on $x<\frac 1 2$ since changing such an $x$ to one in $(2x,1)$ (that doesn't coincide with atoms of $Y$) will increase the integral. Restrict ourselves to $[\frac 1 2,1]$ from now on. Since a similar formula holds for $G$ and we can see at at equilibrium neither $F$ nor $G$ contain any atoms. That implies that $H(x)$ has to stay constant ($=H(1/2)=H(1)=1$) on $[0,1]$: $$x(1+P(Y>x))=1\Leftrightarrow P(Y>x)=\frac 1 x-1\Leftrightarrow f(x)=\frac 1 {x^2}[x\in[\frac 1 2, 1]]$$

Value of such a game is $\frac 1 2$ for both player. Translating into the original problem we get similar distribution on $[50,100]$ and $50$ as a value of the game.


If the value of the game is relative, then the value:

$$2V(X,Y)=2E(X-\frac Y 2;X<Y)+2E(\frac X 2-Y;X>Y)=\int_0^1(xP(Y>x)+x-xP(Y=x)-E(Y;Y<x)-E(Y)+xP(Y=x))=\int_0^1\Big(x(1+P(Y>x))-E(Y;Y<x)\Big)dF(x)-E(Y)=\int_0^1H(x)dF(x)-E(Y)$$ As before, in equilibrium $F$ and $G$ have no atoms and $H$ is constant on some $[x_0,1]$ which is support of $F$. Solving $H'=0$: $$(2-G(x))-xg(x)-xg(x)=0\Leftrightarrow\frac {G'(x)}{2-G(x)}=\frac 1 {2x}\Leftrightarrow \frac {2-G(t)}2=(\frac {x_0} t)^{1/2}$$ Plugging in $G(1)=1$ yields:$$g(t)=\frac 1 2t^{-3/2}I_{[1/4,1]}(t)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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