2021/07/13 by Rahul Chandan, Chandan, Rahul, Dario Paccagnan +3
Economics, Econometrics and Finance · Social Sciences · #Computer Science and Game Theory (cs.GT) #Economic theories and models #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #FOS: Electrical engineering #Game Theory and Voting Systems #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2107.06331
openalex publication_date 2021/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work focuses on the design of taxes in atomic congestion games, a commonly studied model for competitive resource sharing. While most related studies focus on optimizing either the worst- or best-case performance (i.e., Price of Anarchy (PoA) or Price of Stability (PoS)), we investigate whether optimizing for the PoA has consequences on the PoS. Perhaps surprisingly, our results reveal a fundamental trade-off between the two performance metrics. Our main result demonstrates that the taxation rule that optimizes the PoA inherits a matching PoS, implying that the best outcome is no better than the worst outcome under such a design choice. We then study this trade-off in terms of the Pareto frontier between the PoA and PoS. Our results also establish that any taxes with PoS equal to 1 incur a much higher PoA, and that, in several well-studied cases, the untaxed setting lies strictly above the Pareto frontier.