Equilibrium Design for Concurrent Games
- URL: http://arxiv.org/abs/2106.10192v1
- Date: Fri, 18 Jun 2021 15:45:45 GMT
- Title: Equilibrium Design for Concurrent Games
- Authors: Julian Gutierrez, Muhammad Najib, Giuseppe Perelli, Michael Wooldridge
- Abstract summary: In game theory, mechanism design is concerned with the design of incentives so that a desired outcome of the game can be achieved.
We study the design of incentives so that a desirable equilibrium is obtained, for instance, an equilibrium satisfying a given temporal logic property.
As an application, equilibrium design can be used as an alternative solution to the rational synthesis and verification problems for concurrent games.
- Score: 5.9873770241999
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In game theory, mechanism design is concerned with the design of incentives
so that a desired outcome of the game can be achieved. In this paper, we study
the design of incentives so that a desirable equilibrium is obtained, for
instance, an equilibrium satisfying a given temporal logic property -- a
problem that we call equilibrium design. We base our study on a framework where
system specifications are represented as temporal logic formulae, games as
quantitative concurrent game structures, and players' goals as mean-payoff
objectives. In particular, we consider system specifications given by LTL and
GR(1) formulae, and show that implementing a mechanism to ensure that a given
temporal logic property is satisfied on some/every Nash equilibrium of the
game, whenever such a mechanism exists, can be done in PSPACE for LTL
properties and in NP/$\Sigma^{P}_{2}$ for GR(1) specifications. We also study
the complexity of various related decision and optimisation problems, such as
optimality and uniqueness of solutions, and show that the complexities of all
such problems lie within the polynomial hierarchy. As an application,
equilibrium design can be used as an alternative solution to the rational
synthesis and verification problems for concurrent games with mean-payoff
objectives whenever no solution exists, or as a technique to repair, whenever
possible, concurrent games with undesirable rational outcomes (Nash equilibria)
in an optimal way.
Related papers
- Synthesis of Reward Machines for Multi-Agent Equilibrium Design (Full Version) [2.2099217573031678]
We study the problem of equilibrium design using dynamic incentive structures, known as reward machines.
We show how reward machines can be used to represent dynamic incentives that allocate rewards in a manner that optimises the designer's goal.
We present two variants of the problem: strong and weak. We demonstrate that both can be solved in time using a Turing machine equipped with an NP oracle.
arXiv Detail & Related papers (2024-08-19T15:17:58Z) - The Computational Complexity of Single-Player Imperfect-Recall Games [37.550554344575]
We study extensive-form games with imperfect recall, such as the Sleeping Beauty problem or the Absent Driver game.
For such games, two natural equilibrium concepts have been proposed as alternative solution concepts to ex-ante optimality.
arXiv Detail & Related papers (2023-05-28T19:41:25Z) - 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) - Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play.
This work shows that certain regularized equilibria do not possess the aforementioned non-correspondence problem.
Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games.
arXiv Detail & Related papers (2023-01-22T16:54:06Z) - 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) - Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural
Equilibrium Solvers [22.85979978964773]
Solution concepts such as Nash Equilibria, Correlated Equilibria, and Coarse Correlated Equilibria are useful components for many multiagent machine learning algorithms.
We introduce the Neural Equilibrium solver which utilizes a special equivariant neural network architecture to approximately solve the space of all games of fixed shape, buying speed and determinism.
arXiv Detail & Related papers (2022-10-17T17:00:31Z) - 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) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games.
We introduce a new algorithm for computing optimal equilibria in all three notions.
arXiv Detail & Related papers (2022-03-14T15:21:18Z) - 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) - Rational Verification for Probabilistic Systems [2.4254101826561847]
We develop the theory and algorithms for rational verification in probabilistic systems.
We focus on concurrent games (CSGs), which can be used to model uncertainty and randomness in complex multi-agent environments.
arXiv Detail & Related papers (2021-07-19T19:24:16Z)
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.