Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds Global Optima

• URL: http://arxiv.org/abs/2110.01212v1
• Date: Mon, 4 Oct 2021 06:53:59 GMT
• Title: Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds Global Optima
• Authors: Boyi Liu, Jiayang Li, Zhuoran Yang, Hoi-To Wai, Mingyi Hong, Yu Marco Nie, Zhaoran Wang
• Abstract summary: 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.
• Score: 114.31577038081026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To induce a desired equilibrium in a social system comprised of self-interested agents, economic incentives (e.g., taxes, tolls, and subsidies) are often required to correct an inefficient outcome. Such an incentive design problem naturally possesses a bi-level structure, in which an upper-level "designer" revises the payoffs of the agents with incentives while anticipating the response of the agents, who play a non-cooperative game at the lower level. The existing bi-level optimization algorithms developed in machine learning raise a dilemma when applied to this problem: anticipating how incentives affect the agents at equilibrium requires solving the equilibrium problem repeatedly, which is computationally inefficient; bypassing the time-consuming step of equilibrium-finding can reduce the computational cost, but may lead to a sub-optimal solution. Therefore, we propose an efficient method that tackles the designer's and agents' problems simultaneously in a single loop. At each iteration, both the designer and the agents only move one step based on the first-order information. In the proposed scheme, although the designer does not solve the equilibrium problem repeatedly, it can anticipate the overall influence of the incentives on the agents, which guarantees optimality. We prove that the algorithm converges to the global optima at a sublinear rate for a broad class of games.

Related papers

• 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)
• 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)
• Multi-Agent Distributed Reinforcement Learning for Making Decentralized Offloading Decisions [7.326507804995567]
  We formulate computation offloading as a decentralized decision-making problem with autonomous agents. We design an interaction mechanism that incentivizes agents to align private and system goals by balancing between competition and cooperation. For a dynamic environment, we propose a novel multi-agent online learning algorithm that learns with partial, delayed and noisy state information.
  arXiv  Detail & Related papers  (2022-04-05T15:01:48Z)
• Personalized incentives as feedback design in generalized Nash equilibrium problems [6.10183951877597]
  We investigate stationary and time-varying, nonmonotone generalized Nash equilibrium problems. We design a semi-decentralized Nash equilibrium seeking algorithm. We consider the ridehailing service provided by several companies as a service orchestration.
  arXiv  Detail & Related papers  (2022-03-24T09:24:29Z)
• Learning equilibria with personalized incentives in a class of nonmonotone games [7.713240800142863]
  We consider quadratic, nonmonotone generalized Nash equilibrium problems with symmetric interactions among the agents, which are known to be potential. In the proposed scheme, a coordinator iteratively integrates the noisy agents' feedback to learn the pseudo-gradients of the agents, and then design personalized incentives for them. We show that our algorithm returns an equilibrium in case the coordinator is endowed with standard learning policies, and corroborate our results on a numerical instance of a hypomonotone game.
  arXiv  Detail & Related papers  (2021-11-06T11:18:59Z)
• Equilibrium Design for Concurrent Games [5.9873770241999]
  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.
  arXiv  Detail & Related papers  (2021-06-18T15:45:45Z)
• End-to-End Learning and Intervention in Games [60.41921763076017]
  We provide a unified framework for learning and intervention in games. We propose two approaches, respectively based on explicit and implicit differentiation. The analytical results are validated using several real-world problems.
  arXiv  Detail & Related papers  (2020-10-26T18:39:32Z)
• 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)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  We introduce the emphregularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

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.