Mathematicians Roll Dice and Get Rock-Paper-Scissors
Source:https://www.quantamagazine.org/mathematicians-roll-dice-and-get-rock-paper-scissors-20230119/ Mathematicians Roll Dice and Get Rock-Paper-Scissors 2023-01-20 21:58:03

As Bill Gates tells the story, Warren Buffett once challenged him to a game of dice. Each would select one of four dice belonging to Buffett, and then they’d roll, with the higher number winning. These weren’t standard dice — they had a different assortment of numbers than the usual 1 through 6. Buffett offered to let Gates choose first, so he could pick the strongest die. But after Gates examined the dice, he returned a counterproposal: Buffett should pick first.

Gates had recognized that Buffett’s dice exhibited a curious property: No one of them was the strongest. If Gates had chosen first, then whichever die he chose, Buffett would have been able to find another die that could beat it (that is, one with more than a 50% chance of winning).

Buffett’s four dice (call them A, B, C and D) formed a pattern reminiscent of rock-paper-scissors, in which A beats B, B beats C, C beats D and D beats A. Mathematicians say that such a set of dice is “intransitive.”

“It’s not intuitive at all that [intransitive dice] should even exist,” said Brian Conrey, the director of the American Institute of Mathematics (AIM) in San Jose, who wrote an influential paper on the subject in 2013.

Mathematicians came up with the first examples of intransitive dice more than 50 years ago, and eventually proved that as you consider dice with more and more sides, it’s possible to create intransitive cycles of any length. What mathematicians didn’t know until recently was how common intransitive dice are. Do you have to contrive such examples carefully, or can you pick dice randomly and have a good shot at finding an intransitive set?

Looking at three dice, if you know that A beats B and B beats C, that seems like evidence that A is the strongest; situations where C beats A should be rare. And indeed, if the numbers on the dice are allowed to add up to different totals, then mathematicians believe that this intuition holds true.

But a paper posted online late last year shows that in another natural setting, this intuition fails spectacularly. Suppose you require that your dice use only the numbers that appear on a regular die and have the same total as a regular die. Then, the paper showed, if A beats B and B beats C, A and C have essentially equal chances of prevailing against each other.

“Knowing that A beats B and B beats C just gives you no information about whether A beats C,” said Timothy Gowers of the University of Cambridge, a Fields medalist and one of the contributors to the new result, which was proved via an open online collaboration known as a Polymath project.

Meanwhile, another recent paper analyzes sets of four or more dice. That finding is arguably even more paradoxical: If, for example, you pick four dice at random and you find that A beats B, B beats C and C beats D, then it’s slightly more likely for D to beat A than the reverse.

Neither Strong nor Weak

The recent rash of results got its start about a decade ago, after Conrey attended a gathering for math teachers with a session that covered intransitive dice. “I had no idea that such things could exist,” he said. “I got kind of fascinated by them.”

He decided (later joined by his colleague Kent Morrison at AIM) to explore the subject with three high school students he was mentoring — James Gabbard, Katie Grant and Andrew Liu. How often, the group wondered, will randomly chosen dice form an intransitive cycle?

Intransitive sets of dice are thought to be rare if the face numbers of the dice add up to different totals, since the die with the highest total is likely to beat the others. So the team decided to focus on dice that have two properties: First, the dice use the same numbers as on a standard die — 1 through n, in the case of an n-sided die. And second, the face numbers add up to the same total as on a standard die. But unlike standard dice, each die may repeat some of the numbers and leave out others.

In the case of six-sided dice, there are only 32 different dice that have these two properties. So with the help of a computer, the team could identify all the triples in which A beats B and B beats C. The researchers found, to their astonishment, that A beats C in 1,756 triples and C beats A in 1,731 triples — nearly identical numbers. Based on this computation and simulations of dice with more than six sides, the team conjectured that as the number of sides on the dice approaches infinity, the probability that A beats C approaches 50%.

The conjecture, with its blend of accessibility and nuance, struck Conrey as good fodder for a Polymath project, in which many mathematicians come together online to share ideas. In mid-2017, he proposed the idea to Gowers, the originator of the Polymath approach. “I very much liked the question, because of its surprise value,” Gowers said. He wrote a blog post about the conjecture that attracted a flurry of comments, and over the course of six additional posts, the commenters succeeded in proving it.

In their paper, posted online in late November 2022, a key part of the proof involves showing that, for the most part, it doesn’t make sense to talk about whether a single die is strong or weak. Buffett’s dice, none of which is the strongest of the pack, are not that unusual: If you pick a die at random, the Polymath project showed, it’s likely to beat about half of the other dice and lose to the other half. “Almost every die is pretty average,” Gowers said.

The project diverged from the AIM team’s original model in one respect: To simplify some technicalities, the project declared that the order of the numbers on a die matters — so, for example, 122556 and 152562 would be considered two different dice. But the Polymath result, combined with the AIM team’s experimental evidence, creates a strong presumption that the conjecture is also true in the original model, Gowers said.

“I was absolutely delighted that they came up with this proof,” Conrey said.

When it came to collections of four or more dice, the AIM team had predicted similar behavior to that of three dice: For example, if A beats B, B beats C and C beats D then there should be a roughly 50-50 probability that D beats A, approaching exactly 50-50 as the number of sides on the dice approaches infinity.

To test the conjecture, the researchers simulated head-to-head tournaments for sets of four dice with 50, 100, 150 and 200 sides. The simulations didn’t obey their predictions quite as closely as in the case of three dice but were still close enough to bolster their belief in the conjecture. But though the researchers didn’t realize it, these small discrepancies carried a different message: For sets of four or more dice, their conjecture is false.

“We really wanted [the conjecture] to be true, because that would be cool,” Conrey said.

In the case of four dice, Elisabetta Cornacchia of the Swiss Federal Institute of Technology Lausanne and Jan Hązła of the African Institute for Mathematical Sciences in Kigali, Rwanda, showed in a paper posted online in late 2020 that if A beats B, B beats C and C beats D, then D has a slightly better than 50% chance of beating A — probably somewhere around 52%, Hązła said. (As with the Polymath paper, Cornacchia and Hązła used a slightly different model than in the AIM paper.)

Cornacchia and Hązła’s finding emerges from the fact that although, as a rule, a single die will be neither strong nor weak, a pair of dice can sometimes have common areas of strength. If you pick two dice at random, Cornacchia and Hązła showed, there’s a decent probability that the dice will be correlated: They’ll tend to beat or lose to the same dice. “If I ask you to create two dice which are close to each other, it turns out that this is possible,” Hązła said. These small pockets of correlation nudge tournament outcomes away from symmetry as soon as there are at least four dice in the picture.

The recent papers are not the end of the story. Cornacchia and Hązła’s paper only begins to uncover precisely how correlations between dice unbalance the symmetry of tournaments. In the meantime, though, we know now that there are plenty of sets of intransitive dice out there — maybe even one that’s subtle enough to trick Bill Gates into choosing first.

Uncategorized Source:https://www.quantamagazine.org/mathematicians-roll-dice-and-get-rock-paper-scissors-20230119/

Leave a Reply

Your email address will not be published. Required fields are marked *