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.
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.
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.
* 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.
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.
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.
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.
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.
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.
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.
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.
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.
The EMH is specific to asset markets. So stocks and bonds basically. No (respectable, well-known) economist has ever argued that all markets are always efficient.
Also what people mean when they say markets are efficient in other contexts means something very different. The EMH specifically describes how quickly and what kinds of information get incorporated into asset prices. It doesn't make claims about how markets organize production or optimize utility without centralized direction, which is usually what people mean when they say free markets are efficient.
I think a lot of confusion has arisen from the very general-sounding name of the hypothesis which does not reflect its relatively narrow claims. Not that I buy the EMH (no pun intended), but that's a different story.
EMH that this paper refers to is about financial markets. In other areas of econ, no one is claiming that markets are efficient, in fact most of econ talks about "first best", "second best", "losses in efficiency", etc.
So called "Perfect Information", as you point out, is an important requirement of the efficient market hypothesis, but not the only one. It also requires fungible goods (e.g., if I start making bicycles that are better and cheaper than your bicycles, they will necessarily sell more. That's often not the case, especially if there is strong branding).
Another requirement is that entrepreneurs have fair market access to capital. This assumption is true in many developed countries, but not in many developing countries where you need connections to obtain a loan. But even in developed countries, it's difficult to get extremely large loans on the merits of the financials alone, which explains why large infrastructure projects like highways, airports, and power-plants often don't get built solely by the private sector.
Private information here refers to whatever insights you bring with your research. The point is that if you gain some private information (by being a quant, analyst, etc.) you would immediately trade on it and the price would then start reflecting your views.
Also EMH, and that's the point Fama uses a lot to battle critics, does not put a time frame on when the price adjustment happens.
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.
This. Economists and decision theorists like Herb Simon have been actively modeling "bounded rationality" since the 70s, but well before that, literal interpretations of efficient market theory were limited to those with something to sell (mainly to regulators). There are limits to human (and corpory) rationality that kick in way before P?=NP.
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".
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.
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?
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.