首页    期刊浏览 2024年12月03日 星期二
登录注册

文章基本信息

  • 标题:A Priority-Based Model of Routing
  • 本地全文:下载
  • 作者:Babak Farzad ; Neil Olver ; Adrian Vetta
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2008
  • 卷号:2008
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    We consider a priority-based selfish routing model, where agents may have different priorities on a link. An agent with higher priority on a link can traverse it with smaller delay or cost than an agent with lower priority. This general framework can be used to model a number of different problems. The strctural propeties that lead to inefficiencies in routing choices appear different in this priority based model compared to the classical model. In particular, in parallel link networks with nonatomic agents, the price of anarchy is exactly one in the priority based model; that is, selfish behavior leads to optimal routing. In contrast, in the standard model the worst possible price of anarchy can be achieved in a simple two-link network. For multi-commodity networks, selfish routing does lead to inefficiencies in the priority-based model. We present tight bounds on the price of anarchy for such networks. Specifically, in the nonatomic case the worst-case price of anarchy is exactly (d+1)^(d+1) for polynomial latency functions of degree d (hence 4 for linear cost functions). For atomic games, the worst-case price of anarchy is exactly 3+2sqrt(2) in the weighted case, and exactly 17/3 in the unweighted case. An upper bound of O(2^d d^d ) is also shown for polynomial functions in the atomic case, although this is not tight. Our framework (and results) also generalise to include models similar to congestion games.

国家哲学社会科学文献中心版权所有