7 ms·

The problem of market pricing in the economy is NP-hard. It's means as a human if you're good you'll always have a chance. At the very least you can pull moves

• deleted 11y ago
  [deleted]
• javajosh 11y ago
  >The problem of market pricing in the economy is NP-hard. Is it? I mean, I see how it's reflexive (and so chaotic) but NP-hard is the halting problem: given a program and it's input, decide if it halts. E.g. what is the input to your market function? It's like asking if the world halts. The thing about all complexity analysis is that it ignores input/output.
  • Scarblac 11y ago
    NP-hard is the class of problems that are at least as hard as NP. The halting problem is in there, but it isn't decidable _at all_. Just that its NP-hard doesn't mean it's as hard as the halting problem, it could be easily decidable in exponential time. Complexity analysis is all about the size of the input, it doesn't ignore it.
• pjc50 11y ago
  I don't see why you're being downvoted. Here's a reference for market pricing being almost certainly NP-hard: http://arxiv.org/pdf/1002.2284 http://arxiv.org/pdf/1002.2284 "Markets are efficient if and only if P = NP"
  • Natanael_L 11y ago
    Because of the assumption of there being a correct answer. It is as much a problem of definitions and arbitary valuation as anything. An academic analysis like what you linked to has to assume everybody have settled on the same definitions and valuations.
    • meric 11y ago
      That's true of all analysis. We can't even calculate 1 + 1 if we are not going to agree to the definition of the plus sign. See my other comment describing what a perfect answer looks like.
  • eru 11y ago
    There's a good argument to be made, that doing the market is harder than NP.
  • kd0amg 11y ago
    This paper's claim that finding an effective technical trading strategy is in NP relies on the search space for technical strategies being exponential in the length of history being considered (which it's not -- that's the size of a description of a single strategy) and the tacit assumption that historic performance of a strategy guarantees future performance.
• CJefferson 11y ago
  Market pricing can't be NP-hard -- if it was, that would mean there was a perfect answer, we just might not have to computing power to calculate it. I solve huge NP-hard problems every day, I've never seen any suggestion there is a useful way to solve marking pricing.
  • meric 11y ago
    The problem is thus: How to price every good and service at equilibrium in the economy, with regards to the marginal cost and marginal benefit of every individual for every good and service. You have not seen any suggestion to solve this problem, does not mean it isn't NP-hard. >> we just might not have to computing power to calculate it. There is a perfect answer, and there will almost never be enough computing power to calculate it. It is always approximated.
    • Natanael_L 11y ago
      Keywords being cost, benefit and every individual. Those are all big variables. Everybody will define what the cost and what the benefit of everything is differently, both from their own perspective and from the perspective they perceive that others has/should have. So you'll have more "perfect" answers than people, and no way to select any one of them.
      • meric 11y ago
        That's like saying if you don't have a GPS the travelling salesmen problem isn't at least NP complete because you don't know what the weights are and every edge has a different weight, which would screw with your calculations. It's not a valid argument against the fact that everyone does have their marginal benefit and marginal costs for every good and service that can translate to a binary decision of whether they would purchase a good or service at a given price. Just because you can't see it doesn't mean it's not there. And I'm not saying it's impossible to find out individuals marginal benefits and costs, because in markets you very well can. Stock traders, when evaluating whether a stock would go up or down, would often buy a bunch of stock, see how the market takes it, then sell a bunch, and by measuring how fast the market eats his orders, he can estimate the aggregate marginal benefit and cost of holding the stock, and then speculate accordingly.
• adrianN 11y ago
  A problem being NP hard doesn't mean that humans are competitive against computers. I'd like to see you solve SAT instances faster than cryptominisat, or do linear optimization better than Gurobi.
  • meric 11y ago
    We have more of a chance solving complex problems better than AI, than if we were solving "simple" problems like chess, or even, Go. EDIT: Added rabbit ears for simple.
    • adrianN 11y ago
      Those are not simple problems. Generalized Chess is EXPTIME complete, so I'd say it's pretty hard.
• jackcosgrove 11y ago
  An advisory service could recommend a hostile takeover, but not execute it. You don't need to solve an NP hard problem to beat human intervention. You just have to be faster and more accurate. I do think that computers could outperform humans on the supply side, calculating the costs of production relative to competitors better than humans. The demand side is trickier but again computers would do a better job calculating available cash and then ranking marginal goods' likelihood of being purchased based on existing prices. As long as prices and production processes are public knowledge computers will do better than people at modeling the economy. Humans only gain an advantage through insider knowledge and trade secrets.