View source for Intransitive dice

{{Short description|Game variations and descriptions of intransitive die and their behaviour}}
{{Multiple issues|
 {{More citations needed|date=May 2024}}
 {{Original research|date=May 2024}}
}}
A set of [[dice]] is [[Intransitivity|intransitive]] (or nontransitive) if it contains X>2 dice, ''X1'', ''X2'', and ''X3''... with the property that ''X1'' rolls higher than ''X2'' more than half the time, and ''X2'' rolls higher than ''X3'' etc... more than half the time, but where it is not true that ''X1'' rolls higher than ''Xn'' more than half the time. In other words, a set of dice is intransitive if the [[binary relation]] – {{math|''X''}} rolls a higher number than {{math|''Y''}} more than half the time – on its elements is not [[Transitive relation|transitive]].  More simply, ''X1'' normally beats ''X2'', ''X2'' normally beats ''X3'', but ''X1'' does '''not''' normally beat ''Xn''.

It is possible to find sets of dice with the even stronger property that, for each die in the set, there is another die that rolls a higher number than it more than half the time.  This is different in that instead of only "''A'' does '''not''' normally beat ''C''" it is now "''C'' normally beats ''A''". Using such a set of dice, one can invent games which are biased in ways that people unused to intransitive dice might not expect (see [[#Example|Example]]).<ref name="MathWorld">{{cite web|last1=Weisstein|first1=Eric W.|author-link=Eric W. Weisstein|title=Efron's Dice|url=https://mathworld.wolfram.com/EfronsDice.html|access-date=12 January 2021|website=[[Wolfram MathWorld]]|language=en}}</ref><ref>{{cite web|last=Bogomolny|first=Alexander|author-link=Alexander Bogomolny|title=Non-transitive Dice|url=https://www.cut-the-knot.org/Probability/NonTransitiveDice.shtml|url-status=live|archive-url=https://web.archive.org/web/20160112225243/https://www.cut-the-knot.org/Probability/NonTransitiveDice.shtml|archive-date=2016-01-12|website=Cut the Knot}}</ref><ref>{{cite journal |last1=Savage |first1=Richard P. |title=The Paradox of Nontransitive Dice |journal=The American Mathematical Monthly |date=May 1994 |volume=101 |issue=5 |pages=429–436 |doi=10.2307/2974903 |jstor=2974903 |url=https://www.jstor.org/stable/2974903}}</ref><ref name="efron">{{cite journal |last1=Rump |first1=Christopher M. |title=Strategies for Rolling the Efron Dice |journal=Mathematics Magazine |date=June 2001 |volume=74 |issue=3 |pages=212–216 |doi=10.2307/2690722 |jstor=2690722 |url=https://www.jstor.org/stable/2690722 |access-date=12 January 2021}}</ref>

==Example==
[[Image:Intransitive dice 2.svg|thumb|240px|An example of intransitive dice (opposite sides have the same value as those shown).]]

Consider the following set of dice.
* Die ''A'' has sides 2, 2, 4, 4, 9, 9.
* Die ''B'' has sides 1, 1, 6, 6, 8, 8.
* Die ''C'' has sides 3, 3, 5, 5, 7, 7.
The [[probability]] that ''A'' rolls a higher number than ''B'', the probability that ''B'' rolls higher than ''C'', and the probability that ''C'' rolls higher than ''A'' are all {{sfrac|5|9}}, so this set of dice is intransitive. In fact, it has the even stronger property that, for each die in the set, there is another die that rolls a higher number than it more than half the time.

Now, consider the following game, which is played with a set of dice.
# The first player chooses a die from the set.
# The second player chooses one die from the remaining dice.
# Both players roll their die; the player who rolls the higher number wins.
If this game is played with a transitive set of dice, it is either fair or biased in favor of the first player, because the first player can always find a die that will not be beaten by any other dice more than half the time. If it is played with the set of dice described above, however, the game is biased in favor of the second player, because the second player can always find a die that will beat the first player's die with probability {{sfrac|5|9}}. The following tables show all possible outcomes for all three pairs of dice.
{| class="wikitable" style="border:none; text-align:center;margin:0 auto;"
| colspan="4" style="border:none;"|Player 1 chooses die '''A'''<br />Player 2 chooses die '''C''' || rowspan="5" style="border:none;width:2em;"|
| colspan="4" style="border:none;"|Player 1 chooses die '''B'''<br />Player 2 chooses die '''A''' || rowspan="5" style="border:none;width:2em;"|
| colspan="4" style="border:none;"|Player 1 chooses die '''C'''<br />Player 2 chooses die '''B'''
|-
! {{diagonal split header|C|A}} !! 2 !! 4 !! 9
! {{diagonal split header|A|B}} !! 1 !! 6 !! 8
! {{diagonal split header|B|C}} !! 3 !! 5 !! 7
|-
! 3
| style="background:#ffc;"|C || A || A
! 2
| style="background:#ffc;"|A || B || B
! 1
| C || C || C
|-
! 5
| style="background:#ffc;"|C || style="background:#ffc;"|C || A
! 4
| style="background:#ffc;"|A || B || B
! 6
| style="background:#ffc;"|B || style="background:#ffc;"|B || C
|-
! 7
| style="background:#ffc;"|C || style="background:#ffc;"|C || A
! 9
| style="background:#ffc;"|A || style="background:#ffc;"|A || style="background:#ffc;"|A
! 8
| style="background:#ffc;"|B || style="background:#ffc;"|B || style="background:#ffc;"|B
|}

If one allows weighted dice, i.e., with unequal probability weights for each side, then alternative sets of three dice can achieve even larger probabilities than <math>\frac{5}{9} \approx 0.56</math> that each die beats the next one in the cycle. The largest possible probability is one over the [[golden ratio]], <math>\frac{1}{\varphi} \approx 0.62</math>.<ref>{{cite journal |last1=Trybuła |first1=Stanisław |title=On the paradox of three random variables |journal=Applicationes Mathematicae |date=1961 |volume=4 |issue=5 |pages=321-332 |url=https://eudml.org/doc/264121}}</ref>

==Variations==

===Efron's dice===

'''Efron's dice''' are a set of four intransitive dice invented by [[Bradley Efron]].<ref name="efron"/>

[[Image:Efron dice 2.svg|thumb|320px|Representation of Efron's dice. The back side of each die has the same faces as the front except for the 5, 5, 1 die (where the back side of 5 is 1, and the back side of 1 is 5).]]
The four dice A, B, C, D have the following numbers on their six faces:
* A: 4, 4, 4, 4, 0, 0
* B: 3, 3, 3, 3, 3, 3
* C: 6, 6, 2, 2, 2, 2
* D: 5, 5, 5, 1, 1, 1

Each die is beaten by the previous die in the list with wraparound, with probability {{sfrac|2|3}}. C beats A with probability {{sfrac|5|9}}, and B and D have equal chances of beating the other.<ref name="efron"/> If each player has one set of Efron's dice, there is a continuum of optimal strategies for one player, in which they choose their die with the following probabilities, where {{nowrap|0 ≤ ''x'' ≤ {{sfrac|3|7}}}}:<ref name="efron"/>
:P(choose A) = ''x''
:P(choose B) = {{sfrac|1|2}} - {{sfrac|5|6}}''x''
:P(choose C) = ''x''
:P(choose D) = {{sfrac|1|2}} - {{sfrac|7|6}}''x''

===Miwin's dice===
[[Image:Miwin Wuerfel Titan.gif|thumb|240px|Miwin's dice]]
{{main|Miwin's dice}}
Miwin's Dice were invented in 1975 by the physicist Michael Winkelmann.

Consider a set of three dice, III, IV and V such that
* die III has sides 1, 2, 5, 6, 7, 9
* die IV has sides 1, 3, 4, 5, 8, 9
* die V has sides 2, 3, 4, 6, 7, 8
Then:
* the [[probability]] that III rolls a higher number than IV is {{sfrac|17|36}}
* the probability that IV rolls a higher number than V is {{sfrac|17|36}}
* the probability that V rolls a higher number than III is {{sfrac|17|36}}

==Intransitive dice set for more than two players==

A number of people have introduced variations of intransitive dice where one can compete against more than one opponent.

=== Three players ===

==== Oskar dice ====
[[Oskar van Deventer]] introduced a set of seven dice (all faces with probability {{sfrac|1|6}}) as follows:<ref>{{cite web|last=Pegg|first=Ed Jr.|author-link=Ed Pegg Jr.|date=2005-07-11|title=Tournament Dice|url=http://www.mathpuzzle.com/MAA/39-Tournament%20Dice/mathgames_07_11_05.html|url-status=live|archive-url=https://web.archive.org/web/20050804234631/http://www.maa.org/editorial/mathgames/mathgames_07_11_05.html|archive-date=2005-08-04|access-date=2012-07-06|website=Math Games|publisher=[[Mathematical Association of America]]}}</ref>
* A: 2, {{0}}2, 14, 14, 17, 17
* B: 7, {{0}}7, 10, 10, 16, 16
* C: 5, {{0}}5, 13, 13, 15, 15
* D: 3, {{0}}3, {{0}}9, {{0}}9, 21, 21
* E: 1, {{0}}1, 12, 12, 20, 20
* F: 6, {{0}}6, {{0}}8, {{0}}8, 19, 19
* G: 4, {{0}}4, 11, 11, 18, 18

One can verify that A beats {B,C,E}; B beats {C,D,F}; C beats {D,E,G}; D beats {A,E,F}; E beats {B,F,G}; F beats {A,C,G}; G beats {A,B,D}. Consequently, for arbitrarily chosen two dice there is a third one that beats both of them. Namely,
* G beats {A,B}; F beats {A,C}; G beats {A,D}; D beats {A,E}; D beats {A,F}; F beats {A,G};
* A beats {B,C}; G beats {B,D}; A beats {B,E}; E beats {B,F}; E beats {B,G};
* B beats {C,D}; A beats {C,E}; B beats {C,F}; F beats {C,G};
* C beats {D,E}; B beats {D,F}; C beats {D,G};
* D beats {E,F}; C beats {E,G};
* E beats {F,G}.

Whatever the two opponents choose, the third player will find one of the remaining dice that beats both opponents' dice.

====Grime dice====

Dr. James Grime discovered a set of five dice as follows:<ref name="A">{{cite web |last1=Grime |first1=James |title=Non-transitive Dice |url=http://grime.s3-website-eu-west-1.amazonaws.com/ |archive-url=https://web.archive.org/web/20160514125245/http://grime.s3-website-eu-west-1.amazonaws.com/ |archive-date=2016-05-14 |url-status=dead}}</ref><ref>{{Cite journal |last=Pasciuto |first=Nicholas |date=2016 |title=The Mystery of the Non-Transitive Grime Dice |url=http://vc.bridgew.edu/undergrad_rev/vol12/iss1/18 |journal=Undergraduate Review |volume=12 |issue=1 |pages=107–115 |via=Bridgewater State University}}</ref>
* A: 2, 2, 2, 7, 7, 7
* B: 1, 1, 6, 6, 6, 6
* C: 0, 5, 5, 5, 5, 5
* D: 4, 4, 4, 4, 4, 9
* E: 3, 3, 3, 3, 8, 8

One can verify that, when the game is played with one set of Grime dice:
* A beats B beats C beats D beats E beats A (first chain);
* A beats C beats E beats B beats D beats A (second chain).

However, when the game is played with two such sets, then the first chain remains the same, except that D beats C, but the second chain is reversed (i.e. A beats D beats B beats E beats C beats A). Consequently, whatever dice the two opponents choose, the third player can always find one of the remaining dice that beats them both (as long as the player is then allowed to choose between the one-die option and the two-die option):

:{| class="wikitable"
|- align="center"
! colspan="2" rowspan="2" | Sets chosen<br />by opponents
! colspan="2" | Winning set of dice
|- align="center"
! Type
! Number
|- align="center"
| A || B || E || 1
|- align="center"
| A || C || E || 2
|-align="center"
| A || D || C || 2
|- align="center"
| A || E || D || 1
|- align="center"
| B || C || A || 1
|- align="center"
| B || D || A || 2
|- align="center"
| B || E || D || 2
|- align="center"
| C || D || B || 1
|- align="center"
| C || E || B || 2
|- align="center"
| D || E || C || 1
|}

=== Four players ===
A four-player set has not yet been discovered, but it was proved that such a set would require at least 19 dice.<ref name="A" /><ref>{{Cite journal|last1=Reid|first1=Kenneth|last2=McRae|first2=A.A.|last3=Hedetniemi|first3=S.M.|last4=Hedetniemi|first4=Stephen|date=2004-01-01|title=Domination and irredundance in tournaments|url=https://www.researchgate.net/publication/266258217|journal=The Australasian Journal of Combinatorics [electronic only]|volume=29}}</ref>

== Intransitive 4-sided dice ==
[[Tetrahedron|Tetrahedra]] can be used as [[Dice#Polyhedral dice|dice with four possible results]].

;Set 1:
* A: 1, 4, 7, 7
* B: 2, 6, 6, 6
* C: 3, 5, 5 ,8

P(A > B) = P(B > C) = P(C > A) = {{sfrac|9|16}}

The following tables show all possible outcomes:

{| class="wikitable"
! {{diagonal split header|A|B}} !! 2 !! 6 !! 6 !! 6
|-
! 1
| B || B || B || B
|-
! 4
| A || B || B || B
|-
! 7
| A || A || A || A
|-
! 7
| A || A || A || A
|}
In "A versus B", A wins in 9 out of 16 cases.

{| class="wikitable"
! {{diagonal split header|B|C}} !! 3 !! 5 !! 5 !! 8
|-
! 2
| C || C || C || C
|-
! 6
| B || B || B || C
|-
! 6
| B || B || B || C
|-
! 6
| B || B || B || C
|}
In "B versus C", B wins in 9 out of 16 cases.

{| class="wikitable"
! {{diagonal split header|C|A}} !! 1 !! 4 !! 7 !! 7
|-
! 3
| C || A || A || A
|-
! 5
| C || C || A || A
|-
! 5
| C || C || A || A
|-
! 8
| C || C || C || C
|}
In "C versus A", C wins in 9 out of 16 cases.

;Set 2:
* A: 3, 3, 3, 6
* B: 2, 2, 5, 5
* C: 1, 4, 4, 4

P(A > B) = P(B > C) = {{sfrac|10|16}}, P(C > A) = 9/16

== Intransitive 12-sided dice ==
In analogy to the intransitive six-sided dice, there are also dodecahedra which serve as intransitive [[Dice#Non-cubic|twelve-sided dice]]. The points on each of the dice result in the sum of 114. There are no repetitive numbers on each of the dodecahedra.

Miwin's dodecahedra (set 1) win cyclically against each other in a ratio of 35:34.

The miwin's dodecahedra (set 2) win cyclically against each other in a ratio of 71:67.

Set 1:
{|border="1" class="wikitable"
|D III ||purple|| 1 || 2 || || || 5 || 6 || 7 || || 9 || 10 || 11 || || || 14 || 15 || 16 || || 18
|-
|D IV ||red|| 1 || || 3 || 4 || 5 || || || 8 || 9 || 10 || || 12 || 13 || 14 || || || 17 || 18
|-
|D V ||dark grey|| || 2 || 3 || 4 || || 6 || 7 || 8 || || || 11 || 12 || 13 || || 15 || 16 || 17 ||
|}
<gallery mode="packed">
Standard-Dodekaeder-D III.gif|D III
Standard-Dodekaeder-D IV.gif|D IV
Standard-Dodekaeder-D V.gif|D V
</gallery>

Set 2:
{|border="1" class="wikitable"
|D VI ||cyan|| 1 || 2 || 3 || 4 || || || || || 9 || 10 || 11 || 12 || 13 || 14 || || || 17 || 18
|-
|D VII ||pear green|| 1 || 2 || || || 5 || 6 || 7 || 8 || 9 || 10 || || || || || 15 || 16 || 17 || 18
|-
|D VIII ||light grey|| || || 3 || 4 || 5 || 6 || 7 || 8 || || || 11 || 12 || 13 || 14 || 15 || 16 || ||
|}
<gallery mode="packed">
Standard-Dodekaeder-D VI.gif|D VI
Standard-Dodekaeder-D VII.gif|D VII
Standard-Dodekaeder-D VIII.gif|D VIII
</gallery>

=== Intransitive prime-numbered 12-sided dice ===

It is also possible to construct sets of intransitive dodecahedra such that there are no repeated numbers and all numbers are primes. Miwin's intransitive prime-numbered dodecahedra win cyclically against each other in a ratio of 35:34.

Set 1: The numbers add up to 564.
{|border="1" class="wikitable"
|PD 11 ||grey to blue|| 13 || 17 || 29 || 31 || 37 || 43 || 47 || 53 || 67 || 71 || 73 || 83
|-
|PD 12 ||grey to red|| 13 || 19 || 23 || 29 || 41 || 43 || 47 || 59 || 61 || 67 || 79 || 83
|-
|PD 13 ||grey to green|| 17 || 19 || 23 || 31 || 37 || 41 || 53 || 59 || 61 || 71 || 73 || 79
|}
<gallery mode="packed">
Primzahlen-Dodekaeder-PD 11bf.gif|PD 11
Primzahlen-Dodekaeder-PD 12bf.gif|PD 12
Primzahlen-Dodekaeder-PD 13bf.gif|PD 13
</gallery>

Set 2: The numbers add up to 468.
{|border="1" class="wikitable"
|PD 1 ||olive to blue|| 7 || 11 || 19 || 23 || 29 || 37 || 43 || 47 || 53 || 61 || 67 || 71
|-
|PD 2 ||teal to red|| 7 || 13 || 17 || 19 || 31 || 37 || 41 || 43 || 59 || 61 || 67 || 73
|-
|PD 3 ||purple to green|| 11 || 13 || 17 || 23 || 29 || 31 || 41 || 47 || 53 || 59 || 71 || 73
|}
<gallery mode="packed">
Primzahlen-Dodekaeder-PD 1bf.gif|PD 1
Primzahlen-Dodekaeder-PD 2bf.gif|PD 2
Primzahlen-Dodekaeder-PD 3bf.gif|PD 3 
</gallery>

== Generalized Muñoz-Perera's intransitive dice ==
A generalization of sets of intransitive dice with <math>N</math> faces is possible.<ref>Muñoz Perera, Adrián. "A generalization of intransitive dice". December 2024</ref> Given <math>N \geq 3</math>, we define the set of dice <math>\{D_n\}_{n=1}^N</math> as the random variables taking values each in the set <math>\{v_{n,j}\}_{j=1}^J</math> with 

<math>\mathbb{P}\left[D_n = v_{n,j}\right] = \frac{1}{J}</math>,

so we have <math>N</math> fair dice of <math>J</math> faces. 

To obtain a set of intransitive dice is enough to set the values <math>v_{n,j}</math> for <math>n,j = 1, 2, \ldots, N</math> with the expression

<math>v_{n,j} = (j-1)N + (n - j)\text{mod}(N) + 1</math>,

obtaining a set of <math>N</math> fair dice of <math>N</math> faces

Using this expression, it can be verified that 

<math>\mathbb{P}\left[D_m < D_n\right] = \frac{1}{2}  + \frac{1}{2N} - \frac{(n-m)\text{mod}(N)}{N^2}</math>,

So each die beats <math>\lfloor N/2 - 1 \rfloor </math> dice in the set.

=== Examples ===

==== 3 faces ====
{|border="1" class="wikitable"
|<math>D_1</math>||1|| 6|| 8
|-
|<math>D_2</math>|| 2|| 4|| 9
|-
|<math>D_3</math>|| 3|| 5|| 7
|}
The set of dice obtained in tis case is equivalent to the first example on this page, but removing repeated faces. It can be verified that <math>D_3>D_2, D_2>D_1 \ \text{and} \ D_1>D_3</math>.

==== 4 faces ====
{|border="1" class="wikitable"
|<math>D_1</math>||1|| 8|| 11||14
|-
|<math>D_2</math>|| 2|| 5|| 12||15
|-
|<math>D_3</math>|| 3|| 6|| 9||16
|-
|<math>D_4</math>|| 4|| 7|| 10||13
|}
Again it can be verified that <math>D_4>D_3, D_3>D_2, D_2>D_1 \ \text{and} \ D_1>D_4</math>.

==== 6 faces ====
{|border="1" class="wikitable"
|<math>D_1</math>||1|| 12|| 17||22||27||32
|-
|<math>D_2</math>|| 2|| 7|| 18||23||28||33
|-
|<math>D_3</math>|| 3|| 8|| 13||24||29||34
|-
|<math>D_4</math>|| 4|| 9|| 14||19||30||35
|-
|<math>D_5</math>|| 5|| 10|| 15||20||25||36
|-
|<math>D_6</math>|| 6|| 11|| 16||21||26||31
|}
Again <math>D_6>D_5, D_5>D_4, D_4>D_3, D_3>D_2, D_2>D_1 \ \text{and} \ D_1>D_6</math>. Moreover <math>D_6>\{D_5, D_4\}, D_5>\{D_4, D_3\}, D_4>\{D_3, D_2\}, D_3>\{D_2, D_1\}, D_2>\{D_1, D_6\} \ \text{and} \ D_1>\{D_6, D_5\}</math>.

== See also ==
* [[Blotto games]]
* [[Freivalds' algorithm]]
* [[Go First Dice]]
* [[Nontransitive game]]
* [[Rock paper scissors]]
* Condorcet's [[voting paradox]]

==References==
{{reflist}}
==Sources==
{{refbegin}}
* {{cite book|authorlink=Martin Gardner|last=Gardner|first=Martin|title=The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems: Number Theory, Algebra, Geometry, Probability, Topology, Game Theory, Infinity, and Other Topics of Recreational Mathematics|url=https://archive.org/details/colossalbookmath00gard|url-access=limited|edition=1st|location=New York|publisher=W. W. Norton & Company|date=2001|page=[https://archive.org/details/colossalbookmath00gard/page/n302 286]–311}}{{ISBN needed}}
* {{cite book|title=Spielerische Mathematik mit Miwin'schen Würfeln|publisher=Bildungsverlag Lemberger|isbn=978-3-85221-531-0|language=German}}
{{refend}}
==External links==
* [http://mathworld.wolfram.com/EfronsDice.html MathWorld page]
* [https://www.sciencenews.org/article/tricky-dice-revisited Ivars Peterson's MathTrek - Tricky Dice Revisited (April 15, 2002)]
* [https://web.archive.org/web/20061016165934/http://www.jimloy.com/puzz/nontran.htm Jim Loy's Puzzle Page]
* [http://www.miwin.com Miwin official site] {{In lang|de}}
* [https://web.archive.org/web/20120723135456/http://www.devrand.org/view/diceFinder Open Source nontransitive dice finder]
* [http://singingbanana.com/dice/article.htm Non-transitive Dice by James Grime]
* [http://www.mathsgear.co.uk/non-transitive-dice/ Maths Gear]
* [https://www.maa.org/programs/maa-awards/writing-awards/intransitive-dice Conrey, B., Gabbard, J., Grant, K., Liu, A., & Morrison, K. (2016). Intransitive dice. ''Mathematics Magazine,'' 89(2), 133-143. Awarded by Mathematical Association of America]{{Dead link|date=October 2024 |bot=InternetArchiveBot |fix-attempted=yes }}
* [[Timothy Gowers]]' [http://michaelnielsen.org/polymath1/index.php?title=Intransitive_dice project on intransitive dice]
* {{Cite web |last=Klarreich |first=Erica|author-link=Erica Klarreich|date=2023-01-19 |title=Mathematicians Roll Dice and Get Rock-Paper-Scissors |url=https://www.quantamagazine.org/mathematicians-roll-dice-and-get-rock-paper-scissors-20230119/|website=[[Quanta Magazine]]|language=en}}
* [https://pereradrian.github.io Adrián Muñoz Perera's site]'

[[Category:Probability theory paradoxes]]
[[Category:Dice]]