🤖 machine learning

What preferences can - and cannot - predict in multi-agent online learning

This paper investigates the limits of using preference graphs to predict long-run outcomes in multi-agent online learning, demonstrating that while preferential stability is necessary for dynamic stability, it is not sufficient in general games, and proposes "resilience under aggregate deviations" as a stronger, payoff-based condition to guarantee asymptotic stability.

Original authors: Omar Abbadi, Rida Laraki, Panayotis Mertikopoulos

Published 2026-08-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Omar Abbadi, Rida Laraki, Panayotis Mertikopoulos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling digital marketplace where thousands of invisible agents are constantly making choices, trying to get the best deal possible. This isn't just about shopping; it's the hidden engine behind everything from how your social media feed is curated to how self-driving cars negotiate a busy intersection. In the world of game theory, these agents are players, and their choices are moves in a giant, complex game. For a long time, scientists hoped that if these players just kept learning from their mistakes—trying to avoid "regret"—they would eventually settle down into a perfect, stable state where no one wanted to change their strategy. This state is called a Nash equilibrium. But life (and math) is messy. Sometimes, instead of settling down, the players get stuck in endless loops, dancing around each other without ever finding a resting spot. The big question is: can we predict where these players will end up just by looking at their simple preferences? Do they prefer A over B, and B over C? Or do we need to know the exact dollar amounts of their rewards to know what will happen?

This paper, written by Omar Abbadi, Rida Laraki, and Panayotis Mertikopoulos, dives deep into that mystery. They are investigating a specific type of learning called "Follow-the-Regularized-Leader" (FTRL). Think of FTRL as a smart, slightly cautious student who keeps a running tally of their past scores. When it's time to make a new move, this student looks at their total score history, adds a little bit of "regularization" (which is like a gentle nudge to keep them from being too extreme or stuck on one option), and picks the best move based on that. The authors ask a crucial question: Can we predict the long-term behavior of these learning agents just by looking at a map of their preferences (who beats whom), or do we need the exact numbers on the scoreboard?

The answer, it turns out, is a mix of "yes" and "no," and the "no" part is the most surprising. The authors prove that preferences do set some hard rules. If a group of strategies is stable in the long run, it must be "closed" under better replies. Imagine a club where no member wants to leave for a better option outside the club; if they did, the club wouldn't be stable. The paper shows that any stable outcome must look like this: a closed loop where no one has a reason to jump ship. This is a necessary condition. If a set of strategies isn't closed in this way, the learning dynamics will definitely kick the players out.

However, the paper shatters the hope that this preference map is enough to tell the whole story. The authors construct a specific three-player game where the preference map looks perfectly stable—a closed loop where no one seems to want to leave. Yet, when they run the actual learning dynamics, the players drift away from this "stable" loop and crash into a different part of the game. It's like a hiker looking at a map that says, "This valley is safe," only to find that the ground is actually slippery and they slide right out of it. The map of preferences (the ordinal data) was correct about the direction of the slope, but it missed the steepness of the hill. The exact payoff values (the cardinal data) mattered. In this case, the "preference-only" intuition failed completely.

So, what does this mean for the future of learning in games? The authors don't just point out the failure; they offer a new tool to fix it. They introduce a concept called "resilience to aggregate deviations" (rad). Think of this as checking not just if a single player wants to leave, but if the combined temptation for everyone to leave is strong. If the total "gain" from leaving a group is negative, the group is resilient. The paper proves that if a set of strategies is "rad," it will definitely be stable under learning dynamics, regardless of the game's complexity. This is a big deal because it gives us a way to predict stability using the actual numbers, not just the order of preferences.

The paper also clarifies when the simple preference map does work. If the game is restricted to a smaller "subgame" (like playing a specific subset of moves), then the preference map is a perfect predictor. If the map says a subgame is closed, it is stable. But once you step outside those neat, restricted boxes, the map becomes unreliable. The authors also show that in games with many players but few choices, the simple preference rules often hold up, which explains why learning algorithms work so well in some real-world scenarios with massive crowds.

Ultimately, this research draws a clear line in the sand. It tells us that while preferences are a powerful compass, they aren't a complete GPS. They can tell us which directions are forbidden, but they can't always tell us exactly where we'll end up. To get there, we need to look at the actual terrain—the specific values of the rewards. The paper doesn't claim to have solved every mystery of game dynamics; in fact, it admits that for some complex games, the long-term behavior remains elusive. But by showing exactly where the old rules break and offering a new, robust condition (radness) to replace them, it provides a much clearer toolkit for understanding how intelligent agents learn and adapt in a chaotic world.

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

Problem Statement
The paper investigates the relationship between the ordinal structure of a game (encoded via a preference graph) and the long-run asymptotic behavior of multi-agent learning dynamics, specifically Follow-the-Regularized-Leader (FTRL). While classical game theory often assumes full rationality and equilibrium computation, modern applications in reinforcement learning and multi-agent systems rely on adaptive, no-regret learning procedures. A central question arises: To what extent does the combinatorial data of a game—specifically the directions of profitable unilateral deviations—determine the stable outcomes of these learning dynamics?

The authors challenge the intuition that the preference graph alone suffices to predict dynamic stability. While it is known that strict Nash equilibria are locally stable, the global behavior of learning in finite games can be complex, involving recurrence, chaos, or convergence to set-valued attractors rather than single points. The paper seeks to delineate the precise regimes where ordinal information determines stability and where it fails, necessitating cardinal payoff information.

Methodology
The authors employ a framework combining game theory, dynamical systems, and convex analysis.

Preference Graphs: They define a directed graph where vertices are pure strategy profiles and arcs represent weakly profitable unilateral deviations. Key structural concepts include club sets (closed under better replies) and sink equilibria (minimal club sets that are strongly connected).
Learning Dynamics: The analysis focuses on FTRL dynamics, where players maintain cumulative scores and update strategies via a choice map derived from a regularizer. This includes both steep regularizers (e.g., entropic/replicator dynamics) and non-steep regularizers (e.g., Euclidean/projection dynamics).
Dynamical Systems Tools: The authors utilize concepts of Lyapunov stability, attraction, and asymptotic stability. They distinguish between the strategy flow (dynamics directly on the strategy space) and the score-based FTRL dynamics. They employ energy functions (such as the Fenchel gap and Fenchel coupling) to prove stability properties.
Counterexamples and Constructions: To demonstrate limitations, the authors construct specific multi-player games (e.g., $2 \times 2 \times 2$ ) where the preference graph suggests stability, but the actual dynamics diverge.

Key Contributions and Results

1. Necessary Conditions: Dynamic Stability Implies Preferential Stability
The paper establishes that for a broad class of regularized learning dynamics, the "skeleton" (the set of pure profiles contained within) of any asymptotically stable set must satisfy specific ordinal properties:

Theorem 1: If a set $S$ is stable under FTRL, its skeleton is strictly closed under better replies (s-club). This means there are no strictly profitable unilateral deviations leading out of the set.
Proposition 1: If a set $S$ is attracting under the strategy dynamics, its skeleton is closed under better replies (club).
Theorem 2: If an attractor contains a strongly connected set of pure profiles $H$ , it must also contain the entire span of $H$ (the region of mixed strategies supported on $H$ ). Consequently, if the preference graph is strongly connected, the dynamics admit no proper attractor.

2. Sufficient Conditions: When Preferences Are Enough
The authors identify specific regimes where ordinal information fully characterizes dynamic stability:

Subgames (Theorem 3): If a set of pure profiles $B$ forms a subgame (a product structure $B = \prod B_i$ ) and is a club set, then its span is asymptotically stable under FTRL.
Weakly Acyclic Games: In games where every profile has a path of better replies to a Nash equilibrium, the minimal attractors of the strategy dynamics coincide exactly with strict Nash equilibria. This provides a sharp characterization for a class of games that becomes increasingly likely as the number of players grows.

3. The Limit of Ordinal Information
The paper demonstrates that preferential stability is not sufficient for dynamic stability in general settings:

Proposition 2: The authors construct a $2 \times 2 \times 2$ game with a unique proper club set $H$ whose span is not stable under FTRL. Trajectories starting arbitrarily close to the span can drift away. This disproves a stronger version of the conjecture that sink equilibria (minimal club sets) are always attractors, showing that even without a "pure local source," a sink equilibrium can be dynamically unstable.

4. A New Sufficient Condition: Resilience to Aggregate Deviations (rad)
To bridge the gap where preferences fail, the authors introduce a payoff-based condition:

Definition: A set $H$ is resilient to aggregate deviations (rad) if the aggregate payoff flux from any profile in $H$ to any profile outside $H$ is non-positive.
Theorem 4: If a set $H$ is strictly rad (s-rad), then its span is an attractor of the strategy dynamics.
Theorem 5: If $H$ is a rad club set, its span is an attractor of the replicator dynamics.
Complexity: Unlike mixed Nash equilibria (which are PPAD-hard to compute), checking for radness can be done in polynomial time relative to the size of the normal-form representation.

Significance and Claims
The paper claims to provide a "preference-based toolbox" for predicting the long-run behavior of regularized learning. Its primary contribution is clarifying the boundary between ordinal and cardinal determinism in game dynamics:

Constraints vs. Determination: The preference graph imposes unavoidable constraints on stable outcomes (any stable set must be a club/s-club), but it does not always determine them.
Refinement of Existing Conjectures: The work refines the conjecture by Papadimitriou & Piliouras regarding the correspondence between sink equilibria and attractors. While sink equilibria are necessary components of attractors, they are not sufficient; the paper provides a counterexample where a sink equilibrium is dynamically unstable.
Generalization: The introduction of radness offers the first general, setwise, payoff-based condition that guarantees asymptotic stability for arbitrary games and arbitrary sets of pure strategies, extending beyond the specific cases of potential games or two-player games previously studied.
Practical Implication: In applications like AI safety and preference learning, where designers must instantiate numerical rewards to match ordinal specifications, the paper warns that different cardinal realizations of the same preference ordering can lead to drastically different long-run outcomes.

The authors conclude that while the preference graph provides a combinatorial blueprint for stable outcomes, a complete characterization of attractors in general games likely requires new ideas beyond current payoff conditions, as evidenced by games with identical preference graphs exhibiting markedly different limiting behaviors.

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

More like this