Team-versus-one games
Recently, my work focus on settings in which a team of players, for example representing a decentralised computer-controlled system, competes against an environment. Those players are limited in how they can communicate, and in particular, in settings in which randomised strategies are necessary to maximise their chances (think of rock-paper-scissors), they may not be able to use a common source of randomness. This contrasts, for example, with the semantics of logics such as Randomised (or Probabilistic) Alternating Temporal Logic (RATL, PATL), in which one can express the fact that a given coalition of players can guarantee a given property through joint randomisation. We defined an extension of those logics, Individually Randomised Alternating Temporal Logic (IRATL), and showed that a fragment of it, in concurrent graph games, is decidable in PSPACE (CAV 2026). We later showed that its entire qualitative fragment (expressing that a coalition can almost-surely or limit-surely ensure some specification) is decidable in P[NP] (pre-print). We also proposed a formalism called dicey games, to capture settings in which players may resort to sources of randomness that are shared, but only among a given subset of the team (LICS 2026). We studied such games in a one-shot setting.
- L. Brice, T. Henzinger, K. S. Thejaswini, "Dicey Games: Shared Sources of Randomness in Distributed Systems", LICS 2026 (ArXiv)
- L. Brice, T. Henzinger, A. Montaseri, A. Shafiee, K. S. Thejaswini, "Randomise Alone, Reach as a Team", CAV 2026 (ArXiv)
- L. Brice, T. Henzinger, A. Montaseri, A. Shafiee, K. S. Thejaswini, Limit-sure Winning in Team Games without Shared Randomness", pre-print (ArXiv)