Papers › When Smoothness is Not Enough: Toward Exact Quantification and Optimization of the...
When Smoothness is Not Enough: Toward Exact Quantification and Optimization of the Price of Anarchy
Rahul Chandan, Dario Paccagnan, Jason R. Marden
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The price of anarchy (PoA) is a popular metric for analyzing the inefficiency of self-interested decision making. Although its study is widespread, characterizing the PoA can be challenging. A commonly employed approach is based on the smoothness framework, which provides tight PoA values under the assumption that the system objective consists in the sum of the agents' individual welfares. Unfortunately, several important classes of problems do not satisfy this requirement (e.g., taxation in congestion games), and our first result demonstrates that the smoothness framework does *not* tightly characterize the PoA for such settings. Motivated by this observation, this work develops a framework that achieves two chief objectives: i) to tightly characterize the PoA for such scenarios, and ii) to do so through a tractable approach. As a direct consequence, the proposed framework recovers and generalizes many existing PoA results, and enables efficient computation of incentives that optimize the PoA. We conclude by highlighting the applicability of our contributions to incentive design in congestion games and utility design in distributed welfare games.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections