Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Markets are efficient if and only if P = NP (2010)

arxiv.org

Post reply on HN
Print view View original

11–20 of 201 posts

Re: Markets are efficient if and only if P = NP (2010)

#11

Post by CJefferson »

While this is a fun, the title is a little strong.

There are three limitations (whuch apply to many papers about P=NP).

1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error.

2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true.

3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.

Re: Markets are efficient if and only if P = NP (2010)

#13

Post by modeless »

Before people get too carried away criticising markets, check this quote from the paper.

> The results of this paper should not be interpreted as support for government intervention into the market; on the contrary, the fact that market efficiency and computational efficiency are linked suggests that government should no more intervene in the market or regulate market participants than it should intervene in computations or regulate computer algorithms.

Re: Markets are efficient if and only if P = NP (2010)

#15

Post by kome »

modeless wrote: post #13

Before people get too carried away criticising markets, check this quote from the paper. > The results of this paper should not be interpreted as support for government intervention into the market; on the contrary, the fact that market efficiency and computational efficiency are linked suggests that government should no more intervene in the market or regulate market participants than it should intervene in computat…

well, governments should do both. Computer algorithms can be a very subtle form of power. And of course we should have a degree of public control over them.

Re: Markets are efficient if and only if P = NP (2010)

#17

Post by QML »

What does this mean for the class of PPAD-complete [1] problems?

Someone correct me if I'm wrong, but if 1. Nash Equilibrium ⊂ FNP 2. "Markets are efficient" => FNP ⊂ FP

How is this different from "FP = FNP if and only if P = NP" [2], which is a result already found?

[1] https://en.wikipedia.org/wiki/PPAD_(complexity) [2] https://en.wikipedia.org/wiki/FNP_(complexity)

Re: Markets are efficient if and only if P = NP (2010)

#18

Post by SolarNet »

modeless wrote: post #13

Before people get too carried away criticising markets, check this quote from the paper. > The results of this paper should not be interpreted as support for government intervention into the market; on the contrary, the fact that market efficiency and computational efficiency are linked suggests that government should no more intervene in the market or regulate market participants than it should intervene in computat…

Sure, but if what the author is saying is true, then it implies that there is nothing special about markets, and a system involving an equal number of humans and computers following some other optimization algorithm could achieve similar results in efficiency.

And if a government sponsored and modified such an algorithm in an attempt to optimize for equality (second only to efficiency of usage), such a system could be an effective socialism. It is at least an interesting avenue to consider if mathematical and computational parallels could be constructed.

Re: Markets are efficient if and only if P = NP (2010)

#20

Post by SolarNet »

CJefferson wrote: post #11

While this is a fun, the title is a little strong. There are three limitations (whuch apply to many papers about P=NP). 1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error. 2. Ma…

On two, as this appears to be a cross disciplinary paper, it's important to consider that some economists currently claim markets are efficient (the efficient market hypothesis, which is like a big open question in economics). By drawing a link between the EMH and P=NP (which many computer scientists believe is unlikely) the author is linking two open questions with opposing beliefs. So I think point two is sort of a technicality that with context it should be understood that the author is specifically talking about two open questions as they stand today.

Also to further hammer home the point, due to the phrasing of the EMH, although no one may currently be using P=NP, markets would still have the efficiency property now even if no one is exploiting it. Perhaps this sort of vacuously true statement rubs you the wrong way (like it does me a bit) with the strength of the "if and only if" the author used. But if you read "markets are efficient" as the EMH then it is still a valid literal formulation.

On three, sure that's great for reality. But for the formulation of markets being efficient as an inherent property (again the EMH) of markets, the size of the market could be held as effectively infinite (or at least extremely large) and the property should still hold. At some point the size of the theoretical market will explode the polynomial, and for the EMH to hold P=NP must be true.

Post reply on HN