HackerPapers

arXiv:0904.0644cs.CC

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.GTComputer Science and Game Theory

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Sep 2015 to Sep 2015.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Economics Has a Math Problem 1 comment

    • Actually, calculating equilibrium prices of markets is PPAD-hard (similar to NP-hard, but not quite) in general. See for example http://arxiv.org/pdf/0904.0644.pdf

      HermelView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.