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
| CREATOR | Léonard Brice, Thomas A. Henzinger, Alipasha Montaseri, Ali Shafiee, K. S. Thejaswini |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121395 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.07094