What are the chances that the Enemy/Defender game has a stable solution?

Question

There is a game called Enemy/Defender that you might play with kids. The setup is as follows:

Everyone stands in a circle. You say, "Look around the circle and select someone (at random) to be your enemy. Now pick a different person to be your defender. When I say 'Go!', you have to position yourself so that your defender is between you and your enemy... Go!"

The players will run around frantically until you stop the game. On rare occasions though, there is a stable configuration that occurs where everyone is standing in a line and doesn't need to move at all.

The question is: For a game with n players with enemies and defenders chosen uniformly at random, what is the probability that a stable configuration exists?

I'm finding it surprisingly difficult to solve this or even simulate it efficiently. Here's some basic insights:

• Even if there is a solution where everyone is not standing in a line, we can collapse it to a line without breaking the order, so we only need to consider permutations of the players as solutions.
• The game needs at least 3 players, but no solution exists for 3 players. This is easy to see because the middle player in any proposed solution must be adjacent to their enemy. For 4 or more players, there is a nonzero chance a solution exists.
• For any solution, the players at either end of the line cannot be anyone's defenders
• If everyone chooses the same defender, then a stable solution exists iff you can partition the remaining players into two sets such that everyone's enemy is in the opposite set (and the common defender's enemy and defender are in the same set).

Some results from brute force simulation:

• 4 players : 8.3366% of 10000000 games
• 5 players : 12.2495% of 1000000 games
• 6 players : 16.6140% of 100000 games
• 7 players : 21.5500% of 10000 games
• 8 players : 28.1000% of 1000 games
• 9 players : 39.0000% of 100 games

I would be very surprised if a succinct closed form solution exists, but even some insight on how to simulate it faster would be appreciated.

Answer 1

Not an answer but some hopefully interesting comments.

The problem as asked considers a fixed set of choices of enemies and defenders (let's say a fixed "ED choice") among $n$ players, and asks whether there is a permutation of $\{1,\dots,n\}$ that is stable (in the sense that everybody's defender is between them and their enemy).

For a moment, let's reverse the situation: let's fix a permutation of $\{1,\dots,n\}$ (by symmetry, we might as well take the trivial permutation $\{1,\dots,n\}$ itself) and ask: how many of the $\bigl( (n-1)(n-2) \bigr)^n$ ED choices are stable for that permutation? or equivalently, if we make an ED choice uniformly at random, what is the probability that it is stable?

The nice thing about this random sample is that the enemy/defender choices of the $n$ players are all mutually independent. The probability that player $j$'s defender is between them and their enemy is $$ \frac{(j-1)(j-2)/2+(n-j)(n-j-1)/2}{n(n-1)/2} \cdot \frac12, $$ since the first fraction is the probability that the enemy and defender are on the same side of $j$, and the $\frac12$ is the subsequent probability that the defender is closer than the enemy. In other words, the probability that a randomly chosen ED choice is stable is $$ 2^{-n} \prod_{j=1}^n \frac{(j-1)(j-2)+(n-j)(n-j-1)}{n(n-1)}. $$ Considering the expression $$ \frac1n \sum_{j=1}^n \log\frac{(j-1)(j-2)+(n-j)(n-j-1)}{n(n-1)}, $$ we can approximate it by Riemann sums and show that as $n\to\infty$, the expression tends to $$ \int_0^1 \log(1+2x+2x^2)\,dx = -\frac{4-\pi}2. $$ It follows that the probability that an ED choice is stable is, for large $n$, approximately $$ 2^{-n} \prod_{j=1}^n \frac{(j-1)(j-2)+(n-j)(n-j-1)}{n(n-1)} \approx C^{-n} \text{ where } C = 2e^{(4-\pi)/2} \approx 3.072. $$

Now let's go back to thinking about particular ED choices and which permutations are stable for them. By linearity of expectation, it follows that the expected number of stable permutations for a given ED choice is $\approx n!C^{-n}$, which is still very large. If one could find an upper bound for the variance of the number of stable of permutations (for a uniformly randomly chosen ED choice), one could use Chebyshev's inequality to get a lower bound for the probability that an ED choice has a stable permutation. In particular, if the standard deviation is $O(n!(C-\varepsilon)^{-n})$, then the probability of an ED choice having a stable permutation would tend to $1$ as $n\to\infty$.

No matter how large $n$ is, there are certainly some ED choices that have no stable permutations (for example, if players $1$, $2$, and $3$ all choose one another as their enemies and defenders). It's always possible that there's some combinatorial/algebraic construction that provides a large set of ED choices with no stable permutations. This is the constant struggle with forming intuition: is the phenomenon essentially random or is it correlated with some construction?