Finding the best/optimal strategy for this game

Question

My friend posed this question to me which he was unsure if there was a solution (it was an intervew question I think):
It went along the lines of:
The game is the following: You are player $1$ and you are versing another person player $2$. You and player $2$ choose any integer from $1$ to $30$. A $30$ sided die is rolled and whoever's number is the closest to the die's number is the "winner" of the game and gains points according to what they guessed.
e.g. Player $1$ picks number $20$ and player $2$ picks number $15$.
The die lands on the number $18$ so player $1$ wins and gets $20$ points.

(Note that you can choose whether or not to go first or second in picking a number (you will know the other player's number if you go second)).

What is the optimal strategy for this game? (Optimal wasn't really defined from my friend, but I assume it is something like "highest number of points" by the $n$'th round)?

Answer 1

I'll also use the names Alice and Bob, with Alice going first.

I'll assume that at the end of each round, the losing player pays the winning player a dollar amount equal to the winning player's score for that round.

For simplicity, I'll assume no score is awarded if Alice and Bob choose numbers which are equally close to the value of the roll.

Also, I'll assume the rules require Bob to choose a number other than the one already chosen by Alice.

Claim: Alice has the advantage and should always choose $16$.

Alice is trying to maximize not her expected score, but rather, the expected value of her score minus Bob's score.

With Alice choosing $16$, Bob's optimal reply is $15$, but for those choices, the expected value of Alice's score minus Bob's score is $+0.5$, so Alice will win more points, on average, than Bob.

If Alice chooses any number other than $16$, Bob has a reply which can force the expected value of Alice's score minus Bob's score to be negative, so in those cases, Bob will win more points, on average, than Alice.

If Alice chooses $16$, and Bob chooses any number other than $15$, the expected value of Alice's score minus Bob's score will be greater than $0.5$, so Bob's best choice is $15$, since it minimizes Bob's expected loss.

Optimal strategies for Bob:

If Alice chooses $k$ with $k < 16$, Bob's best reply is $31-k$, which yields a positive expectation for Bob.

If Alice chooses $k$ with $k > 16$, Bob's best reply is $k-1$, which yields a positive expectation for Bob.

Finally, if Alice chooses $16$, all choices by Bob yield a negative expectation for Bob, but to minimize the expected loss, Bob should choose $15$.

Bottom line: You want to be Alice!

Answer 2

Edited to add, Tues. Aug 15, 13:58 GMT: I got the rules of the game wrong, I think. Keeping this for posterity.

Original answer: Let's call the players Alice and Bob. Alice goes first, because her name is alphabetically first. I'll assume that Bob gets to know what number Alice picked.

First, let's work out what Bob should pick, and how much he'll win if he does so. If Alice picks $n$, Bob hould pick either $n-1$ or $n+1$. If Bob picks $n-1$, he wins with any number up to $n-1$; if he picks $n-k$ he wins with any number up to $n - k/2$, which is at most $n-1$. So Bob should prefer picking $n-1$ to any smaller number. Similarly he should prefer picking $n+1$ to any bigger number.

Now, if Bob picks $n-1$, he has probability $1/30$ of winning $1$, probability $1/30$ of winning $2$, and so on up to $n$. So Bob's expected winnings in this case are

$$ {1 \over 30} \left( 1 + 2 + 3 + \cdots + (n-1) \right) = {1\over 30} {n(n-1) \over 2}. $$

Similarly if Bob picks $n+1$, he has probability $1/30$ of winning $n+1, n+2, \ldots, 30$. So his expected winnings are

$$ {1 \over 30} \left( (n+1) + (n+2) + \cdots + 30 \right) = {1 \over 30} {(31+n)(30-n) \over 2}. $$

Bob should pick $n-1$ or $n+1$ according to which of these is larger. That is, he should pick $n-1$ if

$$ {{n(n-1) \over 2}} > {(31+n)(30-n) \over 2} $$

and $n+1$ if the inequality goes the other way. We can solve the inequality. Expanding the numerators gives

$$ n^2 - n = 930 - n - n^2 $$

and we can cancel out the $-n$ and rearrange to get $930 = 2n^2$, or $n = \sqrt{465} \approx 21.56$.

So Bob should pick $n-1$ if $n > \sqrt{465}$ (i. e. $n \ge 22$) and $n+1$ otherwise (if $n \le 21$). His expected winnings will be $n(n-1)/60$ if $n \ge 22$ and $(31+n)(30-n)/60$ if $n \le 21$.

Now, what will Alice choose? Alice chooses in such a way as to minimize Bob's expected winnings, because minizing Bob's expected winnings is the same as maximizing her own. This is because the sum of Alice's expected winnings and Bob's expected winnings is the expected number that comes up when you roll a 30-sided die. (This is 15.5, but that's irrelevant right now.) The function $n(n-1)/60$ is increasing with $n$, so Bob does better as $n$ increases above 22. And $(31+n)(30-n)/60$ decreases with $n$, so Bob does better as $n$ decreases below 21. Bob's worst number is therefore either 21 or 22. Explicitly computing, Bob's expected winnigs are $22(22-1)/60 = 7.7$ if Alice picks $n = 22$, and $(31+21)(30-21)/60 = 7.8$ if Alice picks $n = 21$. Therefore Alice will pick $n = 22$, shd expected to win $15.5 - 7.7 = 7.8$, and Bob expects to win $7.7$.

Finally, a player given the choice of going first or second will choose to go first (that is, to be Alice). This depends on the fact that the number of sides of the die is $k = 30$, and in particular on where $\sqrt{k(k+1)/2}$ falls relative to the integers on either side of it.

Answer 3

Assumptions

I hope I got the rules of the game right. I assumed that

1. it isn't valid to choose the same number as your opponent
2. and if the distant to both number is equal then both win.

Model

We have Player1 who picks a number at first and Player2 who responds. Let $X_{n,k}$ be the random variable of the winning of Player1 and $Y_{n,k}$ the corresponding random variable of Player2, where $n$ is the number Player1 chose and $k$ the number Player2 chose. \begin{align*} X_{n,k}(\omega) = \begin{cases}n, & \text{if}\; d(\omega,n) \leq d(\omega,k) \\ 0, & \text{else}\end{cases} \end{align*} For Player2 we have \begin{align*} Y_{n,k}(\omega) = \begin{cases}k, & \text{if}\; d(\omega,k) \leq d(\omega,n) \\ 0, & \text{else}\end{cases} \end{align*} Now we want the maximize the expected value for Player2 for every move that Player1 can do. In order to do that we need a formular for the expected value of $Y_{n,k}$. \begin{align*} \mathbb{E}(Y_{n,k}) = \sum_{i=1}^{30} Y_{n,k}(i) P(\{i\}) = \begin{cases} \sum_{i=1}^{\lfloor\frac{n+k}{2}\rfloor} \frac{k}{30}, &\text{if}\; n>k \\ \sum_{i=\lceil\frac{n+k}{2}\rfloor}^{30} \frac{k}{30}, &\text{else} \end{cases} = \begin{cases} \frac{k}{30}\big\lfloor\frac{n+k}{2}\big\rfloor , &\text{if}\; n>k \\ \frac{k}{30}\big(31-\big\lceil\frac{n+k}{2}\big\rfloor\big) , &\text{else} \end{cases} \end{align*} Now you can try around to find the best $k$ for each $n$ with analytic methods but I didn't feel like doing that so I wrote a short python script.

Code

import math


def expectedValueP1(n,k):
    ev=0;
    if (n < k):
        ev = n/30 * math.floor((n+k)/2)
    elif (n > k):
        ev = n/30 * (31 - math.ceil((n+k)/2));
    return ev;


def expectedValueP2(n,k):
    ev = 0;
    if (n > k):
        ev = k/30 * math.floor((n+k)/2);
    elif (n < k):
        ev = k/30 * (31 - math.ceil((n+k)/2));

    return ev;


def bestResponse(n):
    best_index = 0;
    bestEV = 0;
    for k in range(1,31):
        ev = expectedValueP2(n,k);
        if (ev > bestEV):
            bestEV = ev;
            best_index = k;
    return best_index;


def main():
    for n in range(1,31):
        k = bestResponse(n);
        ev1 = expectedValueP1(n,k);
        ev2 = expectedValueP2(n,k);
        print("P1: %s, P2: %s EVs P1: %s, P2: %s" % (n, k, ev1, ev2));


if __name__ == '__main__':
    main();

The result was that depending on what player 1 choose the best response is:

Output

P1: 1, P2: 29 EVs P1: 0.5, P2: 15.466666666666667
P1: 2, P2: 30 EVs P1: 1.0666666666666667, P2: 15.0
P1: 3, P2: 29 EVs P1: 1.6, P2: 14.5
P1: 4, P2: 28 EVs P1: 2.1333333333333333, P2: 14.0
P1: 5, P2: 29 EVs P1: 2.833333333333333, P2: 13.533333333333333
P1: 6, P2: 28 EVs P1: 3.4000000000000004, P2: 13.066666666666666
P1: 7, P2: 27 EVs P1: 3.966666666666667, P2: 12.6
P1: 8, P2: 26 EVs P1: 4.533333333333333, P2: 12.133333333333333
P1: 9, P2: 27 EVs P1: 5.3999999999999995, P2: 11.700000000000001
P1: 10, P2: 26 EVs P1: 6.0, P2: 11.266666666666667
P1: 11, P2: 25 EVs P1: 6.6, P2: 10.833333333333334
P1: 12, P2: 24 EVs P1: 7.2, P2: 10.4
P1: 13, P2: 25 EVs P1: 8.233333333333334, P2: 10.0
P1: 14, P2: 24 EVs P1: 8.866666666666667, P2: 9.600000000000001
P1: 15, P2: 23 EVs P1: 9.5, P2: 9.200000000000001
P1: 16, P2: 24 EVs P1: 10.666666666666666, P2: 8.8
P1: 17, P2: 16 EVs P1: 7.933333333333334, P2: 8.533333333333333
P1: 18, P2: 17 EVs P1: 7.8, P2: 9.633333333333333
P1: 19, P2: 18 EVs P1: 7.6, P2: 10.799999999999999
P1: 20, P2: 19 EVs P1: 7.333333333333333, P2: 12.033333333333333
P1: 21, P2: 20 EVs P1: 7.0, P2: 13.333333333333332
P1: 22, P2: 21 EVs P1: 6.6, P2: 14.7
P1: 23, P2: 22 EVs P1: 6.133333333333334, P2: 16.133333333333333
P1: 24, P2: 23 EVs P1: 5.6000000000000005, P2: 17.633333333333333
P1: 25, P2: 24 EVs P1: 5.0, P2: 19.200000000000003
P1: 26, P2: 25 EVs P1: 4.333333333333334, P2: 20.833333333333336
P1: 27, P2: 26 EVs P1: 3.6, P2: 22.533333333333335
P1: 28, P2: 27 EVs P1: 2.8, P2: 24.3
P1: 29, P2: 28 EVs P1: 1.9333333333333333, P2: 26.133333333333333
P1: 30, P2: 29 EVs P1: 1.0, P2: 28.033333333333335

If Player2 just want the maximize his output the best strategy for player1 is to pick $16$. In this case Player1 will even have a higher expected value than Player2. If you play a little bit with the script you will figure out that there is no strategy for Player2 the get a higher excepted value than Player1 if Player1 picks $15$ or $16$.

Summary

If both player plays "perfect" then Player1 will have the better initial situation. He will always choose $16$.