Re:Markets are efficient if and only if P = NP
by yummyfajitas on Tuesday February 23, 2010 @12:24AM
(#1144765)
Dupe. This paper is new, but the result is not.
The paper Betting on Permutations by Pennock, Chen, Fortnow and Nikolova already proves this.
Consider a race between n runners. Now consider a prediction market accepting bets of the form "X will finish before Y". They prove that the market maker/auctioneer problem is NP hard. Conversely, if markets are efficient, then they solve the market maker/auctioneer problem.
Re:Markets are efficient if and only if P = NP
by Spark23 on Tuesday February 23, 2010 @05:00AM
(#1145093)
But having an efficient market doesn't imply that an algorithm \in P exists for that problem ??
Efficient markets just imply decidability of the problem.
The paper Betting on Permutations by Pennock, Chen, Fortnow and Nikolova already proves this.
Consider a race between n runners. Now consider a prediction market accepting bets of the form "X will finish before Y". They prove that the market maker/auctioneer problem is NP hard. Conversely, if markets are efficient, then they solve the market maker/auctioneer problem.