Here is a new result which Yoram Bauman has pointed my attention to. The title is "Markets are efficient if and only if P = NP" and the author is Philip Maymin. Here is the abstract:

I prove 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. I also prove the converse by showing how we can "program" the market to solve NP-complete problems. Since P probably does not equal NP, markets are probably not efficient. Specifically, markets become increasingly inefficient as the time series lengthens or becomes more frequent. An illustration by way of partitioning the excess returns to momentum strategies based on data availability confirms this prediction.

Points like this seem to be rediscovered every ten years or so; I am never sure what to make of them. What ever happened to Alain Lewis?

Doesn’t this just restate the “Economic Calculation Problem” as proposed by Hayek and Mises?

Their answer was not that the markets are perfectly efficient, but rather that they were more efficient than the alternative, which was to try and centrally plan the economy.

Did Tyler even read the paper? I doubt it. But, hey, it says “markets are probably not efficient” so it’s all good.

Not a huge fan of this one for the reasons stated.

Interesting concept but it could have been presented so much more eloquently.

I can understand physicists who confuse their mathematical models for reality. At least their mathematical models are useful for something and have some empirical basis. Economists, who are just aping physicists, who then have some naive realist view that nature instantiates their models… well…

Zach wrote: “So what class of problem is an algorithm that will systematically beat the market?”

Generally a felony, although in some cases it can be plea-bargained down to a misdemeanor in exchange for testimony against co-conspirators.

For a Harvard and Chicago graduate, his research is underwhelming. Besides, “market efficiency” is a straw man. More interesting questions have to do with what types of arbitrage strategy are admitted and how quickly or efficiently new information is processed and distributed in a market.

I read through the proof that if the market is efficient (in the weak sense) then P = NP, but it’s entirely unconvincing, and seems to be missing a lot of detail. So at the moment it’s hard to take it seriously.

I didn’t read the other proof, but I wouldn’t be surprised if it also had problems.

As a computer science guy, I think you’re all missing why this paper is a useful first step towards applying the knowledge collected in computational theory to financial markets.

I think that the fact that there’s a bunch of useful research that has come out in the area of financial computational complexity in just the last year is evidence, not overwhelming but significant, that there’s something to it.

Besides the CDO packing example mentioned previously, there’s this paper on the consequences of memory-bounded agents in a marketplace: http://www.ccs.neu.edu/home/viola/papers/HLVreport.pdf .

The use of this paper is not in showing that markets are not efficient, but rather in pointing out a bridge for the tools of a new field (computational complexity) to be brought to bear on financial theory. Is it so hard to believe that new thoughts and ideas could come out of thinking about market efficiency in a new way?

Bill Mill,

They don’t get it. They’re too obsessed with the “markets are not efficient” mantra to actually understand what the paper is saying.

Adam, I don’t see the connection to Mises-Hayek.

Bill Mill, the new head of the Minnesota fed has an old paper that money is equivalent to (a certain form of) memory.

This paper makes a serious error about the term “efficient Market”. In so doing, it turns everything upside down.

An efficient market is not one that computes the “fundamental value of something”. Its one, such that an individual or group, cannot out compute the market.

In this sense, the paper actually proves the efficient market hypothesis. This paper deserves a strong reject.

Comments on this entry are closed.