---
OA_place: publisher
OA_type: gold
_id: '22617'
abstract:
- lang: eng
  text: "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!\r\nWe 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."
acknowledgement: "This work was supported in part by the ERC-2020-AdG 101020093 (VAMOS).\r\nLéonard
  Brice: Part of this work was realised when this author was an FNRS aspirant at Université
  libre de Bruxelles.\r\nK. S. Thejaswini: Part of this work was realised when this
  author was a post-doctoral researcher at IST Austria.\r\nAcknowledgements We thank
  all our colleagues who took the time to hear our puzzle and wasted several hours
  of their research time in pursuit of the optimal bounds for the 3-player matching.\r\npennies
  problem.\r\n"
alternative_title:
- LIPIcs
article_number: 23:1-23:26
article_processing_charge: No
arxiv: 1
author:
- first_name: Leonard J
  full_name: Brice, Leonard J
  id: ce3b3409-db6c-11f0-aa64-ad678f7fd937
  last_name: Brice
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000-0002-2985-7724
- first_name: K. S.
  full_name: Thejaswini, K. S.
  last_name: Thejaswini
citation:
  ama: '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>'
  apa: 'Brice, L. J., Henzinger, T. A., &#38; Thejaswini, K. S. (2026). Dicey games:
    Shared sources of randomness in distributed systems. In <i>41st Annual Symposium
    on Logic in Computer Science</i> (Vol. 380). Lisbon, Portugal: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.LICS.2026.23">https://doi.org/10.4230/LIPIcs.LICS.2026.23</a>'
  chicago: 'Brice, Leonard J, Thomas A Henzinger, and K. S. Thejaswini. “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. <a href="https://doi.org/10.4230/LIPIcs.LICS.2026.23">https://doi.org/10.4230/LIPIcs.LICS.2026.23</a>.'
  ieee: 'L. J. Brice, T. A. Henzinger, and K. S. Thejaswini, “Dicey games: Shared
    sources of randomness in distributed systems,” in <i>41st Annual Symposium on
    Logic in Computer Science</i>, Lisbon, Portugal, 2026, vol. 380.'
  ista: 'Brice LJ, Henzinger TA, Thejaswini KS. 2026. Dicey games: Shared sources
    of randomness in distributed systems. 41st Annual Symposium on Logic in Computer
    Science. LICS: Logic in Computer Science, LIPIcs, vol. 380, 23:1-23:26.'
  mla: 'Brice, Leonard J., et al. “Dicey Games: Shared Sources of Randomness in Distributed
    Systems.” <i>41st Annual Symposium on Logic in Computer Science</i>, vol. 380,
    23:1-23:26, 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>.'
  short: L.J. Brice, T.A. Henzinger, K.S. Thejaswini, in:, 41st Annual Symposium on
    Logic in Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2026.
conference:
  end_date: 2026-07-23
  location: Lisbon, Portugal
  name: 'LICS: Logic in Computer Science'
  start_date: 2026-07-20
corr_author: '1'
das_tickbox: '0'
date_created: 2026-08-02T22:01:52Z
date_published: 2026-07-09T00:00:00Z
date_updated: 2026-08-03T07:03:28Z
day: '09'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.LICS.2026.23
ec_funded: 1
external_id:
  arxiv:
  - '2601.18303'
file:
- access_level: open_access
  checksum: 5d0ff4d267565188a8b4c7502e1bd243
  content_type: application/pdf
  creator: dernst
  date_created: 2026-08-03T07:02:30Z
  date_updated: 2026-08-03T07:02:30Z
  file_id: '22625'
  file_name: 2026_LIPICSLICS_Brice.pdf
  file_size: 919708
  relation: main_file
  success: 1
file_date_updated: 2026-08-03T07:02:30Z
fulldoi: https://doi.org/10.4230/LIPIcs.LICS.2026.23
has_accepted_license: '1'
intvolume: '       380'
keyword:
- Concurrent games
- Shared randomness
- Topology
- Algebraic Geometry
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
publication: 41st Annual Symposium on Logic in Computer Science
publication_identifier:
  isbn:
  - '9783959774345'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Dicey games: Shared sources of randomness in distributed systems'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 380
year: '2026'
...