In graph theory, a tournament is a graph where every pair of vertices are connected by exactly one directed edge.
In this problem, each tournament represents the possible outcomes of a two-player competitive game. Each vertex represents a strategy a player can employ. Each edge represents the outcome of an individual game. The winner of the game is the player that uses the strategy that the arrow is pointing to. By extension, the loser of the game is the player that used the strategy that the arrow is pointing away from. When two players with the same strategy compete against each other it is a tie.
In the context of this problem each vertex in the tournament also has a real number associated with it. The sum of all of these numbers equals one and each number is greater than or equal to zero. These numbers represent the fraction of the total player base that is using that particular strategy. These numbers are equal to the variables $v_1,v_2,v_3,…,v_n$. Where $n$ is the number of vertices.
In each round with this given setup, all players are paired randomly and play a game. There are a total of $\frac{n(n+1)}{2}$ pairings types in each round. There are $n$ pairing types where both players use the same strategy. The fraction of players in this type of pairing is $v_a^2$, where $a$ is the index of the strategy being used. There are $\frac{n(n-1)}{2}$ pairing types where the players are using a different strategy from one another. The fraction of players in this type of pairing is $2v_bv_c$, where $b$ and $c$ are the indices of the strategies being used ($b\neq c$). All players use the same approach when changing strategies from one round to the next. If a player loses they change strategies to the one they lost to, otherwise the players stay on the same strategy they are currently on.
Let's look at the following example:
Tournament 1
Chart 1
$$
\begin{array}{c|rrr}
& v_1 & v_2 & v_3\\ \hline
v_1 & \frac{1}{4} & \frac{1}{6} & \frac{1}{12}\\
v_2 & \frac{1}{6} & \frac{1}{9} & \frac{1}{18}\\
v_3 & \frac{1}{12} & \frac{1}{18} & \frac{1}{36}\\
\end{array}
$$
Tournament 2
Tournament 1 is our initial setup for the games. Tournament 2 is tournament 1 after one round of games. Chart 1 indicates the fraction of players in the first round of play using a particular strategy (indicated by the row label), while the opponent uses another specific strategy (indicated by the column label). The sum of the values in the $v_1$ row is equal to $\frac{1}{2}$ which is identical to the value for $v_1$ in tournament 1. The same can be said for $v_2$ and $v_3$. The value of the $v_1$ value in tournament 2 is the sum of the values $(v_1,v_1), (v_1,v_2),$ and $(v_2,v_1)$ from chart 1. These values are when either both players used the $v_1$ strategy or the $v_1$ strategy won in round one. The sum of the values in chart 1 when both players used $v_2$ or when the $v_2$ strategy won is equal to the $v_2$ value in tournament 2. The same can be said for $v_3$.
A stable tournament is a tournament where the fraction of players in each strategy stays the same from round to round and all strategies have a non-zero fraction of players. The following is an example of a stable tournament:
Tournament 3
Chart 2
$$
\begin{array}{c|rrr}
& v_4 & v_5 & v_6\\ \hline
v_4 & \frac{1}{9} & \frac{1}{9} & \frac{1}{9}\\
v_5 & \frac{1}{9} & \frac{1}{9} & \frac{1}{9}\\
v_6 & \frac{1}{9} & \frac{1}{9} & \frac{1}{9}\\
\end{array}
$$
There are infinitely many stable tournaments. There is an infinite set of stable
tournaments that follow a simple construction pattern. This set of tournaments I refer to as basic odd tournaments. Basic odd tournaments have an odd number of vertices. For each positive odd number, there is exactly one non-isomorphic basic odd tournament. The basic odd tournament with three vertices is Tournament 3. If the number of vertices in the basic odd tournament is $2m+1$, then there are $m$ arrows pointing to each vertex.
Basic odd tournaments can be constructed in the following way: First, arrange the vertices in a circle then pick a single vertex. The next $m$ vertices following the chosen vertex in the clockwise direction are each connected to the chosen vertex with an arrow for each of the $m$ vertices. The arrows start from one of the $m$ vertices and point towards the chosen vertex. Repeat this process for each vertex in the tournament so that each vertex becomes the chosen vertex exactly once.
Below is a visual representation of this process for the $7$ vertex tournament:
Tournament 4 (+ construction steps)
The basic odd tournaments have the same fraction of players using each strategy. The following is a proof of this fact:
Any stable tournament must have the same values from round to round. Basic odd tournaments have $2m+1$ vertices. These two facts can be used to construct an equation for any vertex in the tournament. For $v_1$ in particular, the value for $v_1$ can be expressed differently by using round 1 vertex values in a game to represent the $v_1$ value in round 2. These are the pairings where both players used the $v_1$ strategy or the $v_1$ strategy won the game in round 1.
$$eq(1).\quad v_1=v_1^2+2v_1v_2+2v_1v_3+2v_1v_4+…+2v_1v_{m+1}$$
Both sides can be divided by $v_1$ to get:
$$eq.(2)\quad 1=v_1+2v_2+2v_3+2v_4+…+2v_{m+1}$$
It was stated earlier that the vertex values in a tournament sum to 1. Therefore:
$$eq.(3)\quad 1=v_1+v_2+v_3+v_4+…+v_{2m+1}$$
Now subtract eq.(3) from eq.(2).
$$eq.(4)\quad 0=v_2+v_3+v_4+…+v_{m+1}-v_{m+2}-v_{m+3}-v_{m+4}-…-v_{2m+1}$$
Next, move all negative terms to the other side.
$$eq.(5)\quad v_{m+2}+v_{m+3}+v_{m+4}+…+v_{2m+1}=v_2+v_3+v_4+…+v_{m+1}$$
eq.(1) was created by representing $v_1$ in two different ways. That equation was manipulated to show that the two sets of vertices in the tournament are equal (eq.(5)). This process can be applied to the $v_{m+2}$ vertex and a similar equation can be obtained.
$$eq.(6)\quad v_2+v_3+v_4+…+v_{m+1}=v_{m+3}+v_{m+4}+…+v_{2m+1}+v_1$$
Notice that the right side of eq.(5) is equal to the left side of eq.(6). By the transitive property, the left side of eq.(5) is equal to the right side of eq.(6).
$$eq.(7)\quad v_{m+2}+v_{m+3}+v_{m+4}+…+v_{2m+1}=v_{m+3}+v_{m+4}+…+v_{2m+1}+v_1$$
Most of the terms in eq.(7) cancel can out.
$$eq.(8)\quad v_{m+2}=v_1$$
The process that was applied to $v_1$ and $v_{m+2}$ to establish the equality between them can be applied to $v_2$ and $v_{m+2}$.
$$eq.(9)\quad v_2=v_{m+2}$$
By transitive property:
$$eq.(10)\quad v_1=v_2$$
This process is inductive. Equality can be established for all of the vertices in the tournament starting with $v_1$ then continuing sequentially in order until $v_1=v_2=v_3=…=v_{2m+1}$. This implies all vertices in basic odd tournaments are equal to $\frac{1}{2m+1}$.
There are more stable tournaments that can be constructed using the basic odd tournaments. To show how these tournaments are constructed a new graph operator must be introduced. This operator has three inputs. Two graphs $G$, $H$, and a vertex $u$ in graph $G$. The output of the operator is graph $I$. Graph $I$ is graph $G$ but with vertex $u$ replaced with graph $H$. For each edge in graph $G$ that was connected to vertex $u$ and another vertex $v$, there is a set of edges connected to vertex $v$ in graph $I$. Each set contains an edge for each vertex in (the newly added) $H$, they are connected to a vertex in $H$ (the subset of $I$) and vertex $v$. If the graphs $G$ and $H$ are directed graphs and an edge that was pointed towards vertex $u$ in graph $G$ then the corresponding edges point towards the subgraph $H$ in graph $I$. Similarly, if the edges that are connected but pointing away from vertex $u$ in graph $G$ then the corresponding edges in graph $I$ connect and point away from subgraph $H$. An example of this operator being used is shown below. The middle graph is replacing vertex $4$ in the left graph to create the right graph.
graphs 1 2 and 3 (from left to right)
When this operator is used on basic odd tournaments new stable tournaments can be created, and the fraction of players in each strategy can easily be calculated. All graphs that can be created by only using basic odd tournaments and this operator are trivial tournaments. Below are all of the seven vertex trivial tournaments with the fraction of players in each strategy labeled on each vertex.
seven vertex trivial tournaments
The trivial tournament with $\frac{1}{7}$ of players using each strategy is just the basic odd tournament with seven vertices. (Tournament 4) The trivial tournament with four strategies with $\frac{1}{5}$ of players and the other strategies with $\frac{1}{15}$ players is the three vertex basic odd tournament replacing a vertex in the basic odd tournament with five vertices. The trivial tournament with two strategies with $\frac{1}{3}$ of players and the other strategies with $\frac{1}{15}$ players is the five vertex basic odd tournament replacing a vertex in the basic odd tournament with three vertices. The trivial tournament with one strategy with $\frac{1}{3}$ of players and the other strategies with $\frac{1}{9}$ players is two-three vertex basic odd tournaments replacing two vertices in the basic odd tournament with three vertices (, using the operator twice). The trivial tournament with two strategies each with $\frac{1}{3}$ of players, two strategies each with $\frac{1}{9}$ of players, and the rest of the strategies with $\frac{1}{27}$ is a three vertex basic tournament replacing a vertex in the three vertex basic odd tournament, then a three vertex odd tournament replaces one the strategies with $\frac{1}{9}$ of players. When replacing a vertex with a basic odd tournament the player base gets divided equally among the new vertices.
Below is a chart that shows how many trivial tournaments there are with a given number of vertices. I am certain about the number of trivial tournaments with 3-9 vertices but I am less sure about the entry with 11 vertices. As the number of vertices becomes larger and larger it becomes more difficult to make sure that no two tournaments are repeated and without missing any.
Chart 3
$$
\begin{array}{|c|c|} \hline
\text{Vertices} & \text{Number of trivial tournaments}\\ \hline
3&1\\ \hline
5&2\\ \hline
7&5\\ \hline
9&16\\ \hline
11&60\\ \hline
\end{array}
$$
A non-trivial tournament is a tournament that cannot be constructed only by using basic odd tournaments and the operator.
Are there any non-trivial stable tournaments?
I’m going to divide the question from the title into three parts.
A) Are there any stable non-trivial tournaments that have an odd number of vertices that have the same distribution of players as a trivial tournament?
Two tournaments can have the same distribution of players, but not be isomorphic to one another. The nine vertex basic odd tournament has the same distribution of players as the tournament where each vertex in a three vertex basic odd tournament was replaced with the three vertex basic odd tournament. These two tournaments are not isomorphic to one another.
B) Are there any non-trivial tournaments that have an odd number of vertices that have a different distribution of players from any trivial tournament?
C) Are there any stable tournaments with an even number of vertices?
Best Answer
(A) Some more solutions with uniform distributions
It is easy to come by more stable tournaments on $2m+1$ vertices with a uniform distribution of $\frac1{2m+1}$ on each vertex. Any regular tournament will do! To see this, note that if we start with $v_1 = v_2 = \dots = v_{2m+1}$ in one round, then in the next round we will have $$ v_i \gets v_i^2 + \sum_{j \in N^+(i)} 2v_i v_j = \frac1{(2m+1)^2} + m \cdot \frac{2}{(2m+1)^2} = \frac1{2m+1} $$ where $N^+(i)$ denotes the out-neighborhood of vertex $i$, so by assumption $|N^+(i)|=m$ for all $i$.
The "basic odd tournament" is one way to construct a regular tournament on $2m+1$ vertices, but for large $m$ there are many: see OEIS sequence A096368 for their quickly growing count. The first new one appears with $7$ vertices:
To see that this is not isomorphic to the basic odd tournament, note that if you take any vertex here and look at the three vertices it points to, those three vertices go in a cycle. In the basic odd tournament, if you take any vertex and look at the three vertices it points to, they will not.
(B) Solutions with more unusual distributions
But the tournament above is not very interesting. With $7$ vertices, we also get the first tournament that's stable for its own mysterious and special reasons:
This cannot be obtained from a smaller regular tournament by the vertex blow-up operation, because of the denominator of $11$.
We can get a larger variety of stable tournaments by a sort of inverse of the vertex blow-up. Do the following:
(Here, $b$ is arbitrary, but should be at least $2a+1$ for step $4$ to be possible; then we can apply Landau's theorem to the vertices outside $T$ to make sure they have the desired outdegrees. I'm omitting the details.)
The result is a regular tournament on $2a+2b+1$ vertices, thus assigning $v_i = \frac1{2a+2b+1}$ for all $i$ will work.
Now, replace tournament $T$ by a single vertex $t$, getting a tournament on $2b+1$ vertices. In this tournament, setting $v_t = \frac{2a+1}{2a+2b+1}$ (combining the weights of all the vertices of $T$) and keeping all other vertices at $\frac1{2a+2b+1}$ is still stable! (It is crucial that every vertex outside $T$ has the same behavior against every vertex of $T$, for this to work - but with that condition, the equations practically don't change.)
To get a larger variety of distributions, do this with multiple "planted" tournaments $T_1, T_2, \dots$ instead of the single $T$. For example, the $7$-vertex tournament above with distribution $(1/11, 1/11, 1/11, 1/11, 1/11, 3/11, 3/11)$ can be obtained from an $11$-vertex regular tournament in which we planted two $3$-vertex stable tournaments $T_1$ and $T_2$, then shrank $T_1$ and $T_2$ to single vertices.
(C) There are no solutions with an even number of vertices
All of the solutions above give an odd number of vertices; in particular, there are no regular tournaments with a even number of vertices. (With $2m$ vertices, every vertex would have indegree and outdegree $m - \frac12$, which is nonsense.) In fact, there are also no stable tournaments with an even number of vertices!
To prove this, first take any stable tournament, and write its stable distribution $(v_1, v_2, \dots, v_n)$ in the form $v_i = \frac{p_i}{q_i} \cdot 2^{r_i}$, where $p_i, q_i$ are odd numbers and $r_i$ is an integer (not necessarily positive).
Then, replace the $i^{\text{th}}$ vertex by a stable tournament on $\frac{p_i}{q_i} \cdot q_1 q_2 \cdots q_n$ vertices (an odd integer). The value $v_i$ is split evenly among these vertices, so each of them has value $\frac{2^{r_i}}{q_1 q_2 \cdots q_n}$. If we do this for every $i$, then in the end, every vertex will have the same value, up to a factor which is a power of $2$: there is some common denominator $Q$ such that all vertices have values from the set $\{\frac1Q, \frac2Q, \frac4Q, \frac8Q, \dots\}$. This should still be a stable tournament (with a ginormous number of vertices).
In the ginormous tournament, take another look at the identity $$ v_i = v_i^2 + \sum_{j \in N^+(i)} 2v_i v_j. $$ First consider a vertex $i$ such that $v_i = 1/Q$; since we take $Q$ to be the least common denominator, some such vertex must exist. Multiplying through by $Q^2$ on both sides, we get $$ Q = 1 + \sum_{j \in N^+(i)} 2Q v_j $$ which shows that $Q$ must be odd.
Now suppose that there is any vertex $i$ such that $v_i = 2^k/Q$ for $k>0$. Take the above identity such a vertex and multiply through by $Q/v_i = Q^2/2^k$ on both sides; we get $$ Q = 2^k + \sum_{j \in N^+(i)} 2Q v_j. $$ Here, the LHS is odd, but the RHS is even: contradiction! So in fact all vertices must have $v_i = 1/Q$. This is only possible if the tournament is a regular tournament, which means that it has an odd number of vertices.
But to get there, we did a number of vertex blow-up operations which replaced one vertex by an odd number. This does not affect parity. So we must have started with an odd number of vertices: a stable tournament with an even number of vertices does not exist.