Lipschitz Continuity and Approximate Equilibria
- PDF / 3,555,215 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 171 Views
Lipschitz Continuity and Approximate Equilibria Argyrios Deligkas1 · John Fearnley2 · Paul Spirakis2,3 Received: 1 March 2017 / Accepted: 30 March 2020 © The Author(s) 2020
Abstract 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 L1 and L22 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. Keywords Approximate equilibria · Lipschitz games · Penalty games · Biased games
Argyrios Deligkas and John Fearnley are supported by EPSRC Grant EP/L011018/1. The work of Paul Spirakis was supported partially by the Algorithmic Game Theory Project, (co-financed by the European Union European Social Fund) and by Greek National Funds, under the Research Program THALES. Also by the EU ERC Project ALGAME. * John Fearnley [email protected] 1
Industrial Engineering and Management, Technion, Haifa, Israel
2
Department of Computer Science, University of Liverpool, Liverpool, UK
3
Research Academic Computer Technology Institute (CTI), Patras, Greece
13
Vol.:(0123456789)
Algorithmica
1 Introduction Nash equilibria [29] are the central solution concept in game theory. However, recent advances have shown that computing an exact Nash equilibrium is 𝙿𝙿𝙰𝙳 -complete [8, 10], and so there are unlikely to be polynomial time algorithms for this problem. The hardness of computing exact equilibria has lead to the study of approximate equilibria: while an exact equilibrium requires that all players have no incentive to deviate from their current strategy, an 𝜖-approximate equilibrium requires only that their incentive to deviate is less than 𝜖. A fruitful line of work has developed studying the best approximations that can be found in polynomial-time for bimatrix games, which are two-player strategic form games. There, after a number of papers [5, 11, 12], the best known algorithm was given by Tsaknakis and Spirakis [32], who provide a polynomial time algorithm that finds a 0.3393-equilibrium. The existence of an FPTAS was ruled out by Chen et al. [8] unless 𝙿𝙿𝙰𝙳 = 𝙿 . Recently, Rubinstein [31] proved that there is no PTAS for the problem, assuming the Exponential Time Hypothesis for 𝙿𝙿𝙰𝙳 . However, there is a quasi-polynom
Data Loading...
