[{"has_accepted_license":"1","alternative_title":["LIPIcs"],"corr_author":"1","OA_place":"publisher","scopus_import":"1","file_date_updated":"2026-08-03T07:02:30Z","ec_funded":1,"publication_identifier":{"isbn":["9783959774345"],"issn":["1868-8969"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2026-08-02T22:01:52Z","license":"https://creativecommons.org/licenses/by/4.0/","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","volume":380,"type":"conference","month":"07","supplementarymaterial":"no","ddc":["000"],"file":[{"content_type":"application/pdf","relation":"main_file","file_id":"22625","file_size":919708,"checksum":"5d0ff4d267565188a8b4c7502e1bd243","date_updated":"2026-08-03T07:02:30Z","success":1,"date_created":"2026-08-03T07:02:30Z","access_level":"open_access","file_name":"2026_LIPICSLICS_Brice.pdf","creator":"dernst"}],"department":[{"_id":"ToHe"}],"arxiv":1,"language":[{"iso":"eng"}],"oa":1,"day":"09","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_updated":"2026-08-03T07:03:28Z","das_tickbox":"0","title":"Dicey games: Shared sources of randomness in distributed systems","researchdata_availability":"no","quality_controlled":"1","conference":{"end_date":"2026-07-23","start_date":"2026-07-20","name":"LICS: Logic in Computer Science","location":"Lisbon, Portugal"},"doi":"10.4230/LIPIcs.LICS.2026.23","fulldoi":"https://doi.org/10.4230/LIPIcs.LICS.2026.23","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software"}],"oa_version":"Published Version","date_published":"2026-07-09T00:00:00Z","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."}],"intvolume":"       380","publication_status":"published","author":[{"last_name":"Brice","full_name":"Brice, Leonard J","id":"ce3b3409-db6c-11f0-aa64-ad678f7fd937","first_name":"Leonard J"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000-0002-2985-7724","first_name":"Thomas A"},{"last_name":"Thejaswini","full_name":"Thejaswini, K. S.","first_name":"K. S."}],"article_processing_charge":"No","external_id":{"arxiv":["2601.18303"]},"citation":{"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.","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>.","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>.","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.","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>","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>"},"article_number":"23:1-23:26","publication":"41st Annual Symposium on Logic in Computer Science","keyword":["Concurrent games","Shared randomness","Topology","Algebraic Geometry"],"year":"2026","OA_type":"gold","_id":"22617","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public"},{"intvolume":"     16682","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."}],"author":[{"id":"ce3b3409-db6c-11f0-aa64-ad678f7fd937","full_name":"Brice, Leonard J","last_name":"Brice","first_name":"Leonard J"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000-0002-2985-7724","first_name":"Thomas A"},{"full_name":"Montaseri, Alipasha","id":"709a7f96-8896-11f0-9809-d75612fc0f2e","last_name":"Montaseri","first_name":"Alipasha"},{"first_name":"Ali","full_name":"Shafiee, Ali","id":"2783031a-7378-11f0-b2d0-f17f1db2ebad","last_name":"Shafiee"},{"first_name":"K. S.","last_name":"Thejaswini","full_name":"Thejaswini, K. S."}],"publication_status":"published","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software"}],"fulldoi":"https://doi.org/10.1007/978-3-032-32519-8_12","date_published":"2026-07-24T00:00:00Z","oa_version":"Published Version","quality_controlled":"1","conference":{"start_date":"2026-07-26","name":"CAV: Computer Aided Verification","location":"Lisbon, Portugal","end_date":"2026-07-29"},"doi":"10.1007/978-3-032-32519-8_12","researchdata_availability":"yes","OA_type":"hybrid","_id":"22717","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","year":"2026","publication":"38th International Conference on Computer Aided Verification","article_processing_charge":"Yes (in subscription journal)","external_id":{"arxiv":["2603.07094"]},"citation":{"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.","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.","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>.","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.","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>"},"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.","file":[{"creator":"dernst","file_name":"2026_LNCS_Brice.pdf","access_level":"open_access","date_created":"2026-08-18T06:53:22Z","success":1,"date_updated":"2026-08-18T06:53:22Z","checksum":"10ded8a3ab9ed34c9e4794c0b277622c","file_size":1902192,"file_id":"22724","relation":"main_file","content_type":"application/pdf"}],"department":[{"_id":"ToHe"},{"_id":"GradSch"}],"language":[{"iso":"eng"}],"arxiv":1,"page":"215-236","date_created":"2026-08-16T22:01:44Z","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.","volume":16682,"type":"conference","supplementarymaterial":"no","ddc":["000"],"month":"07","ec_funded":1,"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783032325181"]},"publisher":"Springer Nature","has_accepted_license":"1","file_date_updated":"2026-08-18T06:53:22Z","scopus_import":"1","OA_place":"publisher","das_tickbox":"1","title":"Randomise alone, reach as a team","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_updated":"2026-08-18T06:55:38Z","day":"24","oa":1}]