Lipschitz continuity and approximate equilibria

DOI10.1007/978-3-662-53354-3_2MaRDI QIDQ2819444zbMATH OpenOpenAlexFDO

Authors Argyrios Deligkas, John Fearnley, P. G. Spirakis

Publication date 29 September 2016

Published in Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.02023

zbMATH Keywords

approximate equilibria algorithmconcave gamesLipschitz continuity

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) 2-person games (91A05) Spaces of games (91A70)

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 $L_1$, $L_2^2$, and $L_{i}nfty$ biased games, and then use these algorithms to provide strongly polynomial algorithms that find $2/3$, $5/7$, and $2/3$ approximations for these norms, respectively.

Recommendations

• Lipschitz continuity and approximate equilibria
• PPAD-complete pure approximate Nash equilibria in Lipschitz games
• Lower bounds for the query complexity of equilibria in Lipschitz games
• Lipschitz games
• Correlated equilibria in continuous games: characterization and computation

Cites work

• A note on approximate Nash equilibria
• An optimization approach for approximate Nash equilibria
• Approximate Nash equilibria in anonymous games
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Best-reply dynamics in large binary-choice anonymous games
• Existence and Uniqueness of Equilibrium Points for Concave N-Person Games
• Lipschitz games
• New algorithms for approximate Nash equilibria in bimatrix games
• Non-cooperative games
• Settling the complexity of computing two-player Nash equilibria
• Stability in large Bayesian games with heterogeneous players
• The complexity of computing a Nash equilibrium
• When the players are not expectation maximizers

Cited in

(13)

• Equivalence between Wadge and Lipschitz determinacy
• Lipschitz continuity and approximate equilibria
• The Lipschitz constant of perturbed anonymous games
• Equilibrium computation in resource allocation games
• scientific article; zbMATH DE number 5657307 (Why is no real title available?)
• Lipschitz continuity of an approximate solution mapping to equilibrium problems
• scientific article; zbMATH DE number 2112021 (Why is no real title available?)
• scientific article; zbMATH DE number 786222 (Why is no real title available?)
• Lipschitz games
• Approximating the existential theory of the reals
• Approximating the existential theory of the reals
• PPAD-complete pure approximate Nash equilibria in Lipschitz games
• Smooth equilibrium measures and approximation

This page was built for publication: Lipschitz continuity and approximate equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819444)