Cost-Balancing Tolls for Atomic Network Congestion Games
Cost-Balancing Tolls for Atomic Network Congestion Games
复制标题
原子网络拥塞游戏的成本平衡通行费
作者：
Dimitris Fotakis;P. Spirakis
我们研究了具有不可分割流量和任意非递减延迟函数的原子对称网络拥塞游戏的最佳通行费的存在性。我们关注纯纳什均衡，并考虑一种自然收费机制，我们称之为成本平衡收费。一组成本平衡通行费将其边缘具有正流量的每条路径转变为最小成本路径。因此，任何给定的配置都被归纳为具有相应成本平衡通行费的修改游戏的纯纳什均衡。我们展示了如何在线性时间内计算最优解决方案的一组成本平衡通行费，使得修改游戏的任何纯纳什均衡中任何玩家支付的通行费总额不会超过最优解决方案中最大延迟路径上的延迟。我们的主要结果是，对于具有严格增加延迟函数的串并网络上的拥塞博弈，最优解被归纳为具有相应成本平衡通行费的博弈的唯一纯纳什均衡。据我们所知，在这项工作之前，只有并行链路上的线性拥堵博弈才能承认最佳通行费。为了证明计算一组更好的最优通行费的难度，我们证明即使对于串并网络上的两人线性拥塞博弈，决定最优解是唯一的纯纳什均衡还是存在另一个总成本至少是最优成本的 6/5 倍的纯纳什均衡也是 NP 困难的。
We investigate the existence of optimal tolls for atomic symmetric network congestion games with unsplittable traffic and arbitrary nondecreasing latency functions. We focus on pure Nash equilibria, and consider a natural toll mechanism, which we call cost-balancing tolls. A set of cost-balancing tolls turns every path with positive traffic on its edges into a minimum-cost path. Hence any given configuration is induced as a pure Nash equilibrium of the modified game with the corresponding cost-balancing tolls. We show how to compute in linear time a set of cost-balancing tolls for the optimal solution such that the total amount of tolls paid by any player in any pure Nash equilibrium of the modified game does not exceed the latency on the maximum-latency path in the optimal solution. Our main result is that for congestion games on series-parallel networks with strictly increasing latency functions, the optimal solution is induced as the unique pure Nash equilibrium of the game with the corresponding cost-balancing tolls. To the best of our knowledge, only linear congestion games on parallel links were known to admit optimal tolls prior to this work. To demonstrate the difficulty of computing a better set of optimal tolls, we show that even for two-player linear congestion games on series-parallel networks, it is NP-hard to decide whether the optimal solution is the unique pure Nash equilibrium or there is another pure Nash equilibrium of total cost at least 6/5 times the optimal cost.