Can Markets Compute Equilibria?
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 equilibria Ben-Amram best algorithm bilinear Blum speedup Boolean circuit Boolean Functions Boppana c0NP-complete problem cancellation tricks Circuit Complexity Codenotti computational complexity computational problems COMPUTING EQUILIBRIA conjecture Davidson College efﬁcient technique exists exponential function family of circuits family of minimal given halting problem Hamilton cycle hard to ﬁnd harder identiﬁes IEEE implies input ac input variables instance 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 P-complete problem n-player game natural problem nonmonotone circuits number of steps optimal output P-complete problem p-optimal algorithm P-uniform family Papadimitriou 2007 parallel payoff player polynomial time complexity PPAD preorder price vector problem in NP problem of ﬁnding programs Recursive Functions reﬂects Sipser solve Strassen’s identity superpolynomial speedup trader Turing machines two-player game two-player Nash equilibrium veriﬁcation versus NP question