Can Markets Compute Equilibria?
International Monetary Fund, 2009 - Business & Economics - 20 pages
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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
accepting and rejecting arithmetic modulo Arrow-Debreu equilibrium Ben-Amram best algorithm bilinear Blum speedup Boolean circuit Boolean Functions Boppana cancellation tricks Circuit Complexity Codenotti computational complexity computational problems Compute Equilibria coNP Davidson College efficient technique exists exponential function family of circuits family of minimal find an equilibrium finding equilibria finding one Nash finite finite field given halting problem harder implies input variables integer and matrix integer multiplication known least as hard least element Leontief linear markets mathematical matrix multiplication minimal circuits mixed strategies models monotone and nonmonotone n x n matrices n-player game natural problem nonmonotone circuits number of steps optimal output p-optimal algorithm P-uniform family Papadimitriou 2007 parallel player polynomial function polynomial time complexity possible PPAD preorder price vector Prisoner's Dilemma problem in NP problem of finding programs Recursive Functions Sipser Strassen's identity superpolynomial speedup theorems trader Turing machines two-player game two-player Nash equilibrium verifying certificates versus NP question VP-complete problem