What preferences can - and cannot - predict in multi-agent online learning
Authors: Omar Abbadi, Rida Laraki, Panayotis Mertikopoulos
Organizations: Univ. Mohammed VI Polytechnic, CMSIS, Moroccan Center for Game Theory, 11103 Rabat, Morocco. · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
We examine the interplay between ordinal, preference-based solution concepts in games and the long-run behavior of game dynamics, asking in particular to what extent the combinatorial data of a game -- its preference graph -- determine the outcomes of no-regret learning 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 do preferences determine the long-run behavior of the players' learning dynamics? We begin by showing that preferences 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 collapses: concretely, we construct a three-player game with a preferentially stable set whose span is dynamically unstable, showing in this way that preferences do not suffice as a criterion of dynamic stability. We then bridge this gap via the notion of resilience under aggregate deviations, an easy-to-check payoff-based condition that guarantees asymptotic stability of arbitrary spans of pure strategies.
Figures & tables
Figure 1. In each of these 2×2×2 games, vertices are pure profiles and arrows indicate the direction of profitable unilateral deviations. The part of the graph that is highlighted in red is club ( club ), so players have no preferential incentive to move away from these sets. Translating this intuition to the players’ dynamic behavior fails on the left: trajectories starting arbitrarily close to the top face drift away toward the bottom face, contradicting the preferential viewpoint. On the right the preferential and dynamical viewpoints are aligned: trajectories starting anywhere near the preferentially closed 6-edge cycle (highlighted in red) converge to it.
Figure 2. Payoffs and preferences in Shapley’s game [ 70 ] . The cycle of six profiles in the center—the “hexagon” —is the game’s unique proper club set; since it is minimal, it is a sink equilibrium. See Appendix B for more examples and details.
Figure 3. Preference graphs of three 2×2×2 games. In each one, the red vertex set is a minimal club set / sink equilibrium, and the red region represent its span (an edge cycle on the left, a square face in the middle, and a union of two square faces on the right).
Figure 4. A game with an srad set (for the game’s payoffs, cf. Appendix B ). On the left, we plot the game’s preference graph, highlighting the srad set (and its span) in red; on the right, we plot the evolution of the replicator dynamics in said game. We note that the (span of) the srad set is asymptotically stable, as per Theorem 4 . At the same time, we also note that all replicator orbits eventually converge to the rightmost face, a face which is neither rad (even though it is contained in the original srad set), nor asymptotically stable (an orbit may start arbitrarily close to said face and venture arbitrarily far before eventually returning to it, cf. the red orbit in the plot to the right).
Figure 5. Four games with the same preference graph, differing at only a single payoff entry. As we move from left to right, the dynamics become progressively more complicated and orbits converge to different faces, despite having the same preference graph.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6. Prisoner’s Dilemma
Figure 7. Matching Pennies
Figure 8. A coordination game.
Figure 9. A cube with a club square.
Figure 10. A game with a srad set.
Figure 11. Jordan’s Matching Pennies
Figure 12. Shapley’s game.
Figure 13. A club subgame which is not rad .
Figure 14. Cube X with coordinates (p,q,r)=(x1F,x2R,x3T) . The red vertices represent the unique club set, and the red shaded faces are its span. The blue vertex is a source vertex , meaning it has no incoming edge. In particular it is a repellor of the dynamics. The purple point x∗=(21,21,1) is a NE of the game restricted to the face FT . Nonetheless, Player 3 has a deviation to the bottom in the neighborhood of that point, hence the dynamics are locally repelled from FT near x∗ . This is what shall drive instability.
Figure 15. Three perspectives of ( FTRL ) under entropic regularization for this counterexample game.
We study learning in continuous games when players receive only pairwise preference feedback, revealing which of two actions is preferred but neither payoff values nor preference magnitudes. We first show that standard external regret and coarse correlated equilibria (CCE) are not identifiable from this ordinal information: the same sequence of play can incur zero and linear regret in two ordinally equivalent games, while the distributions that remain CCE across all cardinal representations consistent with the same preferences are exactly those supported on pure Nash equilibria. Motivated by this gap, we develop a first-order ordinal theory based on normalized unilateral preference directions, introducing an ordinal directional regret benchmark and corresponding equilibrium notions. We show that block-normalized pseudogradient dynamics achieve sublinear ordinal regret and, under additional structure, Nash-convergence guarantees. We then use a single-comparison estimator to implement these dynamics from finite pairwise comparisons. With one comparison per player and round, the resulting algorithm achieves sublinear finite-resolution ordinal regret against arbitrary opponent behavior and, in ordinal potential games, almost-sure last-iterate convergence to the Nash set. Our results provide regret, dynamics, and equilibrium guarantees directly from preference feedback without reconstructing cardinal utilities.
We extend the study of learning in games to dynamics that exhibit non-asymptotic stability. We do so through the notion of uniform stability, which is concerned with equilibria of individually utility-seeking dynamics. Perhaps surprisingly, it turns out to be closely connected to economic properties of collective rationality. Up to strategic equivalence, if a mixed equilibrium is uniformly stable, then it is weakly Pareto optimal; there is no way for all players to improve by jointly deviating from the equilibrium. This is a form of collective rationality that rules out the types of behaviors in the prisoner's dilemma or the tragedy of the commons. Moreover, we show that uniform stability determines the last-iterate convergence behavior for the family of incremental smoothed best-response dynamics, used to model individual and corporate behaviors in the markets. Unlike dynamics around strict equilibria, which can stabilize to socially-inefficient solutions, individually utility-seeking behaviors near mixed Nash equilibria lead to collective rationality.
This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.