Lipschitz Continuity and Approximate Equilibria
Lipschitz Continuity and Approximate Equilibria
复制标题
Lipschitz 连续性和近似平衡
DOI：
10.1007/s00453-020-00709-3
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
P. Spirakis
中科院分区：
文献类型：
--
作者：
Argyrios Deligkas;John Fearnley;P. Spirakis
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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_1$$\end{document} and L22\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_2^2$$\end{document} 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.
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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_1$$\end{document} and L22\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_2^2$$\end{document} 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.
影响因子：
1.1
作者：
Czumaj A
通讯作者：
Czumaj A
DOI：
--
发表时间：
2018
期刊：
--
影响因子：
--
作者：
A. Deligkas
通讯作者：
A. Deligkas
有充分支持的纳什均衡近似低于三分之二
影响因子：
1.1
作者：
Fearnley J
通讯作者：
Fearnley J