Last-iterate Convergence for Symmetric, General-sum, $2 \times 2$ Games Under The Exponential Weights Dynamic

• URL: http://arxiv.org/abs/2502.08063v2
• Date: Wed, 08 Oct 2025 16:32:58 GMT
• Title: Last-iterate Convergence for Symmetric, General-sum, $2 \times 2$ Games Under The Exponential Weights Dynamic
• Authors: Guanghui Wang, Krishna Acharya, Lokranjan Lakshmikanthan, Juba Ziani, Vidya Muthukumar,
• Abstract summary: We conduct a comprehensive analysis of discrete-time exponential-weights with a constant step size on all emphgeneral-sum and symmetric $2 times 2$ normal-form games.<n>We show through a first-principles analysis that the exponential weights dynamic converges in the last iterate for such games.<n>We illustrate our theory with extensive simulations and applications to the aforementioned game-theoretic interactions.
• Score: 15.036423818666774
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We conduct a comprehensive analysis of the discrete-time exponential-weights dynamic with a constant step size on all \emph{general-sum and symmetric} $2 \times 2$ normal-form games, i.e. games with $2$ pure strategies per player, and where the ensuing payoff tuple is of the form $(A,A^\top)$ (where $A$ is the $2 \times 2$ payoff matrix corresponding to the first player). Such symmetric games commonly arise in real-world interactions between "symmetric" agents who have identically defined utility functions -- such as Bertrand competition, multi-agent performative prediction, and certain congestion games -- and display a rich multiplicity of equilibria despite the seemingly simple setting. Somewhat surprisingly, we show through a first-principles analysis that the exponential weights dynamic, which is popular in online learning, converges in the last iterate for such games regardless of initialization with an appropriately chosen step size. For certain games and/or initializations, we further show that the convergence rate is in fact exponential and holds for any step size. We illustrate our theory with extensive simulations and applications to the aforementioned game-theoretic interactions. In the case of multi-agent performative prediction, we formulate a new "mortgage competition" game between lenders (i.e. banks) who interact with a population of customers, and show that it fits into our framework.

Related papers

• Scale-Invariant Fast Convergence in Games [67.02769061793619]
  We develop learning dynamics that achieve fast convergence while being both scale-free and scale-invariant.<n>For two-player zero-sum games, we obtain scale-free and scale-invariant dynamics with external regret bounded by $tildeO(A_mathrmdiff)$.<n>For multiplayer general-sum games, scale-free learning is enabled also by a technique called doubling clipping, which clips observed gradients based on past observations.
  arXiv  Detail & Related papers  (2026-02-12T11:57:20Z)
• Convergence of Agnostic Federated Averaging [0.0]
  Federated learning (FL) enables decentralized model training without centralizing raw data.<n>Clients participate intermittently in server aggregation and with unknown, possibly biased participation probabilities.
  arXiv  Detail & Related papers  (2025-07-14T14:32:46Z)
• Towards Collaborative Fairness in Federated Learning Under Imbalanced Covariate Shift [38.61713097663966]
  FedAKD (Federated Asynchronous Knowledge Distillation) is a simple yet effective approach that balances accurate prediction with collaborative fairness.<n>We show that FedAKD significantly improves collaborative fairness, enhances predictive accuracy, and fosters client participation even under highly heterogeneous data distributions.
  arXiv  Detail & Related papers  (2025-07-11T14:13:41Z)
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  We show that for a large family of games, there exists a simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of a new uncoupled learning dynamics.<n>Our reduction applies to games where each player's utility is linear in both their own strategy and the joint strategy of all opponents.
  arXiv  Detail & Related papers  (2025-06-04T00:24:14Z)
• Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis [55.13545823385091]
  Federated reinforcement learning (FedRL) enables collaborative learning while preserving data privacy by preventing direct data exchange between agents. In real-world applications, each agent may experience slightly different transition dynamics, leading to inherent model mismatches. We show that even moderate levels of information sharing can significantly mitigate environment-specific errors.
  arXiv  Detail & Related papers  (2025-03-21T18:06:28Z)
• On Feasible Rewards in Multi-Agent Inverse Reinforcement Learning [8.284137254112848]
  Inverse Reinforcement Learning (IRL) seeks to uncover utilities by analyzing expert behavior. This paper offers a rigorous analysis of the feasible reward set in multi-agent IRL. We introduce entropy-regularized games, ensuring equilibrium uniqueness and enhancing interpretability.
  arXiv  Detail & Related papers  (2024-11-22T16:31:36Z)
• Achieving Fairness in Predictive Process Analytics via Adversarial Learning [50.31323204077591]
  This paper addresses the challenge of integrating a debiasing phase into predictive business process analytics. Our framework leverages on adversial debiasing is evaluated on four case studies, showing a significant reduction in the contribution of biased variables to the predicted value.
  arXiv  Detail & Related papers  (2024-10-03T15:56:03Z)
• Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning [19.543995541149897]
  We provide a methodology to extend any finite-player, possibly asymmetric, game to an "induced MFG" First, we prove that $N$-player dynamic games can be symmetrized and smoothly extended to the infinite-player continuum via explicit Kirszbraun extensions. For certain games satisfying monotonicity, we prove a sample complexity of $widetildemathcalO(varepsilon-6)$ for the $N$-agent game to learn an $varepsilon$-Nash up to symmetrization bias.
  arXiv  Detail & Related papers  (2024-08-27T16:11:20Z)
• Editable Fairness: Fine-Grained Bias Mitigation in Language Models [52.66450426729818]
  We propose a novel debiasing approach, Fairness Stamp (FAST), which enables fine-grained calibration of individual social biases. FAST surpasses state-of-the-art baselines with superior debiasing performance. This highlights the potential of fine-grained debiasing strategies to achieve fairness in large language models.
  arXiv  Detail & Related papers  (2024-08-07T17:14:58Z)
• AMA-LSTM: Pioneering Robust and Fair Financial Audio Analysis for Stock Volatility Prediction [25.711345527738068]
  multimodal methods have faced two drawbacks. They often fail to yield reliable models and overfit the data due to their absorption of information from the stock market. Using multimodal models to predict stock volatility suffers from gender bias and lacks an efficient way to eliminate such bias. Our comprehensive experiments on robustness-world financial audio datasets reveal that this method exceeds the performance of current state-of-the-art solution.
  arXiv  Detail & Related papers  (2024-07-03T18:40:53Z)
• MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games [3.179831861897336]
  This paper proposes an online mean-field reinforcement learning algorithm for computing Nash equilibria of sequential games.<n> MFOML is the first fully approximate multi-agent reinforcement learning algorithm for provably solving Nash equilibria.<n>As a byproduct, we also obtain the first tractable globally convergent computational for approximate computing of monotone mean-field games.
  arXiv  Detail & Related papers  (2024-05-01T02:19:31Z)
• Prediction-sharing During Training and Inference [12.461217702808202]
  We study the differences between contracts that share prediction models only, contracts to share inference-time predictions only, and contracts to share both. Our analysis proceeds on three levels. First, we develop a general Bayesian framework that facilitates our study. In the third level of our analysis we demonstrate the applicability of our concepts in a synthetic simulation using real loan data.
  arXiv  Detail & Related papers  (2024-03-26T09:18:50Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Improved Bayes Risk Can Yield Reduced Social Welfare Under Competition [99.7047087527422]
  In this work, we demonstrate that competition can fundamentally alter the behavior of machine learning scaling trends. We find many settings where improving data representation quality decreases the overall predictive accuracy across users. At a conceptual level, our work suggests that favorable scaling trends for individual model-providers need not translate to downstream improvements in social welfare.
  arXiv  Detail & Related papers  (2023-06-26T13:06:34Z)
• Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games [19.723551683930776]
  We study the sample complexity of identifying an approximate equilibrium for two-player zero-sum $ntimes 2$ matrix games. We derive instance-dependent bounds that define an ordering over game matrices. We prove a converse statement: there exist player strategies that achieve this lower bound.
  arXiv  Detail & Related papers  (2023-03-19T04:51:28Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
  arXiv  Detail & Related papers  (2022-10-30T22:58:22Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• Evolutionary Game-Theoretical Analysis for General Multiplayer Asymmetric Games [22.753799819424785]
  We fill the gap between payoff table and dynamic analysis without any inaccuracy. We compare our method with the state-of-the-art in some classic games.
  arXiv  Detail & Related papers  (2022-06-22T14:06:23Z)
• Competition over data: how does data purchase affect users? [15.644822986029377]
  We study what happens when the competing predictors can acquire additional labeled data to improve their prediction quality. We show that this phenomenon naturally arises due to a trade-off whereby competition pushes each predictor to specialize in a subset of the population.
  arXiv  Detail & Related papers  (2022-01-26T06:44:55Z)
• Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos [42.40985526691935]
  We introduce a natural multi-agent version of this framework, where multiple decision makers try to predict the same outcome. We showcase that such competition can result in interesting phenomena by proving the possibility of phase transitions from stability to instability and eventually chaos.
  arXiv  Detail & Related papers  (2022-01-25T17:26:12Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Alternative Microfoundations for Strategic Classification [33.67797984699066]
  We show that rational agents with perfect information produce discontinuities in the aggregate response to a decision rule. optimal decision rules under standard microfoundations maximize a measure of negative externality known as social burden. Our model retains analytical tractability, leads to more robust insights about stable points, and imposes a lower social burden at optimality.
  arXiv  Detail & Related papers  (2021-06-24T00:30:58Z)
• Test-time Collective Prediction [73.74982509510961]
  Multiple parties in machine learning want to jointly make predictions on future test points. Agents wish to benefit from the collective expertise of the full set of agents, but may not be willing to release their data or model parameters. We explore a decentralized mechanism to make collective predictions at test time, leveraging each agent's pre-trained model.
  arXiv  Detail & Related papers  (2021-06-22T18:29:58Z)
• Characterizing Fairness Over the Set of Good Models Under Selective Labels [69.64662540443162]
  We develop a framework for characterizing predictive fairness properties over the set of models that deliver similar overall performance. We provide tractable algorithms to compute the range of attainable group-level predictive disparities. We extend our framework to address the empirically relevant challenge of selectively labelled data.
  arXiv  Detail & Related papers  (2021-01-02T02:11:37Z)

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.