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.