{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T16:14:08Z","timestamp":1686586448975},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,5,16]],"date-time":"2015-05-16T00:00:00Z","timestamp":1431734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s10878-015-9898-2","type":"journal-article","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T06:26:21Z","timestamp":1431671181000},"page":"1036-1051","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the performance of mildly greedy players in cut games"],"prefix":"10.1007","volume":"32","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Mauro","family":"Paladini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,5,16]]},"reference":[{"issue":"6","key":"9898_CR1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1455248.1455249","volume":"55","author":"H Ackermann","year":"2008","unstructured":"Ackermann H, R\u00f6glin H, V\u00f6cking B (2008) On the impact of combinatorial structure on congestion games. J ACM 55(6):25","journal-title":"J ACM"},{"key":"9898_CR2","unstructured":"Anshelevich E, Caskurlu B (2007) Exact and approximate equilibria for optimal group network formation. In: Proceedings of the 17th annual symposium on algorithms (ESA), LNCS 5757, Springer, pp 239\u2013250"},{"key":"9898_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch B, Azar Y, Epstein A, Mirrokni VS, Skopalik A (2008) Fast convergence to nearly optimal solutions in potential games. In: Proceedings of the 9th ACM conference on electronic commerce (EC), ACM Press, pp 264\u2013273","DOI":"10.1145\/1386790.1386832"},{"key":"9898_CR4","doi-asserted-by":"crossref","unstructured":"Bhalgat A, Chakraborty T, Khanna S (2009) Nash dynamics in congestion games with similar resources. In: Proceedings of the 5th international workshop on internet and network economics (WINE), LNCS 5929, Springer, pp 362\u2013373","DOI":"10.1007\/978-3-642-10841-9_33"},{"key":"9898_CR5","doi-asserted-by":"crossref","unstructured":"Bhalgat A, Chakraborty T, Khanna S (2010) Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. In: Proceedings of the 11th ACM conference on electronic commerce (EC), ACM Press, pp 73\u201382","DOI":"10.1145\/1807342.1807353"},{"key":"9898_CR6","unstructured":"Bil\u00f2 V (2012) A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. In: Proceedings of the 10th workshop on approximation and online algorithms (WAOA), LNCS 7846, Springer, pp 215\u2013228"},{"issue":"1","key":"9898_CR7","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/s00224-010-9309-0","volume":"49","author":"V Bil\u00f2","year":"2011","unstructured":"Bil\u00f2 V, Fanelli A, Flammini M, Moscardelli L (2011) Performance of one-round walks in linear congestion games. Theory Comput Syst 49(1):24\u201345","journal-title":"Theory Comput Syst"},{"issue":"1","key":"9898_CR8","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/s00224-013-9529-1","volume":"56","author":"V Bil\u00f2","year":"2015","unstructured":"Bil\u00f2 V, Flammini M, Monaco G, Moscardelli L (2015) Some anomalies of farsighted strategic behavior. Theory Comput Syst 56(1):156\u2013180","journal-title":"Theory Comput Syst"},{"key":"9898_CR9","doi-asserted-by":"crossref","unstructured":"Caragiannis I, Fanelli A, Gravin N, Skopalik A (2011) Efficient computation of approximate pure Nash equilibria in congestion games. In: Proceedings of the IEEE 52nd annual symposium on foundations of computer science (FOCS), IEEE computer society, pp 532\u2013541","DOI":"10.1109\/FOCS.2011.50"},{"key":"9898_CR10","doi-asserted-by":"crossref","unstructured":"Caragiannis I, Fanelli A, Gravin N, Skopalik A (2012) Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. In Proceedings of the ACM conference on electronic commerce (EC), ACM Press pp 284\u2013301","DOI":"10.1145\/2229012.2229036"},{"issue":"3","key":"9898_CR11","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/s00453-010-9427-8","volume":"61","author":"I Caragiannis","year":"2011","unstructured":"Caragiannis I, Flammini M, Kaklamanis C, Kanellopoulos P, Moscardelli L (2011) Tight bounds for selfish and greedy load balancing. Algorithmica 61(3):606\u2013637","journal-title":"Algorithmica"},{"issue":"16\u201318","key":"9898_CR12","doi-asserted-by":"crossref","first-page":"1855","DOI":"10.1016\/j.tcs.2010.02.005","volume":"411","author":"J Cardinal","year":"2010","unstructured":"Cardinal J, Hoefer M (2010) Non-cooperative facility location and covering games. Theoret Comput Sci 411(16\u201318):1855\u20131876","journal-title":"Theoret Comput Sci"},{"key":"9898_CR13","doi-asserted-by":"crossref","unstructured":"Charikar M, Karloff HJ, Mathieu C, Naor J, Saks ME (2008) Online multicast with egalitarian cost sharing. In Proceedings of the 20th annual ACM symposium on parallelism in algorithms and architectures (SPAA), ACM Press, pp 70\u201376","DOI":"10.1145\/1378533.1378544"},{"issue":"6","key":"9898_CR14","doi-asserted-by":"crossref","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 (2007) Non-cooperative multicast and facility location games. IEEE J Sel Areas Commun 25(6):1193\u20131206","journal-title":"IEEE J Sel Areas Commun"},{"issue":"3","key":"9898_CR15","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen X, Deng X, Teng S (2009) Settling the complexity of computing two-player Nash equilibria. J ACM 56(3):14","journal-title":"J ACM"},{"issue":"2","key":"9898_CR16","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.geb.2009.05.004","volume":"71","author":"S Chien","year":"2001","unstructured":"Chien S, Sinclair A (2001) Convergence to approximate Nash equilibria in congestion games. Games Econ Behav 71(2):315\u2013327","journal-title":"Games Econ Behav"},{"issue":"1","key":"9898_CR17","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/s00453-010-9449-2","volume":"61","author":"G Christodoulou","year":"2011","unstructured":"Christodoulou G, Koutsoupias E, Spirakis PG (2011) On the performance of approximate equilibria in congestion games. Algorithmica 61(1):116\u2013140","journal-title":"Algorithmica"},{"key":"9898_CR18","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2012.02.033","volume":"438","author":"G Christodoulou","year":"2012","unstructured":"Christodoulou G, Mirrokni VS, Sidiropoulos A (2012) Convergence and approximation in potential games. Theoret Comput Sci 438:13\u201327","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"9898_CR19","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1145\/1461928.1461951","volume":"52","author":"K Daskalakis","year":"2009","unstructured":"Daskalakis K, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. Commun ACM 52(2):89\u201397","journal-title":"Commun ACM"},{"key":"9898_CR20","unstructured":"Daskalakis K, Papadimitriou CH (2005) Three-player games are hard. Electronic colloquium on computational complexity (ECCC), 139"},{"key":"9898_CR21","doi-asserted-by":"crossref","unstructured":"Daskalakis C, Papadimitriou CH (2007) Computing equilibria in anonymous games. In Proceedings of the 48th annual IEEE symposium on foundations of computer science (FOCS), IEEE computer society, pp 83\u201393","DOI":"10.1109\/FOCS.2007.24"},{"key":"9898_CR22","doi-asserted-by":"crossref","unstructured":"Fabrikant A, Papadimitriou CH, Talwar K (2004) The complexity of pure Nash equilibria. In Proceedings of the 36th annual ACM symposium on theory of computing (STOC), ACM Press, pp 604\u2013612","DOI":"10.1145\/1007352.1007445"},{"issue":"3","key":"9898_CR23","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/2229163.2229169","volume":"8","author":"A Fanelli","year":"2012","unstructured":"Fanelli A, Flammini M, Moscardelli L (2012) The speed of convergence in congestion games under best-response dynamics. ACM Trans Algorithms 8(3):25","journal-title":"ACM Trans Algorithms"},{"issue":"5","key":"9898_CR24","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00446-011-0145-5","volume":"24","author":"A Fanelli","year":"2011","unstructured":"Fanelli A, Moscardelli L (2011) On best-response dynamics in weighted congestion games with polynomial delays. Distrib Comput 24(5):245\u2013254","journal-title":"Distrib Comput"},{"key":"9898_CR25","doi-asserted-by":"crossref","unstructured":"Goemans MX, Mirrokni VS, Vetta A (2005) Sink equilibria and convergence. In Proceedings of the 46th annual IEEE symposium on foundations of computer science (FOCS), IEEE computer society, pp 142\u2013154","DOI":"10.1109\/SFCS.2005.68"},{"key":"9898_CR26","doi-asserted-by":"crossref","unstructured":"Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. In Proceedings of the 16th international symposium on theoretical aspects of computer science (STACS), LNCS 1653, Springer, pp 404\u2013413","DOI":"10.1007\/3-540-49116-3_38"},{"key":"9898_CR27","doi-asserted-by":"crossref","unstructured":"Mirrokni VS, Vetta A (2004) Convergence issues in competitive games. In Proceedings of the 7th international workshop on approximation algorithms for combinatorial optimization problems (APPROX), LNCS 3122, Springer, pp 183\u2013194","DOI":"10.1007\/978-3-540-27821-4_17"},{"key":"9898_CR28","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"RW Rosenthal","year":"1973","unstructured":"Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2:65\u201367","journal-title":"Int J Game Theory"},{"key":"9898_CR29","doi-asserted-by":"crossref","unstructured":"Skopalik A, V\u00f6cking B (2008) Inapproximability of pure Nash equilibria. In Proceedings of the 40th annual ACM symposium on theory of computing (STOC), ACM Press, pp 355\u2013364","DOI":"10.1145\/1374376.1374428"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9898-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-015-9898-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9898-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9898-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:23:26Z","timestamp":1559262206000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-015-9898-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,16]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["9898"],"URL":"https:\/\/doi.org\/10.1007\/s10878-015-9898-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,16]]}}}