Consider the set of four dice shown below. Like regular playing dice, each has six sides. However, instead of each die having the labels $1-6$ only once, each die has labels $0-6$ on multiple faces. These set of dice are known as Efron's Dice and they are a bit unintuitive.
 |
| Efron's dice. [Wolfram] |
To start, take dice $A$ and $B$. $A$ rolls higher than $B$ with probability $\frac{2}{3}$ ($B$ rolls $3$ with probability $1$ but $A$ rolls greater than $3$ with probability $\frac{4}{6} = \frac{2}{3}$). From this we can say that $A$ beats $B$ since it rolls higher more than the half the time.
Next, consider dice $B$ and $C$. $B$ beats $C$ since $B$ rolls higher than $C$ with probability $\frac{2}{3}$ ($C$ rolls $2$ with probability $\frac{4}{6} = \frac{2}{3}$). Unsurprisingly, it also turns out that $C$ beats $D$ ($C$ rolls higher than $D$ with probability $\frac{2}{6} + \frac{4}{6} \times \frac{3}{6} = \frac{12 + 12}{36} = \frac{2}{3}$).
But what about $A$ and $D$? Since $A$ beats $B$, $B$ beats $C$, and $C$ beats $D$, one might expect that $A$ beats $D$. However, it turns out that this is not true. Instead, $D$ beats $A$ (with probability $\frac{3}{6} + \frac{3}{6} \times \frac{2}{6} = \frac{18 + 6}{36} = \frac{2}{3}$).
This property is known as nontransitivity (or intransitivity) and it is what makes this set of dice peculiar and suitable for some trickery. For example, according to Wikipedia, Warren Buffet once tried to play a game of dice against Bill Gates using Efron's dice. In Mr Buffet's game, each player got to choose one of the four dice to use, and being a charitable man, he insisted that his opponent Mr Gates pick first. Going second meant that Mr Buffet could select the die to beat Mr Gates' with probability greater than a half. Quite the ploy (although apparently not enough to fool Mr Gates)!
Knowing that Efron's dice exist, a natural question arises: can we find other sets of nontransitive dice? As it turns out, we can.
But what about $A$ and $D$? Since $A$ beats $B$, $B$ beats $C$, and $C$ beats $D$, one might expect that $A$ beats $D$. However, it turns out that this is not true. Instead, $D$ beats $A$ (with probability $\frac{3}{6} + \frac{3}{6} \times \frac{2}{6} = \frac{18 + 6}{36} = \frac{2}{3}$).
This property is known as nontransitivity (or intransitivity) and it is what makes this set of dice peculiar and suitable for some trickery. For example, according to Wikipedia, Warren Buffet once tried to play a game of dice against Bill Gates using Efron's dice. In Mr Buffet's game, each player got to choose one of the four dice to use, and being a charitable man, he insisted that his opponent Mr Gates pick first. Going second meant that Mr Buffet could select the die to beat Mr Gates' with probability greater than a half. Quite the ploy (although apparently not enough to fool Mr Gates)!
Knowing that Efron's dice exist, a natural question arises: can we find other sets of nontransitive dice? As it turns out, we can.
How many unique dice are there?
 |
To start looking for Efron's dice, and other sets of nontransitive dice, we first need to determine the number of unique dice with $L$ labels and $S$ sides.
One possible representation for a die is as a vector of non-negative integers of size $L$ which sums to $S$. That is, $\mathbf{d} \in \mathbb{N}_{\geq 0}^L$ where $d_i$ is the number of sides with label $i$ and $\sum_{i = 0}^{L - 1} d_i = S$. An alternative representation useful for counting is the cumulative sum of this vector denoted by $\mathbf{\tilde d}$, where $\tilde d_i$ is the number sides with labels less than or equal to $i$ ($\tilde d_{L - 1} = S$).
To start, lets answer a simpler question: how many dice are there with four sides and two labels? For $L = 2$ and $S = 4$, each die is a vector of the form $\mathbf{\tilde d} = [\tilde d_0, 4]$. Since $0 \leq \tilde d_0 \leq 4$, there are $5$ possible dice. Letting $N_{L, S}$ denotes the number of dice with $L$ labels and $S$ sides, then $N_{2, 4} = 5$ and in general $N_{2, S} = S + 1$.
What about if $L = 3$? Each die is now a vector of the form $\mathbf{\tilde d} = [\tilde d_0, \tilde d_1, 4]$. If $\tilde d_1 = 4$ then $0 \leq \tilde d_0 \leq 4$ (as before) and we have $5$ dice. If $\tilde d_1 = 3$ then we have $4$, and so on, giving a total of $5 + 4 + 3 + 2 + 1 = 15$ dice. That is, $N_{3, 4} = \sum_{i = 0}^4 N_{2, i}$ and in general $N_{L, S} = \sum_{i = 0}^S N_{L - 1, i}$ (num_unique_dice).
So how many unique dice are there for $L = 7$ and $S = 6$ (Efron's dice)? $N_{7, 6} = 924$. That is, there are only $924$ unique distributions which arise from placing $7$ labels (with repetition) on a six-sided die (which is $7^6 > 10^5$ possible dice if every side is identifiable)!
What beats what?
A similar recurrence relation to that used to count the number of unique dice can be used to enumerate them (enumerate_unique_dice). Given the matrix of all $N_{L, S}$ dice, it is subsequently necessary to determine for every pair of dice, how many times the first rolls higher than the second.
Consider two dice $A$ and $B$ with vectors $\alpha \in \mathbb{N}_{\geq 0}^L$ and $\beta \in \mathbb{N}_{\geq 0}^L$. The number of times $A$ rolls higher than $B$, $w_{A, B}$ is given by:
$$w_{A, B} = \sum_{b = 0}^{L - 1} \sum_{a = b + 1}^{L - 1} \beta_b \alpha_a = \sum_{b = 0}^{L - 2} \beta_b \sum_{a = b + 1}^{L - 1} \alpha_a$$
The wins matrix $W$, where $w_{i, j}$ is the number of times dice $i$ rolls higher than dice $j$, is therefore easily evaluated using a single matrix multiplication (num_wins_matrix).
Defining and optimising the objective
Let the best nontransitive dice sets be those for which the sum of probabilities of each die rolling higher than the next is maximum, subject to the constraint that the minimum probability of a die rolling higher than the next is at least greater than a half. As will be shown, this can be solved using Dynamic Programming with a method akin to to the min-sum algorithm.
Let $M$ denote the number of dice in the desired nontransitive set ($M = 4$ for Efron's dice), and let $\mathbf{l} \in \mathbb{N}_{\geq 0}^M$ denote the vector of selected dice indices. Also, for all $w_{i, j} < \frac{S^2}{2}$ set $w_{i, j} \leftarrow -M S^2$. The best nontransitive dice sets then maximise:
\begin{equation} \sum_{m = 0}^{M - 1} w_{l_m, l_{m^+}} \label{eq:e} \end{equation}
where $m^+ \equiv (m + 1) \mod M$.
Naive optimisation of $\eqref{eq:e}$ requires enumerating over $N_{L, S}^M$ possible $\mathbf{l}$. For Efron's dice, this is $924^4 > 10^{11}$ configurations. Instead, efficient optimisation can be achieved by splitting the $\max_\mathbf{1}$ and evaluating the innermost max-sum matrices one at a time. For example, for $M = 4$ the three max-sum matrices are $S^0$, $S^1$, and $S^2$:
\begin{align*}
\max_\mathbf{l}\sum_{m = 0}^{3} w_{l_m, l_{m^+}} &=
\max_\mathbf{l} \left\{ w_{l_0, l_1} + w_{l_1, l_2} + w_{l_2, l_3} + w_{l_3, l_0} \right\} \\
&= \max_{l_0}\max_{l_1} \left\{ w_{l_0, l_1} + \max_{l_2} \left[w_{l_1, l_2} + \max_{l_3} \left( w_{l_2, l_3} + w_{l_3, l_0} \right) \right] \right\} \label{eq:e-l3} \\
&= \max_{l_0}\max_{l_1} \left\{ w_{l_0, l_1} + \max_{l_2} \left[w_{l_1, l_2} + S^0_{l_2, l_0} \right] \right\} \\
&= \max_{l_0}\max_{l_1} \left\{ w_{l_0, l_1} + S^1_{l_1, l_0} \right\} \\
&= \max_{l_0} S^2_{l_0, l_0} \label{eq:e-l0}
\end{align*}
Importantly, if the maximum is less than zero, then a nontransitive set where each die rolls higher than the next with probability greater than a half is not possible. However, if the maximum is greater than or equal to zero, all maximum $\mathbf{l}$ are found by iterating over the arguments for each $\max$ (efrons_dice). Because of the symmetry of the objective, all circular permutations are found.
Finally, in the above formulation, the probability of each die rolling higher than the next does not have to be equal. To achieve this for a given number $n$, all entries in $W$ not equal to $n$ can simply be set to $-M S^2$.
Results: Finding Efron's dice
Running efrons_dice.py with no arguments ($S = 6$, $L = 7$, and $M = 4$) produces approximately $115,000$ lines of output. In this:
- $25 (= \frac{100}{4})$ unique nontransitive sets of dice, where the probability of each die rolling higher than the next does not have to be equal, are found. The first is: $A = (4, 4, 4, 4, 4, 4)$, $B = (3, 3, 3, 3, 3, 3)$, $C = (2, 2, 2, 2, 6, 6)$, and $D = (1, 1, 5, 5, 5, 5)$, where $A$ beats $B$ with probability $1$, $B$ beats $C$ with probability $\frac{2}{3}$, $C$ beats $D$ with probability $\frac{20}{36} = \frac{5}{9}$, and $D$ beats $A$ with probability $\frac{2}{3}$.
- $69$ unique sets of dice where the probability of each die rolling higher than the next is $\frac{21}{36} = \frac{7}{12} < \frac{2}{3}$ are found. The first is: $A = (2, 3, 3, 3, 3, 6)$, $B = (2, 2, 2, 2, 5, 6)$, $C = (1, 1, 1, 5, 5, 5)$, and $D = (0, 3, 4, 4, 4, 4)$.
- $1$ unique set of dice, where the probability of each die rolling higher than the next is $\frac{24}{36} = \frac{2}{3}$ is found. This set is Efron's dice: $A = (0, 0, 4, 4, 4, 4)$, $B = (3, 3, 3, 3, 3, 3)$, $C = (2, 2, 2, 2, 6, 6)$, and $D = (1, 1, 1, 5, 5, 5)$.
 |
| Found. [Ocellaris Clownfish] |
Conclusions
There are a lot of nontransitive dice sets and posing the search as a discrete optimisation problem is a nice way of finding some good ones!
My favourite is the set for $S = 3$, $L = 5$ and $M = 3$: $A = (2, 2, 2)$, $B = (1, 1, 4)$, and $C = (0, 3, 3)$, where $A$ beats $B$ with probability $\frac{2}{3}$, $B$ beats $C$ with probability $\frac{5}{9}$, and $C$ beats $A$ with probability $\frac{2}{3}$.
Until next time ...
