How far can probability intransitivity be stretched? Once upon a time I read about nontransitive dice - sets of dice where "is more likely to roll a higher number than" is not a transitive relation. After the surprise wore off, I wondered - just how far can this phenomenon be pushed? The linked Wikipedia page has a section called "Freivald's investigation" which states that if $n$ dice are arranged in a circle each with probability $p$ of being greater than the next in line, then $p<3/4$ (with $p$ otherwise allowed arbitrarily close). However, it has the infamous tag of [citation needed] and I haven't been able to find any references. But a much more general question is possible.
If we have $n$ random variables, all independent, labelled $1,2,\dots, n$, and we denote by $p_k$ the probability $P(X_k > X_{k+1})$ (with the index $n+1$ cycled around to $1$), then we can speak of the vector $\vec{p}=(p_1,\dots,p_n)\in(0,1)^n$. This raises the question: what is the shape of the space $V \subset (0,1)^n$ of all possible $\vec{p}$'s? In particular, I think there might be a symmetric function such that $V$ is the region bounded by the level sets of $f(\vec{x})$ and $f(\vec{1}-\vec{x})$ for some $f:\mathbb{R}^n\to\mathbb{R}$, but I'm not certain, and of course it seems like it would be impossible to find such an $f$ explicitly. (Also, I'm not sure if the answer would be different for continuous and for discrete situations, or in mixed cases, but all combinations sound interesting.)
 A: We can assume without loss of generality that all numbers are different, since otherwise we could make them slightly different without decreasing the probability for any die to be greater than any other die (since equal results don't contribute to that probability).
Roughly speaking, if the median on the losing die is greater than the median on the winning die, then the lower half of the winning die can't beat the upper half of the losing die, so for the median to increase, we must have $p<3/4$. There are some details to fill in for even and odd numbers of sides; the result is that $p\le3/4-(n/2+\alpha)/n^2$, where $n$ is the number of sides and $\alpha=0$ for even $n$ and $\alpha=1/4$ for odd $n$. This goes to $3/4$ as $n$ goes to infinity.
The number at any rank other than the median can be more easily increased, since you can let all the numbers below it on the winning die beat all the numbers below it on the losing die, and the same for the numbers above it, and the restriction this imposes is tightest at the median. Thus, for each rank, there is an admissible combination to increase the number at that rank.
Now put $n$ dice with $n$ sides in a cycle, and impose a partial order on the as yet unknown numbers by requiring that in each pair of consecutive dice the numbers form one of the order patterns constructed above, with the number at rank $k$ being increased in step $k$ (beginning at the highest rank). To see that this partial order is a total order, note that there is no restriction requiring any number in the shrinking lower parts below the ranks being increased to be greater than any number in the growing upper parts above the ranks being increased. Thus there are no cycles in this order (this is easy to see if you draw out its graph for $n=3$ or $4$), so we can find suitable numbers by topological sorting. Thus we can always construct a cycle with $n$ dice with $n$ sides for $p$ as above; in fact this construction makes it rather straightforward to derive suitable numbers.
Here are examples for $n=3$ and $n=4$ (the latter in hexadecimal), with an attempt to visualize the acyclicity of the order graph:
1 2 8
|/ /|
0 6 7
 /|/|
3 4 5
|/|/
1 2 8
|/ /|
0 6 7

3 4 5 F
|/|/ /|
1 2 D E
|/ /|/|
0 A B C
 /|/|/|
6 7 8 9
|/|/|/
3 4 5 F
|/|/ /|
1 2 D E
|/ /|/|
0 A B C

A: This is a great question, and answered in essentially those terms in this paper from 1965:
Trybuła, S.
On the paradox of $n$ random variables.
Zastos. Mat. 8 (1965), 143–156.
Three he gets a sequence of inequalities on the probabilities you're asking for, but isn't able to solve them concretely.
The case of $n$ variables arranged cyclically is solved by Bogdanov in 2010, and again in a very recent paper:
Komisarski, Andrzej
Nontransitive random variables and nontransitive dice.
Amer. Math. Monthly 128 (2021), no. 5, 423–434.
https://www.tandfonline.com/doi/abs/10.1080/00029890.2021.1889921?journalCode=uamm20
The answer is that with $n$ dice you cannot beat $1-\frac{1}{4 \cos^2 (\pi/(n+2))}$. Komisarksi gives a very nice geometric argument.
The $3/4$ bound you mention in general was found already by Trybuła.
