Dicey games: Shared sources of randomness in distributed systems LIPIcs Brice, Leonard J Henzinger, Thomas A ; https://orcid.org/0000-0002-2985-7724 Thejaswini, K. S. Concurrent games Shared randomness Topology Algebraic Geometry ddc:000 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; if all players share a common source of randomness, they win with probability 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. Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2026 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/22617 https://research-explorer.ista.ac.at/download/22617/22625 Brice LJ, Henzinger TA, Thejaswini KS. Dicey games: Shared sources of randomness in distributed systems. In: <i>41st Annual Symposium on Logic in Computer Science</i>. Vol 380. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPIcs.LICS.2026.23">10.4230/LIPIcs.LICS.2026.23</a> eng info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.LICS.2026.23 info:eu-repo/semantics/altIdentifier/issn/1868-8969 info:eu-repo/semantics/altIdentifier/isbn/9783959774345 info:eu-repo/semantics/altIdentifier/arxiv/2601.18303 info:eu-repo/semantics/openAccess