Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy

• URL: http://arxiv.org/abs/2304.05005v2
• Date: Sun, 29 Jun 2025 13:53:00 GMT
• Title: Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
• Authors: Kaito Fujii,
• Abstract summary: 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.
• Score: 8.430481660019451
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper investigates equilibrium computation and the price of anarchy for Bayesian games, which are the fundamental models of games with incomplete information. In normal-form games with complete information, it is known that efficiently computable no-regret dynamics converge to correlated equilibria, and the price of anarchy for correlated equilibria can be bounded for a broad class of games called smooth games. However, in Bayesian games, as surveyed by Forges (1993), several non-equivalent extensions of correlated equilibria exist, and it remains unclear whether they can be efficiently computed or whether their price of anarchy can be bounded. In this paper, we identify a natural extension of correlated equilibria that can be computed efficiently and is guaranteed to have bounds on the price of anarchy in various games. First, we propose a variant of regret called untruthful swap regret. If each player minimizes it in repeated play of Bayesian games, the empirical distribution of these dynamics is guaranteed to converge to communication equilibria, which is one of the extensions of correlated equilibria proposed by Myerson (1982). We present an efficient algorithm for minimizing untruthful swap regret with a sublinear upper bound, which we prove to be tight in terms of the number of types. As a result, by simulating the dynamics with our algorithm, we can approximately compute a communication equilibrium in polynomial time. Furthermore, we extend existing lower bounds on the price of anarchy based on the smoothness arguments from Bayes--Nash equilibria to equilibria obtained by the proposed dynamics.

Related papers

• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  We provide evidence that existing learning algorithms, such as multiplicative weights update, are close to optimal. Our results are obtained in the algorithmic framework put forward by Kothari and Mehta.
  arXiv  Detail & Related papers  (2024-11-04T00:39:52Z)
• 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)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  Non-concave games introduce significant game-theoretic and optimization challenges. We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria. We also show that Online Gradient Descent can efficiently approximate $Phi$-equilibria in non-trivial regimes.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and Inverse Learning [37.176741793213694]
  We formulate a class of Markov games, termed affine Markov games, where an affine reward function couples the players' actions. We introduce a novel solution concept, the soft-Bellman equilibrium, where each player is boundedly rational and chooses a soft-Bellman policy. We then solve the inverse game problem of inferring the players' reward parameters from observed state-action trajectories via a projected-gradient algorithm.
  arXiv  Detail & Related papers  (2023-03-31T22:50:47Z)
• 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)
• Observable Perfect Equilibrium [0.4895118383237099]
  We define a new equilibrium refinement concept for extensive-form games called observable perfect equilibrium. We prove that observable perfect equilibrium is always guaranteed to exist. We expect observable perfect equilibrium to be a useful equilibrium refinement concept for modeling many important imperfect-information games of interest in artificial intelligence.
  arXiv  Detail & Related papers  (2022-10-29T06:07:29Z)
• 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)
• 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)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)
• Game-theoretic Models of Moral and Other-Regarding Agents [0.0]
  We highlight a number of problems with such equilibria, including computational intractability, a high price of miscoordination, and expensive/problematic extension to general normal form games. We propose some general, intuitive, computationally tractable, other-regarding equilibria related to Kantian equilibria, as well as a class of courses of action that interpolates between purely self-regarding and Kantian behavior.
  arXiv  Detail & Related papers  (2020-12-17T17:16:50Z)
• Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond [107.14897720357631]
  We show that an optimal correlated equilibrium can be computed in time in two-player games with public chance moves. This results in the biggest positive complexity result surrounding extensive-form correlation in more than a decade.
  arXiv  Detail & Related papers  (2020-09-09T14:51:58Z)

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.