MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 316 characters in body

Hm.

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 prived 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.

1

Hm. 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 prived (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.

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.