Is There a Strongest Die in a Set of Dice with the Same Mean Pips?

Shang Lu, Shuji KijimaAAAI 2022 · DOI

Abstract

In a set of dice where each die has the same average value and no two dice share the same face value, the existence of a "strongest" die—one that beats or draws with all others—is not guaranteed. This paper investigates the conditions under which such a die can exist. We prove that in a "regular partition" where all numbers in a sequence are used, a strongest die never exists, leading to inherent non-transitivity. However, in "regular packing" scenarios with gaps in the available numbers, a strongest die can emerge at extreme pip sums. We provide algorithmic tools and mathematical bounds to characterize these occurrences.

Introduction

Non-transitivity is a counterintuitive phenomenon in probability, famously illustrated by Efron’s dice, where Die A beats B, B beats C, and C beats A. This paper explores whether non-transitivity is inevitable in "fair" dice sets. We define fairness through two constraints: first, no two dice can roll the same number (disjoint sets of pips), and second, every die must have the same sum of pips, ensuring equal mean values.

The central question is whether a single "best" die can exist under these constraints. If such a die exists, the game becomes trivial as other options are "useless strategies." If not, the system is non-transitive, resembling games like Rock-Paper-Scissors.

Methodology

The study employs a multi-faceted approach combining combinatorial proofs, dynamic programming, and computational search.

Mathematical Framework

The researchers focused on two primary scenarios:

  1. Regular Partition: $n$ dice with $m$ sides using every number from $1$ to $nm$ exactly once.
  2. Regular Packing: Dice sets that do not necessarily use all available numbers within a range $[1, k]$.

Algorithms

To analyze these sets, the authors developed JUDGEMENT-ONE (Algorithm 1). This dynamic programming approach determines if a specific die is the strongest by maximizing the win probability against it, given constraints on the sum ($w$) and number of sides ($m$). The algorithm runs in $O(kmw)$ time. Additionally, a depth-first search (Algorithm 3) was used to map the existence of strongest dice across the entire range of possible pip sums.

Experimental Setup

Synthetic dice sets were generated using parameters $(k, m, n, w)$, where $k$ is the maximum face value, $m$ is the number of sides, $n$ is the number of dice, and $w$ is the fixed sum of pips.

Results and Discussion

The investigation yielded several key insights into the relationship between pip distribution and die strength.

The Impossibility of a Strongest Die in Partitions

Theorem 5 serves as a core result: for any set of three or more dice forming a regular partition, if any pair has a win-loss relationship, a "strongest" die cannot exist. Non-transitivity is an inescapable reality in these perfectly balanced sets.

The Emergence of Strength at Extremes

In "packing" scenarios, the existence of a strongest die depends heavily on the target sum $w$. Computational mapping revealed a distinct pattern: strongest dice are most likely to appear when $w$ is either very high or very low. In these extreme ranges, the constraints on number distribution are so restrictive that a single configuration often becomes dominant.

Figure 1: Distribution of dice types for k=32, m=8.
Figure 2: Distribution of dice types for k=36, m=8.

As shown in Figures 1 and 2, the "strictly strongest" dice (dashed line) appear at the edges of the possible weight range. Conversely, the "middle" range is dominated by "draw dice" (solid line) or non-transitive sets where the number of possible configurations explodes, leading to chaotic win-loss cycles.

Conclusion

This research demonstrates that while non-transitivity is the norm for perfectly partitioned fair dice, "strongest" dice can emerge when there is flexibility in the numbers used, particularly at the extremes of the possible pip sums. Future work may extend these findings to odd-sided dice and further characterize the complex tournament graphs formed by these non-transitive relationships.

Summary updated

BibTeX
@inproceedings{lu2022is,
  author = {Shang Lu and Shuji Kijima},
  title = {{Is There a Strongest Die in a Set of Dice with the Same Mean Pips?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20447},
}
Figure