Learnable Mixed Nash Equilibria are Collectively Rational

• URL: http://arxiv.org/abs/2510.14907v1
• Date: Thu, 16 Oct 2025 17:25:32 GMT
• Title: Learnable Mixed Nash Equilibria are Collectively Rational
• Authors: Geelon So, Yi-An Ma,
• Abstract summary: We show that uniform stability determines the last-iterate convergence behavior for the family of incremental smoothed best-response dynamics.<n>Unlike dynamics around strict equilibria, which can stabilize to socially-inefficient solutions, individually utility-seeking behaviors near mixed Nash equilibria lead to collective rationality.
• Score: 17.93053401419066
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We extend the study of learning in games to dynamics that exhibit non-asymptotic stability. We do so through the notion of uniform stability, which is concerned with equilibria of individually utility-seeking dynamics. Perhaps surprisingly, it turns out to be closely connected to economic properties of collective rationality. Under mild non-degeneracy conditions and up to strategic equivalence, if a mixed equilibrium is not uniformly stable, then it is not weakly Pareto optimal: there is a way for all players to improve by jointly deviating from the equilibrium. On the other hand, if it is locally uniformly stable, then the equilibrium must be weakly Pareto optimal. Moreover, we show that uniform stability determines the last-iterate convergence behavior for the family of incremental smoothed best-response dynamics, used to model individual and corporate behaviors in the markets. Unlike dynamics around strict equilibria, which can stabilize to socially-inefficient solutions, individually utility-seeking behaviors near mixed Nash equilibria lead to collective rationality.

Related papers

• Stability and Accuracy Trade-offs in Statistical Estimation [7.213400161126317]
  We develop optimal stable estimators for four canonical estimation problems.<n>We formalize the intuition that average-case stability imposes a qualitatively weaker restriction than worst-case stability.
  arXiv  Detail & Related papers  (2026-01-16T18:48:03Z)
• Robust equilibria in continuous games: From strategic to dynamic robustness [25.372363445606265]
  We examine the robustness of Nash equilibria in continuous games under both strategic and dynamic uncertainty.<n>Despite their very distinct origins, we establish a structural correspondence between these two notions of robustness.<n>We show that entropically regularized learning converges at a geometric rate in games with affinely constrained action spaces.
  arXiv  Detail & Related papers  (2025-12-09T00:30:23Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  We study tractable $Phi$-equilibria in non-concave games.<n>We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• The Bayesian Stability Zoo [18.074002943658055]
  We show that many definitions of stability found in the learning theory literature are equivalent to one another. Within each family, we establish equivalences between various definitions, encompassing approximate differential privacy, pure differential privacy, replicability, global stability, perfect generalization, TV stability, mutual information stability, KL-divergence stability, and R'enyi-divergence stability. This work is a step towards a more systematic taxonomy of stability notions in learning theory, which can promote clarity and an improved understanding of an array of stability concepts that have emerged in recent years.
  arXiv  Detail & Related papers  (2023-10-27T18:59:31Z)
• Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy [8.430481660019451]
  We present an efficient algorithm for minimizing untruthful swap regret with a sublinear upper bound.<n>We extend existing lower bounds on the price of anarchy based on the smoothness arguments from Bayes--Nash equilibria to equilibria.
  arXiv  Detail & Related papers  (2023-04-11T06:22:51Z)
• Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution Concept over Nash Equilibria [61.093297204685264]
  An effective approach in multiagent reinforcement learning is to consider the learning process of agents and influence their future policies. This new solution concept is general such that standard solution concepts, such as a Nash equilibrium, are special cases of active equilibria. We analyze active equilibria from a game-theoretic perspective by closely studying examples where Nash equilibria are known.
  arXiv  Detail & Related papers  (2022-10-28T14:45:39Z)
• How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games [64.71476526716668]
  We study the (in)efficiency of any equilibrium players might agree to play. We obtain guarantees that refine existing bounds on the Price of Anarchy. Although the obtained guarantees concern open-loop trajectories, we observe efficient equilibria even when agents employ closed-loop policies.
  arXiv  Detail & Related papers  (2022-10-24T09:32:40Z)
• Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation [93.52573037053449]
  H-MARL (Hallucinated Multi-Agent Reinforcement Learning) learns successful equilibrium policies after a few interactions with the environment. We demonstrate our approach experimentally on an autonomous driving simulation benchmark.
  arXiv  Detail & Related papers  (2022-03-14T17:24:03Z)
• On the Nash equilibrium of moment-matching GANs for stationary Gaussian processes [2.25477613430341]
  We show that the existence of consistent Nash equilibrium depends crucially on the choice of the discriminator family. We further study the local stability and global convergence of gradient descent-ascent methods towards consistent equilibrium.
  arXiv  Detail & Related papers  (2022-03-14T14:30:23Z)
• Simultaneous Transport Evolution for Minimax Equilibria on Measures [48.82838283786807]
  Min-max optimization problems arise in several key machine learning setups, including adversarial learning and generative modeling. In this work we focus instead in finding mixed equilibria, and consider the associated lifted problem in the space of probability measures. By adding entropic regularization, our main result establishes global convergence towards the global equilibrium.
  arXiv  Detail & Related papers  (2022-02-14T02:23:16Z)
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information [32.384868685390906]
  We examine the Nash equilibrium convergence properties of no-regret learning in general N-player games. We establish a comprehensive equivalence between the stability of a Nash equilibrium and its support. It provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games.
  arXiv  Detail & Related papers  (2021-01-12T18:55:11Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.