Optimal point selection to maximize length of closest points interval Consider the following game: there are $n$ players, who pick $x_i\in I = [0,1]$ in turns, $1\leq i\leq n$. For each selection $x = (x_1,\dots,x_n)\in I^n$, the player's $i$ reward is the length of the interval of those points, that are closer to $x_i$ than to any other $x_j$ for $j\neq i$. How to optimally make the selection of these points? I assume that whenever $x_i = x_j$ for $i<j$, the latter point is discarded and the latter player gets $0$ payoff.
For example, when $n = 2$, the optimal choice for the first player is $x_1 = \frac12$, since that leaves the second player indifferent between $x_1+$ and $x_1-$. The payoff for the first player is hence $\frac12+$, and for the second player it is $\frac12-$. However, for 3 players the situation becomes less trivial: intuitively the first two players would go for $x_1 = x_2 = \frac13$, in which case the third player would make a pick just below left or just above right point: if he does that with probability of $\frac12$, the expect payoff for each player is $\frac13\pm$. However, in that case for the second player it makes sense to deviate and pick $x_2 < 1 - x_1$ to force player $3$ to pick a point close to $x_1$.
What is the solution in case of $n = 3$ and $n = 4$? Is there a nice algorithm to solve this problem for any $n$, perhaps some references you know of? I am also interested in solution of a more general case: there is a probability measure $p$ on $I$, and payoff of each player is the measure of the corresponding interval. I guess in this case the interval may as well be unbounded.
 A: Your problem is not well-posed. The pay-off function is discontinuous at points, where two players have taken the same decision. The function is also not upper semicontinuous.
I want to try an analysis for $n=3$. First, analyze the situation of the last player. Assume the first and second player already have taken $0\le x_1 < x_2 \le 1$.
If the third player places between $x_1$ and $x_2$, he can place $x_3$ anywhere in $(x_1,x_2)$ to receive $\frac12(x_2-x_1)$. If the third player places in $(0,x_1)$ or $(x_2,1)$ he receives at most $x_1$ or $1-x_2$. 
That is, the strategy of third player will be 
$$
x_3^*(x_1,x_2) \in \begin{cases} \{x_1-\epsilon\} & \text{ if } x_1 > \max(1-x_2,\frac12(x_2-x_1))\\
(x_1,x_2)& \text{ if } \frac12(x_2-x_1) > \max(x_1,1-x_2)\\
\{x_2+\epsilon\} & \text{ if } 1-x_2 > \max(x_1,\frac12(x_2-x_1))
\end{cases}
$$
The second player now maximizes his gain given the decision of player $1$ and given the optimal response of player $3$. The gain of player $2$ is at least
$$
g_2(x_1,x_2) = \begin{cases} 1-\frac12(x_1+x_2) & \text{ if } x_1 > \max(1-x_2,\frac12(x_2-x_1))\\
1-x_2& \text{ if } \frac12(x_2-x_1) > \max(x_1,1-x_2)\\
\frac12(x_2-x_1) & \text{ if } 1-x_2 > \max(x_1,\frac12(x_2-x_1))
\end{cases}
$$
Doing some experimentation with matlab indicates that the optimal choice for $x_2$ is
$$
x_2^*(x_1) = \begin{cases} \frac23 + \frac13 x_1+ \epsilon& x_1 < \frac14\\ 
1-x_1 +\epsilon & x_1\in(\frac14,\frac12)\\
1-x_1 -\epsilon & x_1\in(\frac12,\frac34)\\
1-(\frac23 + \frac13(1- x_1))-\epsilon& x_1> \frac34.\\
\end{cases}
$$
Surprisingly the best choice for player 1 is thus $1/4$ or $3/4$ with minimal gain $0.25$. Player $2$ chooses then $3/4+\epsilon$ or $1/4-\epsilon$. Player 3 chooses anything between to gain at least $0.5+\epsilon/2$.
If player 1 chooses $1/3$ and player 2 chooses $2/3$, then player $3$ can take $1/3-\epsilon$ or $2/3+\epsilon$, with bad consequences for one of the other players. Thus these players want to avoid such a situation.

For this particular example, there seems to be no easy solution process.

Looking at the general picture, this problem is a multi-level optimization problem, where some variables solve lower-level optimization problems. For $n=3$ this problem (for the first player) reads as follows (with $g_i$ denoting the gain of player $i$):
$$
\max_{x_1} g_1(x_1,x_2,x_3),\\
\text{ subject to }
\left\{\begin{gathered}
x_2 = \text{ arg min } g_2(x_1,x_2,x_3)\\
\text{ subject to }
\begin{gathered}
x_3 = \text{ arg min } g_3(x_1,x_2,x_3)
\end{gathered}
\end{gathered}
\right.
$$
In the inner problem $x_3 = \text{ arg min } g_3(x_1,x_2,x_3)$ the variables $x_1,x_2$ are parameters, in the second-level problem $x_2 = \text{ arg min } g_2(x_1,x_2,x_3)$, $x_1$ is a parameter and $x_3$ is the solution of the inner problem.
