pith. sign in

arxiv: 2605.13644 · v2 · pith:BAOLDG6Enew · submitted 2026-05-13 · 💻 cs.GT

Learning Equilibria in Coordination Games via Minorization-Maximization

Ashok Krishnan K.S. , Helene Le Cadre , Ana Busic This is my paper

Pith reviewed 2026-05-21 08:04 UTC · model grok-4.3

classification 💻 cs.GT
keywords coordination gamesequilibrium learningminorization-maximizationpotential gamesregularizationiterative algorithmsmulti-agent systems
0
0 comments X

The pith

Assuming agents irrationally weigh personal costs lets a minorization-maximization scheme select and learn a unique equilibrium that approximates the original game.

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

The paper studies coordination games in which each agent's utility is the sum of a shared social term and a private cost or reward. Agents are taken to perceive the private term irrationally, which permits the construction of a regularized game whose potential function is strictly concave. The unique maximizer of this potential is shown to be an ε-equilibrium of the original game, with the approximation gap set by the regularizer. An iterative minorization-maximization procedure is introduced to compute the maximizer; the procedure is proved to converge to this distinguished equilibrium. Numerical comparisons indicate faster and more reliable progress than gradient or best-response updates on the same instances.

Core claim

In games where utilities combine a social utility term with an individual cost or reward term, the assumption that agents misperceive the individual term allows regularization to a game possessing a strictly concave potential function. This function selects a unique equilibrium that is an ε-equilibrium of the original game, with ε determined by the regularizing function. A minorization-maximization iterative learning scheme converges to the potential-optimal equilibrium and exhibits superior convergence behavior relative to gradient and best-response methods.

What carries the argument

minorization-maximization iterative scheme that ascends the strictly concave potential of the regularized game to locate the unique equilibrium

If this is right

  • The output of the scheme is guaranteed to be an ε-equilibrium of the original game, with the gap controlled by the choice of regularizer.
  • The iteration converges specifically to the potential-optimal equilibrium rather than to any of the other equilibria that may exist.
  • Convergence occurs with fewer iterations and less oscillation than gradient ascent or best-response dynamics on identical game instances.
  • Each agent can execute the updates using only local information derived from the potential function without requiring full knowledge of others' payoffs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the regularization strength is allowed to vary over time, the same scheme could track equilibria in games whose social utilities change slowly.
  • The same misperception modeling step may be reusable in other potential-game settings where multiple equilibria must be disambiguated without altering the original payoffs.
  • Because updates depend only on the potential, the procedure lends itself to fully distributed implementations that exchange only aggregate statistics rather than individual strategies.

Load-bearing premise

Agents are irrational in their perception of the individual cost or reward, which creates a strictly concave potential in the regularized game.

What would settle it

Apply the minorization-maximization iterations to a two-player coordination game with known multiple equilibria, then measure whether the output profile lies within the predicted ε of every unilateral deviation and coincides with the unique maximizer of the constructed potential.

Figures

Figures reproduced from arXiv: 2605.13644 by Ana Busic, Ashok Krishnan K.S., Helene Le Cadre.

Figure 1
Figure 1. Figure 1: Example of a prospect theoretic value function [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Smooth game. The game has a unique Nash equilibrium, which also coincides with the optimal point of the potential function. We plot the error (i.e., distance to Nash equilibrium) comparing gradient descent (AGA), iterative best response (IBR) and iterative MM (IMM) in [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Steering the collective usage function J (x) to a desired τ using IMM. −5 0 5 10 x1 −6 −4 −2 0 2 4 6 x2 −32 −28 −24 −20 −16 −12 −8 −4 0 4 (a) Zoomed out −0.4 −0.2 0.0 0.2 0.4 x1 −0.4 −0.2 0.0 0.2 0.4 x2 3.93 4.05 4.17 4.29 4.41 4.53 4.65 4.77 4.89 5.01 (b) Zoomed in [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: State evolution of iterative MM, along the contour [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: State evolution of sGA, along the contours of the po [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: State evolution of iterative BR, converging to poin [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Movement of three robotic agents starting from thr [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
read the original abstract

This paper considers games where the utilities for agents are the sum of a term proportional to a social utility, and another term that is an individual cost or reward. The agents are assumed to be irrational in their perception of the individual cost or reward. The multi equilibrium game is regularized, and its strictly concave potential function is used to select a unique equilibrium. This selected equilibrium is shown to be an $\epsilon-$equilibrium of the original game, where $\epsilon$ is parametrized by the regularizing function. A minorization-maximization based iterative learning scheme is proposed to learn equilibria in this game. This scheme converges to the potential-optimal equilibrium, and has superior convergence behaviour in comparison to gradient and best response methods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript considers coordination games where each agent's utility is the sum of a social utility term and an individual cost or reward term. Agents are modeled as irrational in perceiving the individual term. The multi-equilibrium game is regularized to yield a strictly concave potential function that selects a unique equilibrium; this equilibrium is shown to be an ε-equilibrium of the original game, with ε parametrized by the regularizer. A minorization-maximization iterative learning scheme is proposed that converges to the potential-optimal equilibrium and exhibits superior convergence behavior relative to gradient and best-response methods.

Significance. If the central derivations hold, the paper offers a regularization-based mechanism for equilibrium selection in games with multiple equilibria and an MM-based algorithm with convergence guarantees. This could contribute to algorithmic game theory by providing a principled way to select and compute equilibria in coordination settings, along with a comparison to standard dynamics. The ε-equilibrium property and the use of a potential function are potentially useful, though the strength depends on the precise conditions under which the potential is strictly concave.

major comments (1)
  1. [Section on game regularization and potential construction] The claim that the regularized game has a strictly concave potential (and thus selects a unique equilibrium) relies on the modeling of irrational perception of the individual cost/reward term. The manuscript should explicitly state whether this strict concavity holds for general bounded perturbations or additive noise, or whether it requires additional restrictions on the perception model or regularizer (e.g., a specific functional form, Lipschitz bound, or concavity-inducing property). This is load-bearing for the unique-selection and ε-equilibrium claims.
minor comments (1)
  1. [Abstract] The abstract and introduction would benefit from a brief statement of the exact form of the regularizing function and how ε is explicitly parametrized by it.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address the major comment below and will revise the manuscript to improve clarity on the conditions for strict concavity.

read point-by-point responses

  1. Referee: [Section on game regularization and potential construction] The claim that the regularized game has a strictly concave potential (and thus selects a unique equilibrium) relies on the modeling of irrational perception of the individual cost/reward term. The manuscript should explicitly state whether this strict concavity holds for general bounded perturbations or additive noise, or whether it requires additional restrictions on the perception model or regularizer (e.g., a specific functional form, Lipschitz bound, or concavity-inducing property). This is load-bearing for the unique-selection and ε-equilibrium claims.

    Authors: We agree that the strict concavity of the potential function is tied to the specific modeling of agents' irrational perception of the individual cost/reward term. In the paper, this irrationality is incorporated via a perception model that, together with the regularizer, ensures the potential is strictly concave, thereby selecting a unique equilibrium. This property does not hold for arbitrary bounded perturbations or additive noise in the absence of the concavity-inducing features of the regularizer and the irrationality assumption. We will revise the relevant section to explicitly delineate these conditions, including any required properties of the regularizer, to strengthen the presentation of the unique-selection and ε-equilibrium results. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation constructs potential from regularized utilities and proves convergence independently

full rationale

The paper constructs a regularized game from the irrational-perception modeling of individual costs, derives a strictly concave potential function directly from the regularized utilities, selects the unique equilibrium as the maximizer of that potential, and separately proves it is an ε-equilibrium of the original game with ε controlled by the regularizer. The minorization-maximization algorithm is then shown to converge to this potential maximizer using standard MM properties on the concave potential. None of these steps reduce by definition or by self-citation to the final result; the potential is an explicit construction, the ε-bound is a separate approximation argument, and convergence follows from the algorithm's general guarantees rather than from fitting or renaming the target equilibrium itself. No load-bearing self-citation or ansatz smuggling is indicated in the provided text.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The central claims rest on the domain assumption that agents misperceive individual costs and on the mathematical property that regularization produces a strictly concave potential; no free parameters or invented entities are explicitly introduced in the abstract.

free parameters (1)
  • regularization parameter
    Controls the epsilon distance to the original-game equilibrium and is part of the regularizing function.
axioms (2)
  • domain assumption Agents are irrational in their perception of the individual cost or reward.
    Stated directly in the abstract as the modeling premise that enables the regularization approach.
  • domain assumption Regularization yields a strictly concave potential function.
    Invoked to guarantee a unique equilibrium selection.

pith-pipeline@v0.9.0 · 5653 in / 1380 out tokens · 57058 ms · 2026-05-21T08:04:52.079786+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Cooper, Coordination games

    R. Cooper, Coordination games. Cambridge university Press, 1999

    work page 1999

  2. [2]

    Aggregative games and best-reply potenti als,

    M. K. Jensen, “Aggregative games and best-reply potenti als,” Economic theory , vol. 43, no. 1, pp. 45–66, 2010

    work page 2010

  3. [3]

    Voorneveld, Potential games and interactive decisions with multiple cr iteria

    M. Voorneveld, Potential games and interactive decisions with multiple cr iteria. Ph.D. Thesis, Tilburg University, 1999

    work page 1999

  4. [4]

    Achieving a Collective Target through In- centives,

    A. K. KS, H. Le Cadre, and A. Bušić, “Achieving a Collective Target through In- centives,” in International Conference on Network Games, Artificial Inte lligence, Control and Optimization , pp. 57–67, Springer, 2025

    work page 2025

  5. [5]

    Exploration in deep reinforcement learning: From single-agent to multi agent domain,

    J. Hao, T. Yang, H. Tang, C. Bai, J. Liu, Z. Meng, P. Liu, and Z . Wang, “Exploration in deep reinforcement learning: From single-agent to multi agent domain,” IEEE transactions on neural networks and learning systems , vol. 35, no. 7, pp. 8762–8782, 2023

    work page 2023

  6. [6]

    Coordinated control of mult i-robot systems: A survey,

    J. Cortés and M. Egerstedt, “Coordinated control of mult i-robot systems: A survey,” SICE Journal of Control, Measurement, and System Integrati on, vol. 10, no. 6, pp. 495–503, 2017

    work page 2017

  7. [7]

    Emergent col laboration in social purpose games,

    R. P. Gilles, L. Mallozzi, and R. Messalli, “Emergent col laboration in social purpose games,” Dynamic Games and Applications , vol. 13, no. 2, pp. 566–588, 2023

    work page 2023

  8. [8]

    Cooperative games and cooperative organi zations,

    R. A. McCain, “Cooperative games and cooperative organi zations,” The Journal of Socio-Economics, vol. 37, no. 6, pp. 2155–2167, 2008

    work page 2008

  9. [9]

    Bach, Learning with Submodular Functions: A Convex Optimization Perspective

    F. Bach, Learning with Submodular Functions: A Convex Optimization Perspective. Foundations and Trends in Machine Learning, 2013

    work page 2013

  10. [10]

    Mean field games,

    J.-M. Lasry and P.-L. Lions, “Mean field games,” Japanese journal of mathematics , vol. 2, no. 1, pp. 229–260, 2007

    work page 2007

  11. [11]

    Jallais and P.-C

    S. Jallais and P.-C. Pradier, The Allais paradox and its immediate consequences for expected utility theory . Routledge New York, 2005

    work page 2005

  12. [12]

    Quantal response equi libria for normal form games,

    R. D. McKelvey and T. R. Palfrey, “Quantal response equi libria for normal form games,” Games and economic behavior , vol. 10, no. 1, pp. 6–38, 1995

    work page 1995

  13. [13]

    The logit-response dyna mics,

    C. Alós-Ferrer and N. Netzer, “The logit-response dyna mics,” Games and Economic Behavior, vol. 68, no. 2, pp. 413–427, 2010

    work page 2010

  14. [14]

    Robust game theory,

    M. Aghassi and D. Bertsimas, “Robust game theory,” Mathematical programming, vol. 107, no. 1, pp. 231–273, 2006

    work page 2006

  15. [15]

    Prospect theory: An analys is of decision under risk,

    D. Kahneman and A. Tversky, “Prospect theory: An analys is of decision under risk,” Econometrica, vol. 47, no. 2, pp. 363–391, 1979. 20

    work page 1979

  16. [16]

    Von Neumann and O

    J. Von Neumann and O. Morgenstern, Theory of games and economic behavior. Princeton University Press, 1944

    work page 1944

  17. [17]

    Cumulative prospect theory’s functional menagerie,

    H. P. Stott, “Cumulative prospect theory’s functional menagerie,” Journal of Risk and uncertainty, vol. 32, pp. 101–130, 2006

    work page 2006

  18. [18]

    How irrationality sha pes nash equilibria: A prospect-theoretic perspective,

    A. K. KS, H. Le Cadre, and A. Bušić, “How irrationality sha pes nash equilibria: A prospect-theoretic perspective,” in 2025 IEEE 64th Conference on Decision and Control (CDC) , pp. 4428–4433, IEEE, 2025

    work page 2025

  19. [19]

    Existence and uniqueness of equilibrium po ints for concave n-person games,

    J. B. Rosen, “Existence and uniqueness of equilibrium po ints for concave n-person games,” Econometrica: Journal of the Econometric Society , pp. 520–534, 1965

    work page 1965

  20. [20]

    Best response dynamics in finite games w ith additive aggregation,

    N. S. Kukushkin, “Best response dynamics in finite games w ith additive aggregation,” Games and Economic Behavior , vol. 48, no. 1, pp. 94–110, 2004

    work page 2004

  21. [21]

    A tutorial on mm algorithms,

    D. R. Hunter and K. Lange, “A tutorial on mm algorithms,” The American Statis- tician, vol. 58, no. 1, pp. 30–37, 2004

    work page 2004

  22. [22]

    Potential games,

    D. Monderer and L. S. Shapley, “Potential games,” Games and economic behavior , vol. 14, no. 1, pp. 124–143, 1996

    work page 1996

  23. [23]

    Learning i n near-potential games,

    O. Candogan, A. Ozdaglar, and P. A. Parrilo, “Learning i n near-potential games,” in 2011 50th IEEE Conference on Decision and Control and Europe an Control Con- ference, pp. 2428–2433, IEEE, 2011

    work page 2011

  24. [24]

    Management theory applications of prospect theory: Accom plishments, challenges, and opportunities,

    R. M. Holmes Jr, P. Bromiley, C. E. Devers, T. R. Holcomb, a nd J. B. McGuire, “Management theory applications of prospect theory: Accom plishments, challenges, and opportunities,” Journal of Management , vol. 37, no. 4, pp. 1069–1107, 2011

    work page 2011

  25. [25]

    Modeling adversaries in c ounterterrorism decisions using prospect theory,

    J. R. Merrick and P. Leclerc, “Modeling adversaries in c ounterterrorism decisions using prospect theory,” Risk Analysis , vol. 36, no. 4, pp. 681–693, 2016

    work page 2016

  26. [26]

    Modeling noncooperative game of gencos’ participation in electricity markets with prospect theory,

    M. Vahid-Pakdel, S. Ghaemi, B. Mohammadi-Ivatloo, J. Sa lehi, and P. Siano, “Modeling noncooperative game of gencos’ participation in electricity markets with prospect theory,” IEEE Transactions on Industrial Informatics , vol. 15, no. 10, pp. 5489–5496, 2019

    work page 2019

  27. [27]

    Equilibrium notions for agents with cumula tive prospect theory prefer- ences,

    K. Keskin, “Equilibrium notions for agents with cumula tive prospect theory prefer- ences,” Decision Analysis, vol. 13, no. 3, pp. 192–208, 2016

    work page 2016

  28. [28]

    Non-cooperative games w ith prospect theory players and dominated strategies,

    L. P. Metzger and M. O. Rieger, “Non-cooperative games w ith prospect theory players and dominated strategies,” Games and Economic Behavior, vol. 115, pp. 396– 409, 2019

    work page 2019

  29. [29]

    Loss aversion equilibrium,

    J. Shalev, “Loss aversion equilibrium,” International Journal of Game Theory , vol. 29, pp. 269–287, 2000. 21

    work page 2000

  30. [30]

    Application and o utlook of prospect theory applied to bounded rational power system economic de cisions,

    L. Gan, Y. Hu, X. Chen, G. Li, and K. Yu, “Application and o utlook of prospect theory applied to bounded rational power system economic de cisions,” IEEE Trans- actions on Industry Applications , vol. 58, no. 3, pp. 3227–3237, 2022

    work page 2022

  31. [31]

    Non cooperative games with prospect theoretic preferences,

    M. Fochesato, F. Pokou, H. Le Cadre, and J. Lygeros, “Non cooperative games with prospect theoretic preferences,” IEEE Control Systems Letters , 2025

    work page 2025

  32. [32]

    Correlated equilibrium and potential game s,

    A. Neyman, “Correlated equilibrium and potential game s,” International Journal of Game Theory , vol. 26, no. 2, pp. 223–227, 1997

    work page 1997

  33. [33]

    D. P. Bertsekas, Nonlinear programming. Athena Scientific, 1999

    work page 1999

  34. [34]

    Nonconve x optimization via MM algorithms: Convergence theory,

    K. Lange, J.-H. Won, A. Landeros, and H. Zhou, “Nonconve x optimization via MM algorithms: Convergence theory,” arXiv preprint arXiv:2106.02805 , 2021

    work page arXiv 2021

  35. [35]

    Proximal algorithms,

    N. Parikh and S. Boyd, “Proximal algorithms,” Foundations and Trends in optimiza- tion, vol. 1, no. 3, pp. 127–239, 2014

    work page 2014

  36. [36]

    On the convergence of the proximal point algo rithm for convex mini- mization,

    O. Güler, “On the convergence of the proximal point algo rithm for convex mini- mization,” SIAM journal on control and optimization , vol. 29, no. 2, pp. 403–419, 1991

    work page 1991

  37. [37]

    Monotone operators and the proxima l point algorithm,

    R. T. Rockafellar, “Monotone operators and the proxima l point algorithm,” SIAM journal on control and optimization , vol. 14, no. 5, pp. 877–898, 1976

    work page 1976

  38. [38]

    The multi-agent r endezvous problem. part 1: The synchronous case,

    J. Lin, A. S. Morse, and B. D. Anderson, “The multi-agent r endezvous problem. part 1: The synchronous case,” SIAM Journal on Control and Optimization , vol. 46, no. 6, pp. 2096–2119, 2007

    work page 2096

  39. [39]

    Routing o ptimization with vehicle–customer coordination,

    W. Zhang, A. Jacquillat, K. Wang, and S. Wang, “Routing o ptimization with vehicle–customer coordination,” Management Science , vol. 69, no. 11, pp. 6876– 6897, 2023. 22

    work page 2023