{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:31:16Z","timestamp":1750307476410,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,11,1]],"date-time":"2010-11-01T00:00:00Z","timestamp":1288569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"UMIC Research Center","award":["Ho 3831\/3-1"],"award-info":[{"award-number":["Ho 3831\/3-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>\n            We study Nash equilibria in a selfish routing game on\n            <jats:italic>m<\/jats:italic>\n            parallel links with transmission speeds. Each player seeks to communicate a message by choosing one of the links, and each player desires to minimize his experienced transmission time (latency). For evaluating the social cost of Nash equilibria, we consider the price of anarchy, which is the largest ratio of the cost of any Nash equilibrium compared to the optimum solution. Similarly, we consider the price of stability, which is the smallest ratio. The main purpose of this article is to quantify the influence of three parameters upon the prices of the game: the total traffic in the network; restrictions of the players in terms of link choice; and fluctuations in message lengths.\n          <\/jats:p>\n          <jats:p>\n            Our main interest is to bound the sum of all player latencies, which we refer to as\n            <jats:italic>collective latency<\/jats:italic>\n            . For this cost, the prices of anarchy and stability are\n            <jats:italic>\u0398<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>t<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the number of players and\n            <jats:italic>t<\/jats:italic>\n            the sum of message lengths (total traffic); that is, Nash equilibria approximate the optimum solution up to a constant factor if the traffic is high. If each player is restricted to choose from a subset of links, these link restrictions can cause a degradation in performance of order \u0398(\\sqrt{\n            <jats:italic>m<\/jats:italic>\n            }). The prices of anarchy and stability increase to \u0398(\n            <jats:italic>n<\/jats:italic>\n            \\sqrt{\n            <jats:italic>m<\/jats:italic>\n            }\/\n            <jats:italic>t<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            We capture fluctuations in message lengths through a stochastic model, in which we valuate Nash equilibria in terms of their expected price of anarchy. The expected price is \u0398(\n            <jats:italic>n<\/jats:italic>\n            \/\\mathbb{E}[\n            <jats:italic>T<\/jats:italic>\n            ]), where \\mathbb{E}[\n            <jats:italic>T<\/jats:italic>\n            ] is the expected traffic. The stochastic model resembles the deterministic one, even for the efficiency loss of order \u0398(\\sqrt{\n            <jats:italic>m<\/jats:italic>\n            }) for link restrictions.\n          <\/jats:p>\n          <jats:p>\n            For the social cost function maximum latency, the (expected) price of anarchy is 1\u2009+\u2009\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/\n            <jats:italic>t<\/jats:italic>\n            . In this case, Nash equilibria are almost optimal solutions for congested networks. Similar results hold when the cost function is a polynomial of the link loads.\n          <\/jats:p>","DOI":"10.1145\/1867719.1867721","type":"journal-article","created":{"date-parts":[[2010,11,23]],"date-time":"2010-11-23T15:00:38Z","timestamp":1290524438000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Tradeoffs and Average-Case Equilibria in Selfish Routing"],"prefix":"10.1145","volume":"2","author":[{"given":"Martin","family":"Hoefer","sequence":"first","affiliation":[{"name":"RWTH Aachen University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Souza","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a004"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.010"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.06.009"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_28"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060600"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_27"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186814"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01930985"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007446"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.07.055"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9015-8"},{"key":"e_1_2_1_16_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness.W.H. Freeman New York. Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness .W.H. Freeman New York."},{"volume-title":"Proceedings of the 15th European Symposium on Algorithms (ESA). 63--74","author":"Hoefer M.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.032"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Kontogiannis S. and Spirakis P. 2007. Atomic selfish routing in networks: A survey. In Handbook of Parallel Computing J. Reif and S. Rajasekaran Eds. Chapman Hall\/CRC Ch.20. Kontogiannis S. and Spirakis P. 2007. Atomic selfish routing in networks: A survey. In Handbook of Parallel Computing J. Reif and S. Rajasekaran Eds. Chapman Hall\/CRC Ch.20.","DOI":"10.1201\/9781420011296.ch20"},{"volume-title":"Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS). 404--413","author":"Koutsoupias E.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9108-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1211-4"},{"key":"e_1_2_1_25_1","unstructured":"Vredeveld T. 2002. Combinatorial approximation algorithms. guaranteed versus experimental performance. Ph.D. dissertation Technische Universiteit Eindhoven. Vredeveld T. 2002. Combinatorial approximation algorithms. guaranteed versus experimental performance. Ph.D. dissertation Technische Universiteit Eindhoven."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1867719.1867721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1867719.1867721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:08:52Z","timestamp":1750248532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1867719.1867721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.1145\/1867719.1867721"],"URL":"https:\/\/doi.org\/10.1145\/1867719.1867721","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2010,11]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}