Can Markets Compute Equilibria?
AbstractRecent 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by International Monetary Fund in its series IMF Working Papers with number 09/24.
Date of creation: 01 Feb 2009
Date of revision:
Contact details of provider:
Postal: International Monetary Fund, Washington, DC USA
Phone: (202) 623-7000
Fax: (202) 623-4661
Web page: http://www.imf.org/external/pubind.htm
More information through EDIRC
This paper has been announced in the following NEP Reports:
- NEP-ALL-2009-03-28 (All new papers)
- NEP-CBA-2009-03-28 (Central Banking)
- NEP-CMP-2009-03-28 (Computational Economics)
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.:
- Gilboa, Itzhak & Zemel, Eitan, 1989.
"Nash and correlated equilibria: Some complexity considerations,"
Games and Economic Behavior, Elsevier,
Elsevier, vol. 1(1), pages 80-93, March.
- Itzhak Gilboa & Eitan Zemel, 1988. "Nash and Correlated Equilibria: Some Complexity Considerations," Discussion Papers, Northwestern University, Center for Mathematical Studies in Economics and Management Science 777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- McKelvey, Richard D. & McLennan, Andrew, 1996. "Computation of equilibria in finite games," Handbook of Computational Economics, Elsevier, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 2, pages 87-142 Elsevier.
- Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, SUNY-Oswego, Department of Economics, number comp1, Spring.
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.