I love that they put so much work into trying to solve this when there is an equally trivially simple mechanical solution that works just as well and easily scales up to any number of users:
1. Put consecutive numbered tiles in an opaque bag.
2. Each person reaches in and blindly grabs a tile.
3. Play proceeds in the order of tiles.
You can think of dice rolling as simple random sampling with replacement. It's naturally good at generating combinations. Drawing from a bag is random sampling without replacement. It's naturally good at generating permutations.
Using a system that generates combinations to generate uniformly distributed random permutations is a super fun mathematical exercise and I'm sure this brought plenty of joy to the authors. But if you're just trying to design a physical mechanism to generate permutations, it'll be an easier starting point if you do sampling without replacement.
In fact, if you do want to generate permutations with dice, a simple (but laborious) way to do it is:
1. Choose an arbitrary ordering for the players.
2. For each player, roll a die. If the value rolled is the same as any value rolled by a previous player, re-roll. Continue to re-roll until a unique value is rolled.
3. Play proceeds in the order of values each player rolled.
You'll probably want to use d20 or some dice with a large number of faces relative to the number of players in order to minimize collisions and re-rolling.
I'm not 100% certain, but I believe this will generate an unbiased ordering where the order of players in step 1 has no effect on the resulting order determined in step 3.
It's worth noting that they primarily pursue this as a pleasurable puzzle, not for any practical payoff to the problem of player primacy:
>We both understood that this was really a "solution looking for a problem" (there are plenty of perfectly acceptable ways to quickly determine who might go first in a game), but mathematically, wouldn't it be great if a set of dice could be created [...]
There might be a slick method to prove your final approach works to generate a uniformly random permutation. First, it's easy to prove if the number of players, n, equals the number of sides of the die, m. Because a random permutation is characterized as the first player equally likely to land in any spot, along with the permutation among the remaining n-1 players into the remaining n-1 slots being uniformly random. If n=m, then the first player's number that they pick determines where they end up in the permutation. And by induction, the remaining players pick a permutation uniformly from the remaining slots. The base case of n=m=1 is immediate.
Now the slick proof for the case m > n is to add m-n extra "dummy" players. They get to pick after the n players have picked. By the above argument, we get a uniformly random permutation of the m total players, including the dummy players. But when we remove any subset of players from a uniformly random permutation -- in this case, the dummy players -- we are left with a uniformly random permutation on the rest.
> In fact, if you do want to generate permutations with dice, a simple (but laborious) way to do it...in a single roll
A single die of <#players>! sides.
4 players = 24 sided die, each side has an order permutation.
Impractical, but doable. Excepting for all the other arbitrary requirements.
This is all an elaborate exercise borne of someone's idle time, so it's best not to put too much into it. They already did that work.
> If the value rolled is the same as any value rolled by a previous player, re-roll. Continue to re-roll until a unique value is rolled.
This gives an advantage to earlier players because it gives them "first dibs" on higher numbers. In the extreme, if the first player rolls the highest number, no one can subsequently beat them no matter what they roll.
If you consider n players and an n-sided die, you'll see this isn't true in that case. The first player has an exactly equal chance to be first, second, ..., last.
> to generate permutations with dice, a simple (but laborious) way to do it is
Of course, the article rules this out, and requires a single roll.
I can vaguely imagine a system where what the authors describe will come in handy. Let's say you have a group of n distributed agents that collaborate over multiple rounds, and they need to establish a fair order of precedence for each consecutive round. Let's say each agent issues a message each round, and a "counter" decides the order that those messages resolve.
In that case, you can (pre-)assign each agent a pseudorandom go-first die. They can tag their messages with the results of their go-first die, and the counter can now resolve the messages in a fair order.
If you publish the PRNG seeds for all agents, so that every agent has it, they can all be counters. This means that every agent will resolve the messages in a deterministic order every round, and over all the rounds, the processing will be fair. Seems like a useful property.
It might still be if interest from a computational viewpoint. For instance what if you need to compute a fair and random ordering for many many elements of a set? Then the dice method is more parallelizable than the bag method.
Well, I think your second example has problems (already noted by others), but also: get out of here with your sensible and boring practicalities! This is a great article and a worthy quest!
Reiner Knizia uses distributions that are meant to have this quality (or get close enough to make people happy), most notably in Ra. Ra is an auction game where each player gets the name number of bidding tokens. Each token has a unique number on it, and you can only use a single token to bid, ensuring that there are never ties.
Ra is an example, but he uses it elsewhere. He's a math PhD who often writes in his books about how to break down these problems, and I wonder if he approached it the same way or reached the same conclusion.
There's another dice puzzle which can also be named "go first" dice.
There exist three dice where A beats B, B beats C and C beats A, statistically speaking. So if you consistently throw A and B, A has a higher chance of rolling a greater number than B, etc.
Kind of rock-paper-scissors, so whoever "goes first" and picks the die will (statistically) lose against a smart opponent who chooses second.
A friend and I had some manufactured, 20 years ago. We thought about selling them, but had no idea how much interest there would be. My friend did the math to come up with 6-sided ones that had the most uneven odds we could find, and each dice summed to the same number, and all the numbers 1-24 were each used once, and the numbers 1, 2, 3, and 4 were each on a different die, making them easy to identify. We colored them red, green, blue, and then maybe yellow?, if I remember correctly, to also try to make them easy to identify. If I remember correctly, 1 and 3 were fair, and 2 and 4 were fair, which we thought was also neat, because it would help you "prove" that the dice were fair, heh.
I used to play at low level but officially sanctioned Magic: The Gathering tournaments at a local shop, and there was no official policy for deciding who would play first, My understanding is that this is even the case at higher-level prize tournaments, and I think generally only high profile matches are live streamed (e.g. ones with well-known players or the final few rounds after most people are eliminated), and I read an article from a professional player a few years back about how sometimes people try to get away with things when the traditional "high roll" method is used (i.e. each player rolls their own die and the highest roll goes first, with repeats for ties), like bringing extremely large dice that essentially don't roll so much as just flop once, making it easy to toss in a way to force a given result. I'd also seen people use "evens and odds", where one person calls even or odd and the other rolls a die, with the choice of whether to go first going to the person who called if they were right and to the roller if not, but this still gives the person rolling some influence if they're unscrupulous. The article proposed that having one player call evens or odds but having _both_ players roll would eliminate any ability for cheating (assuming both players roll at once), since even being able to choose your result exactly would not be able to affect the chance of the sum being even or odd without knowing what your opponent would roll.
- Permutation-fairness is likely too strong of a condition at anything other than serious competitive tournaments. When playing a game casually, usually the group first sits down in a circle and then chooses someone to go first, taking turns clockwise from there; then if the method for choosing the first player is first-player-fair then it is also place-fair.
- Although having to sometimes resolve ties is annoying, there is one major benefit of choosing turn order by rolls of the same dice: You are guaranteed that any non-fairness in the dice do not affect turn order determination.
For up to 50 players: Roll 2d10 for a number 0-99. Ignore top 100 mod p (reroll). Otherwise
chosen player is r mod p. r is result, p is number of players.
You roll two dice, and you have to decide which permutation to keep, and it gets added to your score. So, if I roll [3,1] then I can add 13 or 31 to my score. The aim is to take turns and get closest to 100 without going over, and you can pass your turn if you think you're close enough.
It can also be played with more dice, ie 1000, 10000, but it gets easier the more dice there are.
The correct webpage seems to load fine for me on Brave 1.45.127 (Chromium 107.0.5304.110), Android 11. It is, however, unencrypted. Maybe something is intercepting your HTTP connection and redirecting you?
I too love the effort put into solving this problem. It's a totally different mindset from my own and clearly they get a lot of satisfaction from it. I myself would be satisfied with understanding that it is possible but non-trivial to do this, and immediately propose a trivial alternative like choosing from a deck of playing cards. Society needs both kinds of people! (and everyone in between)
Can I ask a dumb question? I understand the permutation argument for why using 5 six-sided dice can't possibly be fair, but looking at the serpentine example, I'm having trouble intuiting why. At a glance, removing any one of those dice looks pretty fair.
If you look at just the first 5 dice and compute the probability that player one rolls lowest, of the 6^4 combinations of rolls the other players can make:
1 beats all 6^4; 16 beats 4^4, 17 beats 4^4, 32 beats 2^4, 33 beats 2^4, and 48 beats nothing. So player 1 is lowest 1840 out of 6^5, or ~23.7%.
A similar argument shows player 5 rolls lowest 1414 out of 6^5, or only 18.2% of the time.
Free of financial cost perhaps, but not free of effort. Let's Encrypt is a pain to set up and maintain on a self-hosted website, if you don't maintain websites professionally and don't have experience.
People lament the centralization of the web, but this https-or-the-highway mantra is contributing to exactly that! Because there is a way to truly get https "for free", and it's to throw up your site on Github Pages or Squarespace. Or just use Facebook.
I don't understand why they would be, in general. The content isn't interesting for snoops. I supposed it could screw you if you had an elaborate Murder She Wrote plan to kill someone that relied on a math trick, and visiting this particular page was enough for the jury to convict.
It's good for everybody to use ssl, but people writing essays about their hobbies aren't responsible for shady public wifi endpoints.
At least in FF there's a setting to force you to click through a full page warning to enable visiting a site without ssl. I use it, so I can be aware of my risks.
They’re not “responsible” in the sense that I don’t think it’s not some kind of moral failing. I’m just pointing out that it’s not true that having TLS on this site wouldn’t be useful to anyone. It would, and the webmaster enabling, despite not required, would be appreciated.
Yup. I was at Atlanta airport and clicked on a bunch of links from the HN front page. All the pages that were sent over unencrypted HTTP got invasive ads injected into them. All the pages over HTTPS were fine.
1. Put consecutive numbered tiles in an opaque bag.
2. Each person reaches in and blindly grabs a tile.
3. Play proceeds in the order of tiles.
You can think of dice rolling as simple random sampling with replacement. It's naturally good at generating combinations. Drawing from a bag is random sampling without replacement. It's naturally good at generating permutations.
Using a system that generates combinations to generate uniformly distributed random permutations is a super fun mathematical exercise and I'm sure this brought plenty of joy to the authors. But if you're just trying to design a physical mechanism to generate permutations, it'll be an easier starting point if you do sampling without replacement.
In fact, if you do want to generate permutations with dice, a simple (but laborious) way to do it is:
1. Choose an arbitrary ordering for the players.
2. For each player, roll a die. If the value rolled is the same as any value rolled by a previous player, re-roll. Continue to re-roll until a unique value is rolled.
3. Play proceeds in the order of values each player rolled.
You'll probably want to use d20 or some dice with a large number of faces relative to the number of players in order to minimize collisions and re-rolling.
I'm not 100% certain, but I believe this will generate an unbiased ordering where the order of players in step 1 has no effect on the resulting order determined in step 3.