{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T12:29:56Z","timestamp":1773232196890,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,9,1]],"date-time":"2012-09-01T00:00:00Z","timestamp":1346457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["327620-09"],"award-info":[{"award-number":["327620-09"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>\n            It is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal centralized solution may be\n            <jats:italic>unbounded<\/jats:italic>\n            even if the system consists of only two parallel links. This ratio is called the\n            <jats:italic>price of anarchy<\/jats:italic>\n            (PoA). In this article, we investigate ways by which one can reduce the performance degradation due to selfish behavior. We investigate two primary methods (a)\n            <jats:italic>Stackelberg routing strategies<\/jats:italic>\n            , where a central authority, for example, network manager, controls a fixed fraction of the flow, and can route this flow in any desired way so as to influence the flow of selfish users; and (b)\n            <jats:italic>network tolls<\/jats:italic>\n            , where tolls are imposed on the edges to modify the latencies of the edges, and thereby influence the induced Nash equilibrium. We obtain results demonstrating the effectiveness of both Stackelberg strategies and tolls in controlling the price of anarchy.\n          <\/jats:p>\n          <jats:p>\n            For Stackelberg strategies, we obtain the first results for nonatomic routing in graphs more general than parallel-link graphs, and strengthen existing results for parallel-link graphs. (i) In series-parallel graphs, we show that Stackelberg routing reduces the PoA to a constant (depending on the fraction of flow controlled). (ii) For general graphs, we obtain latency-class specific bounds on the PoA with Stackelberg routing, which give a continuous trade-off between the fraction of flow controlled and the price of anarchy. (iii) In parallel-link graphs, we show that for\n            <jats:italic>any<\/jats:italic>\n            given class\n            <jats:italic>L<\/jats:italic>\n            of latency functions, Stackelberg routing reduces the PoA to at most \u03b1 + (1-\u03b1)\u010b\u03c1(\n            <jats:italic>L<\/jats:italic>\n            ), where \u03b1 is the fraction of flow controlled and \u03c1(\n            <jats:italic>L<\/jats:italic>\n            ) is the PoA of class\n            <jats:italic>L<\/jats:italic>\n            (when \u03b1 = 0).\n          <\/jats:p>\n          <jats:p>\n            For network tolls, motivated by the known strong results for nonatomic games, we consider the more general setting of\n            <jats:italic>atomic splittable<\/jats:italic>\n            routing games. We show that tolls inducing an optimal flow always exist, even for general asymmetric games with heterogeneous users, and can be computed efficiently by solving a\n            <jats:italic>convex program<\/jats:italic>\n            . This resolves a basic open question about the effectiveness of tolls for atomic splittable games. Furthermore, we give a complete characterization of flows that can be induced via tolls.\n          <\/jats:p>","DOI":"10.1145\/2344422.2344426","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T13:50:00Z","timestamp":1349185800000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["The effectiveness of stackelberg strategies and tolls for network congestion games"],"prefix":"10.1145","volume":"8","author":[{"given":"Chaitanya","family":"Swamy","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}]}],"member":"320","published-online":{"date-parts":[[2012,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_2_1_2_1","unstructured":"Beckman M. McGuire C. B. and Winsten C. B. 1956. Studies in the Economics of Transportation. Yale University Press.  Beckman M. McGuire C. B. and Winsten C. B. 1956. Studies in the Economics of Transportation. Yale University Press."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. 748--757","author":"Bhaskar U."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_24"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0442"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_19"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060600"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780618"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.09.010"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0653"},{"key":"e_1_2_1_11_1","unstructured":"Correa J. and Stier-Moses N. 2006. A note on Stackelberg routing. Unpublished manuscript.  Correa J. and Stier-Moses N. 2006. A note on Stackelberg routing. Unpublished manuscript."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0383"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.1.54"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.014"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.69"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9152-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9269-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132529"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.11.002"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.26"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9018-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.554730"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science. 404--413","author":"Koutsoupias E."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 29th International Colloquium on Automata, Languages, and Programming. 776--787","author":"Kumar V. S. A."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.251910"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/646254.683954"},{"key":"e_1_2_1_27_1","unstructured":"Pigou A. C. 1920. The Economics of Welfare. Macmillan.  Pigou A. C. 1920. The Economics of Welfare. Macmillan."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00044-8"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701397059"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Roughgarden T. 2005. Selfish Routing and the Price of Anarchy. MIT Press.   Roughgarden T. 2005. Selfish Routing and the Price of Anarchy. MIT Press.","DOI":"10.21236\/ADA637949"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250925"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 1133--1142","author":"Swamy C.","year":"2007"},{"key":"e_1_2_1_34_1","first-page":"325","article-title":"Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers","volume":"1","author":"Wardrop J. G.","year":"1952","journal-title":"Part II"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0191-2615(02)00074-7","article-title":"The multi-class, multi-criteria traffic network equilibria and system optimum problem","volume":"28","author":"Yang H.","year":"2004","journal-title":"Transport. Res. B"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2007.07.001"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2344422.2344426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:39Z","timestamp":1750273659000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1145\/2344422.2344426"],"URL":"https:\/\/doi.org\/10.1145\/2344422.2344426","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9]]},"assertion":[{"value":"2010-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}