# Subsidy design for better social outcomes

arXiv: https://arxiv.org/abs/2409.03129 · HTML: https://mlsanity.com/paper/2409.03129/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 50 references that are in the map.
- First posted on arXiv 4 Sep 2024.

## Builds on (most cited first, 12 of 12)

- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018)
- [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019)
- [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021)
- [Provably tuning the ElasticNet across instances](https://mlsanity.com/paper/2207.10199/) (2022)
- [An Analysis of Robustness of Non-Lipschitz Networks](https://mlsanity.com/paper/2010.06154/) (2020)
- [Accelerating ERM for data-driven algorithm design using output-sensitive techniques](https://mlsanity.com/paper/2204.03569/) (2022)
- [Inducing Equilibria in Networked Public Goods Games through Network Structure Modification](https://mlsanity.com/paper/2002.10627/) (2020)
- [The Effectiveness of Subsidies and Tolls in Congestion Games](https://mlsanity.com/paper/2102.09655/) (2021)
- [Learning accurate and interpretable tree-based models](https://mlsanity.com/paper/2405.15911/) (2024)

## Built on by (most cited first, 1 of 1)

- [Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees](https://mlsanity.com/paper/2502.12937/) (2025)

## Abstract (arXiv)

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.