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

41–50 of 201 posts

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

#41

Post by stale2002 »

SolarNet wrote: post #20
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…

In economics, the difference between "efficient market" and "epsilon away from efficient" is very little.

IE, it is almost as good.

So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough.

Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin with.

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

#42

Post by talltimtom »

MaysonL wrote: post #39

Somehow this seems to be a confusion of categories: markets are real-world mechanisms, while P and NP are mathematical abstractions. Does not compute. To the extent that it does, it's typical mathematical macroeconomic BS.

Markets are a conceptual and mathematica abstaction used to describe the real world.... so is computation.

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

#43

Post by lend000 »

Ar-Curunir wrote: post #23
lend000 wrote: post #22

Interesting topic and thought experiment. But this theory is not very fleshed out and not at all convincing (especially the part regarding using an existing efficient market to perform computation for anything other than price of the underlying instrument, i.e. what the computation is intended for). The following quote sums up how the author makes very open ended assumptions: > So what should the market do? If it is…

> I'm not sure I understand the author's implication that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price. That's just what P = NP means: the cost to verify a solution is the same as the cost of finding one.

Yes, but how the author relates that to a market's continuous price calculations is beyond me.

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

#44

Post by vanderZwan »

adrianN wrote: post #36
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…

While I technically agree with your points, you and the author use different definitions of "markets are efficient".

Could you elaborate on that?

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

#45

Post by SolarNet »

stale2002 wrote: post #41
SolarNet wrote: post #20

Earlier quoted context omitted.

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…

In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. IE, it is almost as good. So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough. Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin wit…

Sure, but significant facts come out of it:

* Economic systems are optimization algorithms on an NP hard problem. Hence markets have no special efficiency capabilities, they are simply a choice of optimization algorithm, there may be better ones out there with more favorable properties. Any optimization algorithm with similar resources could have effectively equivalent efficiency. This destroys the economic calculation problem.

* That you are wrong about the small epsilon. You can't make even that kind of guarantee in the face of NP hardness. What the market has a state may be wildly far away from the optimum, the market could be stuck in a local minima, and without P=NP you can't even know how far from optimum you are. Without a complexity class for markets you can't even begin to discuss it's properties, and that's what this paper is an attempt at.

It is your cleverness that misses the point, the author is trying to attach 21st century computational theory to economics (he may be wrong, but economic theories aren't going to help disprove it) and it's going to have some consequences.

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

#46

Post by coldtea »

stale2002 wrote: post #41
SolarNet wrote: post #20

Earlier quoted context omitted.

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…

In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. IE, it is almost as good. So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough. Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin wit…

>In economics, the difference between "efficient market" and "epsilon away from efficient" is very little.

In economics, yes. In real life, not so much.

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

#47

Post by stale2002 »

SolarNet wrote: post #30
nordsieck wrote: post #26

Earlier quoted context omitted.

1. I don't think anyone has any illusions that markets are in a mathematical sense optimal. They are a distributed process with no global knowledge - it would be strange if they somehow achieved global optimality. The real question is how efficient are they. 2. If you're serious about > if a government sponsored and modified such an algorithm in an attempt to optimize for equality (second only to efficiency of usage)…

On 1: That's exactly the point of this paper. That's what the EMH claims, and what this paper is linking to P=NP. If this paper is correct then markets are not violations of P=NP, and a lot of economists are wrong (or P=NP). On 2: My answer to both problems (any problems) is Turing equivalence. If one algorithm of people and computers can solve the problem, then so can another one with the same resources. And given o…

Equal number of people doesn't not solve the principle agent problem.

The idea of the principle agent problem is that the best person who is able to understand their own wants and desires is the person themselves.

Markets are currently the way that puts the maximum amount of control into each individuals own hands.

IE, a person has X resources, and they can trade them how they like because they are best able to understand what makes them better off.

If your solution is to take power away from an individual, with regards to how they spend their own resources, IE, by controlling their "means of production", you are going to run into the principle agent problem.

Also, with regards to the paper talking about P=NP is missing the entire point.

Sure, markets aren't 100% efficent. They could instead be 99.9999% efficent. And that's good enough and side steps the whole P=NP problem.

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

#48

Post by ricraz »

lend000 wrote: post #22

Interesting topic and thought experiment. But this theory is not very fleshed out and not at all convincing (especially the part regarding using an existing efficient market to perform computation for anything other than price of the underlying instrument, i.e. what the computation is intended for). The following quote sums up how the author makes very open ended assumptions: > So what should the market do? If it is…

Agreed, I was also quite skeptical about the section you quoted. It seems like a much more hand-wavey proof than I'd expect to accompany an important result like this. Surprised that it was published (in a journal called Algorithmic Finance, which seems respectable enough) in this form.

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

#49

Post by coldtea »

MaysonL wrote: post #39

Somehow this seems to be a confusion of categories: markets are real-world mechanisms, while P and NP are mathematical abstractions. Does not compute. To the extent that it does, it's typical mathematical macroeconomic BS.

>markets are real-world mechanisms, while P and NP are mathematical abstractions

We use mathematical abstractions to model real-world mechanism every day for millennia.

Not only that, but there are all kinds of mathematically defined limits that no real-world mechanism can bypass, from a purely logical perspective.

If you only have 10 dollars and I give you 20 dollars, you'll have 30 dollars, not 500 -- that's a mathematical truth that absolutely holds in the real world too.

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

#50

Post by grosjona »

The market cannot be efficient because a large portion of public information is not true.

Even if all the information was true, there is still the problem that humans have very poor reasoning abilities combined with herd mentality which almost always overrides the reasoning part.

To predict the market, you don't need to understand the market, you need to understand people's distorted view of the market.

Post reply on HN