Show simple item record

dc.contributor.authorGairing, M.en
dc.contributor.authorLücking, T.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorMonien, Burkharden
dc.contributor.authorSpirakis, Paul G.en
dc.creatorGairing, M.en
dc.creatorLücking, T.en
dc.creatorMavronicolas, Mariosen
dc.creatorMonien, Burkharden
dc.creatorSpirakis, Paul G.en
dc.description.abstractWe study extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical links, to control the routing of its own assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link. We provide substantial evidence for the Fully Mixed Nash Equilibrium Conjecture, which states that the worst Nash equilibrium is the fully mixed Nash equilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed Nash Equilibrium Conjecture is valid for pure Nash equilibria. Furthermore, we show, that under a certain condition, the social cost of any Nash equilibrium is within a factor of 2h(1+ε) of that of the fully mixed Nash equilibrium, where h is the factor by which the largest user traffic deviates from the average user traffic. Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is NP-hard to approximate the worst social cost within a multiplicative factor better than 2-2/(m+1). © 2005 Elsevier B.V. All rights reserved.en
dc.sourceTheoretical Computer Scienceen
dc.subjectGame theoryen
dc.subjectRandom processesen
dc.subjectApproximation theoryen
dc.subjectProbability distributionsen
dc.subjectComputational complexityen
dc.subjectSelfish routingen
dc.subjectLatency costsen
dc.subjectExtreme Nash equilibriaen
dc.subjectExtreme Nash equilibriumen
dc.titleStructure and complexity of extreme Nash equilibriaen
dc.description.endingpage157 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :21</p>en
dc.contributor.orcidSpirakis, Paul G. [0000-0001-5396-3749]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record