On the Performance of Approximate Equilibria in Congestion Games

被引：41

作者：

Christodoulou, George ^{[1
]}

Koutsoupias, Elias ^{[2
]}

Spirakis, Paul G. ^{[3
]}

机构：

[1] Univ Saarland, Dept Comp Sci, D-6600 Saarbrucken, Germany

[2] Univ Athens, Dept Informat, Athens, Greece

[3] Univ Patras, Comp Engn & Informat Dept, Patras, Greece

来源：

ALGORITHMICA | 2011年 / 61卷 / 01期

关键词：

Price of anarchy; Price of stability; Congestion games; Algorithmic Game Theory; Approximate equilibria; Selfish routing;

D O I：

10.1007/s00453-010-9449-2

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study the performance of approximate Nash equilibria for congestion games with polynomial latency functions. We consider how much the price of anarchy worsens and how much the price of stability improves as a function of the approximation factor epsilon. We give tight bounds for the price of anarchy of atomic and non-atomic congestion games and for the price of stability of non-atomic congestion games. For the price of stability of atomic congestion games we give non-tight bounds for linear latencies. Our results not only encompass and generalize the existing results of exact equilibria to epsilon-Nash equilibria, but they also provide a unified approach which reveals the common threads of the atomic and non-atomic price of anarchy results. By expanding the spectrum, we also cast the existing results in a new light.

引用

页码：116 / 140

页数：25

共 34 条

[1] Aland S, 2006, LECT NOTES COMPUT SC, V3884, P218
[2] [Anonymous], 1973, International J. of Game Theory, DOI 10.1007/BF01737559
[3] ANSHELEVICH E, 2004, FOCS, P295
[4] Awerbuch B., 2005, P 37 ANN ACM S THEOR, P57
[5] Beckmann M. J., 1956, STUDIES EC TRANSPORT
[6] Caragiannis I, 2006, LECT NOTES COMPUT SC, V4051, P311, DOI 10.1007/11786986_28
[7] Chen H., 2006, SIGIR 06, P29
[8] Chen X, 2006, ANN IEEE SYMP FOUND, P261
[9] CHIEN S, 2007, SODA, P169
[10] CHRISTODOULOU G, 2008, CORR

← 1 2 3 4 →