{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T11:22:40Z","timestamp":1768735360809,"version":"3.49.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"crossref","award":["P2EZP2_181618"],"award-info":[{"award-number":["P2EZP2_181618"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["#N00014-20-1-2359"],"award-info":[{"award-number":["#N00014-20-1-2359"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["#FA9550-20-1-0054"],"award-info":[{"award-number":["#FA9550-20-1-0054"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            How can we design mechanisms to promote efficient use of shared resources? Here, we answer this question in relation to the well-studied class of atomic congestion games, used to model a variety of problems, including traffic routing. Within this context, a methodology for designing tolling mechanisms that minimize the system inefficiency (price of anarchy) exploiting solely local information is so far missing in spite of the scientific interest. In this article, we resolve this problem through a tractable linear programming formulation that applies to and beyond polynomial congestion games. When specializing our approach to the polynomial case, we obtain tight values for the optimal price of anarchy and corresponding tolls, uncovering an unexpected link with load balancing games. We also derive optimal tolling mechanisms that are constant with the congestion level, generalizing the results of Caragiannis et al. [8] to polynomial congestion games and beyond. Finally, we apply our techniques to compute the efficiency of the marginal cost mechanism. Surprisingly, optimal tolling mechanism using only local information perform closely to existing mechanism that utilize global information, e.g., Bil\u00f2 and Vinci [6], while the marginal cost mechanism, known to be optimal in the continuous-flow model, has lower efficiency than that encountered levying\n            <jats:italic>no<\/jats:italic>\n            toll. All results are tight for pure Nash equilibria and extend to coarse correlated equilibria.\n          <\/jats:p>","DOI":"10.1145\/3457168","type":"journal-article","created":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T17:02:19Z","timestamp":1629133339000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Optimal Taxes in Atomic Congestion Games"],"prefix":"10.1145","volume":"9","author":[{"given":"Dario","family":"Paccagnan","sequence":"first","affiliation":[{"name":"Imperial College London, South Kensington, UK"}]},{"given":"Rahul","family":"Chandan","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, Santa Barbara, CA, USA"}]},{"given":"Bryce L.","family":"Ferguson","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, Santa Barbara, CA, USA"}]},{"given":"Jason R.","family":"Marden","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, Santa Barbara, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,8,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/090748986"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/070702370"},{"key":"e_1_2_1_5_1","volume-title":"Ramana","author":"Bergendorff Pia","year":"1997","unstructured":"Pia Bergendorff , Donald W. Hearn , and Motakuri V . Ramana . 1997 . Congestion toll pricing of traffic networks. In Network Optimization. Springer , 51\u201371. Pia Bergendorff, Donald W. Hearn, and Motakuri V. Ramana. 1997. Congestion toll pricing of traffic networks. In Network Optimization. Springer, 51\u201371."},{"key":"e_1_2_1_6_1","article-title":"Dynamic taxes for polynomial congestion games","volume":"7","author":"Bil\u00f2 Vittorio","year":"2019","unstructured":"Vittorio Bil\u00f2 and Cosimo Vinci . 2019 . Dynamic taxes for polynomial congestion games . ACM Trans. Econ. Comput. 7 , 3 (2019), 15:1\u201315:36. Vittorio Bil\u00f2 and Cosimo Vinci. 2019. Dynamic taxes for polynomial congestion games. ACM Trans. Econ. Comput. 7, 3 (2019), 15:1\u201315:36.","journal-title":"ACM Trans. Econ. Comput."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9427-8"},{"key":"e_1_2_1_8_1","article-title":"Taxes for linear atomic congestion games","volume":"7","author":"Caragiannis Ioannis","year":"2010","unstructured":"Ioannis Caragiannis , Christos Kaklamanis , and Panagiotis Kanellopoulos . 2010 . Taxes for linear atomic congestion games . ACM Trans. Algor. 7 , 1 (2010), 13:1\u201313:31. Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos. 2010. Taxes for linear atomic congestion games. ACM Trans. Algor. 7, 1 (2010), 13:1\u201313:31.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"Computing optimal taxes in atomic congestion games. In Proceedings of the 14th Workshop on the Economics of Networks, Systems and Computation (NetEcon\u201919)","volume":"2","author":"Chandan Rahul","year":"2019","unstructured":"Rahul Chandan , Dario Paccagnan , Bryce L. Ferguson , and Jason R. Marden . 2019 . Computing optimal taxes in atomic congestion games. In Proceedings of the 14th Workshop on the Economics of Networks, Systems and Computation (NetEcon\u201919) . ACM , 2 : 1 . Rahul Chandan, Dario Paccagnan, Bryce L. Ferguson, and Jason R. Marden. 2019. Computing optimal taxes in atomic congestion games. In Proceedings of the 14th Workshop on the Economics of Networks, Systems and Computation (NetEcon\u201919). ACM, 2:1.","journal-title":"ACM"},{"key":"e_1_2_1_10_1","volume-title":"Marden","author":"Chandan Rahul","year":"2019","unstructured":"Rahul Chandan , Dario Paccagnan , and Jason R . Marden . 2019 . MATLAB and Python Packages to Compute and Optimize the Price of Anarchy. Retrieved from https:\/\/github.com\/rahul-chandan\/resalloc-poa. Rahul Chandan, Dario Paccagnan, and Jason R. Marden. 2019. MATLAB and Python Packages to Compute and Optimize the Price of Anarchy. Retrieved from https:\/\/github.com\/rahul-chandan\/resalloc-poa."},{"key":"e_1_2_1_11_1","volume-title":"Marden","author":"Chandan Rahul","year":"2019","unstructured":"Rahul Chandan , Dario Paccagnan , and Jason R . Marden . 2019 . Optimal mechanisms for distributed resource-allocation. arXiv:1911.07823. Retrieved from https:\/\/arxiv.org\/abs\/1911.07823. Rahul Chandan, Dario Paccagnan, and Jason R. Marden. 2019. Optimal mechanisms for distributed resource-allocation. arXiv:1911.07823. Retrieved from https:\/\/arxiv.org\/abs\/1911.07823."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 58th IEEE Conference on Decision and Control (CDC\u201919)","author":"Chandan Rahul","unstructured":"Rahul Chandan , Dario Paccagnan , and Jason R. Marden . 2019. When smoothness is not enough: Toward exact quantification and optimization of the price-of-anarchy . In Proceedings of the 58th IEEE Conference on Decision and Control (CDC\u201919) . IEEE, 4041\u20134046. Rahul Chandan, Dario Paccagnan, and Jason R. Marden. 2019. When smoothness is not enough: Toward exact quantification and optimization of the price-of-anarchy. In Proceedings of the 58th IEEE Conference on Decision and Control (CDC\u201919). IEEE, 4041\u20134046."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing","author":"Christodoulou George","year":"2005","unstructured":"George Christodoulou and Elias Koutsoupias . 2005 . The price of anarchy of finite congestion games . In Proceedings of the 37th Annual ACM Symposium on Theory of Computing , Baltimore, Harold N. Gabow and Ronald Fagin (Eds.). ACM, 67\u201373. George Christodoulou and Elias Koutsoupias. 2005. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, Harold N. Gabow and Ronald Fagin (Eds.). ACM, 67\u201373."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.09.010"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129175"},{"key":"e_1_2_1_16_1","unstructured":"Tobias Harks. 2019. Pricing in Resource Allocation Games Based on Lagrangean Duality and Convexification. arXiv:1907.01976. Retrieved from https:\/\/arxiv.org\/abs\/1907.01976.  Tobias Harks. 2019. Pricing in Resource Allocation Games Based on Lagrangean Duality and Convexification. arXiv:1907.01976. Retrieved from https:\/\/arxiv.org\/abs\/1907.01976."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21604"},{"key":"e_1_2_1_18_1","volume-title":"Ramana","author":"Hearn Donald W.","year":"1998","unstructured":"Donald W. Hearn and Motakuri V . Ramana . 1998 . Solving Congestion Toll Pricing Models. Springer US , Boston, MA, 109\u2013124. Donald W. Hearn and Motakuri V. Ramana. 1998. Solving Congestion Toll Pricing Models. Springer US, Boston, MA, 109\u2013124."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 4th International Workshop on Internet and Network Economics (WINE\u201908)","volume":"5385","author":"Hoefer Martin","year":"2008","unstructured":"Martin Hoefer , Lars Olbrich , and Alexander Skopalik . 2008 . Taxing subnetworks . In Proceedings of the 4th International Workshop on Internet and Network Economics (WINE\u201908) , Christos H. Papadimitriou and Shuzhong Zhang (Eds.), Lecture Notes in Computer Science , Vol. 5385 . Springer, 286\u2013294. Martin Hoefer, Lars Olbrich, and Alexander Skopalik. 2008. Taxing subnetworks. In Proceedings of the 4th International Workshop on Internet and Network Economics (WINE\u201908), Christos H. Papadimitriou and Shuzhong Zhang (Eds.), Lecture Notes in Computer Science, Vol. 5385. Springer, 286\u2013294."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914)","author":"Jelinek Tomas","year":"2014","unstructured":"Tomas Jelinek , Marcus Klaas , and Guido Sch\u00e4fer . 2014 . Computing optimal tolls with arc restrictions and heterogeneous players . In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914) , Ernst W. Mayr and Natacha Portier (Eds.), LIPIcs,Vol. 25. Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 433\u2013444. Tomas Jelinek, Marcus Klaas, and Guido Sch\u00e4fer. 2014. Computing optimal tolls with arc restrictions and heterogeneous players. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914), Ernst W. Mayr and Natacha Portier (Eds.), LIPIcs,Vol. 25. Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 433\u2013444."},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Computer Science","volume-title":"Papadimitriou","author":"Koutsoupias Elias","year":"1999","unstructured":"Elias Koutsoupias and Christos H . Papadimitriou . 1999 . Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201999), Christoph Meinel and Sophie Tison (Eds.), Lecture Notes in Computer Science , Vol. 1563 . Springer , 404\u2013413. Elias Koutsoupias and Christos H. Papadimitriou. 1999. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201999), Christoph Meinel and Sophie Tison (Eds.), Lecture Notes in Computer Science, Vol. 1563. Springer, 404\u2013413."},{"key":"e_1_2_1_22_1","volume-title":"The Theory of Incentives: The Principal-Agent Model","author":"Laffont Jean-Jacques","unstructured":"Jean-Jacques Laffont and David Martimort . 2002. The Theory of Incentives: The Principal-Agent Model . Princeton University Press . Jean-Jacques Laffont and David Martimort. 2002. The Theory of Incentives: The Principal-Agent Model. Princeton University Press."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1137"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 9th International Workshop on Agents in Traffic and Transportation (ATT\u201916)","volume":"1678","author":"Meir Reshef","unstructured":"Reshef Meir and David C. Parkes . 2016. When are marginal congestion tolls optimal? In Proceedings of the 9th International Workshop on Agents in Traffic and Transportation (ATT\u201916) co-located with the 25th International Joint Conference On Artificial Intelligence (IJCAI\u201916), Ana L\u00facia C. Bazzan, Franziska Kl\u00fcgl, Sascha Ossowski, and Giuseppe Vizzari (Eds.) , Vol. 1678 . Reshef Meir and David C. Parkes. 2016. When are marginal congestion tolls optimal? In Proceedings of the 9th International Workshop on Agents in Traffic and Transportation (ATT\u201916) co-located with the 25th International Joint Conference On Artificial Intelligence (IJCAI\u201916), Ana L\u00facia C. Bazzan, Franziska Kl\u00fcgl, Sascha Ossowski, and Giuseppe Vizzari (Eds.), Vol. 1678."},{"key":"e_1_2_1_25_1","volume-title":"Internalization of social cost in congestion games. Econ. Theory","author":"Milchtaich Igal","year":"2020","unstructured":"Igal Milchtaich . 2020. Internalization of social cost in congestion games. Econ. Theory ( 2020 ), 1\u201344. Igal Milchtaich. 2020. Internalization of social cost in congestion games. Econ. Theory (2020), 1\u201344."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2607(86)90035-X"},{"key":"e_1_2_1_27_1","volume-title":"Marden","author":"Paccagnan Dario","year":"2019","unstructured":"Dario Paccagnan , Rahul Chandan , Bryce L. Ferguson , and Jason R . Marden . 2019 . Optimal Taxes in Atomic Congestion Games. arXiv:1911.09806. Retrieved from https:\/\/arxiv.org\/abs\/1911.09806. Dario Paccagnan, Rahul Chandan, Bryce L. Ferguson, and Jason R. Marden. 2019. Optimal Taxes in Atomic Congestion Games. arXiv:1911.09806. Retrieved from https:\/\/arxiv.org\/abs\/1911.09806."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2019.2961995"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2849946"},{"key":"e_1_2_1_30_1","volume-title":"The Economics of Welfare","author":"Pigou Arthur C.","unstructured":"Arthur C. Pigou . 1920. The Economics of Welfare . Macmillan . Arthur C. Pigou. 1920. The Economics of Welfare. Macmillan."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806883"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.t01-1-00026"},{"key":"e_1_2_1_34_1","unstructured":"Alexander Skopalik and Vipin Ravindran Vijayalakshmi. 2020. Improving approximate pure Nash equilibria in congestion games. arXiv:2007.15520. Retrieved from https:\/\/arxiv.org\/abs\/2007.15520.  Alexander Skopalik and Vipin Ravindran Vijayalakshmi. 2020. Improving approximate pure Nash equilibria in congestion games. arXiv:2007.15520. Retrieved from https:\/\/arxiv.org\/abs\/2007.15520."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118733.3118816"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2182779"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1680\/ipeds.1952.11259"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457168","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457168","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:19Z","timestamp":1750191439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,16]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3457168"],"URL":"https:\/\/doi.org\/10.1145\/3457168","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,16]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}