Research map / Learning theory and algorithms / Submodular and game algorithms
Learning Optimal Tax Design in Nonatomic Congestion Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Learns the welfare-optimal marginal-cost tax in nonatomic congestion games from equilibrium-only feedback, using piecewise-linear tax approximation, strongly convex shaping, and exploratory tax probes, with O(F^2 β/ε) sample complexity.
Problem
Learning the optimal (welfare-maximizing) tax in nonatomic congestion games when the designer only observes the Nash equilibrium induced by each deployed tax, with no gradient access and a nonconvex objective over an exponentially large tax space.
Approach
Approximates the marginal-cost tax with a piecewise-linear function on a grid, adds a linear term so the tax subgradient is at least epsilon (making the potential strongly convex and the Nash load unique and Lipschitz), and uses a subroutine that finds a "boundary" exploratory tax revealing information about one unknown facility per round.
Key results
- The algorithm outputs a 6εF-optimal tax within T ≤ 2Fβ/ε rounds (theorem), giving O(F^2 β/ε) sample complexity.
- Strong convexity of the reparameterized potential holds with coefficient ε when tax subgradients are lower bounded by ε (lemma).
- The Nash load under tax can be discontinuous in the tax and the social welfare non-convex in the tax (lemma with explicit two-facility counterexamples).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use piece-wise linear tax approximation, an extra linear term for strong convexity, and exploratory taxes with equilibrium feedback | Tax design in nonatomic congestion games · Nonatomic congestion games | sample complexity: O(F^2β/ε) | Helped |
Surprising findings
- The Nash load as a function of tax can be discontinuous, and social cost can be nonconvex in the tax, ruling out direct gradient methods.
Limitations
- Assumes the designer knows the smoothness coefficient β.
- Restricted to nonatomic congestion games with Nash equilibrium feedback; atomic games not covered.
- Sample complexity lower bound is conjectured to be tight but not proven.
Experimental setup
Metrics: sample complexity social cost gap
Baselines: enumeration of epsilon-approximate taxes MPEC gradient-based methods
Builds on: marginal cost mechanism Wardrop equilibrium
Closest papers by meaning
- Learning in Congestion Games with Bandit Feedback (NeurIPS 2022 · similarity 0.87)
- Enhancing the Efficiency of Altruism and Taxes in Affine Congestion Games through Signalling (AAAI 2024 · similarity 0.87)
- A Simple, Fast, and Safe Mediator for Congestion Management (AAAI 2020 · similarity 0.86)
- Learning from Delayed Feedback in Games via Extra Prediction (NeurIPS 2025 · similarity 0.84)
- Cost Minimization for Equilibrium Transition (AAAI 2024 · similarity 0.84)
- LOPT: Learning Optimal Pigovian Tax in Sequential Social Dilemmas (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.