---
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
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'
...
---
OA_place: publisher
OA_type: hybrid
_id: '22717'
abstract:
- lang: eng
  text: "We study concurrent graph games where n players cooperate against an opponent
    to reach a set of target states. Unlike traditional settings, we study distributed
    randomisation: team players do not share a source of randomness, and their private
    random sources are hidden from the opponent and from each other.\r\n\r\nWe show
    that memoryless strategies are sufficient for the threshold problem (deciding
    whether there is a strategy for the team that ensures winning with probability
    that exceeds a threshold), a result that not only places the problem in the Existential
    Theory of the Reals (ER) but also enables the construction of value iteration
    algorithms. We additionally show that the threshold problem is NP-hard. For the
    almost-sure reachability problem, we prove NP-completeness.\r\n\r\nWe introduce
    Individually Randomised Alternating-time Temporal Logic (IRATL). This logic extends
    the standard ATL framework to reason about probability thresholds, with semantics
    explicitly designed for coalitions that lack a shared source of randomness. On
    the practical side, we implement and evaluate a solver for the threshold and almost-sure
    problem based on the algorithms that we develop."
acknowledgement: This work is a part of project VAMOS that has received funding from
  the European Research Council (ERC), grant agreement No 101020093. Part of this
  work was realised when the first author was an FNRS aspirant at Université libre
  de Bruxelles.
article_processing_charge: Yes (in subscription journal)
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: Alipasha
  full_name: Montaseri, Alipasha
  id: 709a7f96-8896-11f0-9809-d75612fc0f2e
  last_name: Montaseri
- first_name: Ali
  full_name: Shafiee, Ali
  id: 2783031a-7378-11f0-b2d0-f17f1db2ebad
  last_name: Shafiee
- first_name: K. S.
  full_name: Thejaswini, K. S.
  last_name: Thejaswini
citation:
  ama: 'Brice LJ, Henzinger TA, Montaseri A, Shafiee A, Thejaswini KS. Randomise alone,
    reach as a team. In: <i>38th International Conference on Computer Aided Verification</i>.
    Vol 16682. Springer Nature; 2026:215-236. doi:<a href="https://doi.org/10.1007/978-3-032-32519-8_12">10.1007/978-3-032-32519-8_12</a>'
  apa: 'Brice, L. J., Henzinger, T. A., Montaseri, A., Shafiee, A., &#38; Thejaswini,
    K. S. (2026). Randomise alone, reach as a team. In <i>38th International Conference
    on Computer Aided Verification</i> (Vol. 16682, pp. 215–236). Lisbon, Portugal:
    Springer Nature. <a href="https://doi.org/10.1007/978-3-032-32519-8_12">https://doi.org/10.1007/978-3-032-32519-8_12</a>'
  chicago: Brice, Leonard J, Thomas A Henzinger, Alipasha Montaseri, Ali Shafiee,
    and K. S. Thejaswini. “Randomise Alone, Reach as a Team.” In <i>38th International
    Conference on Computer Aided Verification</i>, 16682:215–36. Springer Nature,
    2026. <a href="https://doi.org/10.1007/978-3-032-32519-8_12">https://doi.org/10.1007/978-3-032-32519-8_12</a>.
  ieee: L. J. Brice, T. A. Henzinger, A. Montaseri, A. Shafiee, and K. S. Thejaswini,
    “Randomise alone, reach as a team,” in <i>38th International Conference on Computer
    Aided Verification</i>, Lisbon, Portugal, 2026, vol. 16682, pp. 215–236.
  ista: 'Brice LJ, Henzinger TA, Montaseri A, Shafiee A, Thejaswini KS. 2026. Randomise
    alone, reach as a team. 38th International Conference on Computer Aided Verification.
    CAV: Computer Aided Verification vol. 16682, 215–236.'
  mla: Brice, Leonard J., et al. “Randomise Alone, Reach as a Team.” <i>38th International
    Conference on Computer Aided Verification</i>, vol. 16682, Springer Nature, 2026,
    pp. 215–36, doi:<a href="https://doi.org/10.1007/978-3-032-32519-8_12">10.1007/978-3-032-32519-8_12</a>.
  short: L.J. Brice, T.A. Henzinger, A. Montaseri, A. Shafiee, K.S. Thejaswini, in:,
    38th International Conference on Computer Aided Verification, Springer Nature,
    2026, pp. 215–236.
conference:
  end_date: 2026-07-29
  location: Lisbon, Portugal
  name: 'CAV: Computer Aided Verification'
  start_date: 2026-07-26
das_tickbox: '1'
dataavailabilitystatement: "The artifact can be accessed at the link: https://doi.
  org/10.5281/zenodo.19680359.\r\nThe source code is available at:https://github.com/alipashamontaseri/Team-Concurrent-Game."
date_created: 2026-08-16T22:01:44Z
date_published: 2026-07-24T00:00:00Z
date_updated: 2026-08-18T06:55:38Z
day: '24'
ddc:
- '000'
department:
- _id: ToHe
- _id: GradSch
doi: 10.1007/978-3-032-32519-8_12
ec_funded: 1
external_id:
  arxiv:
  - '2603.07094'
file:
- access_level: open_access
  checksum: 10ded8a3ab9ed34c9e4794c0b277622c
  content_type: application/pdf
  creator: dernst
  date_created: 2026-08-18T06:53:22Z
  date_updated: 2026-08-18T06:53:22Z
  file_id: '22724'
  file_name: 2026_LNCS_Brice.pdf
  file_size: 1902192
  relation: main_file
  success: 1
file_date_updated: 2026-08-18T06:53:22Z
fulldoi: https://doi.org/10.1007/978-3-032-32519-8_12
has_accepted_license: '1'
intvolume: '     16682'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 215-236
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
publication: 38th International Conference on Computer Aided Verification
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783032325181'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
researchdata_availability: yes
scopus_import: '1'
status: public
supplementarymaterial: no
title: Randomise alone, reach as a team
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: 16682
year: '2026'
...