dice

Intransitive Dice with a Twist

[Total: 7    Average: 4.1/5]
Intransitive dice are sets of dice that don’t follow the usual rules for “is better/larger than”. If A<B and B<C, then A<C. If Bob runs faster than Alice and Charlie runs faster than Bob, then Charlie runs faster than Alice. If die B wins against die A (larger number wins) and die C wins against die B, then you would expect that die C wins against die A. But it does not have to. Consider three dice with the following sides:

A: 2,2,4,4,9,9
B: 3,3,5,5,7,7
C: 1,1,6,6,8,8

As every number appears twice, we can reduce them to three-sided dice, ignoring physical constraints (although three-sided dice exist):

intransitive dice

A set of dice to surprise friends.

A: 2,4,9
B: 3,5,7
C: 1,6,8

In a direct competition A against B, there are 9 outcomes with equal probability, A wins in 4 of them, B wins in 5. B is better than A.
In a direct competition B against C, there are 9 outcomes with equal probability, B wins in 4 of them, C wins in 5. C is better than B.
In a direct competition C against A, there are 9 outcomes with equal probability, C wins in 4 of them, A wins in 5. A is better than C.
A<B<C<A, and the set of dice is perfectly symmetric in terms of winning chances. If you want to use these for a competition, you can pretend to be generous and let your opponent pick first. No matter which die they pick, you can pick the one that will beat it (on average). It is a bit like rock paper scissors, where choosing second is an advantage as well (an even larger one in this case as you can guarantee a win).

There are many ways to make intransitive dice. There are even sets where you can play against two other players at the same time, let them both pick a die, and then pick one that will beat both of them in direct competitions. Wikipedia has many examples.

What happens if you take the set from above and roll all three at the same time? Which die will win the most? There are now 33 cases to consider, and it turns out that A and C win in 10 out of 27 cases each while B wins in 7 out of 27 cases. Suddenly the symmetry is broken. Is it possible to find a different set of dice where each die has 1/3 winning chance?

With the three-sided dice, the die with the largest number (let’s call it die A) will get 1/3 winning chance from this number alone. This means the other two numbers can never be the largest. In other words, another die (B) will have three numbers all larger than the two other numbers on A. This gives B a 6/9 winning chance over A. While you can add a third die to get intransitive dice, it is impossible to make all winning chances 2/3. In an attempt to make the maximum of all three symmetric, we made the individual comparisons asymmetric. With just three sides per die, there is not enough freedom to get both at the same time.

What about dice with more sides? With n sides we have n3 cases, to make that divisible by 3 we need n to be divisible by 3, so the next case to consider is n=6. If we keep the approach that all sides should have different numbers, we can distribute the numbers 0 to 17 over three dice, this leads to (18 choose 6)*(12 choose 6) options. If we don’t care about the order, we can divide this by 3!=6, for a total of 2,858,856 options. Too many to check them manually, but easy for a computer, so I wrote a program that tests all these options.

Out of 2,858,856 options, there are 10,705 (strictly) intransitive sets. Out of these, 1910 give the same winning chances for A over B, B over C and C over A (“fair intransitive”). Out of these, 7 give each die a 1/3 winning change when they are all rolled together. Here is the full list:

6-sided intransitive dice triples

A: (2, 3, 7, 10, 12, 17)
B: (1, 5, 6, 9, 14, 16)
C: (0, 4, 8, 11, 13, 15)
winning chance: 19/36

A: (2, 4, 5, 10, 14, 16)
B: (1, 3, 7, 12, 13, 15)
C: (0, 6, 8, 9, 11, 17)
winning chance: 19/36

A: (2, 4, 6, 9, 13, 17)
B: (1, 3, 8, 11, 12, 16)
C: (0, 5, 7, 10, 14, 15)
winning chance: 19/36

A: (3, 4, 5, 8, 15, 16)
B: (1, 2, 9, 12, 13, 14)
C: (0, 6, 7, 10, 11, 17)
winning chance: 20/36

A: (3, 4, 5, 8, 15, 16)
B: (1, 2, 10, 11, 13, 14)
C: (0, 6, 7, 9, 12, 17)
winning chance: 20/36

A: (3, 4, 6, 7, 15, 16)
B: (1, 2, 9, 12, 13, 14)
C: (0, 5, 8, 10, 11, 17)
winning chance: 20/36

A: (3, 4, 6, 7, 15, 16)
B: (1, 2, 10, 11, 13, 14)
C: (0, 5, 8, 9, 12, 17)
winning chance: 20/36

 

There are 8 sets of fair intransitive dice with 21/36 winning probability, but none of them also satisfy the 1/3 criterion.

Can we get dice with higher winning probabilities against each other? This requires more sides, and the next case are 9-sided dice. There are (27 choose 9)*(18 choose 9)/6 = 37,978,905,250 options. Too many to test all of them in a reasonable time. Luckily an observation from the 6-sided dice helped: All 1910 fair intransitive sets had in common that the average side for each die was 8.5. Testing 70 million sets of 9-sided dice lead to the same pattern: All fair intransitive sets (30,000 found in the test run) had an average of 13. While I don’t have a mathematical proof, this seems to be necessary. It reduces the number of combinations to tens of millions – and makes an exhaustive search possible (30 minutes). Out of 37,978,905,250 options, there are 17,495,345 fair intransitive dice sets, out of these there are 5077 sets that satisfy the 1/3 winning condition. The strongest sets have 44/81 winning chance, and there are just 4 of them:

9-sided intransitive dice with maximal winning chance

A: (2, 4, 8, 11, 12, 13, 16, 25, 26)
B: (1, 6, 7, 9, 10, 15, 22, 23, 24)
C: (0, 3, 5, 14, 17, 18, 19, 20, 21)
winning chance: 44.0/81

A: (2, 4, 9, 10, 12, 13, 16, 25, 26)
B: (1, 6, 7, 8, 11, 15, 22, 23, 24)
C: (0, 3, 5, 14, 17, 18, 19, 20, 21)
winning chance: 44.0/81

A: (5, 6, 7, 8, 9, 12, 21, 23, 26)
B: (2, 3, 4, 11, 15, 18, 19, 20, 25)
C: (0, 1, 10, 13, 14, 16, 17, 22, 24)
winning chance: 44.0/81

A: (5, 6, 7, 8, 9, 12, 21, 23, 26)
B: (2, 3, 4, 11, 16, 17, 19, 20, 25)
C: (0, 1, 10, 13, 14, 15, 18, 22, 24)
winning chance: 44.0/81

 

With 6-sided dice, the best winning chance is 20/36=0.555…
With 9-sided dice, the best winning chance is 44/81=0.543…
Bad luck – there are no better 9-sided dice. There might be better triples with 12-sided dice, but 564,121,960,420,200 options are “slightly” beyond reasonable computing capacity, even with the constraint on the average for each die. The CERN computing grid wouldn’t have a problem with it, but that is busy going through all the LHC data.

Instead of checking all, I searched through 12-sided dice randomly. In about 120 million sets, 200,000 were fair intransitive dice with 1/3 winning chance each. Only 8 sets exceeded the 80/144=0.555 winning chance found with 6-sided dice.

12-sided intransitive dice with larger winning chance

81/144 winning chance:

(2, 3, 4, 5, 16, 19, 23, 25, 26, 28, 29, 30)
(1, 6, 7, 8, 9, 10, 11, 27, 31, 32, 33, 35)
(0, 12, 13, 14, 15, 17, 18, 20, 21, 22, 24, 34)
winning chance: 63.0/144 = 0.4375 (or 81/144 = 0.5625 in the other direction)

(2, 3, 4, 5, 16, 19, 23, 25, 26, 28, 29, 30)
(1, 6, 7, 8, 9, 10, 12, 27, 31, 32, 33, 34)
(0, 11, 13, 14, 15, 17, 18, 20, 21, 22, 24, 35)
winning chance: 63.0/144 = 0.4375

(3, 7, 8, 9, 11, 12, 13, 21, 29, 30, 33, 34)
(1, 2, 4, 5, 6, 23, 25, 26, 27, 28, 31, 32)
(0, 10, 14, 15, 16, 17, 18, 19, 20, 22, 24, 35)
winning chance: 81.0/144 = 0.5625

82/144 winning chance:

(5, 8, 9, 10, 11, 12, 13, 15, 27, 31, 34, 35)
(1, 2, 3, 4, 6, 23, 25, 26, 28, 29, 30, 33)
(0, 7, 14, 16, 17, 18, 19, 20, 21, 22, 24, 32)
winning chance: 82.0/144 = 0.569444444444

(5, 8, 9, 10, 11, 12, 13, 15, 27, 31, 34, 35)
(1, 2, 3, 4, 6, 24, 25, 26, 28, 29, 30, 32)
(0, 7, 14, 16, 17, 18, 19, 20, 21, 22, 23, 33)
winning chance: 82.0/144 = 0.569444444444

(5, 8, 9, 10, 11, 12, 13, 15, 27, 31, 34, 35)
(1, 2, 3, 4, 7, 22, 25, 26, 28, 29, 30, 33)
(0, 6, 14, 16, 17, 18, 19, 20, 21, 23, 24, 32)
winning chance: 82.0/144 = 0.569444444444

(5, 8, 9, 10, 11, 12, 13, 15, 27, 31, 34, 35)
(1, 2, 3, 4, 7, 23, 24, 26, 28, 29, 30, 33)
(0, 6, 14, 16, 17, 18, 19, 20, 21, 22, 25, 32)
winning chance: 82.0/144 = 0.569444444444

(5, 8, 9, 10, 11, 12, 13, 15, 27, 31, 34, 35)
(1, 2, 3, 4, 7, 23, 25, 26, 28, 29, 30, 32)
(0, 6, 14, 16, 17, 18, 19, 20, 21, 22, 24, 33)
winning chance: 82.0/144 = 0.569444444444

 

There is an interesting publication linking intransitive dice to partitions of integers: Non-transitive dominance. Unfortunately the number of partitions to search for an exhaustive coverage would be even larger than the number of dice to search.

Can we do better? I’m sure it is possible. The number of possible dice grows rapidly with increasing number of sides, much faster than the required conditions on them – there have to be some better options around. Unfortunately a search gets very time-demanding quickly. I don’t know what the maximal winning chance with these conditions is. 3/4 is a strict upper limit, but I’m not aware of triples of dice that come close to this.

It would be interesting to explore this further. I didn’t find any literature that considers rolling all three dice, and even for intransitive dice without this special property there is not much published.

 

 

Working on a PhD for one of the LHC experiments. Particle physics is great, but I am interested in other parts of physics as well.
4 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply