POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

We consider two-player GR(1) games on graphs, where the system player Eve must satisfy the specification $\Box\Diamond A_1\land\cdots\land\Box\Diamond A_m \implies\Box\Diamond G_1\land\cdots\land\Box\Diamond G_n$ against every strategy of the environment player Adam. Here $A_1,\ldots,A_m$ are \textit{assumptions} on the environment, $G_1,\ldots,G_n$ are \textit{guarantees} the system must provide, and $\Box\Diamond S$ denotes ‘‘always eventually $S$’’ in linear temporal logic. Traditional approaches compute \textit{static} strategies that satisfy the specification against all possible adversarial moves. Such strategies are overly conservative: they may ‘‘cheat’’ by actively violating assumptions to trivially satisfy the implication, or abandon all guarantees the moment any assumption is violated. Existing methods to prevent such behaviors incur a doubly exponential blowup in time and strategy complexity.

We introduce an \textit{adaptive} framework in which Adam is treated as a non-adversarial agent with unknown objectives that may violate some assumptions. Eve gives Adam the opportunity to fulfill all assumptions, but continuously monitors which assumptions Adam actually meets and adapts her strategy at runtime to maximize the number of satisfied guarantees. Central to our approach is a novel algorithm for monitoring liveness properties of the form $\Box\Diamond S$. Under a suitable model of non-adversarial behavior, this monitoring algorithm enables Eve to maintain real-time likelihood estimates of which assumptions will be fulfilled. Building on these estimates, we develop a probabilistic adaptation procedure: Eve pre-computes a family of strategies, each optimal for a different subset of assumptions, and deploys a probability distribution over them that is dynamically adjusted based on the monitors’ outputs. We prove that when some assumptions are violated, Eve’s randomized adaptive strategy converges asymptotically to the deterministic strategy that fulfills the maximum number of guarantees. The convergence proof relies on a detailed analysis of the time-varying probabilities governing the adaptive strategy. Using a prototype implementation, we demonstrate that our approach scales better than state-of-the-art methods—completing where the baseline times out—while correctly adapting to the assumptions actually satisfied by the environment.