14

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 potentially a 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 another 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?

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"/smallest set of "simple" dice is that gets you above, say, 70%, 72%, etc.

Also, assuming that the other player doesn't yet understand what's going on, a uniform nontransitive probability of $75%$ - $\epsilon$ can still be improved by making some dice lose with probability > $75$%, so that if the other player chooses randomly from the dice, the will get beaten on average much more than $75$% of the time. The "worse" choices can be encouraged by making the highest number on them very high. As far as I understand the proof in this answer, this possibility is not excluded.

Community
  • 1
Rationalist
  • 151
  • With 4 dice, I suppose you would like to forbid A > B > C > A; D > A, D > B, D > C, and insist A > B > C > D > A? Or what, exactly? – MJD Jan 24 '13 at 23:15
  • 1
    If there is a nontransitive 3-chain in a set of 4 dice, then the 4th dice is superfluous, and there is another answer here on math.stackexchange which claims that the best you can do with 3 dice is $p = 0.58$ – Rationalist Jan 25 '13 at 17:33
  • 1
    You're not going to get $p > 80$% no matter what you do. As this question notes, there's a strict upper bound of $p<3/4$ for any intransitive set of random variables, and for 6-sided dice considerations of discreteness reduce that to $p<2/3$ (so Efron's dice are optimal for a set of 6-sided dice). – Micah Jan 25 '13 at 18:03
  • Thanks, Micah, I just caught that. Presumably there might be a set of 3 20-sided dice which achieve the bound for n=20 sides, 72.5%. This would still be fairly impressive; although the constructed solution in the answer we linked to uses n n-sided dice, Efron shows that you can hit the bound with less than n dice. How good does it get? – Rationalist Jan 25 '13 at 18:35
  • Note that the question for which I determined the optimum $p=21/36\approx0.58$ required the win probability to be independent of which die you pick. The code I posted there is easily modified not to impose that requirement, and then it finds this set of three dice: $(0,3,3,3,3,3)$, $(2,2,2,2,2,5)$, $(1,1,1,4,4,4)$, with win probabilities $25/36$, $21/36$, $21/36$, for which the expected win probability upon uniformly randomly choosing a die is $67/108\approx0.62$, and the worst choice has the highest number. I hope to be posting an answer with more results when I find the time. – joriki Jan 26 '13 at 13:01
  • I think to turn the part of your question where you allow the dice to win with different probabilities into a well-defined mathematical question you'll need to somehow quantify whether the set of dice has an acceptably "fair" appearance. Without any such restriction, you can get an expected win probability of $(k-1)/k$ upon uniformly randomly choosing a die from $k$ dice, simply by making all faces of a die show the same number, and assigning all but one of the dice a number higher than its predecessor. – joriki Jan 26 '13 at 13:09
  • Joriki, thanks for pointing that out. I would certainly want the dice to be nontransitive. But even then there might be some tradeoff between the minimum win probability and the average win probability. What does that tradeoff look like? – Rationalist Jan 26 '13 at 17:49
  • Also, Joriki, I am having some trouble understanding your answer here: http://math.stackexchange.com/questions/57338/how-far-can-probability-intransitivity-be-stretched?rq=1

    Specifically, I don't quite understand "so for the median to increase" - why can't we have a constant median for all dice? Of course a constant median would still impose p <= 0.75.

     – Rationalist Jan 26 '13 at 17:54
  • Actually it is the set, not the dice themselves, which is called nontransitive. – Marc van Leeuwen Sep 02 '13 at 14:28
  • @joriki: To make the game seem fair, we can let the student choose which die they want, saying that you are giving them the advantage of picking first. If they think (wrongly) that there is always a best die, they would not find anything wrong with that. So we want the worst-case to have the highest possible probability of us winning. Anyway there is an answer on MO that states that 2/3 is the best for any 4 dice (http://mathoverflow.net/a/119885). – user21820 Nov 25 '16 at 06:35

1 Answers1

1

A great visual aid for developing a set of four transitive dice is this one:

enter image description here

In the left image, each quadrant shows the probability diagram of each of the four duels. In the right image you see that these diagrams form a spiral.

See also: https://www.quora.com/What-are-some-mathematical-paradoxes/answer/Job-Bouwman

Job Bouwman
  • 1,859