@inproceedings{22617,
  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; 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.},
  author       = {Brice, Leonard J and Henzinger, Thomas A and Thejaswini, K. S.},
  booktitle    = {41st Annual Symposium on Logic in Computer Science},
  isbn         = {9783959774345},
  issn         = {1868-8969},
  keywords     = {Concurrent games, Shared randomness, Topology, Algebraic Geometry},
  location     = {Lisbon, Portugal},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Dicey games: Shared sources of randomness in distributed systems}},
  doi          = {10.4230/LIPIcs.LICS.2026.23},
  volume       = {380},
  year         = {2026},
}