# What are the optimal mixed strategies for this game?

Fix $k < n$ positive integers, and two players play the following game: each player picks a positive integer between 1 and $n$. If the two numbers picked are within $k$ of each other, the larger number wins and that player gains one point while the other player loses one point. Else, the smaller number wins and that player gains one point while the other loses one. Picking the same number results in a tie, and no points gained or lost. I've tried to find patterns for optimal mixed strategies based on arbitrary $k$ and $n$, without success. Here I define an "optimal strategy" as one that has $\geq 0$ expected value against any mixed strategy.

As an example, when $k=1$ and $n=3$ this game specializes to rock-paper-scissors, with a unique optimal strategy of (1/3, 1/3, 1/3).

Any patterns or properties noticed would also be helpful. For example, I believe (without a formal proof) that when $n > 2k + 1$, any optimal mixed strategy will never pick any number greater than $2k + 1$.

## 1 Answer

Let $m=\min(n,2k+1)$. Then the strategy profile in which both players assign equal probability to the numbers in $[1,m-(k+1)]\cup[k+1,m]$ (and $0$ to all others) is a Nash equilibrium. Each of these numbers wins against exactly half (namely $m-(k+1)$) of the others, and all remaining numbers (if any) lose against more of them.

In particular, for $n\ge 2k+1$, both players assign equal probability to the numbers from $1$ to $2k+1$; each of these numbers wins against $k$ and loses against $k$ of the others, and all higher numbers (if any) lose against more of them.