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