Anytime Detection of Strategic Deviations in Multi-Agent Systems

In many multi-agent systems, agents interact repeatedly and are expected to settle into stable, rational behavior over time. Yet in practice, behavior often drifts, and detecting such deviations in real time remains an open challenge. We introduce a sequential testing framework that monitors whether observed play is consistent with a benchmark of strategic behavior, without assuming a fixed sample size. Our approach builds on the e-value framework for safe anytime-valid inference: by "betting" against the benchmark, we construct a test supermartingale that accumulates evidence whenever observed payoffs systematically violate the expected conditions. For repeated normal-form games, we take equilibrium as the benchmark, yielding a statistically sound, interpretable measure of departure from equilibrium that can be monitored online; our framework unifies the treatment of Nash, correlated, and coarse correlated equilibria, offering finite-time guarantees and a detailed analysis of detection times. We also leverage Benjamini-Hochberg-type procedures to increase detection power in large games while rigorously controlling the false discovery rate. Finally, we extend our method to stochastic games, verifying online whether observed trajectories adhere to a specified target policy, such as a computed equilibrium, broadening the framework's applicability to dynamic, state-dependent settings.

Many automated systems involve multiple decision-making agents (trading bots, self-driving cars, recommendation algorithms) that interact repeatedly and are expected to behave in stable, predictable ways. In practice this behavior can drift: an agent may quietly change strategy or stop following the rules it was meant to obey. Catching such changes quickly matters for safety, but is hard to do while the system is still running. We develop a method that monitors these interactions as they unfold. The idea is to treat monitoring as a betting game: at each step, the procedure places a small bet against the assumption that all is normal. If the agents behave as expected, these bets cannot systematically pay off; if behavior has shifted, the winnings accumulate and raise an alarm, with guarantees that false alarms stay rare no matter when one stops to look. The result is a practical tool for keeping complex multi-agent systems safe and trustworthy.