Conference proceeding
Market equilibrium via the excess demand function
Proceedings of the thirty-seventh annual ACM symposium on theory of computing, pp.74-83
STOC '05
05/22/2005
DOI: 10.1145/1060590.1060601
Abstract
We consider the problem of computing market equilibria and show three results. (i) For exchange economies satisfying weak gross substitutability we analyze a simple discrete version of tâtonnement, and prove that it converges to an approximate equilibrium in polynomial time. This is the first polynomial-time approximation scheme based on a simple atonnement process. It was only recently shown, using vastly more sophisticated techniques, that an approximate equilibrium for this class of economies is computable in polynomial time. (ii) For Fisher's model, we extend the frontier of tractability by developing a polynomial-time algorithm that applies well beyond the homothetic case and the gross substitutes case. (iii) For production economies, we obtain the first polynomial-time algorithms for computing an approximate equilibrium when the consumers' side of the economy satisfies weak gross substitutability and the producers' side is restricted to positive production.
Details
- Title: Subtitle
- Market equilibrium via the excess demand function
- Creators
- Bruno Codenotti - Toyota Technological Institute at ChicagoBenton McCune - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the thirty-seventh annual ACM symposium on theory of computing, pp.74-83
- Publisher
- ACM
- Series
- STOC '05
- DOI
- 10.1145/1060590.1060601
- ISSN
- 0737-8017
- Language
- English
- Date published
- 05/22/2005
- Academic Unit
- Computer Science
- Record Identifier
- 9984259435602771
Metrics
6 Record Views