"The market will only be efficient enough such that the marginal cost of making the market more efficient is equal to the marginal benefit of doing so."

Do we have a model of what markets are like under this type of model? It is not clear to me that prices are even close to what efficient ones might be under this situation (though they could be).

Also of course most of the missing markets are the contingent and future ones, which suggests the ways in which things might be biased (forward planning, the firm, the business cycle etc) which are quite important inefficiencies.

  "Do we have a model of what markets are like under this 
  type of model? It is not clear to me that prices are even 
  close to what efficient ones might be under this situation 
  (though they could be)."

I don't know what markets are like under this type of model but here are a two papers recommended by my lecturer on how efficiency is not an either-or proposition.

Adaptive Markets and the New World Order

"Under the AMH, markets are not always efficient, but they are highly competitive and adaptive, and can vary in their degree of efficiency as the economic environment and investor population change over time."

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1977721&#...;

Efficient Markets II (by Fama who was the one who originally came up with the efficient market hypothesis describing the three forms of market efficiency)

"A weaker and economically more sensible version of the efficiency hypothesis says that prices reflect information to the point where the marginal benefits of acting on information (the profits to be made) do not exceed the marginal costs (Jensen (1978))."

http://efinance.org.cn/cn/fm/Efficient%20markets%20II.pdf

  "Also of course most of the missing markets are the 
  contingent and future ones, which suggests the ways in 
  which things might be biased (forward planning, the firm, 
  the business cycle etc) which are quite important 
  inefficiencies."

You can often find sets of stock options' prices that you can arbitrage and make a profit, but only if there were no transaction costs. Information will only be taken into account of if the cost of the information (after taking into account all costs including opportunity costs and risk) is less than the benefit from exploiting that information. So, there are probably lots of information from the future that are missing in the market, which if properly exploited will provide a lot of benefit; but the costs of gathering that information is even greater, possibly requiring the use of a time machine.

My thinking: It could very well be that markets are only efficient only as far as everything else allows it to be; If investors are not able to evaluate information over more than one business cycle, (due to the cost of doing so, economical or psychological or otherwise), then so be it. The market will move its efficiency to match the environment and its participants.

Great point. I am certain that NP-complete problems that can be efficiently approximated can be approximated by markets. No reason why you can't replace algorithms and expertes in your ensemble or regret minimization framework with humans.

A market can compute in some time period only that which is computable in that time period. The only one that says otherwise is the author of this paper, who then uses this assumption to prove... nothing really.