Learning Equilibria in Coordination Games via Minorization-Maximization

arXiv:2605.13644 · cs.GT · Submitted 2026-05-13 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Learning Equilibria in Coordination Games via Minorization-Maximization".

Jane: Here's the gist of the paper. Learning Equilibria in Coordination Games via Minorization-Maximization considers games where agent utilities combine a term proportional to social utility and an individual cost or reward, using prospect theory to model irrationality and proposing a minorization-maximization learning scheme that converges faster than gradient or best response methods.

Tom: Game Model Structure The paper introduces a game model where the utility for user i is given by Jλi(xi, x−i) = aiJλ(x) + Eq˜

Vi ◦ Ri(xi, ξ): .

Jane: This utility function incorporates a regularized collective usage benefit Jλ(x) = J (x) − λH(x), where H: R N → R+ is a non negative regularizing function, and λ ≥ 0.

Tom: The individual random reward Ri(xi, ξ) is viewed subjectively through the PT value function Vi.

Paper summary: Tom: So we're looking at this paper titled "Learning Equilibria in Coordination Games via Minorization-Maximization". Basically, they're tackling games where agents care about both what they get individually and how well the group does together.

Jane: That sounds complicated. What is the main idea here? What are they trying to figure out?

Tom: They’re looking at these utility functions that have a piece proportional to social utility, plus an individual cost or reward, and agents are irrational about that cost or reward part. The paper claims they use prospect theory to model this irrationality.

Lu: And the core of their approach is proposing this minorization-maximization learning scheme which they say converges faster than methods like gradient ascent or best response methods do.

Meng: Faster how much faster are we talking? We’re deploying models here, and convergence speed at scale matters a lot for us.

Lalam: The paper suggests that this specific learning scheme converges to the potential-optimal equilibrium, which is important because that’s usually what you want in these coordination problems.

Tom: Right, so the big claim is that this minorization-maximization scheme learns the potential-optimal equilibrium and does it better than standard gradient or best response methods.

Jane: But how do they set up this game structure? What exactly are these utilities they are using?

Tom: The utility for user i is defined as a term proportional to social utility plus an individual cost or reward, which they call the regularized potential function. This function includes a regularization term that has a unique maximum.

Lu: They introduce this regularization because it helps select a unique equilibrium, and they show that any element in this perturbed game is an epsilon-Nash equilibrium for the original game.

Meng: So it’s like they tweak the problem slightly to make sure there's only one answer, and then they use a specific learning algorithm to find that single answer.

Lalam: That unique solution from the regularized version is shown to be an epsilon-equilibrium of the original game, where that epsilon is determined by how much regularization you have.

Tom: The paper points out that this regularization and the potential formulation can actually be seen as a way to select an equilibrium, so they are linking those two ideas.

Jane: This sounds like a clever way to handle games where things aren't perfectly smooth or differentiable, which is where many real-world coordination problems live.

Lu: That’s exactly what they address because when the utilities aren't continuously differentiable, gradient methods and best response methods can struggle to find the right spot.

Meng: But what about the non-smooth games? That’s where my production models often break down if you don't handle it right.

Lalam: The paper specifically tackles non-smooth games by proposing iterative minorization–maximization, or IMM, which converges to an element in that set and ensures each step is an epsilon of the original game equilibrium.

Tom: So for non-smooth settings, the iterative minorization–maximization approach guarantees convergence to a potential-optimal Nash equilibrium, and it keeps improving its accuracy with each iteration.

Jane: It sounds like they are moving away from just getting *an* equilibrium towards getting the *best* one in these trickier scenarios.

Lu: They show numerically that this iterative minorization–maximization converges to the potential-optimal Nash equilibrium faster than iterative best response or stochastic gradient ascent in non-smooth settings.

Meng: So, if I were deploying a model on real traffic data where the utility function is messy, this suggests IMM could be a better choice for learning than standard iterative methods.

Tom: Exactly, and they use prospect theory to model that agent irrationality—things like loss aversion and reference dependence—to encode risk attitudes into those utilities.

Jane: That’s interesting because it means the learning scheme only needs aggregate information from agents, not their deep individual psychological models.

Lalam: The utility form in equation four is basically a relaxed version of the equilibrium selection problem, which makes it applicable to things like energy markets and multi-agent coordination.

Tom: So the paper concludes that while gradient-based and best response methods work in smooth games, they can fail to find potential-maximizing equilibria when the game is non-smooth.

Jane: The implication for us is that if we are dealing with messy data or complex interactions, we need a method like this minorization–maximization learning scheme instead of just standard optimization tools.

Lu: They emphasize the importance of regularization and optimization-based learning for robust equilibrium selection when you’re not sure the game structure is perfectly smooth.

Meng: I'm concerned about scalability if this iterative process takes too many steps, but if it converges faster than other methods, that might be worth the computational cost.

Lalam: The paper suggests future work could look at extensions to non-convex games and even more general behavioral models to see how far this approach can go.

Tom: So, the main point is that for complex coordination games with irrational agents, this minorization–maximization learning scheme offers a way to find the best possible equilibrium efficiently.

Jane: It’s about making sure the learning process actually lands on the right kind of solution when things get complicated.

Conclusion: Tom: It’s about finding the stable spots in coordination games when agents are irrational, using this minorization maximization thing to learn them faster than gradient methods.

Jane: What does that actually mean for us? Like, if we're building things where people need to coordinate but they aren't perfectly rational, this could be a way to find the best outcome.

Lu: The authors are showing how adding a little bit of regularization helps pick one specific equilibrium out of all the possibilities in these games.

Meng: So it’s not just finding *any* stable point, it’s finding the one that's actually optimal for the whole system, which is what matters when you're trying to ship something.

Lalam: And they prove that their method converges to this potential-optimal equilibrium even when the game isn't perfectly smooth, which is a big deal for real-world messy data.

Tom: It really boils down to moving past methods that just get stuck in local optima and finding the true best outcome using this specific learning scheme.

Jane: So, if you’re thinking about complex systems—like energy markets or traffic control—this paper suggests we should look at these optimization-based learning approaches instead of just standard calculus.

Lu: Yeah, the authors highlight that prospect theory lets us encode weird stuff like loss aversion directly into the utility function, which makes the learning scheme work even if the underlying math is a bit rough.

Meng: I’m interested in how much faster this convergence is compared to what we're currently running on our production systems, because speed matters when you’re dealing with live data.

Lalam: The main thing here is that we can now use these learning tools to find better coordination outcomes without needing perfect information about every single agent’s private psychological state.

Tom: It sets a new direction for how we approach training agents in complex environments, moving toward methods that prioritize finding the best possible system behavior.

Jane: And next, Tom and I want to look at exactly who wrote this and what it means for the next set of papers they plan to publish on this topic.

Ashok Krishnan K.S.†, Hélène Le Cadre↵, Ana BuƑ쎺SIC↵

inria · DI ENS

cs.GT

Submitted: 2026-05-13

Updated: 2026-11-09

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 87/100

The gist: Learning Equilibria in Coordination Games via Minorization-Maximization considers games where agent utilities combine a term proportional to social utility and an individual cost or reward…

Key concepts

Utility Function Jλi(xi, x−i)
This function defines an agent's total utility. It combines a term proportional to the social utility (how well everyone does) with an individual cost or reward, incorporating prospect theory to account for how people irrationally value outcomes.
Prospect Theory (PT)
PT is used to model agent irrationality by showing that people make decisions based on perceived gains and losses relative to a reference point. This framework allows the model to incorporate features like loss aversion and probability distortion into the utility calculation.
Minorization-Maximization (MM)
This is a proposed learning scheme designed to find equilibria. It works by adding a small term (regularization) to the utility function, which helps select a unique equilibrium. MM is shown to converge faster than gradient or best response methods, particularly in non-smooth games.
Potential-Optimal Equilibrium
This is the ideal equilibrium state that maximizes the potential function associated with the game. The paper shows that MM converges specifically to this type of equilibrium, which is superior to equilibria found by simpler iterative methods in certain game settings.

Terminology

Summary

Learning Equilibria in Coordination Games via Minorization-Maximization considers games where agent utilities combine a term proportional to social utility and an individual cost or reward, using prospect theory to model irrationality and proposing a minorization-maximization learning scheme that converges faster than gradient or best response methods. p. 0

Where the paper says it

Learning Equilibria in Coordination Games via Minorization-Maximization∗ Ashok Krishnan K. † , Hélène Le Cadre‡ , Ana Bušić§ 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.

Game Model Structure

The paper introduces a game model where the utility for user i is given by Jλi(xi, x−i) = aiJλ(x) + Eq˜[Vi ◦ Ri(xi, ξ)]. This utility function incorporates a regularized collective usage benefit Jλ(x) = J (x) − λH(x), where H: R N → R+ is a non negative regularizing function, and λ ≥ 0. p. 5

Where the paper says it

This form of the utility function includes the following terms: 1. A regularized collective usage benefit J λ (x) = J (x) − λH(x), where J : X → R is a collective utility common to all agents, H : R N → R+ is a non negative regularizing function, and λ ≥ 0.

The individual random reward Ri(xi, ξ) is viewed subjectively through the PT value function Vi. p. 5
Where the paper says it

An individual random reward Ri(xi , ξ) : Xi × Ξ → R. This reward is random due to its dependence on ξ, and is viewed subjectively through the PT value function Vi .

Assumptions are made regarding the continuity of functions and their concavity properties. p. 8
Where the paper says it

The maximizer exists due to continuity of J λ i and compactness of Xi . For games which have continuously differentiable utilities, strong results can be shown regarding the convergence of these approaches.

Equilibrium Selection via Regularization

The authors develop a regularized (perturbed) game by adding a small term to the utility or potential function, which has a unique maximum, thereby selecting a unique equilibrium. The relationship between the equilibria of the regularized and unregularized games is characterized in terms of the regularizing function H. p. 7

Where the paper says it

Characterizing Regularized Equilibria We relate the regularized potential maximizing equilibria of G λ to the equilibria of the unregularized game G 0 , in terms of the regularizing function H. Let x † be the element of Γ 0 that minimizes the regularizer, x † = argx∈Γ0 min H(x).

Lemma 4 shows that any element xλ of Γλ is an ǫ-Nash equilibrium for G0, where ǫ = λa1H(x†). p. 7
Where the paper says it

Let x † be the element of Γ 0 that minimizes the regularizer, x † = argx∈Γ0 min H(x). Then, any element x λ = (x λ i , x λ −i ) of Γ λ is an ǫ-Nash equilibrium for G 0 , where ǫ = λa1H(x † ).

This suggests that regularization and potential formulation can be viewed together as an equilibrium selection method. p. 3
Where the paper says it

Using the potential structure of the regularized game, we obtain a unique equilibrium which is also the maximum of the potential function associated with the regularized game. Thus, regularization and potential formulation can be viewed together as an equilibrium selection method.

Learning Dynamics Comparison

The paper compares gradient ascent/play (GA), iterative best response (IBR), and minorization-maximization (MM) based learning schemes for computing equilibria. For smooth games, both GA and IBR converge to an ǫ−Nash equilibrium of the unregularized game G0. p. 8

Where the paper says it

For games which have continuously differentiable utilities, strong results can be shown regarding the convergence of these approaches. Convergence of Learning Dynamics in Smooth Games If G λ is smooth, both gradient play and iterative best response can be shown to be converge to an ǫ−Nash equilibrium of the unregularized game G 0 .

However, MM is proposed as a scheme that converges to the potential-optimal equilibrium and improves convergence speed while working well for non smooth utilities. p. 2
Where the paper says it

We see that MM improves convergence speed while leveraging the game’s potential structure. Since it can be used to learn equilibria in games with smooth and non-smooth utilities, we see that it presents itself as an algorithm which can be used across a variety of applications ranging from electricity markets to multi agent coordination.

Non-Smooth Game Performance

In non smooth games, iterative best response leads strategies to fixed points that are Nash equilibria of Gλ, but not optimizers of the potential function. The iterative MM (IMM) approach converges to an element of Γ0 and ensures each iterate is an ǫ(n)−equilibrium of G0, with ǫ(n) → 0 as n → ∞. p. 7

Where the paper says it

Let x † be the element of Γ 0 that minimizes the regularizer, x † = argx∈Γ0 min H(x). Then, any element x λ = (x λ i , x λ −i ) of Γ λ is an ǫ-Nash equilibrium for G 0 , where ǫ = λa1H(x † ).

Numerical examples demonstrate that IMM converges to the potential-optimal Nash equilibrium faster than IBR or sGA in non smooth settings. p. 3
Where the paper says it

This is shown to converge to the potential-optimal equilibrium, and works well for even non smooth utilities. It is also faster than gradient based learning, and does not suffer from multiple fixed points like best response learning.

Application and Utility Encoding

Prospect theory is used to model agent irrationality by incorporating reference dependence, loss aversion, and probability distortion. This framework allows the authors to encode sensitive information like risk attitudes into utilities while requiring only aggregate information for the learning scheme. p. 2

Where the paper says it

Utilities reflecting PT preferences encode sensitive information (e. , risk attitudes, reference points).

The utility form in (4) is viewed as a relaxed form of the equilibrium selection problem. p. 7
Where the paper says it

Among all elements x of Γ 0 , x † minimizes a lower bound on the difference between Φ 0 (x) and Φ 0 (x λ ). The utility form in (4) therefore can be viewed as a relaxed form of the equilibrium selection problem.

This utility model applies to various scenarios, including energy markets and multi agent coordination. p. 0
Where the paper says it

Under mild conditions, they admit a (weighted) potential game structure, enabling equilibrium analysis via a global function [3]. Examples for scenarios where such problems arise, include energy markets, where electricity consumers utilize a shared resource while collectively aiming to meet a common carbon emission target [4], and the multi agent exploration problem [5], where multiple agents try to reach a common target or destination, while moving in a coordinated but distributed fashion.

Conclusion on Learning Schemes

The study concludes that while gradient-based and best response methods converge in smooth settings, they may fail to reach potential-maximizing equilibria in non-smooth games. The proposed MM scheme guarantees convergence to a potential-optimal equilibrium and demonstrates superior convergence behavior compared to other methods. p. 0

Where the paper says it

A minorizationmaximization 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.

These results emphasize the importance of regularization and optimization-based learning for robust equilibrium selection. p. 2
Where the paper says it

To address this challenge, we propose a minorization–maximization (MM) [21] based learning scheme. The key idea is to replace the original optimization problem with a sequence of surrogate problems whose optima converge to a chosen equilibrium.

The paper suggests future work on extensions to non-convex and more general behavioral models. p. 5
Where the paper says it

The functions J , {Vi ◦ Ri} N i=1 are concave in each of their respective arguments, while H is non negative and strictly convex. 1Most of the results in this work can be extended to the case where ξ has continuous distribution, albeit with more conditions on other variables to ensure integrability.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Minorization-Maximization based learning scheme for equilibrium selection allows AI systems to learn equilibria in games with smooth and non-smooth utilities by replacing original optimization problems with a sequence of surrogate problems whose optima converge to a chosen equilibrium.

  2. The improved system can leverage the potential structure of regularized games to select a unique equilibrium, characterizing how this selected equilibrium relates to the set of equilibria of the unregularized game in terms of the regularizing function H.

  3. The AI system can utilize iterative MM (IMM) dynamics, which converges to a global maximum of Phi 0 over the compact strategy set X, ensuring that all limit points lie in Gamma 0 and providing an epsilon-n equilibrium of G 0 with epsilon n approaching zero as n approaches infinity.

  4. For non-smooth games, the system can employ iterative MM to converge to a Nash equilibrium, overcoming the limitation where best response based approaches might fail to reach potential-maximizing equilibria as demonstrated by convergence in Example 1.

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 ε- equilibrium of the original game, where ε 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 behavior in comparison to gradient and best response methods.

Sources

Related papers