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.
翻译:本研究集中于设计原子拥堵游戏中的税收,这是一种通常用于竞争性资源共享的模型。尽管大多数相关研究专注于优化最坏或最好的情况(即Price of Anarchy(PoA)或Price of Stability(PoS)),我们研究了优化PoA对PoS的影响。令人惊讶的是,我们的结果揭示出两个性能指标之间的根本权衡。我们的主要结果表明,优化PoA的税收规则具有匹配的PoS,这意味着在这样的设计选择下,最佳结果不比最差结果更好。然后,我们从PoA和PoS之间的Pareto前沿线研究了这种权衡。我们的结果还证明,任何PoS等于1的税收都会导致更高的PoA,在几种研究较多的案例中,未征税的情况严格位于Pareto前沿线之上。