"Go-first" dice for $N$ players

Question

I'm interested in sets of dice that can be used to determine who "goes first" (hence the name) in an $N$-player game; more generally, I want to determine a complete ordering of the players with a single roll of the dice, and have this ordering be random. Specifically, then, what's needed is an assignment of the labels $\{1,2,...,Nm\}$ to the faces of $N$ different $m$-sided dice, such that:

1. No two faces share a label (so no ties can occur).
2. When a face is chosen at random on each die, the rank-ordering of the dice based on the chosen faces is uniformly random across all permutations (so the rolls are fair).

For instance, if $N=2$ and $m=2$ (two coins, basically), then you can label the coins $\{1,4\}$ and $\{2,3\}$. A solution for $N=4$ and $m=12$ is sold here. For what values of $N$ and $m$ are there solutions?

A simple constraint on the minimum value of $m$ comes from the fact that we are choosing one of $N!$ possibilities on the basis of $m^N$ equiprobable rolls; certainly the former must divide the latter. So for $N=2,3,4,5,6,\dots$, necessarily $m \ge 2, 6, 6, 30, 30, \dots$. Is this minimum value always achievable?

Answer 1

For the N=4 case, m=6 is not sufficient. I exhaustively checked all possible 4d6 configurations and came up empty handed. That is why the GoFirst dice on my website are 4d12 (12-sided). I do not yet know if m=30 is sufficient for N=5 (much less N=6).

Geometrically, a 60-sided fair polyhedron exists and is aesthetically pleasing (q.v. Pentakis Dodecahedron) if that is what is needed. But trying to find a 5d30 is proving more than a typical computer can handle, much less a 5d60.

Answer 2

What constraints are there on $m$, the number of sides of the dice? Once $N$ hits $7$ you need $7$ to divide $m$ and there are no regular polyhedra that can do that. If all the dice are the same, you need $m$ to be a multiple of $210$ if $N \ge 7$. Maybe it is better to use dice of different sizes. There are 14 sided polyhedra that look close to spherical. The truncated cube and truncated octahedron should be able to have the dimensions chosen to be fair. Then for $N=7$, roll $d14, d20, 2d6$ to get $10080$ possibilities. If the dice are colored or otherwise distinguishable, all the $m_1m_2 \ldots m_n$ rolls are distinguishable, so if $N! | m_1m_2 \ldots m_n$ you can certainly do what you want.

Answer 3

If we remove the restriction that dice must have equal numbers of faces, then for $N\!=3$, we have (at least) the following two possibilities, with one $6$-sided, one $3$-sided and one $4$-sided dice (a total of $13$ faces): $$1,3,7,8,11,12\qquad2,9,10\qquad4,5,6,13$$ $$1,3,8,9,10,11\qquad2,7,12\qquad4,5,6,13$$ Since there is no need for faces on any single dice to be distinct, these are equivalent to: $$1,3,5,5,7,7\qquad2,6,6\qquad4,4,4,8$$ $$1,3,6,6,6,6\qquad2,5,7\qquad4,4,4,8$$ respectively.

It seems likely that there are also solutions for $N\!=4$ with fewer (perhaps a lot fewer) than a total of $48$ faces.