{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:03Z","timestamp":1750309083996,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2004,12,1]],"date-time":"2004-12-01T00:00:00Z","timestamp":1101859200000},"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":["SIGACT News"],"published-print":{"date-parts":[[2004,12]]},"abstract":"<jats:p>Recently there has been a lot of interest in problems at the intersection of Game Theory, Economics, and Computer Science. For example, there are interesting developments concerning algorithms for equilibria and cost sharing, algorithmic mechanism design, and the efficiency of systems with selfish users [25]. In this note, I will focus on the last area and in particular on the price of anarchy of task allocation, selfish routing, and congestion games. I will discuss the issues of this area, mention the central results, and suggest some open problems, some of them close in spirit to competitive analysis.<\/jats:p>","DOI":"10.1145\/1054916.1054933","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T19:28:32Z","timestamp":1131391712000},"page":"58-71","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Coordination mechanisms for congestion games"],"prefix":"10.1145","volume":"35","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[{"name":"University of California, Riverside"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elias","family":"Koutsoupias","sequence":"additional","affiliation":[{"name":"University of Athens"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Studies in economics of transportation","author":"Beckmann M.","year":"1956","unstructured":"M. Beckmann , C. B. McGuire , and C. B. Winsten . Studies in economics of transportation . Yale University Press , 1956 . M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in economics of transportation. Yale University Press, 1956."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780618"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779941"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_31"},{"key":"e_1_2_1_5_1","first-page":"413","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Czumaj A.","year":"2002","unstructured":"A. Czumaj and B. V\u00f6cking . Tight Bounds for Worst-case Equilibria . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms , pp. 413 -- 420 , January 2002 . A. Czumaj and B. V\u00f6cking. Tight Bounds for Worst-case Equilibria. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 413--420, January 2002."},{"key":"e_1_2_1_6_1","unstructured":"A. Czumaj Selfish routing on the Internet. http:\/\/www.cis.njit.edu\/~czumaj\/ PUBLICATIONS\/Selfish-Routing-Survey-2003.html  A. Czumaj Selfish routing on the Internet. http:\/\/www.cis.njit.edu\/~czumaj\/ PUBLICATIONS\/Selfish-Routing-Survey-2003.html"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.69"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684270"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_51"},{"key":"e_1_2_1_10_1","first-page":"1563","volume-title":"Bell System Technical Journal, 45","author":"Graham R. L.","year":"1966","unstructured":"R. L. Graham . Bounds for certain multiprocessing anomalies , Bell System Technical Journal, 45 , pages 1563 -- 1581 , 1966 . R. L. Graham. Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 45, pages 1563--1581, 1966."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.26"},{"key":"e_1_2_1_13_1","first-page":"79","volume-title":"Number 81","author":"Koutsoupias E.","year":"2003","unstructured":"E. Koutsoupias . Selfish task allocation. Bulletin of EATCS , Number 81 , pages 79 -- 88 , October 2003 . E. Koutsoupias. Selfish task allocation. Bulletin of EATCS, Number 81, pages 79--88, October 2003."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO)","author":"Koutsoupias E.","year":"2002","unstructured":"E. Koutsoupias , M. Mavronicolas and P. Spirakis . Approximate Equilibria and Ball Fusion . In Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO) , 2002 E. Koutsoupias, M. Mavronicolas and P. Spirakis. Approximate Equilibria and Ball Fusion. In Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764944"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45138-9_49"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380846"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_21_1","first-page":"1","volume-title":"Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science","author":"Nisan N.","year":"1999","unstructured":"N. Nisan . Algorithms for selfish agents: Mechanism design for distributed computation . In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science , pages 1 -- 15 , 1999 . N. Nisan. Algorithms for selfish agents: Mechanism design for distributed computation. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 1--15, 1999."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_23_1","volume-title":"A Course in Game Theory","author":"Osborne M. J.","year":"1994","unstructured":"M. J. Osborne and A. Rubinstein . A Course in Game Theory . The MIT Press , 1994 . M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, 1994."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380883"},{"key":"e_1_2_1_25_1","unstructured":"C. Papadimitriou. Game theory and the Internet (course notes). http:\/\/www.cs.berkeley.edu\/~christos\/games03\/cs294.html  C. Papadimitriou. Game theory and the Internet (course notes). http:\/\/www.cs.berkeley.edu\/~christos\/games03\/cs294.html"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875585"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.28"},{"volume-title":"Computing equilibria for two-person games. Handbook of Game Theory","author":"von Stengel B.","key":"e_1_2_1_30_1","unstructured":"B. von Stengel . Computing equilibria for two-person games. Handbook of Game Theory , Vol. 3 , eds. R. J. Aumann and S. Hart , North- Holland, Amsterdam . B. von Stengel. Computing equilibria for two-person games. Handbook of Game Theory, Vol. 3, eds. R. J. Aumann and S. Hart, North-Holland, Amsterdam."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1054916.1054933","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1054916.1054933","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:30Z","timestamp":1750286610000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1054916.1054933"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,12]]}},"alternative-id":["10.1145\/1054916.1054933"],"URL":"https:\/\/doi.org\/10.1145\/1054916.1054933","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2004,12]]},"assertion":[{"value":"2004-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}