{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T21:27:58Z","timestamp":1764019678667},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175718"},{"type":"electronic","value":"9783642175725"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17572-5_30","type":"book-chapter","created":{"date-parts":[[2010,12,6]],"date-time":"2010-12-06T08:54:45Z","timestamp":1291625685000},"page":"366-377","source":"Crossref","is-referenced-by-count":19,"title":["The Complexity of Equilibria in Cost Sharing Games"],"prefix":"10.1007","author":[{"given":"Vasilis","family":"Syrgkanis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"Ackermann, H., R\u00f6glin, H., V\u00f6cking, B.: On the impact of combinatorial structure on congestion games. J. ACM\u00a055(6) (2008)","DOI":"10.1145\/1455248.1455249"},{"key":"30_CR2","first-page":"295","volume-title":"FOCS","author":"E. Anshelevich","year":"2004","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, \u00c9., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: FOCS, pp. 295\u2013304. IEEE Computer Society, Los Alamitos (2004)"},{"key":"30_CR3","unstructured":"Balcan, M.-F., Blum, A., Mansour, Y.: Circumventing the price of anarchy: Leading dynamics to good behavior. In: ICS, pp. 200\u2013213 (2010)"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/1378533.1378544","volume-title":"SPAA","author":"M. Charikar","year":"2008","unstructured":"Charikar, M., Karloff, H.J., Mathieu, C., Naor, J., Saks, M.E.: Online multicast with egalitarian cost sharing. In: SPAA, pp. 70\u201376. ACM, New York (2008)"},{"issue":"6","key":"30_CR5","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1109\/JSAC.2007.070813","volume":"25","author":"C. Chekuri","year":"2007","unstructured":"Chekuri, C., Chuzhoy, J., Lewin-Eytan, L., Naor, J., Orda, A.: Non-cooperative multicast and facility location games. IEEE Journal on Selected Areas in Communications\u00a025(6), 1193\u20131206 (2007)","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"30_CR6","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1145\/1250910.1250924","volume-title":"EC","author":"A. Epstein","year":"2007","unstructured":"Epstein, A., Feldman, M., Mansour, Y.: Strong equilibrium in cost sharing connection games. In: EC, pp. 84\u201392. ACM, New York (2007)"},{"key":"30_CR7","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/1007352.1007445","volume-title":"STOC","author":"A. Fabrikant","year":"2004","unstructured":"Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure nash equilibria. In: STOC, pp. 604\u2013612. ACM, New York (2004)"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/978-3-642-02026-1_16","volume-title":"COCOA 2009","author":"T.D. Hansen","year":"2009","unstructured":"Hansen, T.D., Telelis, O.: Improved bounds for facility location games with fair cost allocation. In: COCOA 2009. LNCS, vol.\u00a05573, pp. 174\u2013185. Springer, Heidelberg (2009)"},{"key":"30_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-642-15781-3_3","volume-title":"Algorithms \u2013 ESA 2010","author":"T. Harks","year":"2010","unstructured":"Harks, T., Hoefer, M., Klimm, M., Skopalik, A.: Computing pure nash and strong equilibria in bottleneck congestion games. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06347, pp. 29\u201338. Springer, Heidelberg (2010)"},{"key":"30_CR10","unstructured":"Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: A simple class of congestion games. In: AAAI, pp. 489\u2013494 (2005)"},{"issue":"1","key":"30_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci.\u00a037(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"30_CR12","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM\u00a041(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"R.W. Rosenthal","year":"1973","unstructured":"Rosenthal, R.W.: A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory\u00a02(1), 65\u201367 (1973)","journal-title":"International Journal of Game Theory"},{"issue":"1","key":"30_CR14","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/0220004","volume":"20","author":"A.A. Sch\u00e4ffer","year":"1991","unstructured":"Sch\u00e4ffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput.\u00a020(1), 56\u201387 (1991)","journal-title":"SIAM J. Comput."},{"key":"30_CR15","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Matroids, Trees, Stable Sets, vol. B (2003)"},{"key":"30_CR16","first-page":"355","volume-title":"STOC","author":"A. Skopalik","year":"2008","unstructured":"Skopalik, A., V\u00f6cking, B.: Inapproximability of pure nash equilibria. In: STOC, pp. 355\u2013364. ACM, New York (2008)"},{"key":"30_CR17","unstructured":"Syrgkanis, V.: Equilibria in Congestion Game Models. Undergraduate Diploma Thesis (2009), http:\/\/www.cs.cornell.edu\/~vasilis\/thesis.pdf"},{"key":"30_CR18","unstructured":"Tardos, E., Kleinberg, J.: Algorithm Design, ch. 12. Addison-Wesley, Reading (2005)"},{"key":"30_CR19","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Internet and Network Economics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17572-5_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,4]],"date-time":"2023-06-04T11:19:10Z","timestamp":1685877550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17572-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175718","9783642175725"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17572-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}