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

• 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 [63.89699366726275]
  We study how to learn the optimal tax design to maximize the efficiency in nonatomic congestion games. It is known that self-interested behavior among the players can alleviate the system's efficiency.
  arXiv  Detail & Related papers  (2024-02-12T06:32:53Z)
• 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)
• 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)
• Solving Graph-based Public Good Games with Tree Search and Imitation Learning [4.499055111059408]
  We adopt the perspective of a central planner with a global view of a network of self-interested agents and the goal of maximizing some desired property in the context of a best-shot public goods game. Existing algorithms for this known NP-complete problem find solutions that are sub-optimal and cannot optimize for criteria other than social welfare. Our proposed method directly exploits the correspondence between equilibria and the Maximal Independent Set (mIS) structural property of graphs.
  arXiv  Detail & Related papers  (2021-06-12T12:46:44Z)
• 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.