Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
复制标题
用可加分离的公用事业解决市场中阿罗-德布鲁均衡的复杂性
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
Xi Chen;Decheng Dai;Ye Du;S. Teng
我们证明，即使所有交易者都使用可分离的，分段线性和凹入的实用程序功能，计算箭头市场平衡的问题也是PPAD票房。实际上，我们的证明表明，除非PPAD中的每个问题在多项式时间内都可以解决，否则这个市场平衡问题没有完全多项式时间近似方案。
We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility functions. In fact, our proof shows that this market-equilibrium problem does not have a fully polynomial-time approximation scheme, unless every problem in PPAD is solvable in polynomial time.