Article

Equilibria for economies with production: constant-returns technologies and production planning constraints

Authors:

Kasturi VaradarajanAuthors Info & Claims

SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

Pages 688 - 697

Published: 22 January 2006 Publication History

Abstract

We consider the computation of equilibria in two economic models that generalize the exchange model by including production. In the constant returns model, each producer has a convex, constant-returns-to-scale, technology. In particular, this means that if the technology can output a certain quantity of a good using as input certain quantities of other goods, then scaling all these quantities by a common, non-negative, number also results in a technologically feasible plan. The technology also accomodates the no-free-lunch property, which says that it is not possible to produce something from nothing. At a given price, the producer picks a technologically feasible plan that maximizes her profit. Associated with each consumer is an initial endowment of goods and a utility function that describes her preferences between various bundles of goods. At a given price, the consumer sells her initial endowment, thus obtaining a certain income, and demands the bundle of goods maximizing her utility among all bundles that she can afford at the given price with her income.

References

[1]

K. J. Arrow and G. Debreu, Existence of an Equilibrium for a Competitive Economy, Econometrica 22 (3), pp. 265--290 (1954).

[2]

K. J. Arrow, H. D. Block, and L. Hurwicz. On the stability of the competitive equilibrium, II. Econometrica 27, 82--109 (1959).

[3]

N. Chen, X. Deng, X. Sun, and A. Yao, Fisher Equilibrium Price with a Class of Concave Utility Functions, ESA 2004.

[4]

B. Codenotti, B. McCune, K. Varadarajan, Market equilibrium via the excess demand function. In STOC 05.

Digital Library

[5]

B. Codenotti, S. Pemmaraju, K. Varadarajan, Algorithms Column: The Computation of Market Equilibria. SIGACT News Vol. 35(4), December 2004.

Digital Library

[6]

B. Codenotti, S. Pemmaraju, K. Varadarajan, On the Polynomial Time Computation of Equilibria for certain Exchange Economies. SODA 2005.

Digital Library

[7]

B. Codenotti, K. Varadarajan, Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities, ICALP 2004.

[8]

B. Codenotti, B. McCune, S. Penumatcha, and K. Varadarajan. Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation. To appear in FSTTCS 05.

Digital Library

[9]

N. R. Devanur, C. H. Papadimitriou, A. Saberi, V. V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm. FOCS 2002, pp. 389--395.

Digital Library

[10]

N. R. Devanur, V. V. Vazirani, The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness Results, STOC 2004.

Digital Library

[11]

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).

[12]

E. Eisenberg, Aggregation of Utility Functions. Management Sciences, Vol. 7 (4), 337--350 (1961).

[13]

E. Eisenberg and D. Gale, Consensus of Subjective Probabilities: The Pari-Mutuel Method. Annals of Mathematical Statistics, 30, 165--168 (1959).

[14]

M. C. Ferris, J. S. Pang, Engineering and Economic Applications of Complementary Problems, SIAM Review 39(4), 669--713 (1997).

Digital Library

[15]

D. Gale. The Theory of Linear Economic Models. McGraw Hill, N.Y. (1960).

[16]

R. Garg and S. Kapoor, Auction Algorithms for Market Equilibrium. In Proc. STOC, 2004.

Digital Library

[17]

R. Garg, S. Kapoor, and V. V. Vazirani, An Auction-Based Market Equilbrium Algorithm for the Separable Gross Substitutibility Case, APPROX 2004.

[18]

S. Gjerstad. Multiple Equilibria in Exchange Economies with Homothetic, Nearly Identical Preference, University of Minnesota, Center for Economic Research, Discussion Paper 288, 1996.

[19]

K. Jain, A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. FOCS 2004.

Digital Library

[20]

K. Jain and M. T. Hajiaghayi. The Prize-Collecting Generalized Steiner Tree Problem via a new Approach of Primal-Dual Schema. In SODA 06.

Digital Library

[21]

K. Jain, M. Mahdian, and A. Saberi, Approximating Market Equilibria, Proc. APPROX 2003.

[22]

K. Jain, V. V. Vazirani and Y. Ye, Market Equilibria for Homothetic, Quasi-Concave Utilities and Economies of Scale in Production, SODA 2005.

Digital Library

[23]

T. J. Kehoe, Uniqueness and Stability, in Alan P. Kirman, editor, Elements of General Equilibrium Analysis, Basil Blackwell, 1998, 38--87.

[24]

O. L. Mangasarian. Nonlinear Programming, McGraw-Hill, 1969.

[25]

A. Mas-Colell, On the Uniqueness of Equilibrium Once Again, in: Equilibrium Theory and Applications, W. Barnett, B. Cornet, C. DAspremont, J. Gabszewicz, andA. Mas-Colell (eds). Cambridge University Press (1991).

[26]

A. Mas-Colell, M. D. Whinston, and J. R. Green, Microeconomic Theory, Oxford University Press (1995).

[27]

E. I. Nenakov and M. E. Primak. One algorithm for finding solutions of the Arrow-Debreu model, Kibernetica 3, 127--128 (1983). (In Russian.)

[28]

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).

[29]

V. M. Polterovich, Economic Equilibrium and the Optimum, Matekon (5), pp. 3--20 (1973).

[30]

M. E. Primak, An algorithm for finding a solution of the linear exchange model and the linear Arrow-Debreu model, Kibernetika 5, 76--81 (1984).

[31]

M. E. Primak, A converging algorithm for a linear exchange model, Journal of Mathematical Economics 22, 181--187 (1993).

[32]

T. F. Rutherford, Applied General Equilibrium Modeling with MPSGE as a GAMS Sybsystem: An Overview of the Modeling Framework and Syntax, Computational Economics 14, pp. 1--46 (1999).

Digital Library

[33]

A. Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1986.

Digital Library

[34]

J. B. Shoven and J. Whalley. Applying General Equilibrium, Cambridge University Press (1992).

[35]

Y. Ye, A Path to the Arrow-Debreu Competitive Market Equilibrium, To appear in Mathematical Programming.

Digital Library

Cited By

Chen XPaparas DYannakakis M(2017)The Complexity of Non-Monotone MarketsJournal of the ACM10.1145/306481064:3(1-56)Online publication date: 16-Jun-2017
https://dl.acm.org/doi/10.1145/3064810
Garg JMehta RVazirani VYazdanbod SHatami HMcKenzie PKing V(2017)Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibriaProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055474(890-901)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055474
Garg JKannan RRoughgarden TFeldman MSchwarz M(2015)Markets with ProductionProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764517(733-749)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2764468.2764517
Show More Cited By

Index Terms

Equilibria for economies with production: constant-returns technologies and production planning constraints
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
  2. Mathematical analysis
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming

Recommendations

Economies with non-convex production and complexity equilibria
EC '11: Proceedings of the 12th ACM conference on Electronic commerce

The convexity assumptions required for the Arrow-Debreu theorem are reasonable and realistic for preferences; however, they are highly problematic for production because they rule out economies of scale. We take a complexity-theoretic look at economies ...
Pricing Equilibria and Graphical Valuations

We study pricing equilibria for graphical valuations, whichare a class of valuations that admit a compact representation. These valuations are associated with a value graph, whose nodes correspond to items, and edges encode (pairwise) complementarities/...
Lottery Pricing Equilibria
EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

We extend the notion of Combinatorial Walrasian Equilibrium, as defined by \citet{FGL13}, to settings with budgets. When agents have budgets, the maximum social welfare as traditionally defined is not a suitable benchmark since it is overly optimistic. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

January 2006

1261 pages

ISBN:0898716055

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
341
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen XPaparas DYannakakis M(2017)The Complexity of Non-Monotone MarketsJournal of the ACM10.1145/306481064:3(1-56)Online publication date: 16-Jun-2017
https://dl.acm.org/doi/10.1145/3064810
Garg JMehta RVazirani VYazdanbod SHatami HMcKenzie PKing V(2017)Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibriaProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055474(890-901)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055474
Garg JKannan RRoughgarden TFeldman MSchwarz M(2015)Markets with ProductionProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764517(733-749)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2764468.2764517
Garg JVazirani VChekuri C(2014)On computability of equilibria in markets with productionProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634172(1329-1340)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634172
Papadimitriou CWilkens CShoham YChen YRoughgarden T(2011)Economies with non-convex production and complexity equilibriaProceedings of the 12th ACM conference on Electronic commerce10.1145/1993574.1993595(137-146)Online publication date: 5-Jun-2011
https://dl.acm.org/doi/10.1145/1993574.1993595
Wilkens C(2009)The Complexity of Models of International TradeProceedings of the 5th International Workshop on Internet and Network Economics10.1007/978-3-642-10841-9_30(328-339)Online publication date: 9-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10841-9_30
Codenotti BRademacher LVaradarajan K(2006)Computing equilibrium prices in exchange economies with tax distortionsProceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part I10.1007/11786986_51(584-595)Online publication date: 10-Jul-2006
https://dl.acm.org/doi/10.1007/11786986_51
Codenotti BMcCune BPenumatcha SVaradarajan K(2005)Market equilibrium for CES exchange economiesProceedings of the 25th international conference on Foundations of Software Technology and Theoretical Computer Science10.1007/11590156_41(505-516)Online publication date: 18-Dec-2005
https://dl.acm.org/doi/10.1007/11590156_41

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten