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

Summary

This paper studies the extent to which the ordinal structure of a finite normal-form game — encoded in its preference graph, whose arcs record (weakly) profitable unilateral deviations — determines the long-run behavior of no-regret dynamics, focusing on continuous-time follow-the-regularized-leader (FTRL) and its induced strategy flow. Two directions are pursued. In one direction, ordinal closure is shown to be necessary for dynamic stability: the skeleton of any stable set must be closed under strict better replies, and strongly connected pure-profile sets force the mixed span into any attractor that meets them. In the converse direction, the paper delineates when ordinal closure is sufficient: for subgames (product spans), closure under better replies is equivalent to asymptotic stability of the corresponding face, extending the Ritzberger–Weibull principle from the replicator to steep and non-steep regularizers via a Fenchel-gap energy. Beyond subgames, the equivalence breaks — a compact 2x2x2 example refutes a recent conjecture of Biggar and Papadimitriou, with escape happening in the interior rather than through a proper subface. To restore stability, the paper introduces leaklessness, a cardinal condition on unilateral deviation gains aggregated along a profile, and proves that strictly leakless spans are attractors for steep regularizers (Theorem 4), sharpening under leaklessness plus club to the replicator (Theorem 5). The condition is polynomial-time checkable in the normal-form representation and specialises correctly to strict Nash equilibria on singletons, giving a genuinely setwise cardinal generalization of pure-Nash-type stability. The conceptual pay-off — clarifying that ordinal data alone is a constraint rather than a characterization, and identifying an intrinsically cardinal fix — is what gives the paper its bite. The main methodological limitation is that the roadmap of the leaklessness–stability equivalence is left partial: leaklessness is only sufficient, the strict vs. non-strict gap between Theorems 4 and 5 is not motivated, and the "broad class of regularizers" framing understates how much Assumption 1 (which implies steepness) is doing.

Strengths

• Conceptual clarification. The main message — ordinal information constrains but does not determine long-run dynamics under FTRL, and payoff magnitudes can be essential — is landed cleanly with a compact 2x2x2 counterexample. This is a genuinely useful conceptual correction to the "preferences-only" line of work and to the Biggar–Papadimitriou local-source conjecture.
• Leaklessness as a novel condition. Leaklessness is a natural, elementary, payoff-based condition that (i) reduces to pure Nash on singletons, (ii) is invisible to the preference graph, (iii) can be tested and enumerated in polynomial time over the payoff table, and (iv) explains stability of the Jordan and Shapley cycles in a principled way rather than by ad-hoc arguments.
• Fenchel-gap energy. The Fenchel-gap construction (Lemma G.3) plausibly closes the gap in the Biggar–Shames energy noted by Cauvin–Legacci–Mertikopoulos and works uniformly for steep and non-steep regularizers — this is an incremental but real technical contribution.
• Sharp characterization for subgames and weakly acyclic games. Corollaries 1–3 give clean equivalences with the preference graph on the subgame side and, via Johnston–Savery–Scott–Tarbush, a clean minimal-attractor characterization in the many-player / few-actions regime, connecting the theory to a plausible empirical practice.
• Structural results on attractors. Propositions 1 and Theorems 1, 2 tighten the earlier Biggar–Shames chain-transitivity story: closure under strict better replies is forced by (FTRL) stability, and strong connectivity propagates from pure profiles to their mixed span, giving a clean nonexistence-of-proper-attractor conclusion when the preference graph is strongly connected.

Weaknesses

• Definitional slip on "proper" club sets. Section 3.1 states "we will say a club / s-club set is proper if it is neither non-empty nor equal to A". Read literally this means "empty and different from A", which is essentially unsatisfiable and the exact opposite of the intended and downstream-used notion. This is a load-bearing convention (Theorem 2, Proposition 2 all use "proper" club/attractor language) and must be fixed.
• Steepness qualifier missing from headline framing. The abstract and Section 1 present leaklessness as a payoff-based condition guaranteeing stability of a span, without the steepness qualifier. But Theorem 4 uses Assumption 1 (which implies steepness) and Theorem 5 is entropic-only; the non-steep Euclidean setting is not covered by the leaklessness half of the story. The scope of the results should be spelled out in the introduction rather than only in the corresponding proofs.
• Strict vs. non-strict leaklessness gap. Theorem 4 requires strict leaklessness for steep regularizers; Theorem 5 needs only leaklessness + club, but only for the replicator. Whether strict leaklessness is genuinely necessary for general steep FTRL, or whether it is a proof-technique artifact of the exponential-Fenchel energy, is neither shown nor discussed. Given that the Jordan and Shapley cycles are leakless-but-not-strictly-leakless, this gap is not academic.
• Robustness of the counterexample. The Proposition 2 construction uses a payoff magnitude of 10 to make player 3's transverse drift dominant. Whether the instability is structurally stable — i.e., persists on an open neighborhood of payoff perturbations preserving the preference graph — is not addressed. Since this counterexample carries a lot of the paper's conceptual weight (refuting Biggar–Papadimitriou, motivating leaklessness), a robustness statement would substantially strengthen the message.
• Load-bearing proof steps are corrupted or truncated. The rendered manuscript has scrambled or missing displays at several load-bearing points: the concluding integral-divergence step in Proposition E.4's proof, the initialization display and the "It remains to ensure that alpha' ..." sentence in the Theorem 1 proof, and a truncated ratio bound (the sentence beginning "hence x_{i,nu} ...") in the deviating-coalition estimate of Lemma G.8. In each case the argument is reconstructible, but the printed proof is not fully checkable. These are copy-editing errors, but they land squarely on the details a referee is asked to verify.
• Notation clashes and figure-caption slips. The letter B is used for both Bottom and Back in Appendix B.2 (Jordan's Matching Pennies) and Appendix G.3, and Figure 3's caption says "front or bottom" where "back" is meant. Figure 4's caption cites Theorem 5 for a strictly leakless set (Theorem 4's hypothesis). Individually minor, but collectively they slow the reader down at exactly the concrete verification points where the paper needs to be crisp.
• Application to large games slightly overstated. The conclusion that "FTRL works well with games with many players but relatively few actions" is conditional on the game admitting a pure Nash equilibrium (via Johnston et al.). The unconditional-sounding claim in the paper elides that conditioning.
• Discrete-time / algorithmic bridge is asserted, not carried out. The introduction motivates the continuous-time analysis as a stepping stone to discrete algorithmic guarantees via stochastic approximation, but no explicit discrete-time corollary of Theorems 3–5 is provided. Given that the paper's applied framing (preference learning, reward specification, AI safety) is discrete-time, this is a real gap.

Reproducibility & code

The paper is primarily theoretical, and no simulation code or numerical artifact appears to be released with it. That is largely fine — the theorems stand on their proofs. However, several verification points that the paper leaves as "direct computations" or as figures could not be reconstructed from the manuscript alone.

• Figure 5 payoff tables are absent. The four 2x2x2 games with a shared preference graph but progressively modified payoffs are the visual centerpiece of the closing message that cardinal information matters. Yet the payoff tables of the four games are not printed anywhere, the baseline is unnamed, and the "single payoff modified" for each variant is not specified. The qualitative claim about increasing chaos across the four panels is therefore not checkable from the paper.
• Trajectory figures lack initialization data. Figures 1(a-b), 4, and 15 display replicator orbits on 2x2x2 cubes without stating the initial conditions, integration horizons, solvers, or viewing angles. The counterexample argument depends on a specific near-x* initialization, and the "red escape-and-return" trajectory in Figure 4 clearly corresponds to a particular seed. A minimal simulation script would let a reader match figures to trajectories.
• Appendix leakage computations are asserted rather than enumerated. For the strictly-leakless 2x2x2 example of Figure 10, and for the leakless-but-not-strict claim on Jordan's Matching Pennies, the verifications are stated as "a direct computation" giving l_alpha(beta) <= -1 or l_alpha(beta) in {0,-2}. In neither case are the individual pairs enumerated, and the vertex set H is identified only via red highlighting. This is minor for the theorems but leaves the concrete cardinal computations that the paper foregrounds as headline examples not fully independently checkable.
• Empty released code artifact. The environment reflects an empty released code folder, consistent with a theoretical paper with no simulation companion. This is acceptable given the nature of the work, but flagging it lets the reader calibrate expectations.

Recommended Changes

Essential

• Fix the "proper" definition. Rewrite "neither non-empty nor equal to A" as "nonempty and not equal to A" in Section 3.1, and cross-check every downstream use of "proper" (Theorem 2, Proposition 2, Corollary 3, etc.) to ensure the intended reading is preserved. Consider using a different word (e.g. "nontrivial") for club sets vs. "strict" for attractors to eliminate the overloading flagged by footnote 4.
• Restore the corrupted / truncated proof steps. Repair the printed math in (i) Proposition E.4's concluding integration to -infty, (ii) the Theorem 1 proof around the "It remains to ensure that alpha' ..." sentence and the missing initialization of y_i(0), and (iii) the "hence x_{i,nu} ..." step in Lemma G.8. Each is load-bearing for a headline result and cannot be verified as printed.
• Add Figure 5 payoff tables. Print the four 2x2x2 payoff tables (or an appendix table listing the shared preference graph plus the four single-payoff perturbations) so the "increasing chaos" comparison can be reproduced.
• Scope Assumption 1 and steepness in the headline. Rewrite the abstract, Section 1, and Section 3.2 so that the applicability of Theorems 3, 4, 5 to steep vs. non-steep regularizers is unambiguous. In particular, drop "the whole class of (steep) regularized dynamics" phrasings that mix scope and qualifier.

Suggested

• Address the strict vs. non-strict leaklessness gap. Add a remark or open question stating whether Theorem 4 can be strengthened to non-strict leaklessness + club under general steep regularizers, and note explicitly that the Jordan/Shapley cycles are covered only by the entropic Theorem 5.
• Discuss counterexample robustness. Include a short paragraph on whether the Proposition 2 instability persists under small payoff perturbations that preserve the preference graph — a genericity or open-condition statement would remove a natural "knife-edge" reading.
• Fix figure caption and notation slips. Change "front or bottom" to "front or back" in Figure 3; recite Theorem 4 (or explain the reduction to Theorem 5) in Figure 4's caption; use a distinct letter (e.g. K) for Back throughout Appendices B.2 and G.3.
• Enumerate the appendix leakage computations. Provide a small table (or a short verification script) with all l_alpha(beta) values for the sinks in Figures 10 and 11 so the strict-vs-non-strict distinction is fully checkable.
• Document trajectory initializations. For Figures 1, 4, 15, list initial conditions, integration horizon, and solver in the captions or an appendix, so that the qualitative visualizations can be regenerated.
• State a discrete-time corollary. Add a corollary (or an explicit forward reference to Mertikopoulos–Hsieh–Cevher) transferring Theorems 4/5 to discrete-time FTRL with vanishing step size, so the applied framing of the introduction connects to a formal statement.
• Soften the large-games application. Rewrite the "FTRL works well with many players" paragraph to state explicitly the conditioning on existence of a pure Nash equilibrium and cite the relevant literature on pure-Nash existence in the many-player / few-actions regime.
• Rephrase the Prop. 1 tie-case justification. Replace "a game with constant payoffs admits constant dynamics" with the sharper statement about equal marginal payoffs along the edge [alpha,alpha'].
• Recalibrate the related-work framing of Biggar-Shames vs. Ritzberger-Weibull. Rephrase the claim that [9] "essentially recovers" [57] so that the flagged gap in [9]'s energy argument and your Fenchel-gap fix are not in tension with the "recovery" language.