Computing Equilibrium beyond Unilateral Deviation

• URL: http://arxiv.org/abs/2604.28186v1
• Date: Thu, 30 Apr 2026 17:59:07 GMT
• Title: Computing Equilibrium beyond Unilateral Deviation
• Abstract summary: We study an alternative solution concept that minimizes coalitional deviation incentives, rather than requiring them to vanish.<n> Specifically, we focus on minimizing the average gain of a deviating coalition, and extend the framework to weighted-average and maximum-within-coalition gains.<n>For the average-gain and maximum-gain objectives, we prove a lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound.
• Score: 27.786964046329455
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Most familiar equilibrium concepts, such as Nash and correlated equilibrium, guarantee only that no single player can improve their utility by deviating unilaterally. They offer no guarantees against profitable coordinated deviations by coalitions. Although the literature proposes solution concepts that provide stability against multilateral deviations (\emph{e.g.}, strong Nash and coalition-proof equilibrium), these generally fail to exist. In this paper, we study an alternative solution concept that minimizes coalitional deviation incentives, rather than requiring them to vanish, and is therefore guaranteed to exist. Specifically, we focus on minimizing the average gain of a deviating coalition, and extend the framework to weighted-average and maximum-within-coalition gains. In contrast, the minimum-gain analogue is shown to be computationally intractable. For the average-gain and maximum-gain objectives, we prove a lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound. Finally, we use our framework to solve the \emph{Exploitability Welfare Frontier} (EWF), the maximum attainable social welfare subject to a given exploitability (the maximum gain over all unilateral deviations).

Related papers

• Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach [0.23689955632456086]
  Clustered learning benefits from organizing heterogeneous participants into coalitions that train coalition-specific models.<n>We develop a transferable-surplus model separating learning benefit, system cost, participant cost, and monetary transfers.
  arXiv  Detail & Related papers  (2026-07-29T11:29:45Z)
• Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria [3.061219970798378]
  Real-world multi-agent systems are often modeled as general-sum games where individual incentives conflict with collective welfare.<n>Standard deep multi-agent reinforcement learning (MARL) methods struggle with this problem.<n>We propose $$-Actor-Critic ($$-AC), a framework that leverages swap regret minimization to steer learning toward high-welfare correlated equilibria.
  arXiv  Detail & Related papers  (2026-06-09T16:40:26Z)
• Maximin Relative Improvement: Fair Learning as a Bargaining Problem [24.940259610524482]
  We propose a fundamentally different approach to interpreting group fairness as a bargaining problem among subpopulations.<n>This game-theoretic perspective reveals that existing robust optimization methods such as minimizing worst-group loss or regret correspond to classical bargaining solutions.<n>We propose relative improvement, the ratio of actual risk reduction to potential reduction from a baseline predictor, which recovers the Kalai-Smorodinsky solution.
  arXiv  Detail & Related papers  (2026-02-04T02:44:56Z)
• Attack-Resistant Uniform Fairness for Linear and Smooth Contextual Bandits [21.090584232258056]
  We develop novel algorithms that achieve minimax-optimal regret for both linear and smooth reward functions.<n>We show that an adversary with a minimal $tildeO(1)$ budget can not only degrade overall performance as in traditional attacks, but also selectively induce insidious fairness-specific failures.
  arXiv  Detail & Related papers  (2026-02-04T01:37:47Z)
• Toward a Sustainable Federated Learning Ecosystem: A Practical Least Core Mechanism for Payoff Allocation [71.86087908416255]
  We introduce a payoff allocation framework based on the least core (LC) concept.<n>Unlike traditional methods, the LC prioritizes the cohesion of the federation by minimizing the maximum dissatisfaction.<n>Case studies in federated intrusion detection demonstrate that our mechanism correctly identifies pivotal contributors and strategic alliances.
  arXiv  Detail & Related papers  (2026-02-03T11:10:50Z)
• From Debate to Equilibrium: Belief-Driven Multi-Agent LLM Reasoning via Bayesian Nash Equilibrium [52.28048367430481]
  Multi-agent frameworks can boost the reasoning power of large language models (LLMs), but they typically incur heavy computational costs and lack convergence guarantees.<n>We recast multi-LLM coordination as an incomplete-information game and seek a Bayesian Nash equilibrium (BNE)<n>We introduce Efficient Coordination via Nash Equilibrium (ECON), a hierarchical reinforcement-learning paradigm that marries distributed reasoning with centralized final output.
  arXiv  Detail & Related papers  (2025-06-09T23:49:14Z)
• Vairiational Stochastic Games [1.6703448188585752]
  We propose a novel variational inference framework tailored to decentralized multi-agent systems.<n>Our framework addresses the challenges posed by non-stationarity and unaligned agent objectives.<n>We demonstrate theoretical convergence guarantees for the proposed decentralized algorithms.
  arXiv  Detail & Related papers  (2025-03-08T03:21:23Z)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  We prove lower bounds for computing a near-optimal $T$-sparse CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in time.
  arXiv  Detail & Related papers  (2024-11-04T00:34:56Z)
• An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems [4.243592852049963]
  We introduce a new online feasible point method for generalized Nash equilibrium games. Under the assumption that limited communication between the agents is allowed, this method guarantees feasibility. We identify the class of benign generalized Nash equilibrium problems, for which the convergence of our method to the equilibrium is guaranteed.
  arXiv  Detail & Related papers  (2024-10-03T11:27:55Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  We study how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating. The lower level requires solving the Nash equilibrium under a given reward function, which makes the overall problem challenging to optimize in an end-to-end way. We propose a backpropagation scheme that differentiates through the Nash equilibrium, which provides the gradient feedback for the upper level.
  arXiv  Detail & Related papers  (2023-02-20T16:05:04Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Linear Regression Games: Convergence Guarantees to Approximate Out-of-Distribution Solutions [35.313551211453266]
  In this work, we extend the framework in Ahuja et al. for linear regressions by projecting the ensemble-game on an $ell_infty$ ball. We show that such projections help achieve non-trivial OOD guarantees despite not achieving perfect invariance.
  arXiv  Detail & Related papers  (2020-10-28T21:10:24Z)

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.