Lipschitz Continuity and Approximate Equilibria

Deligkas, Argyrios, Fearnley, John and Spirakis, Paul ORCID: 0000-0001-5396-3749 (2020) Lipschitz Continuity and Approximate Equilibria. In: Symposium on Algorithmic Game Theory (SAGT), 2016-9-19 - 2016-9-21, Liverpool UK.

Text SAGT_2016_paper_23.pdf - Author Accepted Manuscript Download (181kB)

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>

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Approximate equilibria, Lipschitz games, Penalty games, Biased games
Depositing User:	Symplectic Admin
Date Deposited:	26 Sep 2016 08:49
Last Modified:	19 Jan 2023 07:34
DOI:	10.1007/s00453-020-00709-3
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3002085