Pith. sign in

REVIEW 3 major objections 6 minor 26 references

Pointwise Convergence in Games with Conflicting Interest

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Optimistic no-regret play converges pointwise to Nash equilibria

desk verdict Pointwise convergence for harmonic games is real and new; the corruption section is ill-posed as written, but repairable without touching the main theorem. read the letter →

arxiv 2505.15454 v1 pith:X5DKTTL6 submitted 2025-05-21 cs.GT

Nanxiang Zhou , Jing Dong , Baoxiang Wang This is my paper · ORCID
classification cs.GT MSC 91A1091A26
keywords non-negativeweightedregretharmonicgameszero-sumoptimisticmirrordescentfollowtheregularizedleaderpointwiseconvergenceNashequilibriumcorruptedlearningdynamics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces a property it calls non-negative weighted regret: there is a fixed vector of positive player weights $m$ such that, for every finite sequence of strategy profiles, the weighted sum of the players' regrets is non-negative. It argues that this property covers harmonic games and several classes of zero-sum games, and that under it the optimistic algorithms OMD and OFTRL reach an $\epsilon$-approximate Nash equilibrium in $O(1/\epsilon^2)$ iterations and converge to the set of Nash equilibria. When the set of Nash equilibria is discrete, meaning finitely many equilibria, the iterates converge to a single Nash equilibrium rather than merely to the set. Convergence to the equilibrium set, and to a single equilibrium when the set is discrete, also survives finite cumulative deviations by players from their prescribed strategies. If the arguments are right, this supplies the first pointwise convergence guarantees for harmonic games and for games with non-negative regret.

What carries the argument

The central objects are the weighted individual regret $m_i\mathrm{Reg}^T_i = \max_{x^*\in\Delta(A_i)}\sum_{t=1}^T m_i\langle x^*-x_i^t, v_i^t\rangle$ and the game property $\sum_{i=1}^n m_i\mathrm{Reg}^T_i \ge 0$ for one fixed positive vector $m$, required to hold for every finite sequence of strategy profiles. The engine of the proof is an optimistic-regret inequality that bounds each player's weighted regret by a Bregman-divergence telescope plus the cumulative variation of the payoff field, minus the squared distances between the played strategy, the optimistic state, and the previous optimistic state. Summing these inequalities and invoking non-negative weighted regret gives a uniform bound on $\sum_{i=1}^n\sum_{t=1}^T(\|x_i^t-g_i^t\|^2+\|x_i^t-g_i^{t-1}\|^2)$, which forces the iterates to become approximate equilibria and consecutive updates to vanish. The final step is a lemma about sequences in a compact set: a bounded sequence that converges to a finite set $E$ and whose consecutive terms get arbitrarily close must converge to one point of $E$.

What would settle it

Run OMD or OFTRL with a constant learning rate in a finite game whose non-negative weighted regret property has been verified directly from Definition 5.2, and record the first iteration at which the joint strategy is an $\epsilon$-approximate Nash equilibrium. If the required number of iterations is not $O(1/\epsilon^2)$, or if the iterates fail to converge to the equilibrium set while the certificate holds, Theorems 6.1 and 6.2 are false. A more local test targets Lemma 5.1: for a small harmonic game, use the weights constructed in the lemma and search over strategy sequences for a negative value of $\sum_{i=1}^n m_i\mathrm{Reg}^T_i$, which would contradict the claimed certificate.

Watch

Extended reading notes

Core claim

The central claim is that conflicting-interest games can be analysed through a single weighted-regret certificate, and that optimistic no-regret learning has pointwise convergence in exactly the games that carry it. Concretely, Theorem 6.1 gives an $O(1/\epsilon^2)$ bound on the number of OMD iterations needed to produce an $\epsilon$-approximate Nash equilibrium, and Theorem 6.2 upgrades the conclusion to convergence of the whole sequence to the equilibrium set; Theorems 6.4 and 6.5 state the parallel guarantees for OFTRL. The pointwise step, Theorem 6.3, says that if the equilibrium set is discrete, then the iterates converge to one Nash equilibrium, not just to the set. The proof route is a regret bound whose summing yields a uniform bound on the squared sizes of the optimistic updates, followed by a compactness argument showing that a bounded sequence with vanishing consecutive differences that accumulates at finitely many Nash equilibria must settle on one of them. The corruption theorems extend the same two-stage argument to play that deviates finitely from the algorithmic output.

Load-bearing premise

The load-bearing premise is the existence of one fixed positive weight vector $m$ such that every finite sequence of strategy profiles in the game has non-negative weighted total regret; the harmonic-game special case constructs such an $m$ from the harmonic weights, but for the general theorem the property is assumed, and if it fails the uniform bound on squared update sizes collapses.

Editorial extensions

If this is right

  • In every finite normal-form game that satisfies non-negative weighted regret, both OMD and OFTRL find an $\epsilon$-approximate Nash equilibrium in $O(1/\epsilon^2)$ iterations; the bound depends on the weights, regularizers, and norm constants.
  • If the game has finitely many Nash equilibria, the actual sequence of play converges to one of them; no uniqueness or condition-number assumption is needed.
  • For two-player zero-sum games with a unique equilibrium this recovers earlier pointwise convergence results as a special case of the discrete-equilibrium theorem.
  • Finite cumulative deviations by players do not destroy convergence: the iterates still approach the Nash equilibrium set, and with finitely many equilibria they still converge to an equilibrium.
  • In harmonic games, the result strengthens the known asymptotic convergence to the equilibrium set into pointwise convergence to an equilibrium whenever the equilibrium set is discrete.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof only uses the weighted-regret certificate through the summed bound on update sizes, so other optimistic or regularized dynamics that admit the same type of inequality should inherit both the $O(1/\epsilon^2)$ rate and the pointwise convergence in this game class.
  • Because the certificate quantifies over all finite sequences, one could in principle search for a witnessing weight vector $m$ computationally for small games, turning non-negative weighted regret into a checkable sufficient condition rather than an assumed property.
  • The finite-corruption result suggests a natural testable extension toward vanishing but non-summable noise: the stated proofs rely on finite total corruption, so decaying errors that still sum to infinity would be the next boundary case.
  • Potential games sit outside the framework as the paper notes; testing whether any potential game with multiple equilibria can have non-negative weighted regret would clarify exactly where the certificate stops.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper introduces a class of games with non-negative weighted regret, a weighted generalization of the non-negative regret property of Anagnostides et al. It shows that optimistic mirror descent (OMD) and optimistic follow-the-regularized-leader (OFTRL) reach an epsilon-approximate Nash equilibrium in O(1/epsilon^2) iterations in such games, and that their iterates converge pointwise to a Nash equilibrium when the equilibrium set is discrete. Harmonic games are shown to have non-negative weighted regret, which yields the paper's advertised first pointwise convergence results for harmonic games, alongside extensions to several zero-sum classes. A final section claims the same convergence guarantees persist under finite cumulative corruption of the played strategies, and the theoretical results are supplemented by small experiments on matching pennies and a harmonic game.

Significance. If the technical gaps are repaired, this is a valuable contribution: the non-negative weighted regret framework plausibly unifies previously disparate convergence results for harmonic and zero-sum games, and the tail-summability argument leading to pointwise convergence under a discrete equilibrium set is a clean and non-obvious step. The OMD proof is largely coherent and follows standard optimistic-regret machinery with an independent algebraic verification of the harmonic-game property in Lemma 5.1. The paper also makes a concrete falsifiable prediction about the behavior of OMD and OFTRL in harmonic games, supported by experiments. However, the corruption model is currently not well-posed, and the OFTRL results depend on an equivalence proof with a genuine technical gap, so the advertised robustness and OFTRL contributions are not yet established as written.

major comments (3)
  1. [Section 7 (Definition 7.1; Theorems 7.1-7.5)] The corrupted update x^{t+1}_i = \tilde x^{t+1}_i + c^{t+1}_i imposes no constraint that x^{t+1}_i lies in the simplex \Delta(A_i), so the 'played strategy' may have negative coordinates or coordinate sum different from 1. Because the paper defines utilities, payoff fields, regret, and approximate Nash equilibrium only for probability distributions, the objects v_i(x^{t+1}), mReg^T_i, and the statement 'x^t is an epsilon-approximate Nash equilibrium' are undefined for such iterates; the proof of Theorem 7.1 also uses \|v_i^t\|_\infty \le 1, which can fail outside the simplex. This gap affects every robustness theorem in Section 7 and the abstract's claim that convergence persists under finite deviations. The section can be repaired by constraining c^t_i so that x^t_i stays in the simplex (for example, c^t_i \ge -\tilde x^{t+1}_i and \sum_j c^t_{i,j} \le 1 - \sum_j \tilde x^{t+1}_{i,j}) or by projecting the corrupted point back onto the simplex, but as written the corruption theorems are internally inconsistent.
  2. [Appendix C (proof of Theorem 6.4)] The base case of the claimed OMD/OFTRL equivalence asserts \nabla R_i(g^0_i)=0 because g^0_i = \arg\min_{x_i \in \Delta(A_i)} R_i(x_i). The constrained first-order condition only gives a normal-cone condition; for an interior minimizer of a Legendre regularizer, \nabla R_i(g^0_i) is a constant multiple of the all-ones vector (or, more generally, lies in the normal cone), not necessarily zero. If \nabla R_i(g^0_i) is not constant on the simplex, the maximizers \hat x^1_i and x^1_i need not coincide, and the induction establishing \hat x^t = x^t collapses. Since Theorems 6.4 and 6.5 rely entirely on this equivalence, the OFTRL convergence results are not established as written; a normal-cone argument or a different initialization is needed.
  3. [Appendix D (Lemma D.2 and Theorem 7.1)] Even after enforcing feasibility, the corruption analysis should clarify which strategy the regret benchmark is taken against. Lemma D.2 begins with a decomposition involving \tilde x^t_i and x^t_i, but Definition 5.1 for mReg^T_i is stated for the played sequence x^t. The decomposition itself is algebraically valid, but the text does not explicitly define the corrupted regret with respect to the actually played strategies; this ambiguity, combined with the Definition 7.1 notation swap described in the minor comments, makes the corruption theorems difficult to verify as stated.
minor comments (6)
  1. [Abstract] The abstract is truncated: 'even if the players deviate Our theoretical findings are supported...' needs to be completed.
  2. [Definition 7.1] The notation is inconsistent with the updates: the text calls \tilde x the 'committed' strategy and x the 'algorithm output', but in the OMD and OFTRL updates x is the corrupted played strategy and \tilde x is the uncorrupted algorithm output; the variables should be swapped or the wording clarified.
  3. [Proof of Theorem 6.5] The proof cites Theorems 7.3 and 7.2; it should refer to the corresponding OMD/OFTRL results, presumably Theorem 6.4 and Theorem 6.2.
  4. [Cross-references in Appendices B-D] Several cross-references appear to be off after renumbering: the proof of Theorem 7.2 refers to 'Theorem 8.1' and 'Theorem B.1', and Appendix D refers to 'Lemma C.1', 'Theorem D.2', and 'Theorem D.3' rather than the actual theorem numbers.
  5. [Theorems 7.1 and 7.4] The displayed iteration bound is typeset with missing plus signs, making the formula unreadable; for example the terms involving \sum_i M_i C_i and \sum_i C_i are not visibly separated.
  6. [Sections 3 and 5] There is a typo 'Norm-form game' in Definition 3.3, and in Lemma 5.2 the phrase 'Takem_i = 1' is missing a space; these should be corrected during revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence theorems follow from the explicitly stated non-negative weighted regret property, and harmonic-game membership is established by an independent algebraic derivation.

full rationale

The derivation chain is self-contained and does not reduce to its inputs. The central sufficient condition (non-negative weighted regret, Definition 5.2) is a stated game property, not a fitted or renamed version of the target convergence claim; Theorem 6.1 derives the OMD guarantee from the regret decompositions in Lemmas B.1-B.4, with the total update bound following from the assumed weighted regret inequality. Lemma 5.1 establishes that harmonic games satisfy this property by a direct algebraic calculation from Definition 3.3, independent of the convergence analysis, and Lemma 5.2 is an immediate reduction to the prior non-negative regret result by taking m_i = 1. The pointwise refinement in Theorems 6.3 and 6.5 is obtained from Theorem 6.1 together with the authors' own compactness and finite-set arguments (Lemmas B.5-B.6), not from any assumed conclusion. The OFTRL guarantees reduce to OMD via a constructive induction showing the two iterates coincide, which is not circular. Section 7 reuses the same regret decomposition with additive corruption terms; although the feasibility of x^{t+1} = \tilde x^{t+1} + c^{t+1} as a point in the simplex may be a correctness concern, it is not a circularity concern. No load-bearing self-citation appears: the authors' own prior work [DWY24] is cited only in a broad related-work list for potential games, and the harmonic-game definition and non-negative regret base results are credited to external prior work.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the game-theoretic property of non-negative weighted regret and standard convex-optimization assumptions on the regularizers. No free parameters are fitted to data; the learning rate constraints are sufficient conditions, not empirical fits.

assumptions (5)
  • domain assumption Finite normal-form game with utilities in [-1,1] and payoff field defined by multilinear extension.
    Section 3.1 defines the game setting used throughout.
  • domain assumption The game has non-negative weighted regret for some positive weight vector m (Definition 5.2).
    This is the defining property of the game class in Theorems 6.1-6.5; without it the proof cannot bound the regret sum.
  • domain assumption Regularizers R_i are 1-strongly convex and G_i-smooth; for OFTRL, Legendre with domain in the simplex.
    Required for the Bregman divergence inequalities in Lemmas B.1-B.3 and for the OMD-OFTRL equivalence proof.
  • domain assumption Learning rate is non-increasing and bounded below by a positive constant eta_i (Theorem 6.1).
    Needed for a T-independent bound on the sum of squared distances, which drives the pointwise convergence argument.
  • ad hoc to paper Corruption is modeled as additive perturbation with finite l1 sum and the played strategy is a valid mixed strategy.
    Section 7, Definition 7.1 and the update rules introduce this model; the paper never proves that adding c^t keeps the strategy in the simplex.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pointwise Convergence in Games with Conflicting Interest." pith.science (2026). https://pith.science/paper/X5DKTTL6

@misc{pith2026250515454,
  author       = {Pith},
  title        = {Pith review of: Pointwise Convergence in Games with Conflicting Interest},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X5DKTTL6}},
  note         = {Machine review of arXiv:2505.15454}
}
abstract

In this work, we introduce the concept of non-negative weighted regret, an extension of non-negative regret \cite{anagnostides2022last} in games. Investigating games with non-negative weighted regret helps us to understand games with conflicting interests, including harmonic games and important classes of zero-sum games.We show that optimistic variants of classical no-regret learning algorithms, namely optimistic mirror descent (OMD) and optimistic follow the regularized leader (OFTRL), converge to an $\epsilon$-approximate Nash equilibrium at a rate of $O(1/\epsilon^2)$.Consequently, they guarantee pointwise convergence to a Nash equilibrium if there are only finitely many Nash equilibria in the game. These algorithms are robust in the sense the convergence holds even if the players deviate Our theoretical findings are supported by empirical evaluations of OMD and OFTRL on the game of matching pennies and harmonic game instances.

Figures

Figures reproduced from arXiv: 2505.15454 by the authors.

Figure 1
Figure 1. Total regret plot in a Har￾monic game where the utility is the col￾lective sum of action minus the individ￾ual action. Each point represents the total regret after 10 rounds. Definition 5.2. A game has non-negative weight regret, if ∃m ∈ Rn ++, Xn i=1 mRegT i ≥ 0 , ∀{x t } T t=1 ∈ ∆(A), T ≥ 1 . It is obvious that if a game has non-negative regret, then it has non-negative weighted regret (just let m = (1, · · · , 1)… view at source ↗
Figure 2
Figure 2. The two plots illustrate the convergence of OMD and OFTRL algorithms towards the Nash [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 25 canonical work pages

  1. [1]

    On last-iterate convergence beyond zero-sum games

    Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning , 2022

    work page 2022

  2. [2]

    Decomposition of games: some strategic considerations

    Joseph Abdou, Nikolaos Pnevmatikos, Marco Scarsini, and Xavier Venel. Decomposition of games: some strategic considerations. Mathematics of Operations Research , 47(1):176--208, 2022

    work page 2022

  3. [3]

    Flows and decompositions of games: Harmonic and potential games

    Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo. Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research , 36(3):474--503, 2011

    work page 2011

  4. [4]

    A payoff-based learning procedure and its application to traffic games

    Roberto Cominetti, Emerson Melo, and Sylvain Sorin. A payoff-based learning procedure and its application to traffic games. Games and Economic Behavior , 70(1):71--83, 2010

    work page 2010

  5. [5]

    Hedging in games: Faster convergence of external and swap regrets

    Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. In Advances in Neural Information Processing Systems , 2020

    work page 2020

  6. [6]

    Near-optimal no-regret algorithms for zero-sum games

    Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In ACM-SIAM Symposium on Discrete Algorithms , 2011

    work page 2011

  7. [7]

    Independent policy gradient methods for competitive reinforcement learning

    Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems , 2020

    work page 2020

  8. [8]

    The complexity of computing a nash equilibrium

    Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM , 52(2):89--97, 2009

    2009

Show all 26 references
  1. [9]

    Last-iterate convergence: Zero-sum games and constrained min-max optimization

    Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. Innovations in Theoretical Computer Science , 2019

    2019

  2. [10]

    Convergence to nash equilibrium and no-regret guarantee in (markov) potential games

    Jing Dong, Baoxiang Wang, and Yaoliang Yu. Convergence to nash equilibrium and no-regret guarantee in (markov) potential games. In International Conference on Artificial Intelligence and Statistics , 2024

    2024

  3. [11]

    Adaptive learning in continuous games: O ptimal regret bounds and convergence to N ash equilibrium

    Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: O ptimal regret bounds and convergence to N ash equilibrium. In Conference on Learning Theory , 2021

    2021

  4. [12]

    Learning with bandit feedback in potential games

    Am \'e lie Heliou, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In Advances in Neural Information Processing Systems , 2017

    2017

  5. [13]

    Differentiable game mechanics

    Alistair Letcher, David Balduzzi, S \'e bastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. Journal of Machine Learning Research , 20(84):1--40, 2019

    2019

  6. [14]

    No-regret learning in harmonic games: Extrapolation in the face of conflicting interests

    Davide Legacci, Panayotis Mertikopoulos, Christos Papadimitriou, Georgios Piliouras, and Bary SR Pradelski. No-regret learning in harmonic games: Extrapolation in the face of conflicting interests. In Conference on Neural Information Processing Systems , 2024

    2024

  7. [15]

    A geometric decomposition of finite games: Convergence vs

    Davide Legacci, Panayotis Mertikopoulos, and Bary Pradelski. A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights. In International Conference on Machine Learning , 2024

    2024

  8. [16]

    Global convergence of multi-agent policy gradient in M arkov potential games

    Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in M arkov potential games. In International Conference on Learning Representations , 2022

    2022

  9. [17]

    Global convergence of multi-agent policy gradient in markov potential games

    Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. In International Conference on Learning Representations , 2022

    2022

  10. [18]

    Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

    Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations , 2019

    2019

  11. [19]

    Potential games

    Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior , 14(1):124--143, 1996

    1996

  12. [20]

    Multiplicative weights update with constant step-size in congestion games: C onvergence, limit cycles and chaos

    Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: C onvergence, limit cycles and chaos. In Advances in Neural Information Processing Systems , 2017

    2017

  13. [21]

    Online learning with predictable sequences

    Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory , 2013

    2013

  14. [22]

    Fast convergence of regularized learning in games

    Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems , 2015

    2015

  15. [23]

    Corrupted learning dynamics in games

    Taira Tsuchiya, Shinji Ito, and Haipeng Luo. Corrupted learning dynamics in games. arXiv preprint arXiv:2412.07120 , 2024

    2024 arXiv

  16. [24]

    Linear last-iterate convergence in constrained saddle-point optimization

    Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In International Conference on Learning Representations , 2020

    2020

  17. [25]

    Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games

    Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Conference on learning theory , 2021

    2021

  18. [26]

    o(t^ -1 )) convergence of optimistic-follow-the-regularized-leader in two-player zero-sum markov games

    Yuepeng Yang and Cong Ma. o(t^ -1 )) convergence of optimistic-follow-the-regularized-leader in two-player zero-sum markov games. In International Conference on Learning Representations , 2022

    2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.