Routing (un-) splittable flow in games with player-specific affine latency functions
Routing (un-) splittable flow in games with player-specific affine latency functions
复制标题
具有特定于玩家的仿射延迟函数的游戏中的路由（非）可分割流
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Karsten Tiemann
中科院分区：
文献类型：
--
作者：
Martin Gairing;B. Monien;Karsten Tiemann
在这项工作中，我们研究了加权网络拥塞游戏与球员特定的延迟功能，自私的球员希望通过共享网络路由他们的流量。我们认为这两种情况下的splittable和unsplittable流量。我们的主要发现如下。对于具有线性延迟函数的并行链路上的路由游戏，我们分别引入了两个新的不可分割和可分割流量的潜在函数。我们使用这些功能，以获得纯纳什均衡的收敛性和计算的平衡结果。对于这些路由游戏的几个概括，我们表明，这样的潜在功能不存在。我们证明了严格的上限和下限的价格无政府状态的多项式延迟函数的游戏。我们关于无政府状态价格的所有结果都可以转化为一般的拥塞博弈。
In this work we study weighted network congestion games with player-specific latency functions where selfish players wish to route their traffic through a shared network. We consider both the case of splittable and unsplittable traffic. Our main findings are as follows. For routing games on parallel links with linear latency functions, we introduce two new potential functions for unsplittable and for splittable traffic, respectively. We use these functions to derive results on the convergence to pure Nash equilibria and the computation of equilibria. For several generalizations of these routing games, we show that such potential functions do not exist. We prove tight upper and lower bounds on the price of anarchy for games with polynomial latency functions. All our results on the price of anarchy translate to general congestion games.