Link o' the Day: Markets are Efficient If and Only If P = NP
Posted on August 24, 2011
by Tommy McGuire
This one from Jeff: a pointer to If computer scientists are right, you can make money on the market. If economists are right, you can compute fast, which is a reference to a paper to appear in Algorithmic Finance by Philip Z. Maymin, Markets are Efficient If and Only If P = NP.Economics and computer science have some things in common; they are the only two fields I know where exponential growth is a common situation, for one thing. Now, speaking as an innocent economic bystander, I have been convinced by the arguments in favor of the weak efficient market hypothesis, that "that future prices cannot be predicted by analyzing prices from the past" (my emphasis), but significantly unconvinced by any of the arguments for any of the stronger forms, specifically the semi-strong (that the current price incorporates all publicly available information) and the strong form (that the current price incorporates all private information). I am also a computer scientist, falling into the "I believe P is not equivalent to NP" camp.
This paper seems to argue that even the weak form is untenable, because the complexity of identifying an exploitable-inefficiency in the stream of market data requires exponential resources (while verifying an inefficiency requires only polynomial resources). As Anders Sandberg says, "In any case, it seems that the paper shows that computational complexity makes markets complex."
I am not sure I buy the complete argument, particularly the second half, where Maymin attempts to encode the SAT-3 problem in market orders, but the paper does have an interesting perspective. Maybe those head-n-boulders charts are good for something.
