Randomise Alone, Reach as a Team

Léonard Brice, Thomas A. Henzinger, Alipasha Montaseri, Ali Shafiee, K. S. Thejaswini · 2026

Read Randomise Alone, Reach as a Team by Léonard Brice, Thomas A. Henzinger, Alipasha Montaseri, Ali Shafiee, K. S. Thejaswini (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-07094.txt.

Description

Brice and colleagues study team games where players cooperate against an opponent to reach target states, but each player randomizes privately, with no shared random source. They show memoryless strategies suffice for the threshold problem, placing it in the existential theory of the reals and enabling value iteration algorithms. They also prove the threshold problem is NP-hard and almost-sure reachability is NP-complete. A new logic, IRATL, extends standard temporal logic to this private-randomness setting.

Catalog record

CREATORLéonard Brice, Thomas A. Henzinger, Alipasha Montaseri, Ali Shafiee, K. S. Thejaswini
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121395
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.07094

Browse the full library · About the Tower of Babel