LEADER 04124oam 22008654 450 001 9910970193003321 005 20250426110813.0 010 $a9786612842467 010 $a9781462335602 010 $a1462335608 010 $a9781452797502 010 $a1452797501 010 $a9781451871715 010 $a1451871716 010 $a9781282842465 010 $a1282842463 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(IMF)WPIEA2009024 035 $aWPIEA2009024 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 08$a9781451916072 311 08$a1451916078 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 $aAsset prices$2imf 606 $aDeflation$2imf 606 $aInflation$2imf 606 $aMacroeconomics$2imf 606 $aMicroeconomic Behavior: Underlying Principles$2imf 606 $aNoncooperative Games$2imf 606 $aPrice Level$2imf 606 $aPrices$2imf 615 0$aComputational complexity. 615 0$aElectronic data processing. 615 7$aAsset prices 615 7$aDeflation 615 7$aInflation 615 7$aMacroeconomics 615 7$aMicroeconomic Behavior: Underlying Principles 615 7$aNoncooperative Games 615 7$aPrice Level 615 7$aPrices 676 $a511.3;511.352 700 $aMonroe$b Hunter$01815784 712 02$aInternational Monetary Fund. 801 0$bDcWaIMF 906 $aBOOK 912 $a9910970193003321 996 $aCan Markets Compute Equilibria$94371297 997 $aUNINA