论文标题
自私行为在负载平衡游戏中的影响
The Impact of Selfish Behavior in Load Balancing Games
论文作者
论文摘要
玩家战略空间的结构在多大程度上影响交通拥堵的解决方案的效率？在这项工作中，我们调查在限制加载平衡游戏时是否可以表现更好的性能，其中玩家只能在单个资源中进行选择。我们考虑了三种不同的解决方案概念，即近似纯净的纳什平衡，大约是由自私的玩家产生的，旨在最大程度地减少其个人成本以及旨在最大程度地减少玩家个人成本总和的同事增加而产生的一轮步行。最后两个概念可以解释为相关资源选择问题的贪婪在线算法的解决方案。我们表明，在相当普遍的延迟功能上，如果玩家加权或不对称，将无法实现更好的界限。从积极的一面来看，我们证明，在对延迟功能的温和假设下，在相同资源的情况下，可以使用加权和对称玩家的负载平衡游戏来改善近似纯Nash平衡的表现。我们还设计了与未加权玩家和相同资源的负载平衡游戏中单轮步行的表现的低界限。
To what extent does the structure of the players' strategy space influence the efficiency of decentralized solutions in congestion games? In this work, we investigate whether better performance are possible when restricting to load balancing games in which players can only choose among single resources. We consider three different solutions concepts, namely, approximate pure Nash equilibria, approximate one-round walks generated by selfish players aiming at minimizing their personal cost and approximate one-round walks generated by cooperative players aiming at minimizing the marginal increase in the sum of the players' personal costs. The last two concepts can be interpreted as solutions of greedy online algorithms for the related resource selection problem. We show that, under fairly general latency functions on the resources, better bounds cannot be achieved if players are either weighted or asymmetric. On the positive side, we prove that, under mild assumptions on the latency functions, improvements on the performance of approximate pure Nash equilibria are possible for load balancing games with weighted and symmetric players in the case of identical resources. We also design lower bounds on the performance of one-round walks in load balancing games with unweighted players and identical resources.
