Very fascinating probability game about maximising greed?

Question

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)

Answer 1

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.

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.

Answer 2

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)$$