The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points
The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points
复制标题
多人凹博弈和角谷不动点的计算复杂度
DOI：
10.1145/3580507.3597812
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Zampetakis, Manolis
中科院分区：
文献类型：
--
作者：
Papadimitriou, Christos;Vlatakis-Gkaragkounis, Emmanouil-Vasileios;Zampetakis, Manolis
角谷不动点定理是拓扑学中的一个基本定理，在博弈论和经济学中有许多应用。角谷的计算公式只存在于特殊情况下，并且限制性太强，无法用于约简。本文给出了角谷不动点定理的一般计算公式，并证明了它是PPAD-完全的。作为我们定理的应用，我们能够描述以下基本问题的计算复杂性：（1）凹博弈。由Debreu和罗森在20世纪50、60年代的著名著作中引入的凹人博弈在经济学和博弈论中有着重要的应用。我们的计算复杂性的特点，在这样的游戏中找到一个均衡。我们表明，这个问题的一般配方属于PPAD，找到一个平衡是PPAD硬，即使是一个相当有限的游戏这种：强凹的效用，可以表示为一个恒定的程度与轴对齐框约束的多元多项式。(2)瓦尔拉斯均衡使用角谷的不动点阿罗和德布鲁，我们解决了一个开放的问题有关的瓦尔拉斯定理的存在价格均衡在一般经济。关于瓦尔拉斯均衡的PPAD-困难性有很多结果，但PPAD中的包含性仅为分段线性效用所知。我们表明，一般凸效用的问题是在PPAD。沿着的方式，我们提供了一个Lipschitz连续版本的Berge的最大值定理，可能是独立的利益。
Kakutani's Fixed Point theorem is a fundamental theorem in topology with numerous applications in game theory and economics. Computational formulations of Kakutani exist only in special cases and are too restrictive to be useful in reductions. In this paper, we provide a general computational formulation of Kakutani's Fixed Point Theorem and we prove that it is PPAD-complete. As an application of our theorem we are able to characterize the computational complexity of the following fundamental problems: (1) Concave Games. Introduced by the celebrated works of Debreu and Rosen in the 1950s and 60s, concave-person games have found many important applications in Economics and Game Theory. We characterize the computational complexity of finding an equilibrium in such games. We show that a general formulation of this problem belongs to PPAD, and that finding an equilibrium is PPAD-hard even for a rather restricted games of this kind: strongly-concave utilities that can be expressed as multivariate polynomials of a constant degree with axis aligned box constraints. (2) Walrasian Equilibrium. Using Kakutani's fixed point Arrow and Debreu we resolve an open problem related to Walras's theorem on the existence of price equilibria in general economies. There are many results about the PPAD-hardness of Walrasian equilibria, but the inclusion in PPAD is only known for piecewise linear utilities. We show that the problem with general convex utilities is in PPAD. Along the way we provide a Lipschitz continuous version of Berge's maximum theorem that may be of independent interest.
登录
查看更多内容
影响因子：
1.3
作者：
Geanakoplos, J
通讯作者：
Geanakoplos, J
DOI：
--
发表时间：
1987
期刊：
影响因子：
--
作者：
G. G. Johnson
通讯作者：
G. G. Johnson
梯度下降的复杂度：CLS = PPAD ∩ PLS
DOI：
10.1145/3406325.3451052
发表时间：
2020
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
John Fearnley;P. Goldberg;Alexandros Hollender;Rahul Savani
通讯作者：
Rahul Savani
DOI：
--
发表时间：
1980
期刊：
21st Annual Symposium on Foundations of Computer Science (sfcs 1980)
影响因子：
--
作者：
R. Karp;C. Papadimitriou
通讯作者：
C. Papadimitriou