Show simple item record

dc.contributor.authorGairing, M.en
dc.contributor.authorLücking, T.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorMonien, Burkharden
dc.creatorGairing, M.en
dc.creatorLücking, T.en
dc.creatorMavronicolas, Mariosen
dc.creatorMonien, Burkharden
dc.description.abstractIn the model of restricted parallel links, n users must be routed on m parallel links under the restriction that the link for each user be chosen from a certain set of allowed links for the user. In a (pure) Nash equilibrium, no user may improve its own Individual Cost (latency) by unilaterally switching to another link from its set of allowed links. The Price of Anarchy is a widely adopted measure of the worst-case loss (relative to optimum) in system performance (maximum latency) incurred in a Nash equilibrium. In this work, we present a comprehensive collection of bounds on Price of Anarchy for the model of restricted parallel links and for the special case of pure Nash equilibria. Specifically, we prove: For the case of identical users and identical links, the Price of Anarchy is Ω(1gm/1g1gm). For the case of identical users, the Price of Anarchy is O(1gn/1g1gn). For the case of identical links, the Price of Anarchy is O (1gm/1g1gm),> which is asymptotically tight. For the most general case of arbitrary users and related links, the Price of Anarchy is at least m - 1 and less than m. The shown bounds reveal the dependence of the Price of Anarchy on n and m for all possible assumptions on users and links. © World Scientific Publishing Company.en
dc.sourceParallel Processing Lettersen
dc.subjectTelecommunication linksen
dc.subjectParallel processing systemsen
dc.subjectPrice of Anarchyen
dc.subjectRestricted Parallel Linksen
dc.subjectSelfish Routingen
dc.subjectSwitching theoryen
dc.titleThe Price of Anarchy for restricted parallel linksen
dc.description.endingpage131 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :20</p>en
dc.source.abbreviationParallel Process Letten

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record