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 also be preferentially stable, that is, it must be closed under profitable deviations. We then ask the converse question: when are preferences sufficient to describe the long-run behavior of the players' learning dynamics? We begin by showing that preferences are indeed enough to fully characterize asymptotic stability in the case of subgames—i.e., subsets of pure profiles obtained by restricting players' action sets. Beyond this case however, the equivalence between dynamic and preferential stability breaks down: in particular, we construct a three-player game with a preferentially stable set whose span is dynamically unstable, showing 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 we use it to identify a payoff-based condition guaranteeing that the span of a set of pure profiles is stable and attracting.

We study multi-agent learning dynamics in order to understand the relationship between agents’ preferences and their long-run behavior. We first show that agents’ preferences strongly constrain which kinds of stable behavior can emerge. However, we also show that not every region that is stable from the viewpoint of preferences is stable under the agents’ actual learning dynamics. To address this gap, we introduce the notion of leaklessness, a measure of how much, in aggregate, agents tend to deviate away from a given region, and show that this condition restores stability under learning.