Dicey Games: Shared Sources of Randomness in Distributed Systems DOI: XXXXXXX.XXXXXXX ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Probabilistic computation CCS: Mathematics of computing Distribution functions CCS: Theory of computation Random network models

Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini · 2026

Read Dicey Games: Shared Sources of Randomness in Distributed Systems DOI: XXXXXXX.XXXXXXX ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Probabilistic computation CCS: Mathematics of computing Distribution functions CCS: Theory of computation Random network models by Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18303.txt.

Introduction

Léonard Brice, Thomas A. Henzinger, and K. S. Thejaswini study games where players share a source of randomness. Their 2026 preprint opens with a four-player matching pennies game. A team of three faces the Devil. Each player calls heads or tails at the same time. The team wins only if all four calls match. If the team randomizes independently, it wins with probability one in eight. Shared randomness changes that math.

The paper grows that seed into a theory of dicey games in distributed systems. Shared coins can align players who cannot talk. That alignment has real value in protocols and verification. The work links a toy game to deep questions about coordination.

Catalog record

CREATORLéonard Brice, Thomas A. Henzinger, K. S. Thejaswini
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18303

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dicey Games: Shared Sources of Randomness in Distributed Systems DOI: XXXXXXX.XXXXXXX ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Theory of computation Probabilistic computation CCS: Mathematics of computing Distribution functions CCS: Theory of computation Random network models Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini Abstract . Consider a 4-player version of Matching Pennies where a team of three players competes against the Devil. Each player simultaneously says “Heads” or “Tails”. The team wins if all four choices match; otherwise the Devil wins. If all team players randomise independently, they win with probability 1 / 8 1/8 ; if all players share a common source of randomness, they win with probability 1 / 2 1/2 . What happens when each pair of team players shares a source of randomness? Can the team do better than win with probability 1/4? The surprising (and nontrivial) answer is yes! We introduce Dicey Games, a formal framework motivated by the study of distributed systems with shared sources of randomness (of which the above example is a specific instance). We characterise the existence, representation and computational complexity of optimal strategies in Dicey Games, and we study the problem of allocating limited sources of randomness optimally within a team. 1. Introduction Concurrent games, and especially two-player zero-sum concurrent games, provide natural models of limited information, distributed decision-making, and simultaneous interaction. One example of concurrent games is matching pennies . Two players, whom we refer to as Ada and the Devil, simultaneously declare either “Heads” or “Tails”. Ada wins if both her and the Devil’s declaration agree, that is, they both say Heads or they both say Tails, while the Devil prefers disagreement. This is a zero-sum concurrent game, and the best possible strategy for Ada ensures her victory with probability 1/2 . For two-player zero sum concurrent games, the value of the game is well defined, since the \max\min value of the game (the largest payoff that Ada can guarantee) is equal to the \min\max value (the smallest payoff the Devil can force). Now consider a version of this game with one additional player: Bertrand. Similar to the previous examples, each player simultaneously says one of either “Heads” or “Tails”. Ada and Bertrand now form a team, and win if all three players declare the same action; the Devil wins otherwise. Ada and Bertrand may communicate beforehand to agree on a strategy, but they do not observe each other’s private random choices at play time. In such a game, the \max\min value is in general not equal to the \min\max value. Indeed, if the Devil commits first to a given strategy, then Ada and Bertrand can ensure victory with probability at least 1/2 (by both deterministically choosing the action that the Devil chooses with the largest probability). The \min\max value of this game is therefore 1/2 . Conversely, assume Ada and Bertrand fix their strategies first. Ada picks “Heads” and “Tails” with probability p_{A} and 1-p_{A} , respectively, while Bertrand picks “Heads” and “Tails” with probability p_{B} and 1-p_{B} , respectively. Then, the Devil can deterministically choose either Heads or Tails to ensure that Ada and Bertrand win with probability at most \min\{p_{A}p_{B},(1-p_{A})(1-p_{B})\} . This quantity is maximised when p_{A}=p_{B}=1/2 , ensuring that the \max\min value is 1/4 . In this paper, we focus on the \max\min value. A natural extension introduces a third team member, Claude, who joins Ada and Bertrand in attempting to match pennies with the Devil. If each player uses an individual source of randomness, the optimal strategy for each player is to choose independently and uniformly, giving a \max\min value of 1/8 . Shared randomness, however, changes the picture. We define a shared source of randomness (or die ) as a random variable ranging uniformly over the interval [0,1] , and to which only a given set of players (always excluding the Devil) have access (note that every continuous distribution can be mapped to the uniform one). Suppose first that Ada and Bertrand share a die. Then, the team can, again, ensure victory with probability 1/4 , since Ada and Bertrand’s outcomes can always be ensured to match. Similarly, if all three team players share a die, the situation collapses to the two-player matching-pennies case (Ada vs. Devil) and the \max\min value becomes 1/2 . We now pose an illustrative question that motivates the broader class of games that we call dicey games , addressed in this work. What is the optimal strategy—and corresponding \max\min value—for achieving an all-Heads or all-Tails outcome in the matching-pennies game played by Ada, Bertrand, and Claude against the Devil, under the assumption that Ada and Bertrand share a die, Bertrand and Claude share another, and Claude and Ada share a third? Suppose, to begin with, that Ada and Bertrand rely solely on their shared die, while Claude bases his action only on one of the other two dice available to him. In this restricted setting, we have already observed that the team can guarantee a success probability of at most 1/4 . At this point we invite the reader to reflect: can the trio do better than 1/4 when all three pairwise shared sources of randomness are available simultaneously? Since each player has access to two independent shared random variables, a strategy for any given player may be viewed as a measurable function [0,1]^{2}\to\{\mathsf{H},\mathsf{T}\} . Equivalently, one may visualise such a strategy as a partition of the unit square into two regions corresponding to “Heads” and “Tails”. A natural attempt a reader might consider is the following: declare Heads whenever the sum of the two shared random values is at most 1 , and Tails otherwise. This strategy is depicted in Fig. 1 . The probability that all three players simultaneously declare Heads (or all declare Tails) then corresponds to the volume of the red (resp blue) tetrahedral region shown in Fig. 1(d) , which is exactly 1/6 . Somewhat disappointingly, this is less than the value 1/4 found earlier—but still better than if they randomise independently. x y \mathsf{H} \mathsf{T} (a) Ada’s strategy y z \mathsf{H} \mathsf{T} (b) Bertrand’s strategy z x \mathsf{H} \mathsf{T} (c) Claude’s strategy x y z (d) The sets \mathsf{H}\mathsf{H}\mathsf{H} and \mathsf{T}\mathsf{T}\mathsf{T} Figure 1 . A strategy to win with probability 1/6 Readers who prefer to discover the optimal construction on their own may wish to pause here, as we will now reveal the solution. The optimal collective strategy turns out to possess a simple geometric form. Each player declares Heads if the value of both their dice are at least \alpha , for some fixed value \alpha\in[0,1] , and Tails otherwise. The probability of an all-Heads (resp. all-Tails) outcome in such a case is equal to the volume of the red (resp. blue) solid in Fig. 2(d) . The value of \alpha that optimises the \max\min value is the one that makes that the volume of the red cube is exactly equal to the volume of the blue solid. Solving the cubic polynomial that captures that equality, we can conclude that the team’s winning probability under this strategy is approximately 0.2781 . Proving that this is optimal is however more challenging. 1.1. Our results In this work, we investigate a class of concurrent games

Read the complete text