What Preferences Can—and Cannot—Predict in Multi-Agent Online Learning

We examine the interplay between ordinal, preference-based solution concepts in games and the outcomes of payoff-driven learning dynamics, asking to what extent the combinatorial data of a game—its preference graph—can predict the long-run behavior of no-regret dynamics such as follow-the-regularized-leader (FTRL). In one direction, we show that the skeleton of every dynamically stable set, i.e., the set of pure profiles it contains, must be preferentially stable, that is, closed under pure profitable deviations. We then ask the converse question: when are preferences sufficient to describe long-run behavior? For subgames—subsets of pure profiles obtained by restricting players’ action sets—preferences are enough to fully characterize asymptotic stability. Beyond subgames however, we construct a three-player counterexample with a preferentially stable set whose span is dynamically unstable, thus establishing that preferences are not sufficient to describe dynamically stable behavior in general. To restore stability, we introduce the notion of leaklessness, a measure of aggregate payoff drift away from a set of pure profiles, and use it to identify a payoff-based condition under which the span of a set of pure profiles remains stable and attracting, thereby setting forth a natural cardinal guarantee of dynamic stability.