Optimally Installing Strict Equilibria

• URL: http://arxiv.org/abs/2503.03676v1
• Date: Wed, 05 Mar 2025 17:11:02 GMT
• Title: Optimally Installing Strict Equilibria
• Authors: Jeremy McMahan, Young Wu, Yudong Chen, Xiaojin Zhu, Qiaomin Xie,
• Abstract summary: We develop a reward design framework for installing a desired behavior as a strict equilibrium across standard solution concepts.<n>We extend our framework to capture the Markov-perfect equivalents of each solution concept.
• Score: 14.491458698581038
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this work, we develop a reward design framework for installing a desired behavior as a strict equilibrium across standard solution concepts: dominant strategy equilibrium, Nash equilibrium, correlated equilibrium, and coarse correlated equilibrium. We also extend our framework to capture the Markov-perfect equivalents of each solution concept. Central to our framework is a comprehensive mathematical characterization of strictly installable, based on the desired solution concept and the behavior's structure. These characterizations lead to efficient iterative algorithms, which we generalize to handle optimization objectives through linear programming. Finally, we explore how our results generalize to bounded rational agents.

Related papers

• Vairiational Stochastic Games [1.6703448188585752]
  We propose a novel variational inference framework tailored to decentralized multi-agent systems. Our framework addresses the challenges posed by non-stationarity and unaligned agent objectives. We demonstrate theoretical convergence guarantees for the proposed decentralized algorithms.
  arXiv  Detail & Related papers  (2025-03-08T03:21:23Z)
• Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games [44.95137108337898]
  We provide an uncoupled policy optimization algorithm that attains a near-optimal $tildeO(T-1)$ convergence rate for computing a correlated equilibrium. Our algorithm is constructed by combining two main elements (i.e. smooth value updates and (ii. the optimistic-follow-the-regularized-leader algorithm with the log barrier regularizer)
  arXiv  Detail & Related papers  (2024-01-26T23:13:47Z)
• Robust Adversarial Reinforcement Learning via Bounded Rationality Curricula [23.80052541774509]
  Adversarial Reinforcement Learning trains a protagonist against destabilizing forces exercised by an adversary in a competitive zero-sum Markov game. Finding Nash equilibria requires facing complex saddle point optimization problems, which can be prohibitive to solve. We propose a novel approach for adversarial RL based on entropy regularization to ease the complexity of the saddle point optimization problem.
  arXiv  Detail & Related papers  (2023-11-03T00:00:32Z)
• Are Equivariant Equilibrium Approximators Beneficial? [3.947165805405381]
  We theoretically characterize benefits and limitations of equivariant equilibrium approximators. For the benefits, we show that they enjoy better generalizability than general ones and can achieve better approximations when the payoff distribution is permutation-invariant. For the limitations, we discuss their drawbacks in terms of equilibrium selection and social welfare.
  arXiv  Detail & Related papers  (2023-01-27T01:11:41Z)
• 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)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets [151.03738099494765]
  We study a Markov matching market involving a planner and a set of strategic agents on the two sides of the market. We propose a reinforcement learning framework that integrates optimistic value iteration with maximum weight matching. We prove that the algorithm achieves sublinear regret.
  arXiv  Detail & Related papers  (2022-03-07T19:51:25Z)
• Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
  Learning in games is arguably the most standard and fundamental setting in multi-agent reinforcement learning (MARL) We establish the finite-sample complexity of fully decentralized Q-learning algorithms in a significant class of general approximation games (SGs) We focus on the practical while challenging setting of fully decentralized MARL, where neither the rewards nor the actions of other agents can be observed by each agent.
  arXiv  Detail & Related papers  (2021-12-15T03:33:39Z)
• Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds Global Optima [114.31577038081026]
  We propose an efficient method that tackles the designer's and agents' problems simultaneously in a single loop. Although the designer does not solve the equilibrium problem repeatedly, it can anticipate the overall influence of the incentives on the agents. We prove that the algorithm converges to the global optima at a sublinear rate for a broad class of games.
  arXiv  Detail & Related papers  (2021-10-04T06:53:59Z)
• Optimization Induced Equilibrium Networks [76.05825996887573]
  Implicit equilibrium models, i.e., deep neural networks (DNNs) defined by implicit equations, have been becoming more and more attractive recently. We show that deep OptEq outperforms previous implicit models even with fewer parameters.
  arXiv  Detail & Related papers  (2021-05-27T15:17:41Z)
• Decentralized Reinforcement Learning: Global Decision-Making via Local Economic Transactions [80.49176924360499]
  We establish a framework for directing a society of simple, specialized, self-interested agents to solve sequential decision problems. We derive a class of decentralized reinforcement learning algorithms. We demonstrate the potential advantages of a society's inherent modular structure for more efficient transfer learning.
  arXiv  Detail & Related papers  (2020-07-05T16:41:09Z)

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.