期刊
JOURNAL OF THE ACM
卷 58, 期 3, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1970392.1970394
关键词
Algorithms; Economics; Theory; Market equilibria; piecewise-linear utilities; Arrow-Debreu market; Fisher market; PPAD
类别
资金
- NSF [CCF-0728640, CCF-0914732, CCF-0728736, CCF-1017955]
- ONR [N000140910755]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1017955, 914732] Funding Source: National Science Foundation
We consider Fisher and Arrow-Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be written using polynomially many bits. There is no simple necessary and sufficient condition for the existence of an equilibrium: The problem of checking for existence of an equilibrium is NP-complete for both market models; the same holds for existence of an epsilon-approximate equilibrium, for epsilon = O(n(-5)). Under standard (mild) sufficient conditions, the problem of finding an exact equilibrium is in PPAD for both market models. Finally, building on the techniques of Chen et al. [2009a] we prove that under these sufficient conditions, finding an equilibrium for Fisher markets is PPAD-hard.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据