LEADER 03925oam 22007814 450 001 9910827376803321 005 20240402050918.0 010 $a1-4623-3560-8 010 $a1-4527-9750-1 010 $a9786612842467 010 $a1-4518-7171-6 010 $a1-282-84246-3 035 $a(CKB)3170000000055188 035 $a(EBL)1608154 035 $a(SSID)ssj0000940078 035 $a(PQKBManifestationID)11512680 035 $a(PQKBTitleCode)TC0000940078 035 $a(PQKBWorkID)10939141 035 $a(PQKB)10244986 035 $a(OCoLC)680613607 035 $a(MiAaPQ)EBC1608154 035 $a(IMF)WPIEE2009024 035 $a(EXLCZ)993170000000055188 100 $a20020129d2009 uf 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aCan Markets Compute Equilibria? /$fHunter Monroe 205 $a1st ed. 210 1$aWashington, D.C. :$cInternational Monetary Fund,$d2009. 215 $a1 online resource (22 p.) 225 1 $aIMF Working Papers 300 $aDescription based upon print version of record. 311 $a1-4519-1607-8 320 $aIncludes bibliographical references. 327 $aContents; I. Introduction; II. Is Computing Equilibria Difficult?; Table; 1. Payoff Matrix for the Prisoner's Dilemma; Figures; 1. NP-complete: Is there a Hamilton Cycle?; 2. P: Is this a Hamilton Cycle?; III. Are There Natural Problems with No Best Algorithm?; A. Superlinear vs. Blum Speedup; B. No Best Algorithm for Integer and Matrix Multiplication?; 3. Boolean circuit: Are at least two inputs "TRUE"?; C. The Power of Cancellation; D. No Best Algorithm for coNP-Complete Problems?; E. No Best Algorithm Versus No Algorithm at All; IV. Conclusion; 4. Is speedup inherited?; References 330 3 $aRecent 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. 410 0$aIMF Working Papers; Working Paper ;$vNo. 2009/024 606 $aComputational complexity 606 $aElectronic data processing 606 $aMacroeconomics$2imf 606 $aNoncooperative Games$2imf 606 $aMicroeconomic Behavior: Underlying Principles$2imf 606 $aPrice Level$2imf 606 $aInflation$2imf 606 $aDeflation$2imf 606 $aAsset prices$2imf 606 $aPrices$2imf 615 0$aComputational complexity. 615 0$aElectronic data processing. 615 7$aMacroeconomics 615 7$aNoncooperative Games 615 7$aMicroeconomic Behavior: Underlying Principles 615 7$aPrice Level 615 7$aInflation 615 7$aDeflation 615 7$aAsset prices 615 7$aPrices 676 $a511.3;511.352 700 $aMonroe$b Hunter$01654499 712 02$aInternational Monetary Fund. 801 0$bDcWaIMF 906 $aBOOK 912 $a9910827376803321 996 $aCan Markets Compute Equilibria$94096898 997 $aUNINA