Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A set of nontransitive dice is a set of dice whose face numbers are such that the relation "is more likely to roll a higher number than" is not transitive. (See wikipedia)

For some sets, the deviation from transitivity is small in the sense that A beats B beats C beats A with probabilities $p_{ij}$ only slightly greater than $0.5$ . Efron's dice (there are 4 of them) beat each other nontransitively with probability $2/3$.

Can we make a strictly better set of $4$ six-sided dice? That is, a set of 4 six-sided dice such that they beat each other nontransitively with all probabilities $> 2/3$ ?

Can we make a strictly better set of $4$ $n$-sided dice for some small $n$ which one can conveniently make a die out of, e.g. $n = 4, 8, 12, 20 $ ?

Can we make a strictly better set of $5$ $n$-sided dice for some small $n$ which one can conveniently make a die out of, e.g. $n = 4, 6, 8, 12, 20 $ ?

Can we make a strictly better set of $3$, $4$ or $5$ dice, each having a potentially different number of sides ($4, 6, 8, 12$ or $20$) ?

Ideally I would like to find a fairly small set of fairly easy-to-make, preferably platonic-solid dice which beat each other nontransitively with probabilities > 80%. They would make an excellent teaching aid and magic trick. There is an answer on math.stackexchange which claims that the best you can do with 3 dice is $p = 0.58$, which is disappointingly close to $0.5$; for a teaching aid you need to be able to beat students almost every time for them to spot the pattern quickly. Efron's dice are substantially better at $2/3$, but is that really the best we can do? (Crossposted from math.stackexchange)

EDIT: I missed this answer which argues that the probability cannot be > than 0.75 irrespective of the details of the dice. Still, it would be nice to know what the "simplest" set of "simple" dice is that gets you above, say, 70%, 72%, etc.

share|improve this question
    
For your teaching purpose, you can easily improve the odds by designing suitable game rules (most wins out of $k$ rolls, or maybe risk version : each player rolls $k$ identical dices of a given type, order them, and we compare the highest of each player, then the second-highest, etc.) –  Benoît Kloeckner Jan 25 '13 at 20:24

2 Answers 2

up vote 10 down vote accepted

If you fix only the number of dice, but let the number of faces be arbitrary (or if you simply find a way to make arbitrary probabitities for different faces), then the answer for $n$ faces is $\displaystyle 1-\frac1{4\cos^2(\pi/(n+2))}$. This is proved (that's quite immodest, I know...) in my paper "intransitive roulettes" in Matematicheskoe prosveschenie, III series, 2010, Vol, 14, pp.~240--2556 but only in Russian, sorry. Similar results (lacking, perhaps, only the explicit constants) you may find in the following papers:

S. Trybula, On the paradox of $n$ random variables, Zastos. Mat. (Appl. Math.) 8 (1965), 143--154.

Z. Usiskin, Max--min probabilities in the voting paradox, Ann. Math. Statist. 35 (1964), 857--862.

The optimal example is the following. Let $q=\frac1{4\cos^2(\pi/(n+2))}$. Define $r_n=0$, $r_{i}=q/(1-r_{i+1})$. Then one can show that $1-q=r_1>r_2>\dots>r_n=0$. Now let us make the following "dice": $i$th die ($1\leq i\leq n$) makes $i$ with probability $1-r_i$ and makes $i+n$ with probability $r_i$. Then each die wins the (cyclically) previous one with probability $1-q$.

Consequently, $2/3$ is the optimal number for $n=4$ for any number of faces. Pitifully, the answers for $n>4$ are irrational, hence they are not achievable on regular dice.

It seems that the optimal configuration for $n>4$ on regular dice can be made by the corresponding modification of the general optimal example. E.g., for $n=5$ we have $r_4=q=0.30797\dots$, $r_3=0.445\dots$, $r_2=1-r_3$, $r_1=1-r_4$, so we cannot achieve 70%. On the other hand, these values can be approximated to make the following 5 icosahedral dice: $$(6\times 1, 14\times 6), \quad (9\times 2, 11\times 7), \quad (11\times 3, 9\times 8), \quad (14\times 4, 6\times 9), \quad (20\times 5), $$ where each wins the (cyclically) next one with probability at most $\frac{9\times 14}{20^2}=0.315$.

Next, there is a bound for the answer when the number of faces is bounded (or fixed, as in our case). If the number of faces is $2k$ for each die, then consider the $k$th maximal numbers on each die. Consider the die which contains the maximal number among them; then it wins the next one with the probability at least $\frac{k+1}{4k}$. Hence for the icosahedral dice the result cannot exceed $\frac{29}{40}=0.725$. THis can be achieved on the following set: $$ (5\times 1,15\times 11), \quad (7\times 2,13\times 12), \quad (8\times 3,12\times 13), \quad (9\times 4,11\times 14), \quad (10\times 5,10\times 15), $$ $$ (11\times 6,9\times 16), \quad (12\times 7,8\times 17), \quad (13\times 8,7\times 18), \quad (15\times 9,5\times 19), \quad (20\times 10), $$ but not on a smaller one. Some less optimal answers with smaller number of dice are $$ (5\times 1,15\times 9), \quad (7\times 2,13\times 10), \quad (9\times 3,11\times 11), \quad (10\times 4,10\times 12), $$ $$ (11\times 5,9\times 13), \quad (13\times 6,7\times 14), \quad (15\times 7,5\times 15), \quad (20\times 8) $$ with losing probability at most $\frac{13\times 9}{20^2}=0.2925$, and $$ (5\times 1,15\times 7), \quad (8\times 2,12\times 8), \quad (10\times 3,10\times 9), (12\times 4,8\times 10), \quad (15\times 5,5\times 11), \quad (20\times 6) $$ with losing probability at most $\frac{15\times 8}{20^2}=\frac{12\times 10}{20^2}=0.3$ --- exactly 30% on 6 dice.

Finally, for dodecahedral dice the bound is $\frac{17}{24}=0.7083\dots$, hence it is also possible to make it more than 70% (but this is impossible for octahedral dice...). The example is as follows: $$ (3\times 1,9\times 9), \quad (4\times 2,8\times 10), \quad (5\times 3,8\times 11), \quad (6\times 4,8\times 12), $$ $$ (7\times 5,8\times 13), \quad (8\times 6,8\times 14), \quad (9\times 7,8\times 15), \quad (12\times 8). $$

I cannot claim that the numbers of dice presented above are optimal for these probabilities, but it seems so.

share|improve this answer
    
Thanks, Ilya. The Icosaherdal set of 6 is exactly what I had been looking for. Now you have already been very helpful, but let me ask one other thing. For the purposes of teaching, it is also useful to maximize the win probability conditional on the opponent choosing uniformly at random from the dice. Suppose that we want to keep the minimum win probability above 70%, can you improve the above sets win respect to the average win probability? –  Rationalist Jan 27 '13 at 14:28
    
can you improve the above sets with respect to the average win probability? –  Rationalist Jan 27 '13 at 15:23

Generalizing Efron, we can get probability $\ge 70\%$ with six 10-sided dice:

  • 10 sides $=6$
  • 3 sides $=11$, 7 sides $=5$
  • 4 sides $=10$, 6 sides $=4$
  • 5 sides $=9$, 5 sides $=3$
  • 6 sides $=8$, 4 sides $=2$
  • 7 sides $=7$, 3 sides $=1$

We can get probability $\ge 72\%$ (actually $.7218934911 = 122/169$) with eight 130-sided dice:

  • 130 sides $=8$
  • 36 sides $=15$, 94 sides $=7$
  • 50 sides $=14$, 80 sides $=6$
  • 58 sides $=13$, 72 sides $=5$
  • 65 sides $=12$, 65 sides $=4$
  • 72 sides $=11$, 58 sides $=3$
  • 80 sides $=10$, 50 sides $=2$
  • 94 sides $=9$, 36 sides $=1$
share|improve this answer
    
Both numbers 6 and 8 are optimal. –  Ilya Bogdanov Jan 25 '13 at 20:55
    
Thanks, @Robert Israel . It seems that the 10 icosahedra above are better than the 130-gons, but the 10-sided dice you present are interesting. Do you have any insight as to the tradeoff between minimum win probability and average win probability? –  Rationalist Jan 28 '13 at 17:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.