[stale2002]

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]

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]

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.

[SolarNet]

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]

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]

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

[SolarNet]

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]

Right, but your statement was about NP hardness in general.

[coldtea]

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

For utilty functions?

Why not?

IE, if a person is only 1$ poorer than the efficient solution, that's not a big deal.

[nwah1]

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.