Every now and then someone finds out that nontransitive dice exist and is surprised by this fact. I in turn am always kinda surprised that their existence is surprising.

Why? Well, basically I don’t expect things to be transitive. Transitivity is a very nice property. When the universe hands you a transitive (total) property it’s basically saying “Hey, here. You’re in luck. The decision problem on this is easy, so you can spend your time worrying about other things”. The universe is a bit of a dick, so I don’t really expect it to do that very often.

So what is transitivity? Transitivity basically says “If A is better than B and B is better than C then A is better than C”. So something is nontransitive if you can find A, B and C where A is better than B, B is better than C and C is better than A.

In particular, nontransitive dice are a set of dice A,B,C such that if you roll pairs of them and the one with the highest score wins, A will consistently beat B which will consistently beat C which will consistently beat A.

They’re quite neat, but their existence shouldn’t be surprising. This is basically a post about how you might go about constructing non-transitive dice if all you had was an inclination that they might exist. Hopefully by the time you get to the end of it you should find the fact that they exist as unsurprising as I do.

We’re going to start with something apparently unrelated: An example of non-transitivity which is especially dear to my heart. Condorcet’s Paradox.

What is Condorcet’s Paradox? It’s the following:

Suppose you run a voting system in which each voter ranks each candidate in order of preference. That is, a vote looks something like “A,B,C” to mean “I prefer A to both B and C and I prefer B to C”.

Given votes cast like this, it is possible to find yourself in a situation where the majority of people prefer A to B, B to C and C to A (where “prefer” here means “ranked higher”). i.e. even though each individual vote gave a transitive ordering of the candidates, the majority preference does not.

How is this possible? Well, lets see if we can construct a simple example.

Well, first lets convince ourselves that this is impossible with only two voters:

The only way two voters can have a majority preference is if they both agree on an ordering.

So if A is preferred by the majority to B and B is preferred to the majority by C then both voters have ranked A ahead of B and B ahead of C. This means that also both voters have ranked A ahead of C, and so A is preferred to C.

So it’s impossible with two voters. Can we do it with three?

Well, in the same way as with two voters, if we have a unanimous preference between two candidates this isn’t going to work. So if this can possible work, for each pair we need to have two voters ranking it one way and one ranking it the other. So lets start with how the votes should look for A and B.

A,B
A,B
B,A

Now we need to figure out a way to insert C into the rankings in order to make this work.

We need to put C after B twice. If we do this for both the A,B votes then we’ll have A and B both preferred to C, which we don’t want, but we have to do it for one of them, which means we need one vote which is “A,B,C”. We also need to do it for the third vote, so this must look like either “B,C,A” or “B,A,C”.

We’re now down to few enough possibilities that we can just try things and see if they work. Let’s try B,C,A.

So we have two votes:

A,B,C
B,C,A

And one which is either A,C,B or C,A,B (because we need C to be before B in this ranking). We want C to be preferred to A in order to get non-transitivity, and they’re currently tied, so we need to have C before A, so this has to be C,A,B.

So our votes are now:

A,B,C
B,C,A
C,A,B

Our tallies now look like:

A is preferred to B because votes 1 and 3 put it before B.
B is preferred to C because votes 1 and 2 put it before C.
C is preferred to A because votes 2 and 3 put it before A.

So we do indeed have A preferred to B preferred to C preferred to A.

I regard Condorcet’s Paradox as basically the protoexample of intransitivity: I find that 9 times out of 10 if you have an intransitive relation you can construct an example that looks like Condorcet’s Paradox.

Let’s see how to do that with our dice:

We’re going to construct dice which basically look like voters.

Specifically each of our dice will have opposite sides marked with the same value, so they can take only three distinct values. We will label these values “Low, Medium and High”. Values may be in the range 1-9, with low values being 1-3, medium being 4-6 and high being 7-9.

The idea of our construction is that any high roll will beat any medium or low roll, etc. Further each die rolls low, medium or high with equal probability. So the only thing that determines the winner will be which one wins when they have the same value type. These categories low, medium and high will be our voters 1, 2 and 3, and one die will beat another most of the time if and only if the majority of voters rank it more highly.

So we want:

Low: A,B,C
Medium: B,C,A
High: C,A,B

Thus A will beat B if we roll low or high. B will beat C if we roll low or medium. C will beat A if we roll medium or high.

Conveniently, we have constructed our categories with three values each, so all we need to do is assign each of those values to a different die to get the ranking.

So:

A takes the values 3,4 and 8 (best low, worst medium, middle high)
B takes the values 2,6,7 (middle low, best medium, worst high)
C takes the values 1,5,9 (worst low, middle medium, best high)

And we get the desired result: On a category tie, A will beat B two thirds of the time, B will beat C two thirds of the time and C will beat A two thirds of the time.

We didn’t deliberately try for it, but it’s also worth noting that these all have the same expected score: 3 + 4 + 8 = 2 + 6 + 7 = 1 + 5 + 9 = 15. So they all have an expected score of 5.

As a side note, the actual victory chances are much lower than this: A tie will only happen a third of the time, and the rest of the time each die wins exactly half the time, so the real advantage is \(\frac{1}{3} \times \frac{2}{3} + \frac{2}{3} \times \frac{1}{2} = \frac{5}{9}\). So they will win more than half the time (just shy of 56% of the time), but not by much.

So there we have it. Non-transitive dice. This isn’t the only way you can get them – you can make it work with only the normal values 1 to 6 for example – but it’s probably the simplest example to understand, and now that we’ve shown that it’s possible the rest is just optimising for specific details.