In an earlier cp4space post, I presented a set of five 5-sided dice. We can draw a directed graph associated with this set of dice:
Each vertex represents a die. If die A beats die B with a probability greater than ½, we draw a directed edge from A to B. If two dice have equal probability of beating each other, we leave the edge blank. We make the additional restriction that for each value x, no two dice can have x on a face; this ensures that there are no ‘draws’ between two dice.
Can we, for every directed graph, create a set of non-transitive dice corresponding to it? Radu Bumbacea answered this question in the affirmative, devising a construction for a set of n dice with 2e faces emulating any given digraph with n vertices and e directed edges. So, for the digraph given above, his construction would require five icosahedral dice. You might want to try finding a similar construction yourself.
Tournaments, lower bounds and quadratic residues
A tournament is a complete directed graph with n vertices and edges. Radu’s construction gives an upper bound of faces on each die. Can we establish a lower bound? Indeed, we can. There are different tournaments on n vertices, and ways to assign distinct values to n dice with F faces each. Using Stirling’s formula and considering the asymptotics, it is evident that we have a lower bound of , where the logarithm is base-2. This is considerably lower than Radu’s upper bound.
In the basic set of three non-transitive dice, we have the property that if one player chooses a die, you can choose another die so that you have a probability greater than ½ of securing a win. We can choose a more complicated tournament, where any pair of dice can be beaten by a third die. An elegant solution is to consider the dice to be integers modulo 7, and declare that one die beats another if their difference is a quadratic residue:
Using Radu’s construction, we can design a set of seven 42-faced dice which beat each other according to this directed graph. It transpires that this is quite suboptimal, though, as Oskar van Deventer discovered an equivalent set of seven 3-faced dice; their double covers are shown below:
The quadratic residue construction also gives a tournament with 19 vertices, where any set of three vertices is beaten by another vertex. Oskar hasn’t found an elegant set of dice for this tournament, although Radu’s construction gives a set of nineteen 342-faced dice. The order-19 tournament is rendered below, where the colour gradient indicates edge direction:
It’s possible to generalise even further, constructing sets of dice such that for any subset of size k, there exists a die which beats each of them with probability ≥ ½.