# Could markets compute equilibria?

It has been shown, for example in the papers

that finding competitive equilibria is in a certain sense computationally intractable. So how does economic theory expect a market to reach a competitive equilibrium if each agent is presumably representable by an efficient computational process? In fact, parallel computation doesn't really help because a polynomial number of processors can be simulated in polynomial time.

• Turns out there's a paper called "Can Markets Compute Equilibria?" by Hunter K. Monroe. A Kamal Jain is quoted as saying "If your laptop can't find it, neither can the market". – Andrew Feb 9 '19 at 18:16

Computing an equilibrium is not needed for implementing it. This was the mistake of Lange and co. and was decisively rebutted by Hayek. If you want a mathematical formulation, simply take a tatonement process. Given prices, each individual needs to compute her net demand correspondence. Under different tatonement mechanisms, which are an idealization of the dynamic process of price adjustment in the real-world economy, prices should converge to approximate equilibria. In both experimental settings and in financial markets, there is ample evidence for convergence.

• If the market finds an equilibrium I would still call that computing the equilibrium, even though it's not the case that someone computes the whole thing on their laptop. An auction or other dynamic process still has to be a form of computation, perhaps a parallel one. At least that's my understanding. – Andrew Sep 2 '17 at 18:52

Generally the fixed-points of Nash Equilibria in a market can also be reached by a dynamic process where actors myopically best-reply to the market result in the last period (see Milgrom and Roberts 1990).

The process will converge to a steady state, which is the equilbrium. What this means is that actors do not need to know anything about the market except the things that happened last period, and they do not require anything but simplest computation (so, being able to best-respond). Since actors can be firms (setting prices) and consumers (buying quantities), this will in the end give you the market equilibrium with respect to a steady state without computational burden.

The difference is basically that you have a mechanism for deriving prices, instead of calculating the set of prices which may be equilibria.

The former describes a market process, the latter is a scientific analysis. Such an analysis is intractable for each actor, but as it can be shown that both converge to the same equilbrium given some assumptions, it is still a valuable tool.

Check out Maymin (2009), who shows that if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then $P = NP$, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time.

• It's not clear how this answers the question. – 410 gone Aug 30 '17 at 11:36
• This answer might be more pedagogically interesting with some elaboration. – Kitsune Cavalry Aug 30 '17 at 14:23