dc.contributor.author | Gairing, M. | en |
dc.contributor.author | Lücking, T. | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.author | Monien, Burkhard | en |
dc.creator | Gairing, M. | en |
dc.creator | Lücking, T. | en |
dc.creator | Mavronicolas, Marios | en |
dc.creator | Monien, Burkhard | en |
dc.date.accessioned | 2019-11-13T10:40:06Z | |
dc.date.available | 2019-11-13T10:40:06Z | |
dc.date.issued | 2006 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53956 | |
dc.description.abstract | In 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.source | Parallel Processing Letters | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-33645210957&doi=10.1142%2fS0129626406002514&partnerID=40&md5=e03a62c9a20f7c41f06eceb3400e3486 | |
dc.subject | Telecommunication links | en |
dc.subject | Scheduling | en |
dc.subject | Parallel processing systems | en |
dc.subject | Routers | en |
dc.subject | Price of Anarchy | en |
dc.subject | Restricted Parallel Links | en |
dc.subject | Selfish Routing | en |
dc.subject | Switching theory | en |
dc.title | The Price of Anarchy for restricted parallel links | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1142/S0129626406002514 | |
dc.description.volume | 16 | |
dc.description.issue | 1 | |
dc.description.startingpage | 117 | |
dc.description.endingpage | 131 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Cited By :20</p> | en |
dc.source.abbreviation | Parallel Process Lett | en |