3 ms·

I skimmed it quickly too, but I think you've misread. The "interesting" claim isn't the 3-SAT encoding; it's earlier where he claims that markets "naturally" ha

by uvdiv 14y ago

I skimmed it quickly too, but I think you've misread. The "interesting" claim isn't the 3-SAT encoding; it's earlier where he claims that markets "naturally" have to solve NP-hard problems, in particular that to optimize an investment strategy you have to solve the Knapsack problem. (?!) It's hand-waving nonsense.

pron 14y ago
It doesn't matter. When people say efficient market, they mean that the market knows whatever is knowable by the present time using current technologies. They don't mean that the market knows everything that's theoretically knowable using unknown/impossible algorithms. Before there were computers in an efficient market (supposing one exists), the current prices would reflect everything that is known and can be computed/deduced without computers by the present time. Anyway, the paper misunderstands "known" to mean "anything which can theoretically be known", which obviously includes solutions NP-hard problems. It's just that nobody claims that's what efficient markets are.
- 001sky 14y ago
  RE: When people say efficient market The hypothesis is predicated on perfect rationality. http://en.wikipedia.org/wiki/Perfect_rationality http://en.wikipedia.org/wiki/Perfect_rationality vs http://en.wikipedia.org/wiki/Bounded_rationality http://en.wikipedia.org/wiki/Bounded_rationality
Dn_Ab 14y ago
I'm surprised he decided to use 3-SAT instead of pointing out the non-convexities which arise in optimization for many interesting markets. Or the problem with digital goods say. That these are exploitable is what leads to excess returns and monopolies. These are failings due to reasons one can argue with computational compexity (non convex optimization is in NP).
- csense 14y ago
  > Or the problem with digital goods say. That these are exploitable is what leads to excess returns and monopolies. Copyright and network effects are the main reasons monopolies exist in digital goods.
  - Dn_Ab 14y ago
    The issue with digital goods is also the matter of uncertainty, the issue to do with scarcity or lack thereof and the trickiness of information as a good itself. In essense there is a built in inefficiency for information goods. But the points you bring up are correct and extend beyond digital goods.

by uvdiv 14y ago

pron 14y ago

It doesn't matter. When people say efficient market, they mean that the market knows whatever is knowable by the present time using current technologies. They don't mean that the market knows everything that's theoretically knowable using unknown/impossible algorithms. Before there were computers in an efficient market (supposing one exists), the current prices would reflect everything that is known and can be computed/deduced without computers by the present time. Anyway, the paper misunderstands "known" to mean "anything which can theoretically be known", which obviously includes solutions NP-hard problems. It's just that nobody claims that's what efficient markets are.

001sky 14y ago
RE: When people say efficient market The hypothesis is predicated on perfect rationality. http://en.wikipedia.org/wiki/Perfect_rationality http://en.wikipedia.org/wiki/Perfect_rationality vs http://en.wikipedia.org/wiki/Bounded_rationality http://en.wikipedia.org/wiki/Bounded_rationality

Dn_Ab 14y ago

I'm surprised he decided to use 3-SAT instead of pointing out the non-convexities which arise in optimization for many interesting markets. Or the problem with digital goods say. That these are exploitable is what leads to excess returns and monopolies. These are failings due to reasons one can argue with computational compexity (non convex optimization is in NP).

csense 14y ago
> Or the problem with digital goods say. That these are exploitable is what leads to excess returns and monopolies. Copyright and network effects are the main reasons monopolies exist in digital goods.
- Dn_Ab 14y ago
  The issue with digital goods is also the matter of uncertainty, the issue to do with scarcity or lack thereof and the trickiness of information as a good itself. In essense there is a built in inefficiency for information goods. But the points you bring up are correct and extend beyond digital goods.