Learning Equilibria in Coordination Games via Minorization-Maximization This work was supported by Défi Inria-EDF
Ashok Krishnan K.S, Hélène Le Cadre, Ana Bušić · 2026
Read Learning Equilibria in Coordination Games via Minorization-Maximization This work was supported by Défi Inria-EDF by Ashok Krishnan K.S, Hélène Le Cadre, Ana Bušić (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13644.txt.
Introduction
Ashok Krishnan, Helene Le Cadre and Ana Busic study games where utility sums a social term and an individual cost or reward term. Agents misread their individual cost or reward. The multi-outcome game is smoothed, and its strictly concave potential function picks a unique equilibrium. That picked equilibrium is an epsilon-equilibrium of the first game, with epsilon set by the smoothing function. A minorisation-maximisation learning scheme moves to the potential-best point faster than gradient and best-reply methods.
Catalog record
| CREATOR | Ashok Krishnan K.S, Hélène Le Cadre, Ana Bušić |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45889 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13644
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Equilibria in Coordination Games via Minorization-Maximization This work was supported by Défi Inria-EDF Ashok Krishnan K.S, Hélène Le Cadre, Ana Bušić 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. I Introduction In many games and optimization problems, an agent’s payoff combines an individual cost with a reward proportional to a collective social utility. This captures scenarios where agents independently pursue a shared objective, making success dependent on coordination. Such interactions naturally form coordination games [ 6 ] and, in some cases, aggregative games, where each agent responds to an aggregate of others’ actions [ 16 ] . Under mild conditions, they admit a (weighted) potential game structure, enabling equilibrium analysis via a global function [ 38 ] . 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 [ 19 ] , and the multi agent exploration problem [ 12 ] , where multiple agents try to reach a common target or destination, while moving in a coordinated but distributed fashion. A particular example of multi agent exploration is the rendezvous problem [ 7 ] , in which multiple robots, initially distributed across an unknown or unexplored environment, seek to reach a common destination while incurring individual energy costs. In all these cases, performance ultimately depends on the agents’ ability to coordinate through the effects of their collective actions. While not all potential games correspond to meaningful social utilities, the closely related class of social purpose games [ 10 ] explicitly decomposes utilities into a collective-benefit term and an individual cost, capturing a broad range of problems involving common or public resources. From another perspective, the presence of a collective objective connects this framework to cooperative game theory [ 25 ] , where one studies how groups of agents generate and share value. In particular, when the underlying social utility exhibits supermodularity, one can leverage strong structural properties—such as increasing returns—to obtain existence, monotonicity, and robustness guarantees for equilibria (see, e.g., [ 3 ] ). Finally, in the large-population regime, when the impact of any single agent on the aggregate becomes negligible, the model relates to mean-field games [ 23 ] . This approximation is attractive for analyzing asymptotic system behavior, but comes at a cost: by averaging interactions, it tends to wash out individual heterogeneity and may fail to capture nuanced agent preferences or cost perceptions. In this paper, we consider such an additive utility model. However, we assume that agents are not fully rational in their perception of individual costs. When agents are human, this deviation from rationality may arise from behavioral biases [ 15 ] . For non-human agents, bounded rationality may instead stem from limitations in information, perspective, or computational capacity, which can hinder effective coordination. Several modeling paradigms have been proposed to capture such deviations from perfect rationality. Quantal best-response [ 26 ] and noisy discrete choice models [ 2 ] introduce stochasticity in decision-making, typically assuming that agents respond smoothly to payoff differences (e.g., via logit dynamics). These models are analytically tractable and well-suited for equilibrium learning, but they primarily capture random errors rather than systematic biases in perception. Distributionally robust game [ 1 ] formulations, on the other hand, account for ambiguity in agents’ beliefs by considering worst-case distributions over uncertainties. While they provide strong robustness guarantees, they tend to reflect ambiguity aversion at the population level rather than individual-level cognitive distortions, and may lead to overly conservative behaviors. In contrast, we adopt prospect theory (PT) [ 17 ] , which explicitly models systematic deviations from expected utility maximization by incorporating reference dependence, loss aversion, and probability distortion. Prospect theory addresses well-documented shortcomings of classical von Neumann–Morgenstern expected utility theory (EUT) [ 37 ] , whose assumption of fully rational agents is often contradicted by experimental evidence [ 15 ] . A variety of prospect-theoretic models exist [ 35 ] , differing in how they model value functions and probability weighting, and often tailored to specific applications. Many games, including those with prospect-theoretic utilities [ 20 ] , admit multiple equilibria, complicating both analysis and learning. To address this, we introduce a regularized (perturbed) game, adding a small term to the utility or potential function. The rgularized potential function has a unique maximum, which selects a unique equilibrium while preserving the structure of the original game. This is analogous to regularization in machine learning to ensure unique maximizers. The regularizer thus acts as a weak equilibrium selection mechanism, linking the perturbed equilibrium to the original set of equilibria. Learning this single equilibrium is the next question of interest. The kind of algorithm that can be used for learning is intricately tied to the structure of the game. Monotone games and potential games show convergence under gradient type learning dynamics [ 33 ] . In the case of aggregative games, best response learning converges under strong assumptions on the structure of the interaction between the users’ strategies and utilities [ 21 ] . However, the performance of many learning algorithms worsens when the game is non smooth, i.e., the utilities are no longer continuously differentiable. To address this challenge, we propose a minorization–maximization (MM) [ 14 ] 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 required aggregate information is communicated through a coordinating agent, enabling scalable learning despite the presence of non-standard utility functions. 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. Utilities reflecting PT preferences encode sensitive information (e.g., risk attitudes, reference points). Our framework requires only aggregate information, protecting individual preferences. The surrogate optimization in MM further supports privacy-preserving modifications, such as adding noise or using secure aggregation, without compromising convergence to the perturbed equilibrium. 1 Literature Review Potential games [ 38 ] are a well studied class of games with enough structure to allow convergence under different types of learning. Results for existence of equilibria and convergence of leaning schemes for finite games and games with differentiable utilities are found in [ 29 ] . Convergence results for best and better response dynamics in near potential games, for games with finite