News for hackers. Stuff that matters.
Re:Markets are efficient if and only if P = NP by leelin on Tuesday February 23, 2010 @05:58AM (#1145145)
Summary of paper:

A.) First several pages are random fluff: Explains P, NP, NP-Hard, NP-Complete, history of P=NP, examples of NP-complete problems, examples of market efficiency, and other very uninteresting stuff that feels like it's trying to fill out pages.

B.) Makes this central argument:

1.) If markets are efficient, then no one can come up with a consistently profitable trading strategy based on analyzing historical data.

2.) Model historical data as a sequence of days where the market can go up or down on any given day.

3.) Model a trading strategy as being long, short, or neutral the market on any given day, to be started after recognizing some pattern for the previous N days.

4.) To determine from historical data whether a profitable strategy exists, you'd need to try all combinations of being long, short, or neutral over some time horizon, while looking for all market patterns. Trying all such combinations is O(3^N) or O(2^N), depending on whether you believe the expensive part is finding the strategy or finding the pattern.

5.) To verify that you have a winning strategy, you merely need to simulate the strategy over your historical data, which only takes O(N).

6.) Therefore, it is in NP. Similarly, it is NP-Hard because we can reduce 3-SAT to a market / trading problem. Therefore, "does a profitable strategy based on historical data exist?" is in NP-complete.

7.) Because our model shows finding the existence of a profitable strategy is NP-complete, then either P=NP or markets are inefficient.

C.) A few comments of my own:

1.) Suppose we believe the argument. The amount of historical data is finite, so maybe some hedge funds brute-forced a solution and removed the market inefficiencies they've found.

2.) I think SAT and travelling salesman are the wrong analogies, because solving both optimally can involve lots of backtracking. A* search on a landscape with reliable heuristics might be a better analogy. In trading markets, you don't need to try all 3^N combinations because just as in search algorithms, you have heuristics that can help prune large parts of your search space (if a strategy starts off losing money, no need to keep exploring all the 3^N combinations under it).

3.) The author assumes everyone represents and models the market his way. Maybe a more clever representation makes the problem tractable. Checkers is a solved game now, even though there are in theory infinitely many possible game histories to test.

Re:Markets are efficient if and only if P = NP by jplewicke on Tuesday February 23, 2010 @11:00AM (#1145623)
When I first saw the headline, I assumed it was going to be about the CDO packing problem discussed at http://rjlipton.wordpress.com/2009/10/22/helping-wall-street... . The basic idea is that if you're buying a Collateralized Debt Obligation, you can't tell whether the people structuring the deal have intentionally given you an unfair share of bad loans, even when you know a lot about each of the loans in particular.

There's also a fairly trivial argument for the incomputability of the EMH: for each Turing machine, issue bonds that compound interest in perpetuity and pay it off if the Turing machine halts. Since the value of the bond is positive if the Turing machine halts and zero if it doesn't, in an efficient market investors will price the bonds in a way that solves the halting problem.

Re:Markets are efficient if and only if P = NP by aprime on Tuesday February 23, 2010 @11:14AM (#1145649)
Doesn't this only prove that there cannot be an efficient market for these special "Turing machine" bonds?
Re:Markets are efficient if and only if P = NP by jplewicke on Tuesday February 23, 2010 @12:35PM (#1145847)
That's definitely true. It's only a counterproof to some extremely strong versions of the EMH that assume that you can buy any possible asset or derivative. http://en.wikipedia.org/wiki/Complete_market
Re:Markets are efficient if and only if P = NP by pohl on Tuesday February 23, 2010 @01:09PM (#1145952)
I think SAT and travelling salesman are the wrong analogies, because solving both optimally can involve lots of backtracking.

Forgive me if I'm not understanding what you're getting at here. (I haven't read the paper). But, on first blush, it appears that 3-SAT is not mentioned for the purpose of analogy, but rather for use as a standard "reduction" (in the parlance of NP-Completeness proofs), in which case reducing to any NP-Complete problem is as good as reducing to any other. They're typically only chosen by whether they are amenable to some poly-time transformation, aren't they?

It's been a long time since I've had my course in this, so caveat emptor.

Re:Markets are efficient if and only if P = NP by leelin on Tuesday February 23, 2010 @01:49PM (#1146056)
You are correct, but the author's big leap of faith is that our particular one case of the problem is intractable. I'm claiming the reduction from 3-SAT to his market problem is likely broken because the general market problem is subject to at least some additional constraints for it to reflect our reality. For example, you can't have MSFT stock rapidly alternating from $10 to $200 every day, which might be what happens during your 3-SAT reduction.

More importantly, I'm calling out the author's representation as bogus. He proves that anyone who represents the markets his way is trying to solve an NP-complete problem, and that given the problem is NP-complete the hedge funds and banks can't possibly have computed the solution.

Re:Markets are efficient if and only if P = NP by pohl on Tuesday February 23, 2010 @03:03PM (#1146272)
I've read the paper now, and I'm still a little confused by the way that you have phrased your objections. More specifically, I don't understand how the form of your objections could constitute a valid criticism of any NP-Completeness proof whatsoever.

(While I don't feel qualified to verify the correctness of the author's reduction, the form of the proof feels like any other that I've read.)

...but the author's big leap of faith is that our particular one case of the problem is intractable.

What does "our particular one case of the problem" mean? Do you mean a particular case of the 3-SAT problem?

If so, reductions don't consider a particular case of 3-SAT (or whatever known NP-Complete problem type one is using for leverage). Rather, they transform any arbitrary 3-SAT problem statement, in poly time, into an equivalent statement in the problem domain under consideration. By showing a transformation of any arbitrary problem, it covers all 3-SAT cases: trivial and intractable. All possible problem statements thus covered, no leap of faith is required.

If not, what sort of problem (and particular case thereof) are you referring to?

Re:Markets are efficient if and only if P = NP by leelin on Tuesday February 23, 2010 @04:27PM (#1146496)
Maybe you've ever seen the cool proof that "Tetris is NP-complete". I loved the paper and it was very entertaining. But it involved a much broader and general Tetris problem than the one found in Nintendo Gameboys, because the width and the height of the pit in the reduction was larger than all the console based tetris games I've ever seen.

My understanding is that Gameboy tetris, given the sequence of all future blocks as input and an empty pit starting state, is actually easy to solve computationally.

Similarly, I have to believe that the market as we know it contains some constraints, and all the historical data will abide by those constraints. To show the market problem is NP-hard, you would need all 3-SAT reductions to lead to a valid market problem. Going back to Tetris, IIRC, a large number of the reductions would lead to Tetris games that could not exist on Gameboy Tetris, because you would need a block-pit that is far taller than the game allows.

Re:Markets are efficient if and only if P = NP by pohl on Tuesday February 23, 2010 @10:15PM (#1147160)
I think I'm following now. You're saying that the author is assuming a model of economies that is more complex than an actual economy. That could be the first time ever that I've heard such a thing about any model, let alone of an economy. :-)

The only assumption that I see him making is the weak form of the Efficient Market Hypothesis.

I'm curious...how do you feel about that hypothesis, anyway? I've thought the EMH was a pretty strange and obviously false hypothesis ever since I first heard of it in the 80s (in college).

Just look at this statement from the Wikipedia page on the subject: It is the assumption "...that prices on traded assets already reflect all available information, and instantly change to reflect new information." This is a flimsy foundation to build on, because it's assuming the instantaneous propagation of information between economic actors. By what mechanism? Quantum entanglement? Crazy action at a distance?

I realize it was probably first intended in the same way that one uses a point-mass in physics ("we know it can't exist, but it makes the math easier") but I don't think it's quite as harmless as that.

Anyway, I'm happy to see the author taking such a clever swing at it.