Came up with a following game recently and after trying to understand the general strategy for hours I have to admit I failed at finding one, so I thought asking here would be a good idea.
As a good friend of mine restated:
Define the "n-player survivor game" as follows: label the players 1, .., n. First, in ascending order by index, each player publicly announces who they plan to eliminate (possibly themselves). Then, in descending order by index, each player eliminates the player they previously announced. If a player is already eliminated, they can no longer eliminate the player they previously announced.
Each player is rational, with the following goals [in order]: (1) survive (don't get eliminated); (2) leave as few survivors as possible. If some player k can make multiple decisions with the same outcomes w.r.t. goals (1) and (2), they choose a decision uniformly at random among those decisions.
If you try for n=3 and 4, it quickly becomes clear that players will follow a mixed strategy.
Is there a closed form P_n(k) for the probability that player k survives in the n-player survivor game?
(Players are not allowed to agree on strategies beforehand. The only information they can share is their announcement of who to eliminate.)
We found a strategy for n=3 and made a tree of choices for n=4, but there's no clear sign of it being trivial for any given n. I can answer questions about the game, so you can ask in comments. I'll be up for a while.
The game runs exactly once, so there may not be a clear winner, just surviving and eliminated players. I'm noting "player k chooses player j" as k!j to simplify the notation.
It was suggested that I change my comments into a proper answer, even though I don't feel remotely close to solving the problem yet :)
Preliminaries
Call an announcement of another player a move, and write "$i$ announces $j$" as $m(i) = j, (i, j) \in \{1, ..., n\}^2$. Call a set of moves for each $k \in [1,n]$ a play of the game. Since the game is sequential, plays can be represented as a decision tree with the $i$th level representing player $i$'s moves.
We're looking for what happens during the optimal strategy, a mixed strategy of plays such that, for each player $i$, given all previous moves, (1) maximizes $i$'s chance of survival and (2) minimizes the total number of survivors.
Claim: All plays with nonzero probability in the optimal strategy leave the same number of survivors.
Proof: For player $n$, given the first $n-1$ players' moves, all optimal moves by player $n$ must leave the same number of survivors; otherwise player $n$ isn't minimizing the total number of survivors.
Similarly, for each player $k \in [1,n)$, given the first $k-1$ players' moves, all optimal moves by player $k$ must leave the same number of survivors, so by induction, any sequence of optimal moves by all players (an optimal play) must leave the same number of survivors. $\blacksquare$
DFS
Unfortunately I wasn't able to get much out of the structure of the game otherwise, since individual moves may have nonlocal consequences that are hard to describe. Instead, I wrote a brute-force DFS search to find the values of $P_n(k)$ for each $n \le 10$.
The code for the DFS can be found in this pastebin (older version here only works with Python 3.9+.)
The general idea is this: at depth $d$ in the decision tree, given the $d-1$ previous moves, we compute
num_survivorsandprob_map, a mapk -> P[k survives]for each $k \in [1,n]$. A node in the tree at depth $d$ combines the result from its children (player $d$'s potential moves) by finding any children whereP[d survives]is maximized andnum_survivorsis minimized, and uniformly choosing between them, i.e. averaging theirprob_maps; theirnum_survivorsare all the same.DFS Results
The code produced the following probabilities for $n \le 10$ where row $n$, column $k$ is $P_n(k)$.
Note that the DFS is a brute-force $O(n^n)$ algorithm; the $n=10$ case was actually computed by a Go re-implementation that used some multithreading, and took 5 hours (the python implementation may require 20+ hours to run; pypy is recommended.)
Thoughts
I'm not even sure how to show that $P_n(n) = 1$ right now, (or even if it's true); perhaps one would want to show that any sequence of previous moves from $1, \ldots, n-1$ that results in $n$ always being eliminated can't be optimal for one of the players?
Other minor observations I came up with:
If all of your moves give a 0% probability of survival, you can't discard moves like $m(i) = i$. One early example is $n=4$, where $m(1) = 1$ is a (tied for) optimal move.
Similarly, it seems like in an optimal strategy, if no player $k \le n-2$ moves $m(k) = n$, then $m(n-1) \neq n$, since $n$ will clearly retaliate with $m(n) = n-1$, giving $n-1$ a 0% survival rate. But for $n=7$, $6$ is always eliminated, so he may be indifferent to choosing $m(6) = 7$ (though in this particular example, $m(6) = 7$ may not be optimal if it results in more people surviving than other moves.)
Perhaps we can reduce the problem if there is some $n'<n$ such that for each $k \le n'$, $m(k) \le n'$, but this doesn't immediately reduce to the problem for a smaller $n$ because the higher-indexed players can vote for one of the first $n'$ players as well.