The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results

ABSTRACT

The traditional model of market equilibrium supports impressive existence results, including the celebrated Arrow-Debreu Theorem. However, in this model, polynomial time algorithms for computing (or approximating) equilibria are known only for linear utility functions. We present a new, and natural, model of market equilibrium that not only admits existence and uniqueness results paralleling those for the traditional model but is also amenable to efficient algorithms.

REFERENCES

• 1: Aliprantis, Brown, and Burkinshaw. "Existence and Optimality of Competitive Equilibria", Springer-Verlag, 1990.
• 2: K. K. Arrow, and G. Debreu, "Existence of an Equilibrium for a Competitive Economy", Econometrica, Vol. 22, pp. 265--290, 1954.
• 3: G. Debreu. Economies with a finite set of equilibria Econometrica, 38:387--92, 1970.
• 4: N. R. Devanur, V. V. Vazirani. "Improved Approximation Scheme for Computing Arrow Debreu Prices in The Linear Case". In Proc. FSTTCS, 2003.
• 5: N. R. Devanur, V. V. Vazirani. "Algorithmic, Existence and Uniqueness Results for the Spending Constraint Model". Manuscript4 2003.
• 6: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 7: N. R. Devanur, C. H. Papadimitriou, A. Saberi, V. V. Vazirani. "Market Equilibrium via a Primal-Dual-Type Algorithm". Full version.
• 8: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509920]
• 9: E. Eisenberg and D. Gale. Consensus of subjective probabilities: The pari-mutuel method. Annals Of Mathematical Statistics, 30:165--168, 1959.
• 10: Rahul Garg , Sanjiv Kapoor, Auction algorithms for market equilibrium, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007430]
• 11: K. Jain. A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. Manuscript, 2004.
• 12: K. Jain, M. Mahdian, and A. Saberi. "Approximating Market Equilibrium". In Proc. APPROX, 2003.
• 13: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 14: H. Scarf. "The Computation of Economic Equilibria" (with collaboration of T. Hansen), Cowles Foundation Monograph No. 24. 1973.
• 15: V. V. Vazirani. "Market Equilibrium When Buyers Have Spending Constraints". Submitted, 2003.
• 16: L. Walras. Elements d'economie politique pure; ou, Theorie de la richesse sociale (Elements of Pure Economics; Or the Theory of Social Wealth). Lausanne, Paris, 1874 (1954, Engl. transl.).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics