August 11, 2011
If computer scientists are right, you can make money on the market. If economists are right, you can compute fast.
I like papers that use one domain to notice non-trivial things about other domains. Here is a fun example:
Philip Maymin, Markets are Efficient if and Only if P = NP. Forthcoming in Algorithmic Finance. (video)
The majority of financial academics believe in market efficiency and the majority of computer scientists believe that P ≠ NP. The result of this paper is that they cannot both be right: either P = NP and the markets are efficient, or P ≠ NP and the markets are not efficient.
He shows that finding a market strategy (that is budget-conscious) and makes profit in a statistically significant way in a given model of market equilibrium is equivalent to the knapsack problem, which is NP-complete. So in order to quickly find strategies (i.e. before the end of time), P must equal NP.
He then shows that one can program the market to solve an arbitrary 3-SAT problem. Variables are represented by buy orders of securities, negated variables by sell orders, and conjunctions as order-cancels-order (a currently nonstandard financial instrument, but not too far out). The problem is converted to a set of OCO orders, which are then put on the market. If the market is efficient then there exists a way of executing (or not executing) the orders so that overall profit is guaranteed, and hence the outcome will tell us in polynomial time whether the problem can be satisfied. Market efficiency implies P=NP.
I am not 100% convinced by this last argument, although it is very fun. What if the polynomial checking is very slow? His setup seems to require waiting for a finite time, but if finding the profitable strategy is very slow this time might be too short. Hence the setup might not be able to reliably prove that the problem cannot be satisfied. However, he could just as well add the negated problem to the market and see if that gets solved.
In any case, it seems that the paper shows that computational complexity makes markets complex.
Of course, if hyperturing computation becomes possible (for example due to closed timelike curves) then markets might become efficient. There is some foreshadowing of this in Forward's Timemaster.
Posted by Anders3 at August 11, 2011 10:38 AM