---
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: 38th International Conference on Computer Aided Verification.
Vol 16682. Springer Nature; 2026:215-236. doi:10.1007/978-3-032-32519-8_12'
apa: 'Brice, L. J., Henzinger, T. A., Montaseri, A., Shafiee, A., & Thejaswini,
K. S. (2026). Randomise alone, reach as a team. In 38th International Conference
on Computer Aided Verification (Vol. 16682, pp. 215–236). Lisbon, Portugal:
Springer Nature. https://doi.org/10.1007/978-3-032-32519-8_12'
chicago: Brice, Leonard J, Thomas A Henzinger, Alipasha Montaseri, Ali Shafiee,
and K. S. Thejaswini. “Randomise Alone, Reach as a Team.” In 38th International
Conference on Computer Aided Verification, 16682:215–36. Springer Nature,
2026. https://doi.org/10.1007/978-3-032-32519-8_12.
ieee: L. J. Brice, T. A. Henzinger, A. Montaseri, A. Shafiee, and K. S. Thejaswini,
“Randomise alone, reach as a team,” in 38th International Conference on Computer
Aided Verification, 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.” 38th International
Conference on Computer Aided Verification, vol. 16682, Springer Nature, 2026,
pp. 215–36, doi:10.1007/978-3-032-32519-8_12.
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
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'
...