O. Abbadi, R. Laraki, and P. Mertikopoulos. In ICML '26: Proceedings of the 43rd International Conference on Machine Learning, 2026.
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.
arxiv link:
[Oral at ICML 2026]