Market equilibria for homothetic, quasi-concave utilities and economies of scale in production

ABSTRACT

Eisenberg and Gale (1959) gave a convex program for computing market equilibrium for Fisher's model for linear utility functions, and Eisenberg (1961) generalized this to concave homogeneous functions of degree one. We further generalize to:1. Homothetic, quasi-concave utilities. This also helps extend Eisenberg's result to concave homogeneous functions of arbitrary degree.2. We introduce the notion of a trading cone which enables us to compute market equilibrium in the presence of economies of scale in production provided differential pricing is allowed. Applications to network pricing are provided.

REFERENCES

• 1: S. Agarwal, P. A. Chou, and K. Jain, Adaptive Network Coding via Pricing Edges. In preparation.
• 2: K. J. Arrow and G. Debreu, Existence of an Equilibrium for a Competitive Economy, Econometrica 22 (3), pp. 265--290 (1954).
• 3: R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung. Network Information Flow. IEEE Trans. Information Theory, IT-46(4):1204--1216, July 2000.
• 4: W. C. Brainard and H. Scarf, How to Compute Equilibrium Prices in 1891. Cowles Foundation Discussion Paper 1270 (2000).
• 5: 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]
• 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: Nikhil R. Devanur, The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007431]
• 8: N. R. Devanur, V. V. Vazirani, An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case. FSTTCS 2003, pp. 149--155 (2003).
• 9: E. Eisenberg, and D. Gale, Consensus of Subjective Probabilities: The Pari-Mutuel Method, Annals of Mathematical Statistics, 30, 165--168 (1959).
• 10: E. Eisenberg, Aggregation of Utility Functions, Management Sciences, vol(7)4, 337--350, 1961.
• 11: J. W. Friedman, Concavity of Production Functions and Non-Increasing Returns to Scale, Econometrica, vol. 41, no. 5, 981--984, 1973.
• 12: M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin Heidelberg, 2nd edition, 1988. 2nd edition 1994.
• 13: D. Gale. The Theory of Linear Economic Models. McGraw Hill, N.Y. (1960).
• 14: 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]
• 15: S. Kapoor, R. Garg and V. Vazirani. An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case. In Proc. APPROX, 2004.
• 16: Kamal Jain, A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.286-294, October 17-19, 2004 [doi>10.1109/FOCS.2004.6]
• 17: K. Jain. Market Equilibrium with Production Planning and Linear Utilities in Walras setting. Manuscript 2004.
• 18: K. Jain, M. Mahdian, and A. Saberi, Approximating Market Equilibria, Proc. APPROX 2003.
• 19: Kamal Jain , Mohammad Mahdian , Mohammad R. Salavatipour, Packing Steiner trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 20: F. P. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8:33--37, 1997.
• 21: O. L. Mangasarian. Nonlinear Programming, McGraw-Hill, 1969.
• 22: J. F. Nash, The Bargaining Problem, Econometrica 28, 1950, pp. 155--162.
• 23: D. J. Newman and M. E. Primak. Complexity of Circumscribed and Inscribed Ellipsoid Methods for Solving Equilibrium Economical Models. Applied Mathematics and Computation 52:223--231 (1992).
• 24: M. Quinzi, Increasing Returns and Efficiency, Oxford University Press, 1992.
• 25: H. Varian, Microeconomic Analysis, New York: W.W. Norton, 1992.
• 26: V. V. Vazirani. Market Equilibrium When Buyers Have Spending Constraints. Submitted, 2003.
• 27: 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.
• 28: Y. Wu, P. A. Chou, and K. Jain, Practical Network Coding. Allerton Conference 2003.
• 29: Y. Ye, A Path to the Arrow-Debreu Competitive Market Equilibrium. Stanford University working paper 2004. Available online.