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.authorRode, M.en
dc.creatorGairing, M.en
dc.creatorLücking, T.en
dc.creatorMavronicolas, Mariosen
dc.creatorMonien, Burkharden
dc.creatorRode, M.en
dc.description.abstractIn a discrete routing game, each of n selfish users employs a mixed strategy to ship her (unsplittable) traffic over m parallel links. The (expected) latency on a link is determined by an arbitrary non-decreasing, non-constant and convex latency function φ{symbol}. In a Nash equilibrium, each user alone is minimizing her (Expected) Individual Cost, which is the (expected) latency on the link she chooses. To evaluate Nash equilibria, we formulate Social Cost as the sum of the users' (Expected) Individual Costs. The Price of Anarchy is the worst-case ratio of Social Cost for a Nash equilibrium over the least possible Social Cost. A Nash equilibrium is pure if each user deterministically chooses a single linken
dc.description.abstracta Nash equilibrium is fully mixed if each user chooses each link with non-zero probability. We obtain:. For the case of identical users, the Social Cost of any Nash equilibrium is no more than the Social Cost of the fully mixed Nash equilibrium, which may exist only uniquely. Moreover, instances admitting a fully mixed Nash equilibrium enjoy an efficient characterization. For the case of identical users, we derive two upper bounds on the Price of Anarchy: For the case of identical links with a monomial latency function φ{symbol} (x) = xd, the Price of Anarchy is the Bell number of orderd + 1 . For pure Nash equilibria, a generic upper bound from the Wardrop model can be transfered to discrete routing games. For polynomial latency functions with non-negative coefficients and degree d, this yields an upper bound of d + 1. For the case of identical users, a pure Nash equilibrium (and thereby an optimum pure assignment) can be computed in time O (m log m log n). For the general case, computing the best or the worst pure Nash equilibrium is NP-complete, even for identical links with an identity latency function. © 2008 Elsevier Inc. All rights reserved.en
dc.sourceJournal of Computer and System Sciencesen
dc.subjectMixed strategiesen
dc.subjectNash equilibriumen
dc.subjectGame theoryen
dc.subjectDistributed computer systemsen
dc.subjectTelecommunication networksen
dc.subjectUpper boundsen
dc.subjectCodes (symbols)en
dc.subjectNon-zero probabilityen
dc.subjectNash equilibriaen
dc.subjectParallel linksen
dc.subjectPrice of Anarchyen
dc.subjectConvex latency functionsen
dc.subjectDiscrete routing gamesen
dc.subjectFully mixed Nash equilibriaen
dc.subjectLatency functionen
dc.subjectSelfish usersen
dc.subjectSingle linken
dc.titleNash equilibria in discrete routing games with convex latency functionsen
dc.description.endingpage1225 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :15</p>en

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record