Link o' the Day: Markets are Efficient If and Only If P = NP

Posted on August 24, 2011 by Tommy McGuire
Labels: theory, link, math
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.
active directory applied formal logic ashurbanipal authentication books c c++ comics conference continuations coq data structure digital humanities Dijkstra eclipse virgo electronics emacs goodreads haskell http java job Knuth ldap link linux lisp math naming nimrod notation OpenAM osgi parsing pony programming language protocols python quote R random REST ruby rust SAML scala scheme shell software development system administration theory tip toy problems unix vmware yeti
Member of The Internet Defense League
Site proudly generated by Hakyll.