Building Sets of Permutation-Fair Dice

Abstract

We define what it means for a set of dice to be m/n permutation fair. We show how some collections of sets of m/n permutation-fair dice can be combined to create new sets of dice that are $(m+1)/n$ permutation fair. By applying this method recursively, we show that our method is generic. That is, it can be used to create sets of dice that are m/n permutation fair for all m and n. We show that our method is more efficient than what we call the concatenation construction, which is the only other known generic method for constructing sets of permutation-fair dice. We conclude by demonstrating how our method can be used to construct a set of five 120-sided dice that is permutation fair.

MSC:

• 60-02
• 60C05
• 60-08

1 Introduction

Many tabletop games are designed so that players take turns interacting with the game’s mechanisms. As such, the players need some way to determine the order in which they will take their turns, i.e. the turn order. For some games, the turn order can significantly affect how the players will play the game and the players will need a way to determine the turn order that is “fair”.

One option is to have each player roll a standard die. If no two players roll the same number then the results of their rolls can be used to determine a turn order, perhaps by specifying that players should take turns in descending order according to the values of their rolls. If two or more players do roll the same number, then those players can break the tie by rolling their dice again. With high probability, only a few rounds would be required to determine a complete turn order.

Suppose that, instead of using standard dice, each player uses a die from a set of n nonstandard dice with the following properties:

• No number appears on more than one face of any die in the set, so rolling this set of dice always yields a result with n distinct numbers.

• The face values are arranged such that if all n dice are rolled and then sorted according to the resulting values, then all $n!$ permutations of the dice are equally likely.

We will say that such a set of dice is permutation fair. By using a set of dice that is permutation fair, the players can determine the turn order for their game in a single round. Table 1 gives one example of a set $\mathcal{G}$ of dice that is permutation fair. This set was discovered by Eric Harshbarger and Robert Ford in 2010 (see [1]).

Table 1 A set of four 12-sided dice that are permutation fair.

*Die	Faces
	i	ii	iii	iv	v	vi	vii	viii	ix	x	xi	xii
a	1	8	11	14	19	22	27	30	35	38	41	48
b	2	7	10	15	18	23	26	31	34	39	42	47
c	3	6	12	13	17	24	25	32	36	37	43	46
d	4	5	9	16	20	21	28	29	33	40	44	45

Notice that if there are fewer than four players, then they can still use $\mathcal{G}$ to determine a turn order. This is because if a set of dice is permutation fair, then every subset of that set of dice is permutation fair as well. But what if there are more than four players? It has been shown (see [2]) that for all $n\in \mathbb{N}$ there are sets of n dice that are permutation fair. So, in principle, by using an appropriate set of permutation-fair dice any number of players can determine a turn order. In practice, the situation is more complicated because the best known generic constructions for permutation-fair sets produce dice with a prohibitively large number of faces.

For example, the construction in [2] produces a set of n dice that have ${(n!)}^{n-1}$ faces. When n = 4 this construction therefore yields a set of four 13,824-sided dice. When n = 5 it yields a set of five 207,360,000-sided dice. Recall, however, that we have seen that there exists a set of four 12-sided dice that are permutation fair. It is then natural to ask, for each n, what is the minimum number of sides necessary to construct a set of n permutation-fair dice? Can we find examples that realize this lower bound? If not, what are the smallest examples that we can find?

Our Contributions

In this paper, we will explore the answers to these questions. We will introduce a novel technique that can be used to construct sets of relatively small dice that are permutation fair. In particular, we will describe how this technique can be used to construct a set of five 120-sided dice that is permutation fair. To the best of our knowledge, our construction is the most efficient known construction for a set of five dice that are permutation fair. The best previously known construction (see [1]) requires five 180-sided dice while the generic construction mentioned above would require five 207,360,000-sided dice.

Our approach to the problem involves working with sets of dice that satisfy weaker symmetry constraints than those required for permutation-fair dice. More precisely, we consider sets of n dice that have the property that every subset of m of those dice is permutation fair. We say that such a set of dice is m/n permutation fair. Observe that the property that we have called permutation fairness to this point is equivalent to a set of dice being n/n permutation fair. Our construction is predicated on the observation that, by combining carefully chosen sets of dice that are m/n permutation fair, we can construct a set of dice that is $(m+1)/n$ permutation fair.

We formulate the problem of choosing sets of dice that are m/n permutation fair to work with as the solution to a integer linear programming (ILP) problem. This allows us to use existing implementations of algorithms to solve ILP problems to find suitable sets of dice or prove that no such sets exist. In our work, we used the ILP solver CBC (see [3]). We used the Python package PuLP (see [4]) to describe our problems, interface with the ILP solver, and process the resulting output.

Practical Considerations

There are many other efficient ways in which a group of players could fairly determine a turn order. These include simply identifying each player with a unique card, shuffling those cards together, and then dealing the cards out one at a time to determine the turn order. This protocol is simple, efficient, and will never require more than a single round to execute. Even the protocol using standard dice described above will be sufficient in most cases because the probability that more than a few rounds will be required is vanishingly small.

While the motivating problem might be more easily solved by the other methods suggested, there is still an important distinction which should be made. Fairly determining a turn order is a proxy for a particular kind of resource allocation problem. At the conceptual level, permutation-fair dice are a solution for an environment which has no central authority and which requires an asynchronous protocol with fixed runtime.

2 Related Work

According to [1], the earliest work on permutation-fair dice was motivated by a question asked by James Ernest in 2010. He asked if it might be possible to construct a set of dice with somewhat nebulously defined “go first” properties. Eric Harshbarger and Robert Ford started working on the problem at that time and together are responsible for many of the fundamental results in the field.

Types of Fairness

Among their earliest contributions was to establish a taxonomy of three different kinds of fairness that a set of “go-first dice” might exhibit.

1. Go-first fairness: A set of dice is go-first fair if, when all of the dice in the set are rolled, every die has an equal probability of displaying the largest value.

2. Place fairness: A set of dice is place fair if, when all of the dice in the set are rolled and then sorted according to the resulting values, every die has an equal probability of ending up in each place in the resulting ordering.

3. Permutation fairness: A set of dice is permutation fair if, when all of the dice are rolled and then sorted according to the resulting values, every possible ordering of the dice occurs with equal probability.

Notice that permutation fairness implies place fairness and place fairness implies go-first fairness. As such, as discussed in the introduction, we will focus our attention on the search for sets of dice that are permutation fair.

Size Constraints

During their initial investigations, Harshbarger and Ford also identified the following condition that a set of permutation-fair dice must satisfy.

Proposition 1.

If $\mathcal{S}$ is a set of n d-sided dice that is permutation fair and $\left\{p_i\right\}$ are the distinct prime factors of $n!$, then $\prod _i{p}_i|d$.

Proof.

There are dⁿ equally likely possible outcomes when the dice in $\mathcal{S}$ are rolled. Because $\mathcal{S}$ is permutation fair, we can partition these outcomes into $n!$ equal parts and so we must have $n!|d^n$. So, for all i we must also have $p_i|d^n$. Therefore for all i we have $p_i|d$ and the result follows immediately. □

Among other things, Proposition 1 sets a lower bound for the size of the dice in a set that is permutation fair. Notably, we see that if $\mathcal{S}$ is a set of five d-sided dice that is permutation fair, then $d\ge 30$.

Construction Methods

The first sets of permutation-fair dice were discovered using a combination of computer searches and bespoke mathematical analyses (see [1]). Since that time, however, at least three construction methods have been devised.

• Induction Construction: This construction (see [5, 6]) provides a way to augment a set of n/n permutation-fair dice to create a set of $(n+1)/(n+1)$ permutation-fair dice. A curious feature of the sets of dice created via this method is that they are often inhomogeneous. That is, sets that can be realized using dice that are not all the same size. The induction construction is believed to have been originally used by Paul Vanetti before being described more fully by Robert Ford.

• Binary Construction: This construction (see [5]) identifies a class of dice that can represented by an array of bits. It can be shown that there are constraints that such an array must satisfy if it is to represent a set of dice that are go-first fair. Furthermore, it is possible to efficiently search the space of candidates that satisfy these constraints to identify sets of binary dice that are place fair or permutation fair. The binary construction was originally described by James Grime and Brian Pollock who used this method to find a set of five 60-sided dice that are place fair.

• Concatenation Construction: This construction (see [2]) provides a way to augment a set of m/n permutation-fair dice to create a set of $(m+1)/n$ permutation-fair dice. This method can be used to build sets of n d-sided dice that are m/n permutation fair where $d={(n!)}^{m-1}$. The concatenation construction was originally described by Tomáš Gavenčiak and Václav Rozhoň.

The techniques presented in this paper are a refinement of the concatenation construction. The concatenation construction can be understood as a sequence of operations, each of which multiplies the number of sides on the dice in the resulting set by $n!$. We show how to reduce the cost of some of these operations. As an extreme example, consider the case of augmenting a set of $3/n$ permutation-fair dice to create a set of $4/n$ permutation-fair dice. Using the concatenation construction, the multiplier associated with this operation would be $n!$. Using our improvements, however, for all n the multiplier associated with this operation is 2.

Other Work

Permutation-fair dice are a subclass of nonstandard dice. While the study of permutation-fair dice is a relatively new field, there is an extensive body of work addressing the properties of other types of nonstandard dice.

One particularly rich vein can be traced back to a series of three papers by Steinhaus and Trybuła in the 1960s (see [7, 8], and [9]). These papers establish some fundamental properties of what are known as nontransitive dice. This work was popularized by Martin Gardner in an article written for the Mathematical Games column in Scientific American in 1970 (see [10]).

Nontransitive dice are often used as an example of a “paradoxical” phenomenon that can occur when considering three or more random variables. To wit, suppose that for all pairs of random variables (X, Y) we write $X\succ Y$ if $\mathbf{P}\{X>Y\}>1/2$. If X and Y represent two dice, then the statement $\mathbf{P}\{X>Y\}>1/2$ can be interpreted as meaning that when the two dice are rolled and the resulting values compared, die X will “beat” die Y more than half of the time. If $\mathcal{S}=\{A,B,C\}$ is a set of dice such that $A\succ B,B\succ C$, and $C\succ A$, then we say that $\mathcal{S}$ is nontransitive.

Of the papers that discuss nontransitive dice, those that are most closely related to the study of permutation-fair dice are those that are concerned with the probability that two dice will be tied. Here we say that the dice X and Y are tied if $\mathbf{P}\{X>Y\}=1/2$. These include the work of Traldi et al. (see [11, 12]), Schaefer et al (see [13, 14]), and Hur and Kim (see [15]). Notice that $\mathcal{S}$ is a set of n tied dice if and only if it is $2/n$ permutation fair.

One limitation of the work on tied dice is that it is concerned only with the properties of pairs of dice. With permutation-fair dice, we are concerned with the properties of an entire set of dice. If we return our attention to the more general study of nonstandard dice, however, we can find some studies of nontransitive dice that work with the joint properties of large ensembles of dice. Most prominent among these are a series of papers that examine the relationships between various sums of multiple copies of each dice in a set. These include the work of James Grime (see [16]) and that of Buhler, Graham, and Hales (see [17]).

Physical dice

An appealing feature of the permutation-fair dice described in Table 1 is that they can be realized using a physical set of four 12-sided dice. It has been shown (see [18]) that isohedra can be used to create physical dice that are fair in the sense that they have the same chance of landing on each face after a vigorous roll. Recall that the disdyakis tricontahedron is a Catalan solid that has one hundred twenty faces. Because every Catalan solid is an isohedron [19], we see that our set of five 120-sided permutation-fair dice can be realized as a physical set of fair dice as well.

3 Notation and Terminology

In what follows, it will be useful to adopt a different representation of a set of dice. Recall that we have assumed that no number appears on more than one face of any die in a given set. Also, we are only concerned with the relative values on the faces of the dice. So, we can assume that all of the face values in a set of n d-sided dice are drawn from the set $\{1,2,\dots ,\mathit{\text{nd}}\}$.

String representations

Given a set $\mathcal{S}$ of dice, we can define a string representation $\mathbf{s}=(s_1,\dots ,s_r)$ of $\mathcal{S}$. To do so, we first assign a distinct label for each die in $\mathcal{S}$. Then, we let the ith character of s be the label for the die on which the value i appears.

• If s is a string of length r, then we will write ${\mathbf{s}}_{\le i}=(s_1,\dots ,s_i)$ to denote the first i characters of s, ${\mathbf{s}}_{>i}=(s_{i+1},\dots ,s_r)$ to denote the last r – i characters of s, and ${\mathbf{s}}_{i_1\le j\le i_2}=(s_{i_1},\dots ,s_{i_2})$ to denote a contiguous substring of s.

• If s is a string, and σ is a permutation on the characters that comprise s, then we will write $\sigma (\mathbf{s})=(\sigma (s_1),\dots ,\sigma (s_r))$ to denote a relabelling of s.

• If s is a string, then we will write ${\mathbf{s}}^{\prime }=(s_r,\dots ,s_1)$ to denote the reverse of s.

• If s and t are any two strings, then we will write $\mathbf{s}\left|\right|\mathbf{t}=(s_1,\dots ,s_r,t_1,\dots ,t_r)$ to denote the concatenation of s and t. If $\mathcal{S}$ and $\mathcal{T}$ are sets of dice with string representations s and t, respectively, then we will write $\mathcal{S}\left|\right|\mathcal{T}$ to denote the set of dice with string representation $\mathbf{s}\left|\right|\mathbf{t}$.

Example 2.

Consider the set $\mathcal{G}$ of dice described in Table 1. If g is the string representation of $\mathcal{G}$ then we have $$\mathbf{g}=\mathtt{\text{abcddcba}}\mathtt{ }\mathtt{\text{dbaccabd}}\mathtt{ }\mathtt{\text{cbaddabc}}\mathtt{ }\mathtt{\text{cbaddabc}}\mathtt{ }\mathtt{\text{dbaccabd}}\mathtt{ }\mathtt{\text{abcddcba}}.$$

Patterns

It will also be useful for us to be able to describe the outcome when we roll some subset of a given set of dice. We will say that x is a pattern of length m if x is a string comprised of a single instance of m distinct labels.

• If x is a pattern, then we will write $\left|\mathbf{x}\right|$ to denote the length of x.

• If x is a pattern and s is a string, then we will say that x appears in s if we have $\mathbf{x}=(s_{i_1},\dots ,s_{i_m})$ with $i_1<\cdots <i_m$.

• If x is a pattern and s is a string, then we will write $(\mathbf{x};\mathbf{s})$ to denote the number of times x appears in s. That is, $(\mathbf{x};\mathbf{s})=\left|\right\{i_1<\cdots <i_m|\mathbf{x}=(s_{i_1},\dots ,s_{i_m})\}|$.

To compute the number of times a pattern x appears in a string s, we can group those appearances according to where the last character of x appears in s. That is, if $\left|\mathbf{x}\right|=m$ then we have (1) $$(\mathbf{x};\mathbf{s})=\sum _{i:s_i=x_m}({\mathbf{x}}_{\le m-1};{\mathbf{s}}_{\le i-1}).$$(1)

So, by recursively applying (1), we can efficiently compute $(\mathbf{x};\mathbf{s})$. Given a set $\mathcal{S}$ of dice with string representation s, we can verify that $\mathcal{S}$ is m/n permutation fair by computing $(\mathbf{x};\mathbf{s})$ for all x with $\left|\mathbf{x}\right|=m$.

Permutation Fairness

Using the language of strings and patterns, we can make a precise statement of what it means for a set of dice to be permutation fair.

Definition 3.

We will say that a set $\mathcal{S}$ of n d-sided dice with string representation s is m/n permutation fair if, for every x such that $\left|\mathbf{x}\right|=m$, we have (2) $$(\mathbf{x};\mathbf{s})=\frac{d^m}{m!}.$$(2)

Example 4.

Consider the set $\mathcal{S}=\{S_1,S_2,\dots ,S_n\}$ of n 2-sided dice with face values $S_1=\{1,2n\},S_2=\{2,2n-1\},\dots ,S_n=\{n,n+1\}$. Notice that for any pattern x with $\left|\mathbf{x}\right|=2$ we can compute $(\mathbf{x};\mathbf{s})=2=2^2/2!$ which is consistent with our precise definition of permutation fairness given above.

4 An Improved Concatenation Construction

Before we state our main theoretical result, it will be useful to consider a simple motivating example which was discovered by Eric Harshbarger and Robert Ford in 2010 (see [1]). Note that while this example illustrates the concepts that we use in our construction, it was found using an ad hoc manual search rather than by the methods that we describe in this paper.

Example 5.

Consider the set $\mathcal{F}$ of 3/3 permutation-fair dice described in Table 2 that has string representation $$\mathbf{f}=\mathtt{\text{abccba}}\mathtt{ }\mathtt{\text{bcaacb}}\mathtt{ }\mathtt{\text{cabbac}}.$$

Table 2 A set $\mathcal{F}$ of three 6-sided dice that are permutation fair.

Die	Faces
	i	ii	iii	iv	v	vi
a	1	6	9	10	14	17
b	2	5	7	12	15	16
c	3	4	8	11	13	18

Notice that f can be decomposed into three blocks of six characters and that each block is a palindrome in which each label appears twice. In fact, each block is the string representation of a set of dice that is 2/3 permutation fair. In [2], the authors describe a generic construction for creating $(m+1)/n$ permutation-fair sets of dice by concatenating $n!$ different sets of m/n permutation-fair dice. In this case, $n!=6$ but only three sets of 2/3 permutation-fair dice were required to create a set of 3/3 permutation-fair dice. To understand why, we counted how many times each pattern of length three appeared in each block. The resulting values are described in Table 3. Notice that the sum of the values in each row of Table 3 is the same.

Table 3 Counts for each three-long pattern in the blocks of f.

Pattern	Counts
	${\mathbf{f}}_{1\le j\le 6}$	${\mathbf{f}}_{7\le j\le 12}$	${\mathbf{f}}_{13\le j\le 18}$
abc	2	2	0
acb	2	0	2
bac	0	2	2
bca	2	0	2
cab	0	2	2
cba	2	2	0

While the three blocks that comprise f in the preceding example are not 3/3 permutation fair, they have been carefully chosen to be compatible. That is, the ways in which they are unfair cancel out when they are combined via concatenation. The following theorem extends this idea to the general case and, in particular, proves that the preceding example is indeed 3/3 permutation fair. It provides a criterion which ensures that a collection of m/n permutation-fair sets of dice can be combined via concatenation to create a set of $(m+1)/n$ permutation-fair dice.

Theorem 6

(Lifting Theorem). Suppose that for all $1\le i\le k,{\mathcal{S}}_i$ is an m/n permutation-fair set of d_i-sided dice with string representation ${\mathbf{s}}_i$. If there exists a constant C such that for all patterns x with $\left|\mathbf{x}\right|=m+1$ we have (3) $$\sum _{i=1}^k(\mathbf{x};{\mathbf{s}}_i)=C,$$(3) then $\mathcal{S}={\mathcal{S}}_1\left|\right|\cdots \left|\right|{\mathcal{S}}_k$ is a set of dice that is $(m+1)/n$ permutation fair.

Proof.

Let $\mathbf{s}={\mathbf{s}}_1\left|\right|{\mathbf{s}}_2\left|\right|\cdots \left|\right|{\mathbf{s}}_k$. We can decompose the quantity $(\mathbf{x};\mathbf{s})$ into a sum of products by grouping the appearances of x according to which part of s that each substring of x appears in. That is, suppose that the first i₁ components of x appear in ${\mathbf{s}}_1$, the next i₂ components of x appear in ${\mathbf{s}}_2$, and so on. Let $i_1^{\prime }=i_1$ and for all $2\le j\le k$ let $i_j^{\prime }=i_{j-1}^{\prime }+i_j$. Using this decomposition we see that (4) $$(\mathbf{x};\mathbf{s})=\sum _{\begin{array}{c}{i}_1+\cdots +i_k=m+1\\ 0\le i_1,i_2,\dots ,i_k\le m+1\end{array}}({\mathbf{x}}_{1\le j\le i_1^{\prime }};{\mathbf{s}}_1)({\mathbf{x}}_{i_1^{\prime }<j\le i_2^{\prime }};{\mathbf{s}}_2)\cdots ({\mathbf{x}}_{i_{k-1}^{\prime }<j\le i_k^{\prime }};{\mathbf{s}}_k).$$(4)

We can use the fact that each part of s is m/n permutation fair to compute the contribution of each partition with $0\le i_1,i_2,\dots ,i_k\le m$. Observe that, if $\mathcal{S}$ is m/n permutation fair, then $\mathcal{S}$ is $\mathcal{l}/n$ permutation fair for all $\mathcal{l}\le m$. So, we have (5) $$({\mathbf{x}}_{1\le j\le i_1^{\prime }};{\mathbf{s}}_1)({\mathbf{x}}_{i_1^{\prime }<j\le i_2^{\prime }};{\mathbf{s}}_2)\cdots ({\mathbf{x}}_{i_{k-1}^{\prime }<j\le i_k^{\prime }};{\mathbf{s}}_k)=\frac{d_1^{i_1}}{i_1!}\frac{d_2^{i_2}}{i_2!}\cdots \frac{d_k^{i_k}}{i_1!}.$$(5)

Notice that the condition $0\le i_1,i_2,\dots ,i_k\le m$ holds unless every component of x appears in the same part of s. So, (5) shows that the contributions of partitions that are distributed across more than one part of s do not depend on x. We can conclude that for all patterns x with $\left|\mathbf{x}\right|=m+1$ there exists some constant D such that (6) $$(\mathbf{x};\mathbf{s})=D+\sum _{i=1}^k(\mathbf{x};{\mathbf{s}}_i)=D+C.$$(6)

Therefore each pattern of length m + 1 appears the same number of times and we can conclude that $\mathcal{S}$ is $(m+1)/n$ permutation fair. Finally, notice that this result does not depend on the order in which the ${\mathcal{S}}_i$ are concatenated. □

5 Finding Compatible Sets of Dice

We now turn our attention to the task of actually finding new sets of permutation-fair dice. Notice that while Theorem 6 provides a guarantee that certain sets of m/n permutation-fair dice can be combined to create a set of $(m+1)/n$ permutation-fair dice, it does not provide a way to find such compatible sets of dice. Now, we will describe several techniques for doing so.

Analytic techniques

Our first approach is predicated on the fact that the labels that we assign to the dice in a given set are arbitrary. This implies that if s is the string representation for a set $\mathcal{S}$ of dice, then $\sigma (\mathbf{s})$ is the string representation for a set $\mathcal{T}$ of dice that is equivalent in some sense to $\mathcal{S}$. In particular, $\mathcal{T}$ will have the same fairness properties as $\mathcal{S}$. More precisely, we have the following proposition.

Proposition 7

(Relabelling Theorem). If $\mathcal{S}$ is a set of dice that has string representation s and σ is a permutation on the set of characters that comprise s, then s is m/n permutation fair if and only if $\sigma (\mathbf{s})$ is m/n permutation fair.

Proof.

Because for all patterns x we have $(\mathbf{x};\sigma (\mathbf{s}))=({\sigma }^{-1}(\mathbf{x}),\mathbf{s}))$, the result follows immediately from the definition of m/n permutation fairness. □

Proposition 7 provides a way to generate multiple sets of m/n permutation-fair dice from a single seed. As described in [2], the set of all possible permutations applied to a set of m/n permutation-fair dice can be combined via concatenation to form a new, and much larger, set of dice that is $(m+1)/n$ permutation fair. The following theorem is a restatement of this result using the language developed in this paper.

Theorem 8.

Suppose that $\mathcal{S}$ is a set of m/n permutation-fair dice with string representation s, and that ${\left\{{\sigma }_i\right\}}_{i=1}^{n!}$ is the set of all permutations on the characters that comprise s. If $\mathbf{t}={\sigma }_1(\mathbf{s})\left|\right|\cdots \left|\right|{\sigma }_{n!}(\mathbf{s})$, then t is the string representation of a set of dice that is $(m+1)/n$ permutation fair.

Proof.

Notice that for all i and x, $(\mathbf{x};{\sigma }_i(\mathbf{s}))=({\sigma }_i^{-1}(\mathbf{x});\mathbf{s})$. Notice also that for all $1\le i\le n!$ we have (7) $$\sum _{\mathbf{x}:\left|\mathbf{x}\right|=m+1}(\mathbf{x};{\sigma }_i(\mathbf{s}))=\left(\begin{array}{c}n\\ m+1\end{array}\right)d^{m+1}.$$(7)

Because $i\mapsto {\sigma }_i(\mathbf{x})$ is a $(n-|\mathbf{x}|)!$-to-1 map, we can conclude that for all patterns x with $\left|\mathbf{x}\right|=m+1$ we have (8) $$\begin{array}{c}\sum _{i=1}^{n!}(\mathbf{x};{\sigma }_i(\mathbf{s}))=\sum _{i=1}^{n!}({\sigma }_i^{-1}(\mathbf{x});\mathbf{s})\hfill \\ =\left(n-(m+1)\right)!·\left(\begin{array}{c}n\\ m+1\end{array}\right)d^{m+1}.\hfill \end{array}$$(8)

The result then follows from Proposition 7 and Theorem 6. □

As stated earlier, Theorem 8 provides a way to construct a set of dice that are m/n permutation fair for arbitrary m and n. Because the dice in the resulting sets will be quite large, however, we would like to find efficient alternative construction methods. Rather than trying to find alternatives that are generic, we will focus our attention on two special cases.

Consider the problem of how to build a set of $2/n$ permutation-fair dice out of k sets of $1/n$ permutation-fair dice. The following theorem shows that this can be done with k = 2 by concatenating a string and its reverse to form a palindrome. This theorem provides a possible explanation for the ubiquity of palindromic blocks that we have observed in both the set $\mathcal{G}$ of 4/4 permutation-fair dice described in Table 1 and the set $\mathcal{F}$ of 3/3 permutation-fair dice described in Section 4.

Theorem 9.

Suppose that $\mathcal{S}$ is a set of d_s-sided dice that has string representation $\mathbf{s}=(s_1,s_2,\dots ,s_r)$. Let $\mathbf{t}=\mathbf{s}\left|\right|{\mathbf{s}}^{\prime }$ and $d_t=2d_s$. If $\mathcal{S}$ is $1/n$ permutation fair, then t is the string representation of a set of d_t-sided dice that is $2/n$ permutation fair.

Proof.

Consider a pattern x that has $\left|\mathbf{x}\right|=2$ and let ${\mathbf{x}}^{\prime }$ be the reverse of x. We have (9) $$\begin{array}{c}(\mathbf{x};\mathbf{t})=(\mathbf{x};\mathbf{s})+({\mathbf{x}}_{\le 1};\mathbf{s})({\mathbf{x}}_{>1};{\mathbf{s}}^{\prime })+(\mathbf{x};{\mathbf{s}}^{\prime })\hfill \\ =(\mathbf{x};\mathbf{s})+d_s^2+(d_s^2-(\mathbf{x};\mathbf{s})).\hfill \end{array}$$(9)

Let $d_t=2d_s$, and notice that if $\mathcal{T}$ is the set of dice with string representation t, then $\mathcal{T}$ is comprised of d_t-sided dice. Therefore we have $(\mathbf{x};\mathbf{t})=d_t^2/2$ and the result follows from the definition of $2/n$ permutation fairness. □

Along similar lines, our next theorem provides a way to construct a set of $4/n$ permutation-fair dice out of two sets of $3/n$ permutation-fair dice. As before, this construction works by concatenating a string with its reverse to form a palindrome. Notice that this result demonstrates the advantage of our construction over the concatenation construction as described in [2]. That construction would require the use of $n!$ sets of $3/n$ permutation-fair dice in order to create a set of $4/n$ permutation-fair dice while we are able to use just two sets, independent of the value of n.

Theorem 10.

Suppose that $\mathcal{S}$ is a set of d_s-sided dice that has string representation $\mathbf{s}=(s_1,s_2,\dots ,s_r)$. Let $\mathbf{t}=\mathbf{s}\left|\right|{\mathbf{s}}^{\prime }$ and $d_t=2d_s$. If $\mathcal{S}$ is $3/n$ permutation fair, then t is the string representation of a set of d_t-sided dice that is $4/n$ permutation fair.

Proof.

It suffices to show that $(\mathbf{x};\mathbf{t})=d_t^4/24=8d_s^4/12$ for all x with $\left|\mathbf{x}\right|=4$. As in the proof of Theorem 6, we can decompose $(\mathbf{x};\mathbf{t})$ by grouping the appearances of x according to which part of t each substring of x appears in. Doing so, we see that (10) $$\begin{array}{c}(\mathbf{x};\mathbf{t})=\sum _{i=0}^4({\mathbf{x}}_{\le i};\mathbf{s})({\mathbf{x}}_{>i};{\mathbf{s}}^{\prime })\hfill \\ =(\mathbf{x};\mathbf{s})+(\mathbf{x};{\mathbf{s}}^{\prime })+\sum _{i=1}^3({\mathbf{x}}_{\le i};\mathbf{s})({\mathbf{x}}_{>i};{\mathbf{s}}^{\prime })\hfill \\ =(\mathbf{x};\mathbf{s})+(\mathbf{x};{\mathbf{s}}^{\prime })+\sum _{i=1}^3\frac{d_s^i}{i!}\frac{d_s^{4-i}}{(4-i)!}\hfill \\ =(\mathbf{x};\mathbf{s})+(\mathbf{x};{\mathbf{s}}^{\prime })+\frac{7d_s^4}{12}.\hfill \end{array}$$(10)

So, it suffices to show that $(\mathbf{x};\mathbf{s})+(\mathbf{x};{\mathbf{s}}^{\prime })=d_s^4/12$. Without loss of generality, we can assume that $\mathbf{x}=\mathtt{\text{abcd}}$. Notice that we have (11) $$d_s^4\mathbf{P}\{\mathtt{a}<\mathtt{b}<\mathtt{c}\}=(\mathtt{\text{dabc}};\mathbf{s})+(\mathtt{\text{adbc}};\mathbf{s})+(\mathtt{\text{abdc}};\mathbf{s})+(\mathtt{\text{abcd}};\mathbf{s})$$(11) (12) $$\begin{array}{c}{d}_s^4\mathbf{P}\{\mathtt{a}<\mathtt{b},\mathtt{d}<\mathtt{c}\}=(\mathtt{\text{dabc}};\mathbf{s})+(\mathtt{\text{adbc}};\mathbf{s})+(\mathtt{\text{abdc}};\mathbf{s})\hfill \\ (\mathtt{\text{adcb}};\mathbf{s})+(\mathtt{\text{dacb}};\mathbf{s})+(\mathtt{\text{dcab}};\mathbf{s})\hfill \end{array}$$(12) (13) $$d_s^4\mathbf{P}\{\mathtt{d}<\mathtt{c}<\mathtt{b}\}=(\mathtt{\text{adcb}};\mathbf{s})+(\mathtt{\text{dacb}};\mathbf{s})+(\mathtt{\text{dcab}};\mathbf{s})+(\mathtt{\text{dcba}};\mathbf{s}).$$(13)

Observe that $(\mathbf{x};{\mathbf{s}}^{\prime })=({\mathbf{x}}^{\prime };\mathbf{s})$. So, we have (14) $$\begin{array}{c}(\mathbf{x};\mathbf{s})+(\mathbf{x};{\mathbf{s}}^{\prime })=(\mathtt{\text{abcd}};\mathbf{s})+(\mathtt{\text{dcba}};\mathbf{s})\\ =d_s^4\left(\mathbf{P}\{\mathtt{a}<\mathtt{b}<\mathtt{c}\}+\mathbf{P}\{\mathtt{d}<\mathtt{c}<\mathtt{b}\}-\mathbf{P}\{\mathtt{a}<\mathtt{b},\mathtt{d}<\mathtt{c}\}\right).\end{array}$$(14)

Because s is $3/n$ permutation fair we have $\mathbf{P}\{\mathtt{a}<\mathtt{b}<\mathtt{c}\}=\mathbf{P}\{\mathtt{d}<\mathtt{c}<\mathtt{b}\}=1/6$ and $\mathbf{P}\{\mathtt{a}<\mathtt{b},\mathtt{d}<\mathtt{c}\}=\mathbf{P}\{\mathtt{a}<\mathtt{b}\}\mathbf{P}\{\mathtt{d}<\mathtt{c}\}=1/4$. Therefore we can conclude that $(\mathbf{x};\mathbf{s})+(\mathbf{x};{\mathbf{s}}^{\prime })=d_s^4/12$ as required. □

Numerical Techniques

In cases where we have not been able to discover any applicable analytic techniques, we need an efficient way to search for compatible sets of dice numerically. Fortunately, we can characterize compatible sets of dice as the solution to an integer linear programming problem. This allows us to take advantage of a mature ecosystem of software tools designed to solve such problems.

Recall that an integer linear programming problem is a linear optimization problem in which the variables are constrained to be integers. That is, given a set of variables $\mathbf{y}={\left\{y_i\right\}}_{i=1}^k$, we want to find values of y that optimize some linear objective function $\mathbf{c}·\mathbf{y}$ subject to the constraints $\mathbf{A}·\mathbf{y}+\mathbf{r}=\mathbf{b},\mathbf{r}\ge 0$, and $\mathbf{y}\in {\mathbb{N}}^k$. Throughout, we will assume that our ILP solver is configured to minimize the objective function.

We will assume that we have identified a collection ${\left\{{\mathbf{s}}_i\right\}}_{i=1}^k$ of k candidate sets of dice, all of which are m/n permutation fair. Frequently, the collections that we consider will be comprised of all $n!$ possible permutations of the labels assigned to the dice in a single seed set of m/n permutation-fair dice, but we can apply this technique with arbitrary collections of suitable candidates. The variables ${\left\{y_j\right\}}_{j=1}^k$ in our ILP will represent the number of copies of each candidate that we will combine via concatenation to form a new set of dice.

For our objective function, we will let c be the vector of all ones. That is, $\mathbf{c}=\mathbf{1}$ and the objective function simply counts how many candidates are used in any solution. As such, any solutions that we find will be those that use the fewest possible candidates and the dice in the resulting sets will be as small as possible.

For our constraints, we will let r and b be vectors of all zeros. That is, $\mathbf{r}=\mathbf{b}=\mathbf{0}$. All of the permutation-fairness constraints will be encoded in the matrix A. Because we are hoping to create a set of dice that are $(m+1)/n$ permutation fair, we will need to consider the counts of all patterns x with $\left|\mathbf{x}\right|=m+1$. If we let r denote the number of such patterns, then $r=(\begin{array}{c}n\\ m+1\end{array})·(m+1)!$.

Finally, we will set each column of A to be the vector of pattern counts for one of the candidate sets of dice that has been normalized to have mean zero. If we let μ_j be the mean value for the jth column of A then we have ${\mu }_j=d_j^{m+1}/r$. So, A will be an r × k matrix and i, j we will set $a_{\mathit{\text{ij}}}=({\mathbf{x}}_i;{\mathbf{s}}_j)-{\mu }_j$.

All together, this yields an integer linear programming problem in which we want to minimize the quantity $\sum _j{y}_j$ subject to the constraints $\mathbf{A}·\mathbf{y}=\mathbf{0}$ where $\mathbf{y}\in {\mathbb{N}}^k$. Incidentally, this formulation shows that the search for compatible sets of dice can be understood as a kind of multi-dimensional knapsack problem.

6 Building Sets of Permutation-Fair Dice

We can use the machinery developed in the preceding discussion to construct relatively small sets of permutation-fair dice. Starting with some seed set of dice, we can recursively apply Theorems 6, 9, or 10 to build a series of m/n permutation-fair sets of dice, where m increases at each step. This process culminates with a set of dice that are n/n permutation fair.

Example 11.

Consider the set $\mathcal{G}$ of permutation-fair dice described in Table 1. The following four-step recipe describes how our construction can be used to create $\mathcal{G}$.

1. Start with the seed set $\mathcal{S}$ of dice with string representation $\mathbf{s}=\mathtt{\text{abcd}}$. Notice that s is a set of four 1-sided dice that is 1/4 permutation fair.

2. Let $\mathcal{T}$ be the set of dice with string representation $\mathbf{t}=\mathbf{s}\left|\right|{\mathbf{s}}^{\prime }=\mathtt{\text{abcddcba}}$. Theorem 9 implies that $\mathcal{T}$ is a set of four 2-sided dice that is 2/4 permutation fair.

3. Let $\mathcal{U}$ be the set of dice with string representation $\mathbf{u}={\sigma }_1(\mathbf{t})\left|\right|{\sigma }_2(\mathbf{t})\left|\right|{\sigma }_3(\mathbf{t})$, where ${\sigma }_1=(\mathtt{a},\mathtt{b},\mathtt{c},\mathtt{d}),{\sigma }_2=(\mathtt{d},\mathtt{b},\mathtt{a},\mathtt{c})$, and ${\sigma }_3=(\mathtt{c},\mathtt{b},\mathtt{a},\mathtt{d})$. Theorem 6 implies that $\mathcal{U}$ is a set of four 6-sided dice that is 3/4 permutation fair.

4. Let $\mathcal{G}$ be the set of dice with string representation $\mathbf{g}=\mathbf{v}\left|\right|{\mathbf{v}}^{\prime }$. Theorem 10 implies that $\mathcal{G}$ is a set of four 12-sided dice that is 4/4 permutation fair.

To create a set of 5/5 permutation-fair dice, we can follow a recipe like the one described above for creating a set of 4/4 permutation-fair dice. The process is similar, but when we use Theorem 6 to lift ${\mathcal{T}}_5$ and create a set of 3/5 permutation-fair dice ${\mathcal{U}}_5$ we find that we need to use six different permutations to do so. As such, at the end of the fourth step, we end up with a set ${\mathcal{G}}_5$ of five 24-sided dice. Unfortunately, we could not find a way to lift ${\mathcal{G}}_5$ using less than 120 permutations. Doing so yields a set of five 2880-sided dice that is 5/5 permutation fair.

Fortunately, we can do better. Rather than starting with a seed that is 1/5 permutation fair and building everything from scratch, we can start with any seed that is 4/5 permutation fair and use it to try find a compatible set of dice.

Example 12.

Consider the set $\mathcal{H}$ of five 12-sided dice with string representation $$\mathbf{h}=\mathtt{\text{eeabcddcbadbaccabdcbaddabceeeeeeeecbaddabcdbaccabdabcddcbaee}}.$$

We can verify by direct computation that $\mathcal{H}$ is 4/5 permutation fair. So, if we can identify a collection of permutations σ_i such that $\{{\sigma }_i(\mathbf{h})\}$ are compatible, then we can use Theorem 6 to lift h and create a set of dice that is 5/5 permutation fair. Using an ILP solver, we were able to identify the following collection of ten permutations: $$\begin{array}{c}{\sigma }_1=(\mathtt{a},\mathtt{c},\mathtt{b},\mathtt{d},\mathtt{e})\hfill \\ {\sigma }_2=(\mathtt{d},\mathtt{c},\mathtt{b},\mathtt{a},\mathtt{e})\hfill \\ {\sigma }_3=(\mathtt{e},\mathtt{c},\mathtt{b},\mathtt{d},\mathtt{a})\hfill \\ {\sigma }_4=(\mathtt{d},\mathtt{c},\mathtt{b},\mathtt{e},\mathtt{a})\hfill \\ {\sigma }_5=(\mathtt{e},\mathtt{c},\mathtt{a},\mathtt{b},\mathtt{d})\hfill \end{array}\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}\begin{array}{c}{\sigma }_6=(\mathtt{b},\mathtt{c},\mathtt{a},\mathtt{e},\mathtt{d})\hfill \\ {\sigma }_7=(\mathtt{e},\mathtt{c},\mathtt{a},\mathtt{d},\mathtt{b})\hfill \\ {\sigma }_8=(\mathtt{d},\mathtt{c},\mathtt{a},\mathtt{e},\mathtt{b})\hfill \\ {\sigma }_9=(\mathtt{a},\mathtt{e},\mathtt{d},\mathtt{b},\mathtt{c})\hfill \\ {\sigma }_{10}=(\mathtt{b},\mathtt{e},\mathtt{d},\mathtt{a},\mathtt{c}).\hfill \end{array}$$

So, as we can verify via direct computation, the set $\mathcal{I}$ of dice with string representation $$\begin{array}{l}\mathtt{eeacbddbcabcdaadcbdcabbacdeeeeeeeedcabbacdbcdaadcbacbddbcaee}\hfill \\ \mathtt{eedcbaabcdbcaddacbacdbbdcaeeeeeeeeacdbbdcabcaddacbdcbaabcdee}\hfill \\ \mathtt{aaecbddbcebcdeedcbdcebbecdaaaaaaaadcebbecdbcdeedcbecbddbceaa}\hfill \\ \mathtt{aadcbeebcdbceddecbecdbbdceaaaaaaaaecdbbdcebceddecbdcbeebcdaa}\hfill \\ \mathtt{ddecabbaceacbeebcabceaaecbddddddddbceaaecbacbeebcaecabbacedd}\hfill \\ \mathtt{ddbcaeeacbacebbecaecbaabceddddddddecbaabceacebbecabcaeeacbdd}\hfill \\ \mathtt{bbecaddaceacdeedcadceaaecdbbbbbbbbdceaaecdacdeedcaecaddacebb}\hfill \\ \mathtt{bbdcaeeacdaceddecaecdaadcebbbbbbbbecdaadceaceddecadcaeeacdbb}\hfill \\ \mathtt{ccaedbbdeadebaabedbeaddaebccccccccbeaddaebdebaabedaedbbdeacc}\hfill \\ \mathtt{ccbedaadebdeabbaedaebddbeaccccccccaebddbeadeabbaedbedaadebcc},\hfill \end{array}$$ is a set of five 120-sided dice that is 5/5 permutation fair. A physical realization of this set of dice is shown in Figure 1.

Fig. 1 A set of five 120-sided dice that is 5/5 permutation fair. This set of dice was produced by David Blanco and this image is used here with his permission.

7 Future Work

There are many questions about permutation-fair dice that remain unanswered. Most obviously, perhaps, is the question of whether there exists a permutation-fair set of five d-sided dice where $d\in \{30,60,90\}$. Outside of a few highly structured subclasses of dice for which the existence of such sets has been ruled out, this remains a tantalizing open problem.

We can ask similar questions about the existence of permutation-fair dice for other values of n. In particular, one might hope to find a set of six 30-sided dice that is permutation fair. For larger values of n the number of sides required for a set to be permutation fair grows quite quickly, but there is plenty of scope for research into what sorts of bounds might be achievable.

To answer these questions, it would be useful to know which sets of dice can be lifted efficiently. That is, for which sets of dice can we apply Theorem 6 using only a small number of permutations? Can we improve the asymptotic performance of the best known construction methods for arbitrarily large sets of permutation-fair dice?

If we expand our search to include inhomogeneous sets of dice, then there are even more questions that remain unanswered. In this regime, we have several ways to measure the size of a set of dice. Because the dice in such sets are not all the same size, we might consider only the size of the largest die. Alternatively, we might consider the total number of faces on all dice in the set. How small can a set of permutation-fair dice be when we use one of these metrics to measure its size?

ACKNOWLEDGMENT

While the work described herein was done independently, after finding the permutation fair set of five 120-sided dice, we shared our results with Eric Harshbarger. This has since led to a wonderful series of collaborations both with him and other researchers. We would like to thank him for his pioneering technical contributions and for the work that he has done to organize the community of researchers interested in permutation-fair dice. We would also like to thank all of the reviewers, particularly Michael Cromer and Brett Witty, for their excellent feedback throughout the drafting of this paper.

DISCLOSURE STATEMENT

No potential conflict of interest was reported by the author.

Additional information

Notes on contributors

Michael Purcell

MICHAEL PURCELL received his PhD from the University of Utah in 2010 where he studied under the supervision of Davar Khoshnevisan. After completing his degree, he worked as an applied research mathematician for the U.S. Department of Defense for ten years. In 2020 he joined the Software Innovation Institute at The Australian National University as a senior research engineer. In 2022 he moved into his current role as a senior fellow in the School of Computing at the Australian National University. His research interests include probability, cryptography, and differential privacy. In addition to his technical work, he is also an enthusiastic amateur musician and game designer.