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

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?

How many dice? [Dice Sculptures by Tony Cragg] |

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 ...

## No comments:

## Post a Comment