EXACT PRICE OF ANARCHY FOR POLYNOMIAL CONGESTION GAMES

被引：64

作者：

Aland, Sebastian ^{[1
]}

Dumrauf, Dominic ^{[1
]}

Gairing, Martin ^{[2
]}

Monien, Burkhard ^{[1
]}

Schoppmann, Florian ^{[1
]}

机构：

[1] Univ Paderborn, Dept Comp Sci Elect Engn & Math, D-33102 Paderborn, Germany

[2] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England

来源：

SIAM JOURNAL ON COMPUTING | 2011年 / 40卷 / 05期

关键词：

atomic unsplittable congestion games; selfish routing; price of anarchy; NASH EQUILIBRIA; LATENCY;

D O I：

10.1137/090748986

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show exact values for the worst-case price of anarchy in weighted and unweighted (atomic unsplittable) congestion games, provided that all cost functions are bounded-degree polynomials with nonnegative coefficients. The given values also hold for weighted and unweighted network congestion games.

引用

页码：1211 / 1233

页数：23

共 41 条

[1]

Aland S, 2006, LECT NOTES COMPUT SC, V3884, P218

[2]

Awerbuch B., 2005, P 37 ANN ACM S THEOR, P57

[3] Tradeoffs in worst-case equilibria [J].

Awerbuch, Baruch ;

Azar, Yossi ;

Richter, Yossi ;

Tsur, Dekel .

THEORETICAL COMPUTER SCIENCE, 2006, 361 (2-3) :200-209

[4]

Beckmann M., 1956, Studies in the Economies of Transportation

[5]

Bhawalkar K, 2010, LECT NOTES COMPUT SC, V6347, P17, DOI 10.1007/978-3-642-15781-3_2

[6]

Blum A, 2008, ACM S THEORY COMPUT, P373

[7]

Christodoulou G, 2005, LECT NOTES COMPUT SC, V3669, P59

[8]

Christodoulou G, 2005, P 37 ANN ACM S THEOR, P67, DOI DOI 10.1145/1060590.1060600

[9] The Impact of Oligopolistic Competition in Networks [J].

Cominetti, Roberto ;

Correa, Jose R. ;

Stier-Moses, Nicolas E. .

OPERATIONS RESEARCH, 2009, 57 (06) :1421-1437

[10] Tight Bounds for Worst-Case Equilibria [J].

Czumaj, Artur ;

Voecking, Berthold .

ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (01)

← 1 2 3 4 5 →