3 ms·

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

by 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...
  - SolarNet 8y ago
    Not in the face of generic NP hardness. From your own link, even NP completeness is not enough. > Any strongly NP-hard [which may include strongly NP-complete] optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP I was criticizing someone for claiming the author's work is pointless. The author's work is an attempt to find a complexity class for markets (and the problem they solve). If we know the complexity class then maybe there is a PTAS. But without the author's work you can't begin to claim there is an epsilon.
    - throwaway37585 8y ago
      Right, but your statement was about NP hardness in general.
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.

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...
- SolarNet 8y ago
  Not in the face of generic NP hardness. From your own link, even NP completeness is not enough. > Any strongly NP-hard [which may include strongly NP-complete] optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP I was criticizing someone for claiming the author's work is pointless. The author's work is an attempt to find a complexity class for markets (and the problem they solve). If we know the complexity class then maybe there is a PTAS. But without the author's work you can't begin to claim there is an epsilon.
  - throwaway37585 8y ago
    Right, but your statement was about NP hardness in general.

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.