On the performance of approximate equilibria in congestion games

@misc{citeulike:2699732, abstract = {We study the performance of approximate Nash equilibria for linear congestion games. 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 (almost) tight upper and lower bounds for both the price of anarchy and the price of stability for atomic and non-atomic congestion games. 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. For example, the Pigou network, which gives tight results for exact Nash equilibria of selfish routing, remains tight for the price of stability of \$\epsilon\$-Nash equilibria but not for the price of anarchy.}, author = {Christodoulou, George and Koutsoupias, Elias and Spirakis, Paul }, citeulike-article-id = {2699732}, eprint = {0804.3160}, keywords = {congestion}, month = {Apr}, posted-at = {2008-04-22 10:53:51}, priority = {2}, title = {On the performance of approximate equilibria in congestion games}, url = {http://arxiv.org/abs/0804.3160}, year = {2008} }

TY - ELEC ID - citeulike:2699732 L3 - citeulike-article-id:2699732 TI - On the performance of approximate equilibria in congestion games N2 - We study the performance of approximate Nash equilibria for linear congestion games. 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 (almost) tight upper and lower bounds for both the price of anarchy and the price of stability for atomic and non-atomic congestion games. 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. For example, the Pigou network, which gives tight results for exact Nash equilibria of selfish routing, remains tight for the price of stability of $\epsilon$-Nash equilibria but not for the price of anarchy. KW - congestion AU - Christodoulou, George AU - Koutsoupias, Elias AU - Spirakis, Paul PY - 2008/Apr/21/ UR - http://arxiv.org/abs/0804.3160 ER -