{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:38:57Z","timestamp":1787326737926,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Program of Scientific and Technological Collaboration"},{"name":"IST Program of the European Union","award":["IST-1999-14186"],"award-info":[{"award-number":["IST-1999-14186"]}]},{"name":"IST Program of the European Union","award":["IST-2001-33116"],"award-info":[{"award-number":["IST-2001-33116"]}]},{"name":"IST Program of the European Union","award":["15964"],"award-info":[{"award-number":["15964"]}]},{"DOI":"10.13039\/100012996","name":"University of Cyprus","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012996","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A Nash equilibrium of a routing game is a stable state where no (randomizing) user could benefit from a unilateral deviation. We consider the simplest case of the parallel links network, where links are related. The Social Cost of a Nash equilibrium is the expected maximum latency. We seek the worst-case Nash equilibrium [E. Koutsoupias and C. H. Papadimitriou, Comput. Sci. Rev., 3 (2009), pp. 65\u201369], which maximizes Social Cost. We continue the study of the fully mixed Nash equilibrium conjecture, abbreviated as the FMNE Conjecture, stating that the worst-case Nash equilibrium is the fully mixed Nash equilibrium, where each user assigns strictly positive probability to every link. Through an extensive combinatorial analysis, we confirm the FMNE Conjecture for the two basic cases where there are either (i) two users on related links, or (ii) many users on two identical links.<\/jats:p>","DOI":"10.1137\/22m1542635","type":"journal-article","created":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T10:42:33Z","timestamp":1717584153000},"page":"1701-1732","source":"Crossref","is-referenced-by-count":1,"title":["Which is the Worst-Case Nash Equilibrium?"],"prefix":"10.1137","volume":"38","author":[{"given":"Thomas","family":"L\u00fccking","sequence":"first","affiliation":[{"name":"SAP AG, D-69190 Walldorf, Germany. The work of this author was done while at the Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, 33102 Paderborn, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marios","family":"Mavronicolas","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Cyprus, Nicosia, 1678, Cyprus. Part of the work of this author was done while visiting the Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Burkhard","family":"Monien","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, 33102, Paderborn, Germany. Part of the work of this author was done while visiting the Department of Computer Science, University of Cyprus."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, L69 3BX, UK, and Research Academic Computer Technology Institute, 261 10 Patras, Greece."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Imrich","family":"Vrto","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, Slovak Academy of Sciences, 841 04 Bratislava 4, Slovak Republic."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,6,5]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186814"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"R. Els\u00e4sser, M. Gairing, T. L\u00fccking, M. Mavronicolas, and B. Monien, A simple graph-theoretic model for selfish restricted scheduling, in Proceedings of the 1st International Workshop on Internet and Network Economics, Lecture Notes in Comput. Sci. 3828, Springer-Verlag, 2005, pp. 195\u2013209.","DOI":"10.1007\/11600930_20"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9199-1"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.11.017"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.019"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.004"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.07.055"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.001"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.011"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9015-8"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626409000122"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1131-5"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2009.04.003"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.045"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"M. Mavronicolas, I. Milchtaich, B. Monien, and K. Tiemann, Congestion games with player-specific constants, in Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 4708, Springer-Verlag, 2006, pp. 633\u2013644.","DOI":"10.1007\/978-3-540-74456-6_56"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9108-4"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0056-1"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"ref20","volume-title":"A Course in Game Theory","author":"Osborne M. J.","year":"1994"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.2307\/2308012"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1542635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:35:26Z","timestamp":1787322926000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1542635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,5]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1137\/22M1542635"],"URL":"https:\/\/doi.org\/10.1137\/22m1542635","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,5]]}}}