• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Experimental and Efficient Algorithms(WEA 2005); 20050510-13; Santorini Island(GR) >Efficient Convergence to Pure Nash Equilibria in Weighted Network Congestion Games
【24h】

Efficient Convergence to Pure Nash Equilibria in Weighted Network Congestion Games

机译：加权网络拥塞博弈中的有效收敛到纯纳什均衡

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

摘要

In large-scale or evolving networks, such as the Internet, there is no authority possible to enforce a centralized traffic management. In such situations, Game Theory and the concepts of Nash equilibria and Congestion Games are a suitable framework for analyzing the equilibrium effects of selfish routes selection to network delays. We focus here on layered networks where selfish users select paths to route their loads (represented by arbitrary integer weights). We assume that individual link delays are equal to the total load of the link. We focus on the algorithm suggested in [2], i.e. a potential-based method for finding pure Nash equilibria (PNE) in such networks. A superficial analysis of this algorithm gives an upper bound on its time which is polynomial in n (the number of users) and the sum of their weights. This bound can be exponential in n when some weights are superpolynomial. We provide strong experimental evidence that this algorithm actually converges to a PNE in strong polynomial time in n (independent of the weights values). In addition we propose an initial allocation of users to paths that dramatically accelerates this algorithm, compared to an arbitrary initial allocation. A by-product of our research is the discovery of a weighted potential function when link delays are exponential to their loads. This asserts the existence of PNE for these delay functions and extends the result of [2].
机译：在大规模或不断发展的网络（例如Internet）中，没有权限实施集中式流量管理。在这种情况下，博弈论以及纳什均衡和拥塞博弈的概念是用于分析自私路由选择对网络延迟的均衡影响的合适框架。我们在这里集中于分层的网络，其中自私的用户选择路径来路由其负载（用任意整数权重表示）。我们假设单个链路延迟等于链路的总负载。我们专注于[2]中提出的算法，即一种基于势能的方法，用于在此类网络中寻找纯纳什均衡（PNE）。对这种算​​法的表面分析给出了其时间的上限，该上限是n（用户数）的多项式及其权重之和。当某些权重是超多项式时，此界在n中可以是指数的。我们提供了有力的实验证据，表明该算法实际上在n的强多项式时间内收敛到PNE（与权重值无关）。此外，与任意初始分配相比，我们建议对路径的用户进行初始分配，从而极大地加速了该算法。我们研究的副产品是当链路延迟与其负载成指数关系时，发现了加权潜在函数。这断言了这些延迟功能存在PNE，并扩展了[2]的结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号