{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:51Z","timestamp":1759637631358},"reference-count":3,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p> 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. <\/jats:p><jats:p> 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: <\/jats:p><jats:p> \u2022 For the case of identical users and identical links, the Price of Anarchy is [Formula: see text]. <\/jats:p><jats:p> \u2022 For the case of identical users, the Price of Anarchy is [Formula: see text]. <\/jats:p><jats:p> \u2022 For the case of identical links, the Price of Anarchy is [Formula: see text], which is asymptotically tight. <\/jats:p><jats:p> \u2022 For the most general case of arbitrary users and related links, the Price of Anarchy is at least m \u2013 1 and less than m. <\/jats:p><jats:p> The shown bounds reveal the dependence of the Price of Anarchy on n and m for all possible assumptions on users and links. <\/jats:p>","DOI":"10.1142\/s0129626406002514","type":"journal-article","created":{"date-parts":[[2006,3,24]],"date-time":"2006-03-24T06:18:03Z","timestamp":1143181083000},"page":"117-131","source":"Crossref","is-referenced-by-count":28,"title":["THE PRICE OF ANARCHY FOR RESTRICTED PARALLEL LINKS"],"prefix":"10.1142","volume":"16","author":[{"given":"MARTIN","family":"GAIRING","sequence":"first","affiliation":[{"name":"Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, D-33102 Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"THOMAS","family":"L\u00dcCKING","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, D-33102 Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARIOS","family":"MAVRONICOLAS","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Cyprus, Nicosia CY-1678, Cyprus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BURKHARD","family":"MONIEN","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, D-33102 Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1131-5"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626406002514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:16:41Z","timestamp":1565093801000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626406002514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":3,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1142\/S0129626406002514"],"URL":"https:\/\/doi.org\/10.1142\/s0129626406002514","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]}}}