5 ms·

While this is a fun, the title is a little strong. There are three limitations (whuch apply to many papers about P=NP). 1. The market could still be efficient

While this is a fun, the title is a little strong. There are three limitations (whuch apply to many papers about P=NP). 1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error. 2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true. 3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.

SolarNet 8y ago
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.
- 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.
totemizer 8y ago
1. in reality, nothing ever is continuous, and those small errors are black swans. 2. PN!=P not because we can't solve it, but because it is impossible to solve, because there are more possible solutions than space we can use to model them. (oversimplified, i know) 3. que?
adrianN 8y ago
While I technically agree with your points, you and the author use different definitions of "markets are efficient".
- vanderZwan 8y ago
  Could you elaborate on that?
hvidgaard 8y ago
There is an impedance mismatch between the terminology in economics and CS. CS is at it's core a hard math discipline, and absolute statements are used a lot, and they differ quite a bit from what people outside of the field understand. This paper assumes a basic knowledge about CS theory and economic theory. While you're right in your points here, the CS aspect of this paper leans on the CS theory. When a computer scientist say, "we cannot do this efficiently" it means, "We might be able to do this efficiently for some instances of the problem, but not for all instances". And when the scientist say "we can do this efficiently" it means "we know how to solve this in a way that when we double the input size, the difficulty will be a fixed factor larger. But it might be infeasible to solve any instance of the problem what so ever".
SilasX 8y ago
The result also exploits how the notion of efficient markets doesn’t include the computational time and cost of detecting the arbitrage opportunities, and so should be updated.

SolarNet 8y ago

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

totemizer 8y ago

1. in reality, nothing ever is continuous, and those small errors are black swans. 2. PN!=P not because we can't solve it, but because it is impossible to solve, because there are more possible solutions than space we can use to model them. (oversimplified, i know) 3. que?

adrianN 8y ago

While I technically agree with your points, you and the author use different definitions of "markets are efficient".

vanderZwan 8y ago
Could you elaborate on that?

hvidgaard 8y ago

There is an impedance mismatch between the terminology in economics and CS. CS is at it's core a hard math discipline, and absolute statements are used a lot, and they differ quite a bit from what people outside of the field understand. This paper assumes a basic knowledge about CS theory and economic theory. While you're right in your points here, the CS aspect of this paper leans on the CS theory. When a computer scientist say, "we cannot do this efficiently" it means, "We might be able to do this efficiently for some instances of the problem, but not for all instances". And when the scientist say "we can do this efficiently" it means "we know how to solve this in a way that when we double the input size, the difficulty will be a fixed factor larger. But it might be infeasible to solve any instance of the problem what so ever".

SilasX 8y ago

The result also exploits how the notion of efficient markets doesn’t include the computational time and cost of detecting the arbitrage opportunities, and so should be updated.