{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:03:31Z","timestamp":1757311411133,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:00:00Z","timestamp":1725580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DoD, Airforce DoDAirForce","award":["FA9550-23-1-0487"],"award-info":[{"award-number":["FA9550-23-1-0487"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>\n            We study the inefficiency of pure Nash equili bria in symmetric unweighted network congestion games. We first explore the impact of symmetry on the worst-case PoA of network congestion games. For polynomial delay functions with highest degree\n            <jats:italic>p<\/jats:italic>\n            , we construct a family of symmetric congestion games over arbitrary networks which achieves the same worst-case PoA of asymmetric network congestion games. Next, we explore the impact of network structure within the class of symmetric network congestion games. For delay functions in class \ud835\udc9f, we introduce a quantity\n            <jats:italic>y<\/jats:italic>\n            (\ud835\udc9f) and we show that the PoA is at most\n            <jats:italic>y<\/jats:italic>\n            (\ud835\udc9f) in games defined over series-parallel networks. Thus, for polynomial delays with highest degree\n            <jats:italic>p<\/jats:italic>\n            , the PoA cannot exceed 2\n            <jats:sup>\n              <jats:italic>p<\/jats:italic>\n              +1\n            <\/jats:sup>\n            - 1, which is significantly smaller than the worst-case PoA in games defined over arbitrary networks. Moreover, we prove that the worst-case PoA quickly degrades from sub-linear to exponential when relaxing the network topology form extension-parallel to series-parallel.\n          <\/jats:p>\n          <jats:p>\n            Finally, we consider measuring the social cost as the maximum players\u2019 cost. For polynomial delays of maximum degree\n            <jats:italic>p<\/jats:italic>\n            we show that the worst-case PoA is significantly smaller than that of general symmetric congestion games, but dramatically larger than that of games defined over extension-parallel networks.\n          <\/jats:p>","DOI":"10.1145\/3665590","type":"journal-article","created":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T11:06:10Z","timestamp":1719572770000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Inefficiency of pure Nash equilibria in network congestion games: the impact of symmetry and network structure"],"prefix":"10.1145","volume":"12","author":[{"given":"Bainian","family":"Hao","sequence":"first","affiliation":[{"name":"Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, United States"}]},{"given":"Carla","family":"Michini","sequence":"additional","affiliation":[{"name":"Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, United States"}]}],"member":"320","published-online":{"date-parts":[[2024,9,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_17"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/090748986"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/070702370"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15781-3_2"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629666"},{"key":"e_1_3_2_8_2","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"17:1\u201317:14","volume-title":"Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017).","volume":"87","author":"Bil\u00f2 V.","year":"2017","unstructured":"V. Bil\u00f2 and C. Vinci. 2017. On the impact of singleton strategies in congestion games. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017).Kirk Pruhs and Christian Sohler (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 87, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 17:1\u201317:14."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9427-8"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060600"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0968"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958027"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186814"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.04.011"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_28"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_5"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9205-7"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9152-8"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129175"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_55"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9191-9"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.001"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77105-0_42"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","unstructured":"B. Hao and C. Michini. 2024. The price of Anarchy in series-parallel network congestion games. Mathematical Programming 203 1 (2024) 499\u2013529.","DOI":"10.1007\/s10107-022-01803-w"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.22.1.39"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-014-0448-4"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2009.04.003"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_48"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.045"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0056-1"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-021-10038-9"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/90.251910"},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","unstructured":"R. W. Rosenthal. 1973. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2 1 (1973) 65\u201367.","DOI":"10.1007\/BF01737559"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00044-8"},{"key":"e_1_3_2_35_2","first-page":"980","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Roughgarden T.","year":"2004","unstructured":"T. Roughgarden. 2004. The Maximum Latency of Selfish Routing. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). Society for Industrial and Applied Mathematics, USA, 980\u2013981."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536485"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806883"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007941"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211023"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3665590","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3665590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:04Z","timestamp":1750291564000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3665590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,6]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3665590"],"URL":"https:\/\/doi.org\/10.1145\/3665590","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2024,9,6]]},"assertion":[{"value":"2023-02-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}