31 ms·
Markets are efficient if and only if P=NP (2010)
- pochamago 6y agoLike foodgore, but for economics.
- whoisburbansky 6y agoHow much does this matter given that in the vast majority of cases, we don't care about exact/perfect solutions to problems that might be NP complete in the general case, but usually have heuristic methods that work well enough for most practical purposes?
- na85 6y agoWell what I think is interesting as an amateur with an interest in economics and investing, is that if P!=NP then it would cast a great deal of doubt on so-called Technical Market Analysis or "Technicals" which are predicated on the Efficient Market Hypothesis being true. My own suspicions have been for quite some time now that fundamentals are what move markets and that technicals are mostly bullshit and are only valid because algo-traders school like fish based on technicals.
- whoisburbansky 6y agoThe efficient market hypothesis doesn't say anything about the amount of time it might take for markets to iron out inconsistencies and take into account new information; "the market can remain irrational longer than you can stay solvent." It's the sort of thing that's hard to falsify because you can always say "oh, it'll eventually become consistent." Given that, I don't think this fundamentally changes anything about "technicals," even if P!=NP, but my intuition a priori is also the same as yours, that "technicals" are mostly window dressing anyways.
- na85 6y ago>The efficient market hypothesis doesn't say anything about the amount of time it might take for markets to iron out inconsistencies and take into account new information Actually it does. The central premise of the Efficient Market Hypothesis is that all relevant information is already priced in. >"the market can remain irrational longer than you can stay solvent." Irrational behaviour by uninformed investors is theoretically already priced in, if the market is efficient.
- whoisburbansky 6y agoTaking that literally, it's clearly false; information can't affect prices faster than the speed of light.
- na85 6y agoAh yes the good ol' HN pedantry. Please go actually read the hypothesis and understand its central tenets.
- jabl 6y agoAh, but here's an interesting topic for an ambitious research project, "Efficient relativistic markets". The proposal would score cross-disciplinarity brownie points in the evaluation committee.
- hchasestevens 6y agoYou might be surprised to learn that the well-known economist Paul Krugman wrote in the late 70s about trade in relativistic scenarios, see https://en.wikipedia.org/wiki/The_Theory_of_Interstellar_Trade https://en.wikipedia.org/wiki/The_Theory_of_Interstellar_Tra... and http://www.standupeconomist.com/pdf/misc/interstellar.pdf http://www.standupeconomist.com/pdf/misc/interstellar.pdf (for the paper itself).
- jabl 6y agoAh, but of course. When you're not a subject matter expert what you think is a novel idea is something the actual experts have already investigated decades ago. sigh, oh well.
- akra 6y agoI thought technical analysis (as opposed to fundamental analysis) assumes markets aren't efficient and subject to things like herd behavior and other psychological effects of human decision making. Otherwise things like momentum trading wouldn't work (i.e. price would just gap to the true value if markets were indeed efficient). If tech analysis works at times for me it would show that markets aren't that efficient as a whole. IMO markets can't be efficient because we as humans aren't - our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc.
- bo1024 6y ago> our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc. The intuition behind the efficient market hypothesis is that each of these deviations from "homo economicus", if it occurs in a market, is an opportunity for someone else to make money. EMH says that opportunity won't be wasted, at least for very long.
- kohlerm 6y agoThat still means efficiency is lost. E.g. the market might fluctuate between non-optimal state. And then again in case monopolies build up, then there is no easy way to get out of a suboptimal state, because there are no real opportunities for someone else.
- shawnz 6y agoTechnical analysis doesn't depend on EMH being true, in fact it depends on EMH being false. It is not evidence based in any way.
- klyrs 6y agoThe first corollary that I see is that greedy algorithms will almost certainly suck for society at large. I'm looking specifically at the meme that public companies are somehow required to maximize short-term profits for their shareholders. Some NP-complete problem classes have polynomial time approximation schemes, but not all, unless P=NP. That is to say, sufficiently large markets may be arbitrarily inefficient. I'm curious to see that dichotomy resolved.
- whoisburbansky 6y agoIn every case of problems classes I have seen, in my admittedly limited experience, polynomial time approximation schemes only fail under pathological circumstances. I'm not convinced that there's a connection between pathological problem instances and problem sizes, necessarily, and I'm even less convinced that real-world markets would reflect such pathological instances.
- klyrs 6y agoGranted, but such a PTAS would need to be agreed upon and faithfully executed by all market players.
- unishark 6y agoGreedy algorithms suck compared to what? If the greedy algorithm still converges fastest and is closest to optimal compared to any other practical scheme, the paper's result still does not say anything of practical use.
- klyrs 6y agoThey suck at escaping local minima, for one. Your "if" is doing a ton of work there, and this paper is quite abstract market theory. The "practical use" is to better contextualize the efficient market hypothesis.
- unishark 6y agoThey don't escape local minimum at all. And that means they suck for society at large compared to what? Random guessing? A corrupt government price system? An omniscient one that can solve NP hard problems? The "if" motivates answering the question. Anyway markets have a lot more going on than a simple greedy algorithm. For injecting noise into the optimization to get out of local minima. Markets clearly have a lot of this.
- adrianN 6y agoWell given that this assumes rational actors and humans aren't really rational, it's probably not very important in practice.
- coldtea 6y ago>How much does this matter given that in the vast majority of cases, we don't care about exact/perfect solutions to problems that might be NP complete in the general case, but usually have heuristic methods that work well enough for most practical purposes? Well, define "well enough"... We do get results. Are they "well enough"?
- sacado2 6y agoEven better, in practice we have amazing tools nowadays that can solve practical NP complete problems in a reasonable amount of time (I mean, optimal solutions, not OK-ish ones).
- tingletech 6y agoSo much for capitalism then?
- benlivengood 6y agoInefficient markets still work; you just have to regulate the arbitration potential so it doesn't eat too much legitimate profit and regulate scammers to protect information-poor people. Hyper-optimizing just-in-time inventory and production practices and betting on the outcome at nanosecond timescales? Probably harmful. Investing in useful businesses? Probably pretty beneficial.
- rocqua 6y ago> Hyper-optimizing just-in-time inventory and production practices and betting on the outcome at nanosecond timescales? Probably harmful. Certainly, betting on nanosecond timescales seems very unlikely to be very beneficial for society at large.
- deleted 6y ago[deleted]
- anm89 6y agoYup. Go send yourself to the gulag because somebody published a paper.
- UK-Al05 6y agoThey just have better than what humans can plan.
- OscarCunningham 6y agoI suspect other solutions also require P=NP.
- Proven 6y agoNo. Free market capitalism is merely more efficient than any other known approach. From one of earlier responses: > you just have to regulate the arbitration potential so it doesn't eat too much legitimate profit Oh yeah? And why would someone who has the power to regulate do that in a way that doesn't optimize capitalism for the regulators and not some (unachievable!) academic optimum that you propose?
- readams 6y agoFrom 2010
- semi-extrinsic 6y agoAnd has been cited 39 times in that period FWICT. If it is a remarkable paper, it's definitely not attracted much attention.
- advanced-DnD 6y agostill arxiv and not published... it does say a lot of about the paper. .... and the paper is written in MS Office.
- marcosdumay 6y agoThere are entire conferences out there that only accept papers written in MS Word. Math, CS and Physics are the exception here.
- dang 6y agoIf curious see also 2018 https://news.ycombinator.com/item?id=17202950 https://news.ycombinator.com/item?id=17202950 2012 https://news.ycombinator.com/item?id=4589264 https://news.ycombinator.com/item?id=4589264 2011 https://news.ycombinator.com/item?id=2895474 https://news.ycombinator.com/item?id=2895474 Discussed at the time: https://news.ycombinator.com/item?id=1144548 https://news.ycombinator.com/item?id=1144548 and https://news.ycombinator.com/item?id=1124782 https://news.ycombinator.com/item?id=1124782 (a bit)
- ericjang 6y agoCurious, why does this specific arxiv submission keep on cropping up popularly over the years? Is this common for any top post?
- LolWolf 6y agoI'm also curious. This is a particularly... interesting (for lack of a better word) submission to appear so repeatedly. Maybe it's just the right word-combination to appear in hn? Computer science + finance, with a touch of academic-ish?
- kybernetikos 6y agoI think it's because people like to laugh at silly economists for thinking that markets are efficient. Of course economists know that markets are not perfectly efficient, but what they tend to believe is that markets tend towards efficiency, and markets that are big enough and free enough will correct trivial inefficiencies relatively quickly. This is why the advice is generally that returns in easy to access markets are very closely related to the risk you took on. If you made better than market returns, it's probably because (whether intentionally or not) you took on more risk than the market as a whole. This doesn't hold true for those with an information edge, but more people believe they have such a thing than actually have it.
- jokethrowaway 6y agoEnough time passed since the collapse of USSR and socialism is becoming popular again. Socialists need to discredit the market.
- adamnemecek 6y agoP==PN on analog photonic machines. A light prism calculates Fourier in O(1) (given a prism is not aware of Big O). Using Fourier, one can factorize a number in O(1), and then solve NP in P.
- FeepingCreature 6y agoPhotons are discrete.
- adamnemecek 6y agoWhat's your point?
- FeepingCreature 6y agoYou cannot do continuous computation with discrete components.
- beervirus 6y agoWhatever you're encoding into the light that gets shined on the prism... that process is probably not gonna be O(1).
- adamnemecek 6y agoIt's not, no. Whats your point? The factorization step is still O(1).
- beervirus 6y agoYou can't factorize a number in O(1) if it takes O(n) or whatever to set up the problem. Everything is O(1) if you can ignore steps.
- adamnemecek 6y agoI don't think you understand my point.
- philosopher1234 6y agoMarkets are obviously not efficient. The proof is trivial. Have you ever made a mistake? Congrats, that’s your proof. The market is a collection of people making decisions. People are capable of mistakes. People en masses are still people, and just as fallible, if not more. Thus, markets can and constantly do misprice things/inefficiently allocate capital. These real events are incompatible with perfectly efficient markets: * tulips * Bitcoin * google (billion dollar startups) * crashes * theranos * salem witch hunts that’s not to say markets are perfectly inefficient either. But they’re clearly fallible and imperfect. They clearly misinterpret available information all the time, even though they easily could’ve interpreted it correctly. Markets are full of emotion driven irrational actors, not Bayesian robotic egoless predictors, even though we like to pretend we’re the latter sometimes.
- ashtonkem 6y agoIt’s kind of amazing in retrospect that “the markets are efficient” was a position leading up to 2008 that didn’t get you laughed out of the room. Nowadays we know that markets aren’t perfectly efficient, 2008 was quite the instruction, and we can now have a serious discussion about degrees of efficiency and inefficiency that the markets achieve.
- quixoticelixer- 6y agoActually markets are efficient, they just aren't maximally efficient.
- kohlerm 6y agoThat is like saying that Bubblesort is efficent because it is more efficient than https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort :-) Unless you come up with an upper bound of efficiency loss your statement is IMHO pretty meaningless.
- nlitened 6y agoWasn’t 2008 crisis due to excessive risk-taking by government-backed banks? I doubt it is an “instruction” on markets efficiency — yes, if a government puts a lot of tax and newly-printed money in ponzi-schemes, bad things will happen.
- ummonk 6y agoThe only if is clear but the if side seems to be assuming that P=NP entails not just proving the existence of polynomial time solution algorithms but also constructing said algorithms?
- ericjang 6y agoThe report, while a fun thought exercise for any aspiring academic, is not a novel insight, and is obviously untrue for most definitions of market efficiency. If we are going to play the academic one-upmanship game, a more general result that "best" or "multiple" N-player Nash Equilibria for N > 2 is already NP-hard. The implication of an efficient market would be if every player had a polynomial-time algorithm to solve the NP-hard problem, ergo P=NP. [1] https://people.csail.mit.edu/costis/simplified.pdf https://people.csail.mit.edu/costis/simplified.pdf [2] https://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium-20170718/ https://www.quantamagazine.org/in-game-theory-no-clear-path-... [3] https://arxiv.org/abs/1104.3760#:~:text=Unlike%20general%20Nash%20equilibrium%2C%20which,as%20finding%20a%20planted%20clique https://arxiv.org/abs/1104.3760#:~:text=Unlike%20general%20N....
- LolWolf 6y agoYeah, even with unbounded computational power, Nash equilibria are communication-hard; i.e., you need exponentially many bits for an n-player game to converge to an equilibrium, even when all players have unbounded computational power. See https://arxiv.org/pdf/1608.06580.pdf https://arxiv.org/pdf/1608.06580.pdf.
- 02020202 6y agonot going to be reading that but markets ARE efficient. just because you think company Foo "should" be worth more/less does not mean everyone else agrees with you. what is someone willing to pay and what is someone willing to sell for is by definition the price of that thing. nothing else matters. markets are not about value but about price and price is not value. it's just worth of some thing to an individual, or many individuals - the market, in this case. these statements about markets not being efficient come from people that simply have no understanding of how or what the stock markets are to begin with. like teachers that have no real experience, just theoretical. these are the people that will never make good investments in their lives because it is simply beyond their understanding. not everyone can figure skate, not everyone can be an investor. yet it is so incredibly simple.
- LolWolf 6y agoThis paper just gets me every time I see it. It really doesn’t claim or do much that isn’t already quite obvious (it also has the other problem of going on completely unrelated tangents.) First, it does this funny thing where it “proves” that EMH (or market efficiency) is NP-hard, by building gadgets based on options and then using them to “embed” 3-SAT. This is fine except (a) we often don’t care about an exact solution (so we need approximation-hardness that isn’t shown) and (b) I can come up with millions of other obvious things like this! Here’s a silly one one: I give a derivative whose price is $1 if a solution (that is known to exist) to an NP-hard problem is found by a given time. This will “show the NP hardness of EMH” because obviously the derivative price should be 1 (the problem has a solution, by construction) and so anyone should “obviously” price it at $1. This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior. Taking it to its extreme then everything breaks, because the model is wrong. We don’t throw up our hands and quit because making real-life decisions is a sampling-hard, query-hard, and NP-hard problem (if all data is known), but a basic model of rationality would say that humans can “perfectly” solve it. (Which is obviously crazy, but we obviously don’t throw the assumption of rationality of agents out the window because of this.) Otoh, I am definitely of the opinion that some economists hold EMH as a “magical” axiom, but that’s a different story.
- murbard2 6y agoIt's not even needed to introduce weird derivatives, a publicly traded company can announce $1,000,000 dollar prizes for factoring a RSA keys. In fact, you can embed more powerful oracles like this, e.g. publicly traded company announces a $1,000,000 dollar prize for anyone who submits an inconsistent statement in ZFC. The EMH is a framework. With any scrutiny it's obvious that it can at most be first order accurate since obtaining and processing information is costly. This is not a particularly new insight or one that would be a surprise to any proponent of the EMH.
- yowlingcat 6y ago> The EMH is a framework. With any scrutiny it's obvious that it can at most be first order accurate since obtaining and processing information is costly. This is not a particularly new insight or one that would be a surprise to any proponent of the EMH. Great clarification. I'm always suspicious of interpretations of EMH that are a lot more literal than they should be, drawing effectively false conclusions from double negations. I think the truth is as you said.
- advanced-DnD 6y ago... you can't prove mathematical theory with social science 'theories'. The latter is not even well defined.. ln(x) \approx x (for interest rate)? common...
- johntfella 6y agofun combo read; https://arxiv.org/abs/1401.2982 https://arxiv.org/abs/1401.2982
- loourr 6y agoAnd we know markets to be efficient! Therefor P=NP QED
- shawnz 6y agoDoes this mean the Grossman-Stiglitz paradox proves P != NP?
- godelzilla 6y agoThis is an ok way to show that much of "theoretical economics" has no mathematical basis. But bad epistemology is rampant in economics. If "markets" are defined as purely mathematical, then they're not "real markets" (if such things even exist). If "markets" are part of reality, then they're divorced from pure mathematics. Either way it's misleading to place markets and P=NP in the same epistemological context.