Subsidy design for better social outcomes

• URL: http://arxiv.org/abs/2409.03129v1
• Date: Wed, 4 Sep 2024 23:38:30 GMT
• Title: Subsidy design for better social outcomes
• Authors: Maria-Florina Balcan, Matteo Pozzi, Dravyansh Sharma,
• Abstract summary: central planner can significantly mitigate these issues by injecting a subsidy to reduce certain costs associated with the system. We show that designing subsidies that perfectly optimize the social good, in terms of minimizing the Price of Anarchy or preventing the information avoidance behavior, is computationally hard under standard complexity theoretic assumptions.
• Score: 24.2043855572415
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Overcoming the impact of selfish behavior of rational players in multiagent systems is a fundamental problem in game theory. Without any intervention from a central agent, strategic users take actions in order to maximize their personal utility, which can lead to extremely inefficient overall system performance, often indicated by a high Price of Anarchy. Recent work (Lin et al. 2021) investigated and formalized yet another undesirable behavior of rational agents, that of avoiding freely available information about the game for selfish reasons, leading to worse social outcomes. A central planner can significantly mitigate these issues by injecting a subsidy to reduce certain costs associated with the system and obtain net gains in the system performance. Crucially, the planner needs to determine how to allocate this subsidy effectively. We formally show that designing subsidies that perfectly optimize the social good, in terms of minimizing the Price of Anarchy or preventing the information avoidance behavior, is computationally hard under standard complexity theoretic assumptions. On the positive side, we show that we can learn provably good values of subsidy in repeated games coming from the same domain. This data-driven subsidy design approach avoids solving computationally hard problems for unseen games by learning over polynomially many games. We also show that optimal subsidy can be learned with no-regret given an online sequence of games, under mild assumptions on the cost matrix. Our study focuses on two distinct games: a Bayesian extension of the well-studied fair cost-sharing game, and a component maintenance game with engineering applications.

Related papers

• Deceptive Sequential Decision-Making via Regularized Policy Optimization [54.38738815697299]
  Two regularization strategies for policy synthesis problems that actively deceive an adversary about a system's underlying rewards are presented. We show how each form of deception can be implemented in policy optimization problems. We show that diversionary deception can cause the adversary to believe that the most important agent is the least important, while attaining a total accumulated reward that is $98.83%$ of its optimal, non-deceptive value.
  arXiv  Detail & Related papers  (2025-01-30T23:41:40Z)
• Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality [62.18973784316808]
  In economic theory, the concept of externality refers to any indirect effect resulting from an interaction between players that affects the social welfare. Our work removes the classical assumption that bargainers possess perfect knowledge of the underlying game. We then design a policy for the players which allows them to learn a bargaining strategy which maximizes the total welfare.
  arXiv  Detail & Related papers  (2024-06-28T11:00:53Z)
• Learning Optimal Tax Design in Nonatomic Congestion Games [56.85292809260111]
  In multiplayer games, self-interested behavior among the players can harm the social welfare. We take the initial step of learning the optimal tax that can induce social welfare with limited feedback in congestion games.
  arXiv  Detail & Related papers  (2024-02-12T06:32:53Z)
• 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)
• 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)
• Multi-Principal Assistance Games [11.85513759444069]
  Impossibility theorems in social choice theory and voting theory can be applied to such games. We analyze in particular a bandit apprentice game in which the humans act first to demonstrate their individual preferences for the arms. We propose a social choice method that uses shared control of a system to combine preference inference with social welfare optimization.
  arXiv  Detail & Related papers  (2020-07-19T00:23:25Z)
• Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry [66.82463322411614]
  The paper focuses on the problem of optimal ex ante persuasive signaling schemes, showing that symmetry is a crucial property for its solution. We show that an optimal ex ante persuasive scheme can be computed in time when players are symmetric and have affine cost functions.
  arXiv  Detail & Related papers  (2020-02-12T19:38:15Z)

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.