{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T22:03:41Z","timestamp":1766181821733,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>\n            Routing games over time are widely studied due to various applications, e.g., transportation, road and air traffic control, logistic in production systems, communication networks like the internet, and financial flows. In this article, we present a new competitive packet routing game with edge priorities motivated by traffic and transportation. In this model a set of selfishly acting players travels through the network over time. If the number of players who want to enter an edge at the same time exceeds the inflow capacity of this edge, then edge priorities with respect to the preceding edge are used to resolve these conflicts, which is similar to right-of-way rules in traffic. We analyze the efficiency of pure Nash equilibria, present an efficient algorithm for computing equilibria in symmetric games, and show that it is\n            <jats:italic>NP<\/jats:italic>\n            -hard to decide whether a Nash equilibrium exists in an asymmetric game. Furthermore, we address the problem of constructing optimal priorities.\n          <\/jats:p>","DOI":"10.1145\/3488268","type":"journal-article","created":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T11:57:19Z","timestamp":1644407839000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Routing Games with Edge Priorities"],"prefix":"10.1145","volume":"10","author":[{"given":"Robert","family":"Scheffler","sequence":"first","affiliation":[{"name":"Brandenburg University of Technology, Cottbus, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4241-6584","authenticated-orcid":false,"given":"Martin","family":"Strehler","sequence":"additional","affiliation":[{"name":"Brandenburg University of Technology, Zwickau, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7499-5958","authenticated-orcid":false,"given":"Laura Vargas","family":"Koch","sequence":"additional","affiliation":[{"name":"RWTH Aachen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,2,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0382"},{"key":"e_1_3_2_5_2","volume-title":"Approximation Hardness of Short Symmetric Instances of MAX-3SAT","author":"Berman Piotr","year":"2003","unstructured":"Piotr Berman, Marek Karpinski, and Alexander D. Scott. 2003. Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Technical Report TR03-049. Electronic Colloquium on Computational Complexity. https:\/\/eccc.weizmann.ac.il\/report\/2003\/049\/."},{"key":"e_1_3_2_6_2","first-page":"258","article-title":"\u00dcber ein Paradoxon aus der Verkehrsplanung","volume":"12","author":"Braess Dietrich","year":"1968","unstructured":"Dietrich Braess. 1968. \u00dcber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12 (1968), 258\u2013268. DOI:https:\/\/doi.org\/10.1007\/BF01918335","journal-title":"Unternehmensforschung"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085101"},{"key":"e_1_3_2_8_2","volume-title":"A Primer for Dynamic Traffic Assignment","author":"Chiu Yi-Chang","year":"2010","unstructured":"Yi-Chang Chiu, Jon Bottom, Michael Mahut, Alex Paz, Ramachandran Balakrishna, Travis Waller, and Jim Hicks. 2010. A Primer for Dynamic Traffic Assignment. Technical Report. ADB30 Transportation Network Modeling Committee of the Transportation Research Board."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060600"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/2027223.2027279"},{"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.1016\/0022-247X(65)90125-3"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427215"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00037-6"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.3.419"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028998140"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-540-77203-3_12","volume-title":"Mathematics\u2014Key Technology for the Future","author":"Gawrilow Ewgenij","year":"2008","unstructured":"Ewgenij Gawrilow, Ekkehard K\u00f6hler, Rolf H. M\u00f6hring, and Bj\u00f6rn Stenzel. 2008. Dynamic routing of automated guided vehicles in real-time. In Mathematics\u2014Key Technology for the Future, Hans-Joachim Krebs and Willi J\u00e4ger (Eds.). Springer, Berlin, 165\u2013177. DOI:https:\/\/doi.org\/10.1007\/978-3-540-77203-3_12"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3184137"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_4"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/3066311"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71924-5_19"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/978-3-642-04645-2_29","volume-title":"Algorithmic Game Theory","author":"Koch Ronald","year":"2009","unstructured":"Ronald Koch and Martin Skutella. 2009. Nash equilibria and the price of anarchy for flows over time. In Algorithmic Game Theory, LNCS Vol. 5814. Springer, Berlin, 323\u2013334. DOI:https:\/\/doi.org\/10.1007\/978-3-642-04645-2_29"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9299-y"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764944"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/1296179"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030104"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20398"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04612-5_27"},{"issue":"2","key":"e_1_3_2_32_2","first-page":"301","article-title":"Spieltheoretische behandlung eines oligopolmodells mit nachfragetr\u00e4gheit \u2013 Teil I: Bestimmung des dynamischen preisgleichgewichts","volume":"121","author":"Selten Reinhard","year":"1965","unstructured":"Reinhard Selten. 1965. Spieltheoretische behandlung eines oligopolmodells mit nachfragetr\u00e4gheit \u2013 Teil I: Bestimmung des dynamischen preisgleichgewichts. Zeitschr. Gesamte Staatswissensch. 121, 2 (1965), 301\u2013324.","journal-title":"Zeitschr. Gesamte Staatswissensch."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76796-1_21"},{"key":"e_1_3_2_34_2","volume-title":"Competitive Variants of Discrete and Continuous Flows Over Time","author":"Koch Laura Vargas","year":"2020","unstructured":"Laura Vargas Koch. 2020. Competitive Variants of Discrete and Continuous Flows Over Time. Ph.D. Dissertation. RWTH Aachen. DOI:https:\/\/doi.org\/10.18154\/RWTH-2020-11648"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.7.1602"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0191-2615(97)00023-4"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-1647(71)90020-7"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488268","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3488268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:23Z","timestamp":1750188623000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,9]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3488268"],"URL":"https:\/\/doi.org\/10.1145\/3488268","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2022,2,9]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}