03925oam 22007814 450 991082737680332120240402050918.01-4623-3560-81-4527-9750-197866128424671-4518-7171-61-282-84246-3(CKB)3170000000055188(EBL)1608154(SSID)ssj0000940078(PQKBManifestationID)11512680(PQKBTitleCode)TC0000940078(PQKBWorkID)10939141(PQKB)10244986(OCoLC)680613607(MiAaPQ)EBC1608154(IMF)WPIEE2009024(EXLCZ)99317000000005518820020129d2009 uf 0engur|n|---|||||txtccrCan Markets Compute Equilibria? /Hunter Monroe1st ed.Washington, D.C. :International Monetary Fund,2009.1 online resource (22 p.)IMF Working PapersDescription based upon print version of record.1-4519-1607-8 Includes bibliographical references.Contents; 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?; ReferencesRecent 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.IMF Working Papers; Working Paper ;No. 2009/024Computational complexityElectronic data processingMacroeconomicsimfNoncooperative GamesimfMicroeconomic Behavior: Underlying PrinciplesimfPrice LevelimfInflationimfDeflationimfAsset pricesimfPricesimfComputational complexity.Electronic data processing.MacroeconomicsNoncooperative GamesMicroeconomic Behavior: Underlying PrinciplesPrice LevelInflationDeflationAsset pricesPrices511.3;511.352Monroe Hunter1654499International Monetary Fund.DcWaIMFBOOK9910827376803321Can Markets Compute Equilibria4096898UNINA