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

61–70 of 201 posts

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

#61

Post by js8 »

Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world.

If you want a full critique, read Steve Keen's Debunking Economics, it has a chapter on EMH.

Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that as well.

Amusingly enough, the first thing that a rational person would do upon discovering a relatively efficient algorithm to solve NP problems would be to cash in all the Bitcoins. Thus proving in practice that no, markets are not really efficient. :-)

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

#62

Post by SilasX »

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…

The result also exploits how the notion of efficient markets doesn’t include the computational time and cost of detecting the arbitrage opportunities, and so should be updated.

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

#63

Post by lajhsdfkl »

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

> then it implies that there is nothing special about markets

How so? It implies simply that markets are not efficient. It does not imply that state control would be more efficient and it does not imply that markets are not the most efficient way of determining the value of a resource.

What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods and fix prices based on that determination.

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

#64

Post by cheschire »

mortdeus wrote: post #52

"For simplicity but without loss of generality, assume there are n past price changes, each of which is either UP (1) or DOWN (0)." You know, this is the kind of thing that makes me wonder about how much quantum computation is going to change the game. Where we aren't just calculating ups and downs but superpositions between the two.

Digital is a framework built on top of analog. Boolean logic is the foundation of all of our modern computing, and so we built all of our circuits around the ability to handle HIGH and LOW signals. What your describing seems to me like you're saying that leveraging an analog signal is the benefit of quantum computation. If so, I don't really agree. If not, then I misunderstood.

Either way, I suspect that the superposition between the change in value and the change in time, in relation to all of the other superpositions in value/time changes, is the true computational power of quantum technology.

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

#65

Post by SolarNet »

mzl wrote: post #54
SolarNet wrote: post #45

Earlier quoted context omitted.

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 calculati…

The concept of NP-complete is different form the concept of np-hard to approximate in any way. The question if a particular problem is hard to approximate is typically a diverse and interesting research area, that does not have obvious answers. For example, it has been proven that the well-known traveling salesperson problem on metric instances (i.e., instances satisfying the triangle inequality) can not be approxima…

This is why I support the authors research, without knowing if it even is NP complete (as this paper claims) we are faced with it being NP hard. Without studying the problem, we can't even begin to find approximation algorithms.

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

#66

Post by mortdeus »

So just to better understand the issue of P=NP, am I right in assuming that an NP problem is like trying to build a neural net for image recognition?

In the sense that it takes a huge amount of time and images to train the thing to become smart (in other words, to go through the entire network of neurons one by one and assign better weight values etc) but when it comes to actually verifying if our network is smart all it takes is to run an image straight through the network?

And the issue of trying to prove N=NP is essentially trying to prove that there isn't a magical way to train a neural network with just one image of training data?

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

#67

Post by mzl »

SolarNet wrote: post #65
mzl wrote: post #54

Earlier quoted context omitted.

The concept of NP-complete is different form the concept of np-hard to approximate in any way. The question if a particular problem is hard to approximate is typically a diverse and interesting research area, that does not have obvious answers. For example, it has been proven that the well-known traveling salesperson problem on metric instances (i.e., instances satisfying the triangle inequality) can not be approxima…

This is why I support the authors research, without knowing if it even is NP complete (as this paper claims) we are faced with it being NP hard. Without studying the problem, we can't even begin to find approximation algorithms.

The paper claims NP-completeness AFAICS, so I thought that was what you meant. Sorry if I misunderstood.

There are problems that have approximations that can get arbitrarily close to the optimum. One particularly interesting case IMHO are so-called polynomial approximation schemes. These schemes can be used to create an approximation algorithm for any choice of approximation factor and that algorithm will have a polynomial time complexity, but the polynomial will depend on the actual approximation factor chosen.

I agree that it is an interesting problem to study, especially since it meshes well with my own biases that the efficient market hypothesis is too strong.

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

#68

Post by SolarNet »

lajhsdfkl wrote: post #63
SolarNet wrote: post #18

Earlier quoted context omitted.

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 b…

> then it implies that there is nothing special about markets How so? It implies simply that markets are not efficient. It does not imply that state control would be more efficient and it does not imply that markets are not the most efficient way of determining the value of a resource. What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods…

> It implies simply that markets are not efficient.

No it implies that efficient market states are an NP complete problem. And that we are likely approximating the optimization of efficiency (of the allocation of resources) using markets. Different approximation algorithms have different properties. Might markets be the best in every possible way, sure, but it's very unlikely given what we know about approximation algorithms. It's like one of the best variants in one way, perhaps that's the best way, but we should figure that sort of thing out. And that's what this paper is laying the ground work for.

> What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods and fix prices based on that determination.

In it's editorializing about markets. Which isn't incorrect. But the larger consequences of efficiency being an NP complete problem means that there are many possible algorithms we could use to solve them if they are given equivalent resources. If those equivalent resources are thousands (or millions) of government panels then we should be able to mathematically prove equivalency. That's my point.

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

#69

Post by jdironman »

js8 wrote: post #61

Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world. If you want a full critique, read Steve Keen's Debunking Economics, it has a chapter on EMH. Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that a…

Maybe someone knows something we don't and that's why crypto coin was created in the first place? Just having fun speculating guys.

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

#70

Post by jonathanstrange »

soVeryTired wrote: post #58

Meh. Whatever your opinions on P = NP, the efficient markets hypothesis is unfalsifiable. You can only falsify a joint hypothesis of efficiency plus some model of information flow into a market.

Wait a minute, if the paper correctly links a theoretical definition of efficiency to the complexity class and indeed shows that markets can be efficient only iff. P=NP, then any future proof that P!=NP falsifies the thesis that markets are efficient. And most experts agree that if we ever get a proof, then it will be a proof of NP!=P.

Knuth is a notable exception, although he has to my knowledge never really vigorously advocated P=NP but merely suggested the possibility that P=NP and that the algorithms to transform NP problems into P problems could be very, very complex but still in P. Seems unlikely, though.

Post reply on HN