{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:08Z","timestamp":1740109268204,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,3,10]],"date-time":"2016-03-10T00:00:00Z","timestamp":1457568000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100009043","name":"University of Patras","doi-asserted-by":"publisher","award":["Caratheodory grant E.114"],"award-info":[{"award-number":["Caratheodory grant E.114"]}],"id":[{"id":"10.13039\/100009043","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0143-x","type":"journal-article","created":{"date-parts":[[2016,3,10]],"date-time":"2016-03-10T14:11:59Z","timestamp":1457619119000},"page":"1143-1158","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games"],"prefix":"10.1007","volume":"77","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Fanelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nick","family":"Gravin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,3,10]]},"reference":[{"key":"143_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Epstein, A., Mirrokni, V.\u00a0S., Skopalik, A.: Fast convergence to nearly optimal solutions in potential games. In: Proceedings of the 9th ACM Conference on Electronic Commerce (EC), pp. 264\u2013273 (2008)","DOI":"10.1145\/1386790.1386832"},{"issue":"1","key":"143_CR2","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/110821317","volume":"42","author":"M-F Balcan","year":"2013","unstructured":"Balcan, M.-F., Blum, A., Mansour, Y.: Circumventing the price of anarchy: leading dynamics to good behavior. SIAM J. Comput. 42(1), 230\u2013264 (2013)","journal-title":"SIAM J. Comput."},{"key":"143_CR3","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Chakraborty, T., Khanna, S.: Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games. In: Proceedings of the 11th ACM Conference on Electronic Commerce (EC), pp. 73\u201382 (2010)","DOI":"10.1145\/1807342.1807353"},{"key":"143_CR4","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Efficient computation of approximate pure Nash equilibria in congestion games. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 532\u2013541 (2011)","DOI":"10.1109\/FOCS.2011.50"},{"issue":"1","key":"143_CR5","doi-asserted-by":"crossref","first-page":"art. 2","DOI":"10.1145\/2614687","volume":"3","author":"I Caragiannis","year":"2015","unstructured":"Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. ACM Trans. Econ. Comput. 3(1), art. 2 (2015)","journal-title":"ACM Trans. Econ. Comput."},{"issue":"1","key":"143_CR6","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/2325713.2325718","volume":"11","author":"I Caragiannis","year":"2012","unstructured":"Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Computing approximate pure Nash equilibria in congestion games. SIGecom Exch. 11(1), 26\u201329 (2012)","journal-title":"SIGecom Exch."},{"issue":"2","key":"143_CR7","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.geb.2009.05.004","volume":"71","author":"S Chien","year":"2011","unstructured":"Chien, S., Sinclair, A.: Convergence to approximate Nash equilibria in congestion games. Games Econ. Behav. 71(2), 315\u2013327 (2011)","journal-title":"Games Econ. Behav."},{"key":"143_CR8","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, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. Theor. Comput. Sci. 438, 13\u201327 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"143_CR9","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.\u00a0H., Talwar, K.: The complexity of pure nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 604\u2013612 (2004)","DOI":"10.1145\/1007352.1007445"},{"issue":"6","key":"143_CR10","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum sut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"4","key":"143_CR11","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J Hastad","year":"2001","unstructured":"Hastad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"143_CR12","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37, 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"143_CR13","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On the hardness of global and local approximation. In: Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 1097, Springer, pp. 88\u201399 (1996)","DOI":"10.1007\/3-540-61422-2_123"},{"key":"143_CR14","doi-asserted-by":"crossref","unstructured":"Krentel, M.W.: Structure in locally optimal solutions. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 216\u2013221 (1989)","DOI":"10.1109\/SFCS.1989.63481"},{"key":"143_CR15","volume-title":"Theoretical Aspects of Local Search. EATCS Monographs in Theoretical Computer Science","author":"W Michiels","year":"2007","unstructured":"Michiels, W., Aarts, E., Korst, J.: Theoretical Aspects of Local Search. EATCS Monographs in Theoretical Computer Science. Springer, New York (2007)"},{"key":"143_CR16","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1137\/S0097539703431007","volume":"33","author":"JB Orlin","year":"2004","unstructured":"Orlin, J.B., Punnen, A.P., Schulz, A.S.: Approximate local search in combinatorial optimization. SIAM J. Comput. 33, 1201\u20131214 (2004)","journal-title":"SIAM J. Comput."},{"key":"143_CR17","doi-asserted-by":"crossref","unstructured":"Piliouras, G., Nikolova, E., Shamma, J.S.: Risk sensitivity of price of anarchy under uncertainty. In: Proceedings of the 13th ACM Conference on Electronic Commerce (EC), pp. 715\u2013732 (2013)","DOI":"10.1145\/2492002.2482578"},{"key":"143_CR18","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1137\/S0097539793245350","volume":"24","author":"S Poljak","year":"1995","unstructured":"Poljak, S.: Integer linear programs and local search for max-cut. SIAM J. Comput. 24, 822\u2013839 (1995)","journal-title":"SIAM J. Comput."},{"key":"143_CR19","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"RW 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":"143_CR20","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/0220004","volume":"20","author":"AA Sch\u00e4ffer","year":"1991","unstructured":"Sch\u00e4ffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20, 56\u201387 (1991)","journal-title":"SIAM J. Comput."},{"key":"143_CR21","doi-asserted-by":"crossref","unstructured":"Skopalik, A., V\u00f6cking, B.: Inapproximability of pure Nash equilibria. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 355\u2013364 (2008)","DOI":"10.1145\/1374376.1374428"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0143-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0143-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0143-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0143-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:24Z","timestamp":1559072844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0143-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,10]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["143"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0143-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,3,10]]}}}