💻 computer science

Dicey Games: Shared Sources of Randomness in Distributed Systems

This paper introduces "Dicey Games," a formal framework for analyzing distributed systems with shared sources of randomness, demonstrating that teams can achieve optimal winning probabilities exceeding independent randomization by strategically allocating pairwise shared randomness and characterizing the existence, representation, and computational complexity of such strategies.

Original authors: Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini

Published 2026-05-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a high-stakes game of "Matching Pennies," but instead of just two people, you have a team of friends trying to beat a cunning opponent called "The Devil."

Here is the setup:

The Goal: Everyone (the team and the Devil) simultaneously shouts "Heads" or "Tails."
The Win Condition: The team wins only if everyone shouts the exact same thing (all Heads or all Tails). If even one person disagrees, the Devil wins.
The Problem: The Devil is smart. He knows your strategy. If you just flip your own private coins, the Devil can easily predict you, and your chances of winning are tiny.

The Magic Ingredient: Shared Dice

The paper introduces a twist: Shared Randomness.

Imagine the team has access to magical dice.

Private Dice: If everyone rolls their own private die, they are independent. The Devil can exploit the gaps between them.
Shared Dice: If two friends share a single die, they can see the same number. They can agree, "If the die shows a number greater than 0.5, we both shout 'Heads'." This creates a perfect link between them.

The big question the authors ask is: What if the team has a complex web of shared dice?

Alice and Bob share a die.
Bob and Charlie share a different die.
Charlie and Alice share a third die.

Can this web of connections help them win more often than if they just had one giant shared die?

The Surprising Discovery

The authors found that the answer is yes, but the solution is weirdly geometric.

The Naive Approach: You might think, "Let's just add up the numbers on our dice. If the sum is high, we shout Heads." The paper shows this is actually a bad idea. It only gets you a win rate of about 16.6% (1/6).
The "Cube" Strategy: The optimal strategy is much simpler but harder to visualize. Imagine the dice rolls as coordinates in a 3D cube. The team agrees on a specific "cut" inside that cube.
- If your two dice rolls are both above a certain magical number (let's call it $\alpha$ ), you shout "Heads."
- If either is below, you shout "Tails."
- This creates a shape inside the cube (like a smaller cube in the corner) where everyone agrees.

By tuning this magical number $\alpha$ perfectly, the team can boost their win rate to approximately 27.8%. This is a huge jump from the 16.6% of the naive approach and much better than the 12.5% they would get with no shared dice at all.

The "Grid" Discovery

The paper proves something very important about how these teams should think.

You might imagine a team strategy as a complex, messy painting where every tiny speck of color represents a different decision based on the dice rolls. The authors prove that you don't need a painting.

You only need a grid.
Think of the space of all possible dice rolls as a giant cake. The optimal strategy is simply to slice this cake with straight cuts (like a grid) into rectangular blocks. Inside each block, the team just picks one action (Heads or Tails).

Why this matters: It turns a messy, infinite mathematical problem into a clean, finite puzzle. Instead of worrying about infinite possibilities, you just need to figure out where to place a few straight lines.

The "Devil's" Perspective

The paper treats this as a zero-sum game. The Devil is trying to minimize the team's win rate, and the team is trying to maximize it.

If the team picks a strategy, the Devil picks the action (Heads or Tails) that hurts the team the most.
The "Value" of the game is the win rate the team can guarantee no matter what the Devil does.

The Complexity (The "Hard" Part)

The authors also looked at how hard it is to solve these games on a computer.

The Size of the Solution: Even though the answer might be an irrational number (like $\sqrt{2}$ or a weird root of a polynomial), the paper proves that you can describe the optimal strategy using a finite amount of information. It's like saying, "The answer is a specific number that is the root of this specific equation."
Computational Difficulty: Finding this optimal strategy is computationally very heavy. It's so hard that it belongs to a class of problems that would take a supercomputer an exponential amount of time to solve as the game gets bigger. However, if the number of dice each person holds is small and fixed, the problem becomes much more manageable.

The "Pairing" Conjecture

Finally, the authors looked at what happens if you have a huge team (say, 100 people) where everyone shares a die with everyone else.

Intuition: You might think you need to use all those connections.
The Reality: The authors suspect (and have verified for small groups) that the best strategy is actually to ignore most of the dice.
- If you have an even number of players, just pair them up. Each pair uses their shared die to coordinate perfectly, and they ignore everyone else.
- If you have an odd number, group three people together to use the "Cube Strategy" mentioned earlier, and pair up the rest.
- The extra dice? They are essentially useless noise.

Summary

This paper is about a team of players trying to coordinate perfectly against a smart opponent using limited, shared random signals. They discovered that:

Complex connections don't always mean complex strategies. The best plan is often a simple "grid" cut.
Geometry is key. The solution involves finding the perfect shape inside a multi-dimensional space.
Less is often more. Even with a web of shared randomness, the team often wins best by ignoring most of it and focusing on small, tight-knit groups.

It's a mathematical proof that in a game of chance and coordination, sometimes the simplest, most rigid structure (a grid) beats the most complex, fluid one.

Technical Summary: Dicey Games: Shared Sources of Randomness in Distributed Systems

1. Problem Definition

The paper introduces Dicey Games, a formal framework for analyzing concurrent games played by a team of players against a single opponent (the "Devil") under constraints of shared randomness.

In standard concurrent games, players often randomize independently. However, in distributed systems, agents may share specific sources of randomness (modeled as independent random variables, or "dice," uniformly distributed over $[0, 1]$ ) while lacking access to others. The core problem is to determine the max-min value of such games: the highest probability of winning the team can guarantee, assuming the Devil knows the team's strategy and plays optimally to minimize that probability.

The framework generalizes the concept of correlated equilibria (where all players share a single common source) and independent randomization (where no sources are shared). The specific challenge addressed is how the topology of shared randomness—which subset of players has access to which dice—affects the team's ability to coordinate and the computational complexity of finding optimal strategies.

The motivating example is a "triangular matching pennies" game with three team players (Ada, Bertrand, Claude) and the Devil. Each pair of team players shares a distinct die. The paper investigates whether the team can achieve a win probability higher than $1/4$ (the bound for independent randomization or simple pairwise sharing) by utilizing the full triangular structure of shared dice.

2. Methodology

The authors employ a blend of game theory, computational algebraic geometry, and non-linear optimization.

2.1 Geometric Representation of Strategies

A player's strategy is modeled as a measurable function from the space of accessible dice rolls $[0, 1]^\ell$ to the set of actions. Geometrically, this corresponds to partitioning a hypercube. The authors focus on grid strategies, where the hypercube is partitioned by cutting each coordinate axis into $k$ intervals.

Key Insight: The paper proves that for any dicey game where the Devil has $k$ actions, there exists an optimal collective strategy that is a $k$ -grid strategy. This reduces the infinite-dimensional space of measurable functions to a finite-dimensional optimization problem defined by threshold values on the dice axes.

2.2 Transformation via Slicing

To prove the optimality of grid strategies, the authors use a constructive approach based on Carathéodory's theorem. They demonstrate that any arbitrary collective strategy can be transformed into a grid strategy without decreasing the game's value. This is achieved by "slicing" the strategy space along specific dice dimensions and replacing complex partitions with convex combinations of a finite number of slices.

2.3 Algebraic Formulation and Complexity Analysis

Once reduced to grid strategies, the problem of finding the optimal value is formulated as a system of polynomial inequalities over real variables (the thresholds and action assignments).

Existence and Representation: The authors utilize results from real algebraic geometry (specifically Cylindrical Algebraic Decomposition by Collins and properties of semi-algebraic sets by Basu, Pollack, and Roy) to prove that optimal strategies admit finite representations.
Optimality Conditions: They apply Fritz John conditions to characterize the set of optimal solutions, showing that the optimal value and strategy parameters lie within semi-algebraic sets that can be bounded in size.

3. Key Contributions and Results

3.1 Structural Results

Theorem 12 (Normal Form): For any dicey game where the Devil has $k$ actions, if a collective strategy guarantees a value $t$ , there exists a $k$ -grid collective strategy that also guarantees $t$ . This implies that optimal strategies can be described by a finite set of thresholds.
Theorem 15 (Finite Representation): Optimal collective strategies and their values have finite representations. The bit-size of these representations grows exponentially with the size of the game description but is bounded. This result relies on a novel combination of algebraic geometry and non-linear optimization techniques.

3.2 Complexity Results

The paper establishes the computational complexity of three natural problems:

Threshold Problem: Deciding if a team can guarantee a payoff $\ge t$ $\geq t$ .
- Result: The problem is in EXPSPACE and is NEXP-hard.
- Fixed Die Bound: If the number of dice per player is bounded by a constant, the problem is in NP $_\mathbb{R}$ (the existential theory of the reals) and is $\exists\mathbb{R}$ -hard.
Value Computation: Computing the exact max-min value.
- Result: Solvable in EXPSPACE.
Allocation Problem: Determining how to optimally allocate a fixed set of dice among players to maximize the team's value.
- Result: Falls into the same complexity classes as the fixed-structure versions (EXPSPACE/NEXP-hard generally; NP $_\mathbb{R}$ / $\exists\mathbb{R}$ -hard with fixed die bounds).

3.3 Specific Case Studies

Triangular Matching Pennies: For the 3-player case with pairwise shared dice, the optimal win probability is approximately 0.2781 (specifically $\beta = 3\alpha^2 - 2\alpha^3$ , where $\alpha$ is the root of $X^3 - 3X + 1 = 0$ in $[0, 1]$ ). This is strictly better than the $1/4$ bound achievable with independent randomization or simple pairwise coordination.
4-Clique and 5-Clique Matching Pennies:
- In a 4-player game where every pair shares a die, the optimal strategy surprisingly ignores most dice. The team groups into two pairs, each using their shared die to coordinate perfectly, achieving a win probability of $1/4$ .
- In a 5-player game, the optimal strategy involves a group of three players using the triangular strategy (yielding $\approx 0.2781$ ) and the remaining two forming a pair (yielding $0.5$), resulting in a total value of $\approx 0.139$ .

3.4 Conjecture

Based on the examples, the authors propose Conjecture 32: In a matching pennies game with $n$ players where every pair shares a die, the optimal strategy involves grouping players into pairs (using $1/2$ probability coordination) and, if $n$ is odd, grouping three players to use the triangular strategy. This suggests that complex global coordination via shared randomness often collapses into simpler local structures.

4. Significance and Motivation

The paper claims significance in several areas:

Theoretical Bridge: It provides a formal intermediate model between independent randomization (Cournot, Nash) and full correlated equilibria, addressing the realistic constraint that shared randomness is often limited by topology.
Distributed Systems: The framework models scenarios in computer science where unrestricted shared randomness can compromise privacy, create unintended communication channels, or violate protocol correctness. It offers a way to model and verify systems under restricted randomness.
Economics and Social Choice: The model captures constraints in financial markets (legal/organizational limits on coordination) and social choice theory (how restricted information sources affect voting outcomes and fairness).
Mathematical Novelty: The work introduces a "novel blend" of techniques from computational algebraic geometry and non-linear optimization to solve game-theoretic problems, providing tools potentially applicable to similar problems in the future.

The authors emphasize that while the optimal strategies can be irrational and complex, they are always representable with finite precision, and the computational hardness of finding them is well-characterized within the hierarchy of complexity classes.