# Learning Optimal Tax Design in Nonatomic Congestion Games

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

## Key facts

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

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

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [End-to-End Learning and Intervention in Games](https://mlsanity.com/paper/2010.13834/) (2020)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [Inducing Equilibria via Incentives: Simultaneous Design-and-Play Ensures Global Convergence](https://mlsanity.com/paper/2110.01212/) (2021)
- [Generalized Mirror Descents in Congestion Games](https://mlsanity.com/paper/1605.07774/) (2016)
- [BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent](https://mlsanity.com/paper/2303.01101/) (2023)
- [Semi Bandit Dynamics in Congestion Games: Convergence to Nash Equilibrium and No-Regret Guarantees](https://mlsanity.com/paper/2306.15543/) (2023)
- [Differentiable Bilevel Programming for Stackelberg Congestion Games](https://mlsanity.com/paper/2209.07618/) (2022)
- [In Congestion Games, Taxes Achieve Optimal Approximation](https://mlsanity.com/paper/2105.07480/) (2021)
- [Achieving Hierarchy-Free Approximation for Bilevel Programs With Equilibrium Constraints](https://mlsanity.com/paper/2302.09734/) (2023)
- [Taming the Exponential Action Set: Sublinear Regret and Fast Convergence to Nash Equilibrium in Online Congestion Games](https://mlsanity.com/paper/2306.13673/) (2023)
- [Offline congestion games: How feedback type affects data coverage requirement](https://mlsanity.com/paper/2210.13396/) (2022)
- [Polynomial Convergence of Bandit No-Regret Dynamics in Congestion Games](https://mlsanity.com/paper/2401.09628/) (2024)

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

- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)

## Abstract (arXiv)

In multiplayer games, self-interested behavior among the players can harm the social welfare. Tax mechanisms are a common method to alleviate this issue and induce socially optimal behavior. In this work, we take the initial step of learning the optimal tax that can maximize social welfare with limited feedback in congestion games. We propose a new type of feedback named equilibrium feedback, where the tax designer can only observe the Nash equilibrium after deploying a tax plan. Existing algorithms are not applicable due to the exponentially large tax function space, nonexistence of the gradient, and nonconvexity of the objective. To tackle these challenges, we design a computationally efficient algorithm that leverages several novel components: (1) a piece-wise linear tax to approximate the optimal tax; (2) extra linear terms to guarantee a strongly convex potential function; (3) an efficient subroutine to find the exploratory tax that can provide critical information about the game. The algorithm can find an ε-optimal tax with O(β F2/ε) sample complexity, where β is the smoothness of the cost function and F is the number of facilities.