On the performance of approximate equilibria in congestion games

Simple item page
dc.creatorChristodoulou, George
dc.creatorKoutsoupias, Elias
dc.creatorSpirakis, Paul
dc.date2008-04-21
dc.date2008-05-10
dc.date.accessioned2026-07-07T12:18:25Z
dc.date.available2026-07-07T12:18:25Z
dc.descriptionWe 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 $ε$. 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 $ε$-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 $ε$-Nash equilibria but not for the price of anarchy.
dc.identifierhttps://arxiv.org/abs/0804.3160
dc.identifierhttp://arxiv.org/abs/0804.3160
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/212405
dc.subjectComputer Science and Game Theory
dc.subjectArtificial Intelligence
dc.subjectNetworking and Internet Architecture
dc.titleOn the performance of approximate equilibria in congestion games
dc.typetext

Files

Collections

arXiv