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.
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.