Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria

Details Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria

2009-07-23

arxiv.org/abs/0907.4130v1

Computer Science

Computer Science and Game Theory

Scientific paper

It is a common belief that computing a market equilibrium in Fisher's spending model is easier than computing a market equilibrium in Arrow-Debreu's exchange model. This belief is built on the fact that we have more algorithmic success in Fisher equilibria than Arrow-Debreu equilibria. For example, a Fisher equilibrium in a Leontief market can be found in polynomial time, while it is PPAD-hard to compute an approximate Arrow-Debreu equilibrium in a Leontief market. In this paper, we show that even when all the utilities are additively separable, piecewise-linear, and concave functions, finding an approximate equilibrium in Fisher's model is complete in PPAD. Our result solves a long-term open question on the complexity of market equilibria. To the best of our knowledge, this is the first PPAD-completeness result for Fisher's model.

Affiliated with

Also associated with

No associations

Rating

Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-355430