First to Five Points

Question

The Problem:

1. There are two players.
2. Each player writes a number, hidden from the other player. It can be any integer 1 or greater.
3. The players reveal their numbers.
4. Whoever chose the lower number gets 1 point, unless the lower number is lower by only 1, then the player with higher number gets 2 points.
5. If they both chose the same number, neither player gets a point.
6. This repeats, and the game ends when one player has 5 points.

Is it possible to have a strong winning strategy?

My Approach:

1. There is no such thing as random if there is a strategy.
2. If so, naturally each player is going to to pick 1. But if I know that you are going to pick 1, I will pick 2. Then you know I am going to pick 2, you will pick 3. And so forth.
3. Obviously I can't deduce that into a strategy based on I know that you know I know you know. So I can only take a guess as the best bet.
4. The way I guess your next number is taken the average of all the numbers you played in the same round. Plus 1. Unless your average number is greater than 2, then I will pick your mean mod by 5 (a simple way to counter skew the mean).

Not Strong Enough: There seems to be a better winning strategy. So what are the shortcomings of this approach?

Answer 1

If you have a strategy that wins more than 50% of the time, your opponent can use the same strategy and also win more than 50% of the time, which is impossible. Therefore, the best possible strategy cannot guarantee winning more than 50% of the time.

But what strategy will guarantee at least 50% against any other strategy?

---

Part 1: Without the 5 points goal

For now, we will ignore the goal of getting to 5 points, and just try to maximize the value of our score minus the opponent's score. We must find a mixed strategy such that the expected value against any other strategy is at least 0.

Suppose we choose 1 with probability $p_1$, 2 with probability $p_2$, and so on, such that $p_1+p_2+p_3+\ldots=1$.

If the opponent always chooses 1, our expected payoff is $2p_2-p_3-p_4-\ldots=p_1+3p_2-1$. This quantity must be at least 0, or else we are losing. We can repeat this process for each possible number the opponent chooses:

$$-2p_1+2p_3-p_4-p_5-\ldots=-p_1+p_2+3p_3-1\ge0\\ p_1-2p_2+2p_4-p_5-\ldots=2p_1-p_2+p_3+3p_4-1\ge0$$

In general, for all $n\ge2$,

$$2(p_1+p_2+\ldots+p_{n-2})-p_{n-1}+p_n+3p_{n+1}-1\ge0\\ 2(p_1+p_2+\ldots+p_{n+1})+p_{n+1}\ge1+3p_{n-1}+p_n$$

Let $S_n=p_1+p_2+\ldots+p_n$. Then

$$3S_{n+1}-S_n\ge1+S_n+2S_{n-1}-3S_{n-2}\\ 3S_{n+1}+3S_{n-2}\ge1+2S_n+2S_{n-1}$$

This holds down to $n=1$ if we assume $S_0=S_{-1}=0$. Some linear algebra produces a solution: $$S_1=1/16\\S_2=3/8\\S_3=5/8\\S_4=15/16\\S_5=1$$

So our optimal strategy is: $$p_1=p_5=1/16\\p_2=p_4=5/16\\p_3=1/4$$

This strategy guarantees that in the long run, our points will keep pace with the opponent's points.

---

Part 2: With the goal

Now we add the goal. This changes things slightly, because if we have four points, it doesn't matter whether we win one point or two, and similarly for the opponent.

4-4

Suppose both players have 4 points. If we get one point or two points, our payoff is 1, and if the opponent gets one point or two points, our payoff is -1. We require our expected payoff to be 0 (any higher is again impossible because of symmetry). Repeating the process with the adjusted payoffs results in the inequality:

$$2S_{n+1}+2S_{n-2}\ge1+S_n+S_{n-1}$$

We can solve this to find:

$$p_1=p_2=p_3=1/3$$

This makes sense, because this situation is basically rock-paper-scissors with the numbers 1, 2, and 3: each number beats one and loses to one. All the numbers greater than 3 are irrelevant because they lose to this strategy.

4-3

This case is asymmetric, which makes it harder to analyze. The side with 4 points wins with one point or two, while the side with 3 points wins if getting two points. We know the situation is equal if the side with 3 points gains one point.

If my methods and calculations were correct, the value of this situation is about $0.239142$ for the player with 4 points (or about 62% chance to win). This number is the real root of a fifth degree polynomial. The strategy for the player with 4 points is

$$p_1\approx0.067558\\p_2\approx0.222986\\p_3\approx0.253375\\p_4\approx0.333977\\p_5\approx0.122105$$

and the strategy for the player with 3 points is the same in reverse:

$$p_1\approx0.122105\\p_2\approx0.333977\\p_3\approx0.253375\\p_4\approx0.222986\\p_5\approx0.067558$$

This result indicates that it is very unlikely that there will be a nice solution for the rest of the problem.

3-3

Using $0.239142$ as the value of winning or losing one point, we can calculate the optimal strategy for a score of 3-3: $$p_1=p_7\approx0.009228\\p_2=p_6\approx0.191209\\p_3=p_5\approx0.161754\\p_4\approx0.275618$$

I'm not going to continue further than this because the rest of the asymmetric scores will be very tedious to solve.

Answer 2

I'd have to say:

No it's not possible to have a strong winning strategy. If we are assuming both players play optimally, then no matter what strategy is used, both players will always play optimally. This is the case for any game in which both players take their turns simultaneously. Unless the opponent is playing non-optimally and we are given their exact strategy, there is no way to create an optimal strategy.

Answer 3

The situation is not dissimilar to rock, paper scissors, which can be shown using game theory (if my memory serves me correctly - the lecture was ~20 years ago) that picking a random number works best.

The unboundedness is kind of interesting. But there's obviously a trend to keep the game close to 1, and the symmetry would suggest that it's impossible to get an edge.

However it should still be possible to set up a game theory matrix and find the Nash equilibrium, which would give you the optimal relative probability of choosing each number. But I wasn't able to figure this out yet. I'll try to find a bit of time later!