• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithmic Game Theory >The Influence of Link Restrictions on (Random)Selfish Routing
【24h】

The Influence of Link Restrictions on (Random)Selfish Routing

机译：链接限制对（随机）Selfish路由的影响

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper we consider the influence of link restrictions on the price of anarchy for several social cost functions in the following model of selfish routing. Each of n players in a network game seeks to send a message with a certain length by choosing one of m parallel links. Each player is restricted to transmit over a certain subset of links and desires to minimize his own transmission-time (latency). We study Nash equilibria of the game, in which no player can decrease his latency by unilaterally changing his link. Our analysis of this game captures two important aspects of network traffic: the dependency of the overall network performance on the total traffic t and fluctuations in the length of the respective message-lengths. For the latter we use a probabilistic model in which message lengths are random variables. We evaluate the (expected) price of anarchy of the game for two social cost functions. For total latency cost, we show the tight result that the price of anarchy is essentially Θ (n m~(1/2)/t). Hence, even for congested networks, when the traffic is linear in the number of players, Nash equilibria approximate the social optimum only by a factor of Θ (m~(1/2)). This efficiency loss is caused by link restrictions and remains stable even under message fluctuations, which contrasts the unrestricted case where Nash equilibria achieve a constant factor approximation. For maximum latency the price of anarchy is at most 1+m~2/t. In this case Nash equilibria can be (almost) optimal solutions for congested networks depending on the values for m and t. In addition, our analyses yield average-case analyses of a polynomial time algorithm for computing Nash equilibria in this model.
机译：在以下自私路由模型中，我们考虑了几个社会成本函数的链接限制对无政府状态价格的影响。网络游戏中的n个玩家中的每一个都试图通过选择m个并行链接之一来发送具有一定长度的消息。每个玩家都被限制通过链接的某个子集进行传输，并且希望将自己的传输时间（延迟）最小化。我们研究游戏的纳什均衡，其中没有玩家可以通过单方面更改链接来减少等待时间。我们对该游戏的分析捕获了网络流量的两个重要方面：总体网络性能对总流量t的依赖性以及各个消息长度的波动。对于后者，我们使用概率模型，其中消息长度是随机变量。我们针对两个社会成本函数评估游戏的无政府状态价格（预期价格）。对于总等待时间成本，我们显示出严格的结果，即无政府状态的价格实质上为Θ（n m〜（1/2）/ t）。因此，即使对于拥挤的网络，当流量在参与者数量上是线性的时，纳什均衡也仅以Θ（m〜（1/2））的因子近似社会最优值。这种效率损失是由链路限制引起的，即使在消息波动时也保持稳定，这与Nash均衡达到常数因子近似的无限制情况形成了对比。对于最大延迟，无政府状态的价格至多为1 + m〜2 / t。在这种情况下，取决于m和t的值，纳什均衡可以（几乎）是拥塞网络的最佳解决方案。另外，我们的分析产生了用于在该模型中计算纳什均衡的多项式时间算法的平均情况分析。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号