Tradeoffs in worst-case equilibria

被引：46

作者：

Awerbuch, Baruch

Azar, Yossi

Richter, Yossi ^{[1
]}

Tsur, Dekel

机构：

[1] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel

[2] Johns Hopkins Univ, Dept Comp Sci, Baltimore, MD 21218 USA

[3] Ben Gurion Univ Negev, Dept Comp Sci, IL-84105 Beer Sheva, Israel

来源：

THEORETICAL COMPUTER SCIENCE | 2006年 / 361卷 / 2-3期

基金：

以色列科学基金会;

关键词：

worst-case coordination ratio; restricted assignment; unrelated links;

D O I：

10.1016/j.tcs.2006.05.010

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate the problem of routing traffic through a congested network in an environment of non-cooperative users. We use the worst-case coordination ratio suggested by Koutsoupias and Papadimitriou to measure the performance degradation due to the lack of a centralized traffic regulating authority. We provide a full characterization of the worst-case coordination ratio in the restricted assignment and unrelated parallel links model. In particular, we quantify the tradeoff between the "negligibility" of the traffic controlled by each user and the worst-case coordination ratio. We analyze both pure and mixed strategies systems and identify the range where their performance is similar. (C) 2006 Elsevier B.V. All rights reserved.

引用

页码：200 / 209

页数：10

共 12 条

[1] COLE R, 2003, P 4 ACM C EL COMM, P98
[2] Cole Richard, 2003, S THEOR COMP ASS COM, P521
[3] Czumaj A, 2002, SIAM PROC S, P413
[4] Czumaj A., 2002, ACM S THEORY COMPUTI, P287
[5] Huet Gerard P., 1987, FDN SOFTWARE TECHNOL, DOI [10.1007/3-540-18625-5_61, DOI 10.1007/3-540-18625-5_61]
[6] Mavronicolas M., 2001, ACM S THEORY COMPUTI, P510
[7] Motwani Rajeev, 1995, RANDOMIZED ALGORITHM
[8] Papadimitriou C, 2001, P 33 ANN ACM S THEOR, P749, DOI DOI 10.1145/380752.380883
[9] The price of anarchy is independent of the network topology
Roughgarden, T
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (02) : 341 - 364
[10] Roughgarden T, 2002, SIAM PROC S, P203

← 1 2 →