caa a22 4500 445805161 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9449-2 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9449-2 On the Performance of Approximate Equilibria inCongestion Games [Elektronische Daten] [George Christodoulou, Elias Koutsoupias, Paul Spirakis] 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 ε. 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 ε-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. Springer Science+Business Media, LLC, 2010 Price of anarchy nationallicence Price of stability nationallicence Congestion games nationallicence Algorithmic Game Theory nationallicence Approximate equilibria nationallicence Selfish routing nationallicence Christodoulou George Department of Computer Science, University of Saarland, Saarbrücken, Germany aut Koutsoupias Elias Department of Informatics, University of Athens, Athens, Greece aut Spirakis Paul Computer Engineering and Informatics Department, Patras University, Patras, Greece aut Algorithmica Springer-Verlag 61/1(2011-09-01), 116-140 0178-4617 61:1<116 2011 61 453 https://doi.org/10.1007/s00453-010-9449-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9449-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Christodoulou George Department of Computer Science, University of Saarland, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Koutsoupias Elias Department of Informatics, University of Athens, Athens, Greece aut NATIONALLICENCE 700 1- Spirakis Paul Computer Engineering and Informatics Department, Patras University, Patras, Greece aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 116-140 0178-4617 61:1<116 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer