Can Markets Compute Equilibria?
Recent turmoil in financial and commodities markets has renewed questions regarding how well markets discover equilibrium prices, particularly when those markets are highly complex. A relatively new critique questions whether markets can realistically find equilibrium prices if computers cannot. For instance, in a simple exchange economy with Leontief preferences, the time required to compute equilibrium prices using the fastest known techniques is an exponential function of the number of goods. Furthermore, no efficient technique for this problem exists if a famous mathematical conjecture is correct. The conjecture states loosely that there are some problems for which finding an answer (i.e., an equilibrium price vector) is hard even though it is easy to check an answer (i.e., that a given price vector is an equilibrium). This paper provides a brief overview of computational complexity accessible to economists, and points out that the existence of computational problems with no best solution algorithm is relevant to this conjecture.
|Date of creation:||01 Feb 2009|
|Date of revision:|
|Contact details of provider:|| Postal: |
Phone: (202) 623-7000
Fax: (202) 623-4661
Web page: http://www.imf.org/external/pubind.htm
More information through EDIRC
|Order Information:||Web: http://www.imf.org/external/pubs/pubs/ord_info.htm|
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Itzhak Gilboa & Eitan Zemel, 1988.
"Nash and Correlated Equilibria: Some Complexity Considerations,"
777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
- Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1.
- McKelvey, Richard D. & McLennan, Andrew, 1996. "Computation of equilibria in finite games," Handbook of Computational Economics, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 2, pages 87-142 Elsevier.
When requesting a correction, please mention this item's handle: RePEc:imf:imfwpa:09/24. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Jim Beardow)or (Hassan Zaidi)
If references are entirely missing, you can add them using this form.