{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:17Z","timestamp":1759638617861,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T00:00:00Z","timestamp":1587772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L011018\/1"],"award-info":[{"award-number":["EP\/L011018\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study games with continuous action spaces and non-linear payoff functions. Our key insight is that Lipschitz continuity of the payoff function allows us to provide algorithms for finding approximate equilibria in these games. We begin by studying Lipschitz games, which encompass, for example, all concave games with Lipschitz continuous payoff functions. We provide an efficient algorithm for computing approximate equilibria in these games. Then we turn our attention to penalty games, which encompass biased games and games in which players take risk into account. Here we show that if the penalty function is Lipschitz continuous, then we can provide a quasi-polynomial time approximation scheme. Finally, we study distance biased games, where we present simple strongly polynomial time algorithms for finding best responses in<jats:inline-formula><jats:alternatives><jats:tex-math>$$L_1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>L<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:tex-math>$$L_2^2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msubsup><mml:mi>L<\/mml:mi><mml:mn>2<\/mml:mn><mml:mn>2<\/mml:mn><\/mml:msubsup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>biased games, and then use these algorithms to provide strongly polynomial algorithms that find 2\/3 and 5\/7 approximate equilibria for these norms, respectively.<\/jats:p>","DOI":"10.1007\/s00453-020-00709-3","type":"journal-article","created":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T03:57:30Z","timestamp":1587787050000},"page":"2927-2954","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Lipschitz Continuity and Approximate Equilibria"],"prefix":"10.1007","volume":"82","author":[{"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0791-4342","authenticated-orcid":false,"given":"John","family":"Fearnley","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,25]]},"reference":[{"issue":"2","key":"709_CR1","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1287\/moor.1120.0557","volume":"38","author":"Y Azrieli","year":"2013","unstructured":"Azrieli, Y., Shmaya, E.: Lipschitz games. Math. Oper. Res. 38(2), 350\u2013357 (2013)","journal-title":"Math. Oper. Res."},{"key":"709_CR2","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.geb.2013.04.007","volume":"81","author":"Y Babichenko","year":"2013","unstructured":"Babichenko, Y.: Best-reply dynamics in large binary-choice anonymous games. Games Econ. Behav. 81, 130\u2013144 (2013)","journal-title":"Games Econ. Behav."},{"key":"709_CR3","doi-asserted-by":"crossref","unstructured":"Babichenko, Y., Barman, S., Peretz, R.: Simple approximate equilibria in large games. In: Proceedings of EC, pp. 753\u2013770 (2014)","DOI":"10.1145\/2600057.2602873"},{"key":"709_CR4","doi-asserted-by":"crossref","unstructured":"Barman, S.: Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Caratheodory\u2019s theorem. In: Proceedings of STOC 2015, pp. 361\u2013369 (2015)","DOI":"10.1145\/2746539.2746566"},{"issue":"1","key":"709_CR5","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.tcs.2009.09.023","volume":"411","author":"H Bosse","year":"2010","unstructured":"Bosse, H., Byrka, J., Markakis, E.: New algorithms for approximate Nash equilibria in bimatrix games. Theor. Comput. Sci. 411(1), 164\u2013173 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"709_CR6","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kurokawa, D., Procaccia, A.D.: Biased games. In: Proceedings of AAAI, pp. 609\u2013615 (2014)","DOI":"10.1609\/aaai.v28i1.8831"},{"issue":"2","key":"709_CR7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1006\/obhd.1999.2841","volume":"79","author":"GB Chapman","year":"1999","unstructured":"Chapman, G.B., Johnson, E.J.: Anchoring, activation, and the construction of values. Organ. Behav. Hum. Decis. Process. 79(2), 115\u2013153 (1999)","journal-title":"Organ. Behav. Hum. Decis. Process."},{"issue":"3","key":"709_CR8","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 14:1\u201314:57 (2009)","journal-title":"J. ACM"},{"issue":"3","key":"709_CR9","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1007\/s00453-018-0465-y","volume":"81","author":"A Czumaj","year":"2019","unstructured":"Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J., Jurdzinski, M., Savani, R.: Distributed methods for computing approximate equilibria. Algorithmica 81(3), 1205\u20131231 (2019)","journal-title":"Algorithmica"},{"issue":"1","key":"709_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"key":"709_CR11","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate Nash equilibria. In: Proceedings of EC, pp. 355\u2013358 (2007)","DOI":"10.1145\/1250910.1250962"},{"issue":"17","key":"709_CR12","doi-asserted-by":"publisher","first-page":"1581","DOI":"10.1016\/j.tcs.2008.12.031","volume":"410","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: A note on approximate Nash equilibria. Theor. Comput. Sci. 410(17), 1581\u20131588 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"709_CR13","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.jet.2014.02.002","volume":"156","author":"C Daskalakis","year":"2015","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Approximate Nash equilibria in anonymous games. J. Econ. Theory 156, 207\u2013245 (2015)","journal-title":"J. Econ. Theory"},{"issue":"C","key":"709_CR14","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1016\/j.jet.2015.02.001","volume":"157","author":"J Deb","year":"2015","unstructured":"Deb, J., Kalai, E.: Stability in large Bayesian games with heterogeneous players. J. Econ. Theory 157(C), 1041\u20131055 (2015)","journal-title":"J. Econ. Theory"},{"key":"709_CR15","unstructured":"Deligkas, A., Fearnley, J., Melissourgos, T., Spirakis, P.G.: Approximating the existential theory of the reals. In: Web and Internet Economics\u201414th International Conference, WINE 2018, Oxford, UK, December 15\u201317, 2018, Proceedings, pp. 126\u2013139 (2018)"},{"key":"709_CR16","unstructured":"Deligkas, A., Fearnley, J., Melissourgos, T., Spirakis, P.G.: Computing exact solutions of consensus halving and the Borsuk\u2013Ulam theorem. CoRR, arXiv:1903.03101 (2019)"},{"issue":"2","key":"709_CR17","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s00453-015-0078-7","volume":"77","author":"A Deligkas","year":"2017","unstructured":"Deligkas, A., Fearnley, J., Savani, R., Spirakis, P.: Computing approximate Nash equilibria in polymatrix games. Algorithmica 77(2), 487\u2013514 (2017)","journal-title":"Algorithmica"},{"issue":"6","key":"709_CR18","doi-asserted-by":"publisher","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531\u20132597 (2010)","journal-title":"SIAM J. Comput."},{"key":"709_CR19","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Goldberg, P.W., Savani, R., S\u00f8rensen, T.B.: Approximate well-supported Nash equilibria below two-thirds. In: SAGT, pp. 108\u2013119 (2012)","DOI":"10.1007\/978-3-642-33996-7_10"},{"key":"709_CR20","doi-asserted-by":"crossref","unstructured":"Fiat, A., Papadimitriou, C.H.: When the players are not expectation maximizers. In: SAGT, pp. 1\u201314 (2010)","DOI":"10.1007\/978-3-642-16170-4_1"},{"key":"709_CR21","unstructured":"Ganzfried, S., Sandholm, T.: Game theory-based opponent modeling in large imperfect-information games. In: 10th International Conference on Autonomous Agents and Multiagent Systems\u2014Volume 2, AAMAS \u201911, pp. 533\u2013540 (2011)"},{"key":"709_CR22","doi-asserted-by":"crossref","unstructured":"Ganzfried, S., Sandholm, T.: Safe opponent exploitation. In: Proceedings of EC, EC \u201912, pp. 587\u2013604. ACM, New York (2012)","DOI":"10.1145\/2229012.2229056"},{"key":"709_CR23","first-page":"721","volume-title":"Advances in Neural Information Processing Systems","author":"M Johanson","year":"2008","unstructured":"Johanson, M., Zinkevich, M., Bowling, M.: Computing robust counter-strategies. In: Platt, J., Koller, D., Singer, Y., Roweis, S. (eds.) Advances in Neural Information Processing Systems, vol. 20, pp. 721\u2013728. Curran Associates, Inc., Red Hook (2008)"},{"issue":"2","key":"709_CR24","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/0749-5978(92)90015-Y","volume":"51","author":"D Kahneman","year":"1992","unstructured":"Kahneman, D.: Reference points, anchors, norms, and mixed feelings. Organ. Behav. Hum. Decis. Process. 51(2), 296\u2013312 (1992)","journal-title":"Organ. Behav. Hum. Decis. Process."},{"issue":"4","key":"709_CR25","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s00453-008-9227-6","volume":"57","author":"SC Kontogiannis","year":"2010","unstructured":"Kontogiannis, S.C., Spirakis, P.G.: Well supported approximate equilibria in bimatrix games. Algorithmica 57(4), 653\u2013667 (2010)","journal-title":"Algorithmica"},{"issue":"5","key":"709_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0041-5553(80)90098-1","volume":"20","author":"M Kozlov","year":"1980","unstructured":"Kozlov, M., Tarasov, S., Khachiyan, L.: The polynomial solvability of convex quadratic programming. USSR Comput. Math. Math. Phys. 20(5), 223\u2013228 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"709_CR27","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: EC, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"709_CR28","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2016.04.013","volume":"634","author":"M Mavronicolas","year":"2016","unstructured":"Mavronicolas, M., Monien, B.: The complexity of equilibria for risk-modeling valuations. Theor. Comput. Sci. 634, 67\u201396 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"709_CR29","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"issue":"3","key":"709_CR30","doi-asserted-by":"publisher","first-page":"520","DOI":"10.2307\/1911749","volume":"33","author":"JB Rosen","year":"1965","unstructured":"Rosen, J.B.: Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33(3), 520\u2013534 (1965)","journal-title":"Econometrica"},{"key":"709_CR31","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Settling the complexity of computing approximate two-player Nash equilibria. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 258\u2013265. IEEE (2016)","DOI":"10.1109\/FOCS.2016.35"},{"issue":"4","key":"709_CR32","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1080\/15427951.2008.10129172","volume":"5","author":"H Tsaknakis","year":"2008","unstructured":"Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate Nash equilibria. Internet Math. 5(4), 365\u2013382 (2008)","journal-title":"Internet Math."},{"issue":"4157","key":"709_CR33","doi-asserted-by":"publisher","first-page":"1124","DOI":"10.1126\/science.185.4157.1124","volume":"185","author":"A Tversky","year":"1974","unstructured":"Tversky, A., Kahneman, D.: Judgment under uncertainty: heuristics and biases. Science 185(4157), 1124\u20131131 (1974)","journal-title":"Science"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00709-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00709-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00709-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T08:03:19Z","timestamp":1666425799000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00709-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,25]]},"references-count":33,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["709"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00709-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,4,25]]},"assertion":[{"value":"1 March 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}