{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,4]],"date-time":"2024-07-04T07:21:20Z","timestamp":1720077680745},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,6,3]],"date-time":"2010-06-03T00:00:00Z","timestamp":1275523200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s00453-010-9417-x","type":"journal-article","created":{"date-parts":[[2010,6,2]],"date-time":"2010-06-02T14:50:14Z","timestamp":1275490214000},"page":"274-297","source":"Crossref","is-referenced-by-count":18,"title":["Graphical Congestion Games"],"prefix":"10.1007","volume":"61","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Angelo","family":"Fanelli","sequence":"additional","affiliation":[]},{"given":"Michele","family":"Flammini","sequence":"additional","affiliation":[]},{"given":"Luca","family":"Moscardelli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,6,3]]},"reference":[{"issue":"1","key":"9417_CR1","doi-asserted-by":"crossref","first-page":"77","DOI":"10.4086\/toc.2008.v004a004","volume":"4","author":"E. Anshelevich","year":"2008","unstructured":"Anshelevich, E., Dasgupta, A., Tardos, \u00c9., Wexler, T.: Near-optimal network design with selfish agents. Theory Comput. 4(1), 77\u2013109 (2008)","journal-title":"Theory Comput."},{"key":"9417_CR2","doi-asserted-by":"crossref","unstructured":"Ashlagi, I., Krysta, P., Tennenholtz, M.: Social context games. In: WINE, pp. 675\u2013683 (2008)","DOI":"10.1007\/978-3-540-92185-1_73"},{"key":"9417_CR3","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/1060590.1060599","volume-title":"STOC","author":"B. Awerbuch","year":"2005","unstructured":"Awerbuch, B., Azar, Y., Epstein, A.: Large the price of routing unsplittable flow. In: Gabow, H.N., Fagin, R. (eds.) STOC, pp. 57\u201366. ACM, New York (2005)"},{"key":"9417_CR4","first-page":"103","volume-title":"ACM Conference on Electronic Commerce","author":"M. Babaioff","year":"2007","unstructured":"Babaioff, M., Kleinberg, R., Papadimitriou, C.H.: Congestion games with malicious players. In: MacKie-Mason, J.K., Parkes, D.C., Resnick, P. (eds.) ACM Conference on Electronic Commerce, pp.\u00a0103\u2013112. ACM, New York (2007)"},{"key":"9417_CR5","first-page":"746","volume-title":"SODA","author":"R. Beier","year":"2004","unstructured":"Beier, R., Czumaj, A., Krysta, P., V\u00f6cking, B.: Computing equilibria for congestion games with (im)perfect information. In: Munro, J.I. (ed.) SODA, pp. 746\u2013755. SIAM, Philadelphia (2004)"},{"issue":"3","key":"9417_CR6","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1016\/j.tcs.2009.10.007","volume":"411","author":"V. Bil\u00f2","year":"2010","unstructured":"Bil\u00f2, V., Fanelli, A., Flammini, M., Moscardelli, L.: When ignorance helps: Graphical multicast cost sharing games. Theor. Comput. Sci. 411(3), 660\u2013671 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9417_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/11786986_28","volume-title":"ICALP (1)","author":"I. Caragiannis","year":"2006","unstructured":"Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 4051, pp. 311\u2013322. Springer, Berlin (2006)"},{"key":"9417_CR8","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1145\/1386790.1386816","volume-title":"ACM Conference on Electronic Commerce","author":"P.-A. Chen","year":"2008","unstructured":"Chen, P.-A., Kempe, D.: Altruism, selfishness, and spite in traffic routing. In: Fortnow, L., Riedl, J., Sandholm, T. (eds.) ACM Conference on Electronic Commerce, pp.\u00a0140\u2013149. ACM, New York (2008)"},{"key":"9417_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/11561071_8","volume-title":"ESA","author":"G. Christodoulou","year":"2005","unstructured":"Christodoulou, G., Koutsoupias, E.: On the price of anarchy and stability of correlated equilibria of linear congestion games. In: Brodal, G.S., Leonardi, S. (eds.) ESA. Lecture Notes in Computer Science, vol. 3669, pp. 59\u201370. Springer, Berlin (2005)"},{"key":"9417_CR10","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1060590.1060600","volume-title":"STOC","author":"G. Christodoulou","year":"2005","unstructured":"Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Gabow, H.N., Fagin, R. (eds.) STOC, pp. 67\u201373. ACM, New York (2005)"},{"key":"9417_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/11672142_28","volume-title":"STACS","author":"G. Christodoulou","year":"2006","unstructured":"Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. In: Durand, B., Thomas, W. (eds.) STACS. Lecture Notes in Computer Science, vol. 3884, pp. 349\u2013360. Springer, Berlin (2006)"},{"issue":"36","key":"9417_CR12","doi-asserted-by":"crossref","first-page":"3327","DOI":"10.1016\/j.tcs.2009.01.005","volume":"410","author":"G. Christodoulou","year":"2009","unstructured":"Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. Theor. Comput. Sci. 410(36), 3327\u20133336 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9417_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/11496915_13","volume-title":"IPCO","author":"J.R. Correa","year":"2005","unstructured":"Correa, J.R., Schulz, A.S., Stier Moses, N.E.: On the inefficiency of equilibria in congestion games. In: J\u00fcnger, M., Kaibel, V. (eds.) IPCO. Lecture Notes in Computer Science, vol. 3509, pp. 167\u2013181. Springer, Berlin (2005)"},{"key":"9417_CR14","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: Babai, L. (ed.) STOC, pp. 604\u2013612. ACM, New York (2004)"},{"key":"9417_CR15","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1023\/A:1004991825894","volume":"42","author":"G. Facchini","year":"1997","unstructured":"Facchini, G., van Megen, F., Borm, P., Tijs, S.: Congestion models and weighted Bayesian potential games. Theory Decis. 42, 193\u2013206 (1997)","journal-title":"Theory Decis."},{"issue":"2\u20133","key":"9417_CR16","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/j.tcs.2005.09.024","volume":"348","author":"D. Fotakis","year":"2005","unstructured":"Fotakis, D., Kontogiannis, S.C., Spirakis, P.G.: Selfish unsplittable flows. Theor. Comput. Sci. 348(2\u20133), 226\u2013239 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9417_CR17","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00224-007-9015-8","volume":"42","author":"M. Gairing","year":"2008","unstructured":"Gairing, M., Monien, B., Tiemann, K.: Selfish routing with incomplete information. Theory Comput. Syst. 42(1), 91\u2013130 (2008)","journal-title":"Theory Comput. Syst."},{"key":"9417_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9417_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1066","DOI":"10.1007\/11600930_107","volume-title":"WINE","author":"D. Garg","year":"2005","unstructured":"Garg, D., Narahari, Y.: Price of anarchy of network routing games with incomplete information. In: Deng, X., Ye, Y. (eds.) WINE. Lecture Notes in Computer Science, vol. 3828, pp. 1066\u20131075. Springer, Berlin (2005)"},{"key":"9417_CR20","volume-title":"IPDPS","author":"C. Georgiou","year":"2006","unstructured":"Georgiou, C., Pavlides, T., Philippou A.: Network uncertainty in selfish routing. In: IPDPS. IEEE Press, New York (2006)"},{"key":"9417_CR21","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1287\/mnsc.14.3.159","volume":"14","author":"J.C. Harsanyi","year":"1967","unstructured":"Harsanyi, J.C.: Games with incomplete information played by Bayesian players, i. Manag. Sci. 14, 159\u2013182 (1967)","journal-title":"Manag. Sci."},{"key":"9417_CR22","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1287\/mnsc.14.5.320","volume":"14","author":"J.C. Harsanyi","year":"1967","unstructured":"Harsanyi, J.C.: Games with incomplete information played by Bayesian players, ii. Manag. Sci. 14, 320\u2013332 (1967)","journal-title":"Manag. Sci."},{"key":"9417_CR23","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1287\/mnsc.14.3.159","volume":"14","author":"J.C. Harsanyi","year":"1967","unstructured":"Harsanyi, J.C.: Games with incomplete information played by Bayesian players, iii. Manag. Sci. 14, 468\u2013502 (1967)","journal-title":"Manag. Sci."},{"key":"9417_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01737554","volume":"21","author":"J.C. Harsanyi","year":"1973","unstructured":"Harsanyi, J.C.: Games with randomly disturbed payoffs. Int. J. Game Theory 21, 1\u201323 (1973)","journal-title":"Int. J. Game Theory"},{"key":"9417_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-3-642-04128-0_16","volume-title":"ESA","author":"M. Hoefer","year":"2009","unstructured":"Hoefer, M., Skopalik, A.: Altruism in atomic congestion games. In: Fiat, A., Sanders, P. (eds.) ESA, Lecture Notes in Computer Science, vol.\u00a05757, pp.\u00a0179\u2013189. Springer, Berlin (2009)"},{"key":"9417_CR26","first-page":"253","volume-title":"UAI","author":"M.J. Kearns","year":"2001","unstructured":"Kearns, M.J., Littman, M.L., Singh, S.P.: Graphical models for game theory. In: Breese, J.S., Koller, D. (eds.) UAI, pp. 253\u2013260. Morgan Kaufmann, San Mateo (2001)"},{"key":"9417_CR27","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: The small-world phenomenon: an algorithm perspective. In: STOC, pp.\u00a0163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"9417_CR28","first-page":"431","volume-title":"NIPS","author":"J.M. Kleinberg","year":"2001","unstructured":"Kleinberg, J.M.: Small-world phenomena and the dynamics of information. In: Dietterich, T.G., Becker, S., Ghahramani, Z. (eds.) NIPS, pp. 431\u2013438. MIT Press, Cambridge (2001)"},{"key":"9417_CR29","first-page":"3","volume":"37","author":"J.M. Kleinberg","year":"2004","unstructured":"Kleinberg, J.M.: The small-world phenomenon and decentralized search. SIAM News 37, 3 (2004)","journal-title":"SIAM News"},{"issue":"2","key":"9417_CR30","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"E. Koutsoupias","year":"2009","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65\u201369 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"9417_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/978-3-540-74456-6_54","volume-title":"MFCS","author":"E. Koutsoupias","year":"2007","unstructured":"Koutsoupias, E., Panagopoulou, P.N., Spirakis, P.G.: Selfish load balancing under partial knowledge. In: Kucera, L., Kucera, A. (eds.) MFCS. Lecture Notes in Computer Science, vol. 4708, pp. 609\u2013620. Springer, Berlin (2007)"},{"key":"9417_CR32","unstructured":"Kukushkin, N.S. Congestion games revisited. In: Game Theory and Information, EconWPA (2004)"},{"key":"9417_CR33","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1006\/game.1996.0027","volume":"13","author":"I. Milchtaich","year":"1996","unstructured":"Milchtaich, I.: Congestion games with player-specific payoff functions. Games Econ. Behav. 13, 111\u2013124 (1996)","journal-title":"Games Econ. Behav."},{"issue":"2","key":"9417_CR34","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J.F. Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"9417_CR35","doi-asserted-by":"crossref","unstructured":"Nash, J.F. Equilibrium points in n-person games. In: Proceedings of the National Academy of Sciences, vol.\u00a036, pp.\u00a048\u201349 (1950)","DOI":"10.1073\/pnas.36.1.48"},{"key":"9417_CR36","doi-asserted-by":"crossref","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. Int. J. Game Theory 2, 65\u201367 (1973)","journal-title":"Int. J. Game Theory"},{"key":"9417_CR37","doi-asserted-by":"crossref","unstructured":"Roth, A.: The price of malice in linear congestion games. In: WINE, pp.\u00a0118\u2013125 (2008)","DOI":"10.1007\/978-3-540-92185-1_20"},{"issue":"2","key":"9417_CR38","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T. Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? J. ACM 49(2), 236\u2013259 (2002)","journal-title":"J. ACM"},{"issue":"2","key":"9417_CR39","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/j.geb.2003.06.004","volume":"47","author":"T. Roughgarden","year":"2004","unstructured":"Roughgarden, T., Tardos, \u00c9.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econ. Behav. 47(2), 389\u2013403 (2004)","journal-title":"Games Econ. Behav."},{"issue":"1","key":"9417_CR40","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00453-006-1211-4","volume":"47","author":"S. Suri","year":"2007","unstructured":"Suri, S., T\u00f3th, C.D., Zhou, Y.: Selfish load balancing and atomic congestion games. Algorithmica 47(1), 79\u201396 (2007)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9417-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9417-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9417-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T11:30:18Z","timestamp":1685619018000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9417-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,3]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9417"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9417-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,3]]}}}