<p>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. </p>

CC BY-SA 3.0
2017-09-02T18:52:20.533Z
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
CC BY-SA 3.0
2017-08-30T10:18:06.660Z
2017-08-30T10:18:06.660Z
Fato
<p>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). </p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2017-08-31T08:43:21.637Z
2017-08-31T08:43:21.637Z
IMA
<p>Check out <a href="https://arxiv.org/pdf/1002.2284.pdf" rel="nofollow noreferrer">Maymin (2009)</a>, 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.</p>

CC BY-SA 3.0
2017-08-30T11:36:50.563Z
It's not clear how this answers the question.
410 gone
CC BY-SA 3.0
2017-08-30T14:23:33.020Z
This answer might be more pedagogically interesting with some elaboration.
Kitsune Cavalry
CC BY-SA 3.0
2017-08-30T10:34:36.780Z
2017-08-30T10:43:15.890Z
2017-08-30T10:43:15.890Z
pafnuti
<p>It has been shown, for example in the papers</p>

<ul>
<li>Deng, Du, <a href="https://www.researchgate.net/profile/Xiaotie_Deng/publication/222532184_The_Computation_of_Approximate_Competitive_Equilibrium_is_PPAD-hard/links/0a85e537c19b4cd78d000000.pdf" rel="noreferrer">The Computation of Approximate Competitive Equilibrium is PPAD-hard</a></li>
<li>Hirsch, Papadimitriou, Vavasis, <a href="http://ac.els-cdn.com/0885064X89900174/1-s2.0-0885064X89900174-main.pdf?_tid=890ab13e-8acc-11e7-b232-00000aacb35e&amp;acdnat=1503799853_06f5caef5edfe726ead13a8e429eda9d" rel="noreferrer">Exponential Lower Bounds for Finding Brouwer Fixed Points</a></li>
</ul>

<p>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.</p>

CC BY-SA 4.0
2019-02-09T18:16:59.073Z
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
<competitive-equilibrium><computation>
Could markets compute equilibria?
Andrew
# Could markets compute equilibria?

(Asked by: username_0 on 2017-08-27)

It has been shown, for example in the papers

* Deng, Du, [The Computation of Approximate Competitive Equilibrium is PPAD-hard](https://www.researchgate.net/profile/Xiaotie_Deng/publication/222532184_The_Computation_of_Approximate_Competitive_Equilibrium_is_PPAD-hard/links/0a85e537c19b4cd78d000000.pdf)
* Hirsch, Papadimitriou, Vavasis, [Exponential Lower Bounds for Finding Brouwer Fixed Points](http://ac.els-cdn.com/0885064X89900174/1-s2.0-0885064X89900174-main.pdf?_tid=890ab13e-8acc-11e7-b232-00000aacb35e&acdnat=1503799853_06f5caef5edfe726ead13a8e429eda9d)

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.

**Tags:** competitive-equilibrium, computation

> **Comments:**
> **username_0**: 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".  

---

## 3 answers

### Answer by username_1 on 2017-08-30. Score: 4

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2017-08-31. Score: 3

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.


---

### Answer by username_3 on 2017-08-30. Score: 1

Check out [Maymin (2009)](https://arxiv.org/pdf/1002.2284.pdf), 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.

> **Comments:**
> **username_4**: It's not clear how this answers the question.  
> **username_5**: This answer might be more pedagogically interesting with some elaboration.  

---

