6 ms·

On two, as this appears to be a cross disciplinary paper, it's important to consider that some economists currently claim markets are efficient (the efficient m

On two, as this appears to be a cross disciplinary paper, it's important to consider that some economists currently claim markets are efficient (the efficient market hypothesis, which is like a big open question in economics). By drawing a link between the EMH and P=NP (which many computer scientists believe is unlikely) the author is linking two open questions with opposing beliefs. So I think point two is sort of a technicality that with context it should be understood that the author is specifically talking about two open questions as they stand today. Also to further hammer home the point, due to the phrasing of the EMH, although no one may currently be using P=NP, markets would still have the efficiency property now even if no one is exploiting it. Perhaps this sort of vacuously true statement rubs you the wrong way (like it does me a bit) with the strength of the "if and only if" the author used. But if you read "markets are efficient" as the EMH then it is still a valid literal formulation. On three, sure that's great for reality. But for the formulation of markets being efficient as an inherent property (again the EMH) of markets, the size of the market could be held as effectively infinite (or at least extremely large) and the property should still hold. At some point the size of the theoretical market will explode the polynomial, and for the EMH to hold P=NP must be true.

stale2002 8y ago
In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. IE, it is almost as good. So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough. Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin with.
- SolarNet 8y ago
  Sure, but significant facts come out of it: * Economic systems are optimization algorithms on an NP hard problem. Hence markets have no special efficiency capabilities, they are simply a choice of optimization algorithm, there may be better ones out there with more favorable properties. Any optimization algorithm with similar resources could have effectively equivalent efficiency. This destroys the economic calculation problem. * That you are wrong about the small epsilon. You can't make even that kind of guarantee in the face of NP hardness. What the market has a state may be wildly far away from the optimum, the market could be stuck in a local minima, and without P=NP you can't even know how far from optimum you are. Without a complexity class for markets you can't even begin to discuss it's properties, and that's what this paper is an attempt at. It is your cleverness that misses the point, the author is trying to attach 21st century computational theory to economics (he may be wrong, but economic theories aren't going to help disprove it) and it's going to have some consequences.
  - mzl 8y ago
    The concept of NP-complete is different form the concept of np-hard to approximate in any way. The question if a particular problem is hard to approximate is typically a diverse and interesting research area, that does not have obvious answers. For example, it has been proven that the well-known traveling salesperson problem on metric instances (i.e., instances satisfying the triangle inequality) can not be approximated within around 1.008 unless P=NP, and there is an approximation algorithm that has factor 1.5. I have not read the above pre-print, but from a cursory glance it does not discuss theoretical approximation hardness at all. It does have a section on approximations, but it is hand-wavy and fluffy and uses a colloquial/non-strict meaning for approximation.
    - deleted 8y ago
      [deleted]
    - SolarNet 8y ago
      This is why I support the authors research, without knowing if it even is NP complete (as this paper claims) we are faced with it being NP hard. Without studying the problem, we can't even begin to find approximation algorithms.
      - mzl 8y ago
        The paper claims NP-completeness AFAICS, so I thought that was what you meant. Sorry if I misunderstood. There are problems that have approximations that can get arbitrarily close to the optimum. One particularly interesting case IMHO are so-called polynomial approximation schemes. These schemes can be used to create an approximation algorithm for any choice of approximation factor and that algorithm will have a polynomial time complexity, but the polynomial will depend on the actual approximation factor chosen. I agree that it is an interesting problem to study, especially since it meshes well with my own biases that the efficient market hypothesis is too strong.
  - throwaway37585 8y ago
    > You can't make even that kind of guarantee in the face of NP hardness. You can. https://en.m.wikipedia.org/wiki/Polynomial-time_approximation_scheme https://en.m.wikipedia.org/wiki/Polynomial-time_approximatio...
- coldtea 8y ago
  >In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. In economics, yes. In real life, not so much.
  - stale2002 8y ago
    For utilty functions? Why not? IE, if a person is only 1$ poorer than the efficient solution, that's not a big deal.
- nwah1 8y ago
  Markets don't need to be 99.9999% efficient either. Central planning can have a wide variance in efficiency. It could be substantially more efficient or extremely inefficient. If markets are able to reliably produce more efficiently year after year, even at the cost of lower peak-efficiency, then markets can still triumph in the long run.
ianai 8y ago
I don’t think economists claim markets are efficient. There’s far too many examples to the contrary - see amazon, wellsfargo, and Verizon as examples. While those companies do technically have competition, they operate with significant market power. Also, I once heard an Econ explain EH as “true if enough people operate under the assumption that it is not true” Edit-After waking up a little more, I’m not entirely sure of my statement that amazon, wellsfargo, and Verizon serve as examples against EH. But the later quote I heard from someone with 30+ years of research.
- sshine 8y ago
  The "true if enough people operate under the assumption that it is not true" is funny and somewhat intuitive: If you know markets are efficient, there is no reason to haggle about the price. But haggling is the mechanism that enhances price efficiency.
  - speedplane 8y ago
    In a truly efficient market, you wouldn't need to haggle about the price. You would have a slew of options that you could choose from, and would choose the option that best fits your demand. In an efficient market, if you were ever being overcharged by a company, another company would pop up overnight, and you would immediately switch from one to the other. No haggling required, just knowledge of what's available and easy movement from one option to another.
- yellowstuff 8y ago
  The efficient market theory is that all information, public and private, is incorporated into all stock prices at all times, so there's no point to researching companies to try to outperform the stock market. I don't think anyone believes it is literally true, just that it is a good model for most stocks most of the time. If everyone believed it then no one would bother to research stocks, and the markets would be less efficient.
  - cimmanom 8y ago
    That's a far more limited claim. There's a very common claim that "markets are efficient". Extending to all markets all the time. Explaining why market based solutions are the best way to provide health care and education and other (arguably common) goods. But many markets (the labor market, the health care market, etc) work in such a way that it's ridiculous to assume that most participants know all public and private information all or most of the time.

stale2002 8y ago

In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. IE, it is almost as good. So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough. Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin with.

SolarNet 8y ago
Sure, but significant facts come out of it: * Economic systems are optimization algorithms on an NP hard problem. Hence markets have no special efficiency capabilities, they are simply a choice of optimization algorithm, there may be better ones out there with more favorable properties. Any optimization algorithm with similar resources could have effectively equivalent efficiency. This destroys the economic calculation problem. * That you are wrong about the small epsilon. You can't make even that kind of guarantee in the face of NP hardness. What the market has a state may be wildly far away from the optimum, the market could be stuck in a local minima, and without P=NP you can't even know how far from optimum you are. Without a complexity class for markets you can't even begin to discuss it's properties, and that's what this paper is an attempt at. It is your cleverness that misses the point, the author is trying to attach 21st century computational theory to economics (he may be wrong, but economic theories aren't going to help disprove it) and it's going to have some consequences.
- mzl 8y ago
  The concept of NP-complete is different form the concept of np-hard to approximate in any way. The question if a particular problem is hard to approximate is typically a diverse and interesting research area, that does not have obvious answers. For example, it has been proven that the well-known traveling salesperson problem on metric instances (i.e., instances satisfying the triangle inequality) can not be approximated within around 1.008 unless P=NP, and there is an approximation algorithm that has factor 1.5. I have not read the above pre-print, but from a cursory glance it does not discuss theoretical approximation hardness at all. It does have a section on approximations, but it is hand-wavy and fluffy and uses a colloquial/non-strict meaning for approximation.
  - deleted 8y ago
    [deleted]
  - SolarNet 8y ago
    This is why I support the authors research, without knowing if it even is NP complete (as this paper claims) we are faced with it being NP hard. Without studying the problem, we can't even begin to find approximation algorithms.
    - mzl 8y ago
      The paper claims NP-completeness AFAICS, so I thought that was what you meant. Sorry if I misunderstood. There are problems that have approximations that can get arbitrarily close to the optimum. One particularly interesting case IMHO are so-called polynomial approximation schemes. These schemes can be used to create an approximation algorithm for any choice of approximation factor and that algorithm will have a polynomial time complexity, but the polynomial will depend on the actual approximation factor chosen. I agree that it is an interesting problem to study, especially since it meshes well with my own biases that the efficient market hypothesis is too strong.
- throwaway37585 8y ago
  > You can't make even that kind of guarantee in the face of NP hardness. You can. https://en.m.wikipedia.org/wiki/Polynomial-time_approximation_scheme https://en.m.wikipedia.org/wiki/Polynomial-time_approximatio...
coldtea 8y ago
>In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. In economics, yes. In real life, not so much.
- stale2002 8y ago
  For utilty functions? Why not? IE, if a person is only 1$ poorer than the efficient solution, that's not a big deal.
nwah1 8y ago
Markets don't need to be 99.9999% efficient either. Central planning can have a wide variance in efficiency. It could be substantially more efficient or extremely inefficient. If markets are able to reliably produce more efficiently year after year, even at the cost of lower peak-efficiency, then markets can still triumph in the long run.

ianai 8y ago

I don’t think economists claim markets are efficient. There’s far too many examples to the contrary - see amazon, wellsfargo, and Verizon as examples. While those companies do technically have competition, they operate with significant market power. Also, I once heard an Econ explain EH as “true if enough people operate under the assumption that it is not true” Edit-After waking up a little more, I’m not entirely sure of my statement that amazon, wellsfargo, and Verizon serve as examples against EH. But the later quote I heard from someone with 30+ years of research.

sshine 8y ago
The "true if enough people operate under the assumption that it is not true" is funny and somewhat intuitive: If you know markets are efficient, there is no reason to haggle about the price. But haggling is the mechanism that enhances price efficiency.
- speedplane 8y ago
  In a truly efficient market, you wouldn't need to haggle about the price. You would have a slew of options that you could choose from, and would choose the option that best fits your demand. In an efficient market, if you were ever being overcharged by a company, another company would pop up overnight, and you would immediately switch from one to the other. No haggling required, just knowledge of what's available and easy movement from one option to another.
yellowstuff 8y ago
The efficient market theory is that all information, public and private, is incorporated into all stock prices at all times, so there's no point to researching companies to try to outperform the stock market. I don't think anyone believes it is literally true, just that it is a good model for most stocks most of the time. If everyone believed it then no one would bother to research stocks, and the markets would be less efficient.
- cimmanom 8y ago
  That's a far more limited claim. There's a very common claim that "markets are efficient". Extending to all markets all the time. Explaining why market based solutions are the best way to provide health care and education and other (arguably common) goods. But many markets (the labor market, the health care market, etc) work in such a way that it's ridiculous to assume that most participants know all public and private information all or most of the time.