9 ms·
Markets are Efficient if and Only if P = NP
- ColinWright 15y agoIt feels to me that all he's done is show that the "instantly" in the usual definition of markets being "efficient" is a nonsense. Prices must take time to compute, you can't know the correct price instantly even with access to all the past information. He proves that, but it doesn't seem that surprising to me.
- gfodor 15y agoIf it's true it uproots a lot of conventional wisdom about trading and the ability to time the market.
- mquander 15y agoNo, it doesn't. Relevant conclusions about markets in a theoretical sense all depend on (from the link) "current prices...[reflecting]...information available in past prices," which isn't even approximately true in the real world; current prices are driven by irrational actors with incomplete information.
- gfodor 15y agoWhat you're saying here is not 'conventional wisdom.' Conventional wisdom (at least, fundamental analysis) is that the price on the market incorporates all information and that the market is by and large full of rational actors. So, timing the market is a fool's errand, since you can't get ahead of the present. I'm not saying I agree with this, I'm just saying that that's what you're taught in school. If there were a way to prove this indisputably incorrect then it would probably be an interesting result.
- adas 15y agoANUS FUCKER!
- peteretep 15y agoI was coming here to write almost exactly this. Markets are provably not 'instantly' efficient because arbitrage exists. Arbitrage is simply not possible in an efficient market, because it's an exploit of inefficiency. However, exploitation of abitrage (and of knowledge generally) is what makes markets largely efficient.
- Rickasaurus 15y agoThe point though is that whoever has the most computational power has the most power to exploit arbitrage.
- peteretep 15y agoThat's /a/ point. Whenever people start harping on about Market Efficiency, you need to find out "why do you care?". The answer to "Are markets efficient? I have this hot stock tip I read on Tech Crunch" then the answer is yes, because other people have more time, money, expertise and - as you point out - computational power - as well things like preferential data access and physical proximity to the exchange.
- CWuestefeld 15y agoWhile I'm pretty much a free-market zealot, I'm also a Hayek groupie. It seems to me that Hayek's work should show us that markets approach perfect efficiency. Because the market is a hideously complex system that only produces its information as an evolved, emergent system, then it is likely that its output is not precise but only extremely close to optimal.
- jbooth 15y agoWas the fall of 2008 "extremely close" to optimal? I'd submit that worldviews based on 1-dimensional criteria like "market!" or "hayek!" fall pretty far short of the mark. Although I can see the attraction. It's nice to simplify things to a level where a human being can actually have the answers with a high degree of confidence. Both the tea-party-hayekians and the linked paper fall into this trap.. what about information asymmetry? What about borked incentives? What about just plain stupid? "I played golf with the guy so I'll buy it"? "I know these instruments are crap but I'll sell them to my clients to get them off my balance sheet"? A friend was telling me at his old job, they actually worked in season tickets to a luxury booth at Yankee stadium into a very significant tech purchase. Is that market efficiency?
- CWuestefeld 15y agoI'm not sure you understand what the free market is, or how it works. The fall of 2008 wasn't a free market. In particular, the government was forcing lenders to accept more risk (viz sub-prime borrowers) than they would otherwise have done. Also, the lenders themselves incorrectly modeled their risk exposures. None of your objections: what about information asymmetry? What about borked incentives? What about just plain stupid? "I played golf with the guy so I'll buy it"? "I know these instruments are crap but I'll sell them to my clients to get them off my balance sheet"? hold any water: Information asymmetry (also, incorrect information as with lenders in '08): This has nothing to do with the efficiency of markets. The efficient market hypothesis depends on actors behaving rationally to achieve their goals. That does not mean that those actors will always be correct. For example, in The Myth of the Rational Voter[1], Caplan describes how it's actually rational behavior for voters to vote irrationally: the benefit of the degree they can sway the election is far smaller than the cost of acquiring sufficient knowledge to determine what candidate would most benefit them. Bad incentives: it's the incentives (see "Invisible Hand") that make things work properly! To the extent that the incentives are wrong, these are the regulations, the aberrations that make things deviate from the free market. In your '08 complaint, that was the Congress forcing lenders to take on borrowers that would not normally have qualified. It also comes from externalities, places where our laws prevent the free market from completely accounting for the costs of an action. For example, because air and waterways are held in common by the government, without a real owner, there is nothing capturing the cost of pollution. Thus, incomplete property rights leads to market failures. If the government got out of the way, the market could resolve it (see "Coase Theorem") Stupidity: as separate from your other points, well, there's no such thing -- at least not that we can perceive. Mises shows that (a) each person acts to maximize his own utility, and (b) it's impossible for outside observers (and frequently even the individual himself) to know what ends he is attempting to achieve. Thus, if your hypothetical golfer places some personal value on the relationship with his golf buddy, it may be perfectly rational for him to spend extra few bucks buying from the guy. And you and I certainly aren't privy to enough information to decide that it's not so. Fraud: your Yankees example seems to be an example of fraud, and thus can't be considered a free market transaction. Fooling someone into a transaction is no different from forcing them into a transaction. That said, research in psychology and econometrics has shown that people do systematically misconstrue very large or very small values, leading us to sometimes choose differently from what we really intend. The only solution to this, of course, is to formally model the problem to enable us to act rationally. In this day and age, such models are de rigeur, but -- as I note above -- the investment in the models itself has some risk: we're balancing correctness against cost to develop and feed the model. As with the rational voter, this can lead us to "rationally irrational" behavior, but this is just a meta-behavior of the free market, not an indictment of it. Moreover, there is no way around any of the issues that you cite. All of these things can be applied equally -- if not more -- to government regulators (see "public choice economics", "regulatory capture", etc.). Why would you want to give power to entities who won't be able to use it any more wisely than the people themselves? [1] http://en.wikipedia.org/wiki/The_Myth_of_the_Rational_Voter http://en.wikipedia.org/wiki/The_Myth_of_the_Rational_Voter [2] http://en.wikipedia.org/wiki/Human_Action http://en.wikipedia.org/wiki/Human_Action
- deleted 15y ago[deleted]
- ChuckMcM 15y agoPretty much in a nutshell his exposition. For me, my interest lies in the economic value of information, and one way in which information gains value is by being 'timely.' When explaining to folks I often use the example that the 15 minute delayed stock price feed (aka 'ticker') is less valuable than the real time stock 'ticker'. This is intuitive for many folks but the OP's work shows the math behind that intuition. Stock price feeds are generally used by algorithms to anticipate the market price of a commodity and act when there is a delta between that and reality. They 'manufacture' new information by taking that real time stock feed and identifying trends. Their market value then becomes a function of their ability to identify trends sooner and thus allow for capturing the most value between the current price and the correct price.
- 3pt14159 15y agoTitle should read: "If markets are perfectly efficient P=NP" rather than "Markets are efficient if and only if P = NP". For example, say P = NP, but the only person that knows the proof is me. If I start using my knowledge that P = NP to trade I will not have enough capital to swing the market to truly reflect the efficient price. Therefore it does not follow that if P = NP the market will be perfectly efficient, which is required in an "if and only if" proof.
- gwern 15y ago> If I start using my knowledge that P = NP to trade I will not have enough capital to swing the market to truly reflect the efficient price. How long would it take you to gain enough capital to start moving prices? If you have a systematic edge on all trades... In any event, I didn't find OP interesting the first time and I don't know. Most people aren't using OP's extremely strong definition of efficient market, but merely saying that humans and current algorithms cannot over long periods extract money; it's a statement about the market vs other actors, not markets versus omniscient gods.
- kragen 15y agoResults like general equilibrium are conditional on the OP's extremely strong definition of efficient market. Whether or not you personally can get rich by beating the market is not the only possible interesting question about economics!
- jsharpe 15y agoOr maybe just "Markets can be perfectly efficient if and only if P = NP".
- bugsy 15y agoIn the paper he states "I also prove the converse", meaning the iff clause is justified.
- tokenadult 15y agoHacker News submission and discussion from 540 days ago of previous version of same author's paper: http://news.ycombinator.com/item?id=1144548 http://news.ycombinator.com/item?id=1144548
- nopassrecover 15y agoI also posted the author's video explanation here the other day: http://news.ycombinator.com/item?id=2867429 http://news.ycombinator.com/item?id=2867429
- aklein 15y ago"The majority of financial academics believe in market efficiency and the majority of computer scientists believe that P ≠ NP. The result of this paper is that they cannot both be right: either P = NP and the markets are efficient, or P ≠ NP and the markets are not efficient." I'll hazard a guess the computer scientists are right, but most financial academics will probably get by just fine if markets are approximately efficient - if prices can be estimated in probabilistic polynomial time.
- mseebach 15y agoI'm pretty sure financial academics don't claim that markets are efficient, but that they tend towards efficiency.
- wpietri 15y agoFor those wanting to know more about the efficient-markets hypothesis, Wikipedia has a good article: http://en.wikipedia.org/wiki/Efficient_markets http://en.wikipedia.org/wiki/Efficient_markets My amateur understanding is that most academics get that it's a simplifying assumption, but that a lot of other people treat it as a guarantee. It's sort of like people who learn a little about evolution and then conclude that a) we are the most highly evolved organism on the planet, and b) we are therefore perfect.
- artsrc 15y ago> a) we are the most highly evolved organism on the planet I know little about evolution and assume that bacteria are the most evolved because they have a faster cycle of reproduction, and stronger selective pressure. > My amateur understanding is that most academics get that it's a simplifying assumption, but that a lot of other people treat it as a guarantee. Most practitioners do understand that it is a simplifying assumption, and then ignore that fact, just as most engineers ignore quantum and relativity effects when calculating the required size of beams. The difference between the better and the simpler models is big enough to cause problems in economics.
- zeteo 15y agoEven if the problem that markets are trying to solve is NP hard, this doesn't mean anything. Market forces are always subject to random factors. For practical purposes, randomized approximation algorithms are actually a great choice for tackling NP hard problems.
- tmeasday 15y agoSometimes. I think the simple answer to that is 'it depends on the problem'.
- knowtheory 15y agoThat's not an answer, that's an IOU for an answer, unless you can begin to describe broad classes of problems and how they differ.
- bradshaw1965 15y agoPeople get tied up in knots about the Efficient Market Hypothesis. The factor that often gets ignored when approaching the problem is the costs factor. Trading fees, Analysis, Commissions, etc. make it very hard in practicality to beat passive investment with the markets only being passably efficient.
- artsrc 15y agoI think that analysis ignores tax effects. To have a stable excess return you need some collection of people accept a stable lower return. This is possible if you have different tax regimes. Tax advantaged entities can accept coupons/dividends, and highly taxed entities want capital gains.
- hahaonlysirius 15y agoSince politicians have no business trying to solve NP problems, perhaps we'd better deregulate the market.
- rvkennedy 15y agoBeen there, done that, bought the recession. Regulation, of course, isn't "solving the NP problem", it's modifying the boundary conditions to prevent the system from getting too far out of whack.
- imogynn 15y agoFree markets are a great heuristic.
- aphyr 15y agoIf we allow that large, computationally capable entities are likely to form in free markets, it is probable that individuals will be faced with a market in which the prices of major goods vary wildly from minute to minute, from person to person, and are predicated on both fantastically complicated loyalty programs and data collected about the individual and current market circumstances, processed in statistical models that no human has ever understood or evaluated. A market in which machines algorithmically game humans and each other by adjusting prices and the nature of the goods themselves to exploit cognitive or algorithmic flaws in other actors.[1] The classical model of efficient, free markets ignores computational complexity and time bounds, as the article notes. These were reasonable approximations for a hundred or even twenty years ago, but I can forsee environments in which these factors lead to significant asymmetry. I question whether humans can really compete successfully in this environment, and whether the process of doing so is really best for us. [1] Cases in point: Amazon, insurance companies, grocery stores, every major retailer, Google, high-frequency trading firms, airline ticket sales.
- artsrc 15y agoEven fairly simple tools must be able to game humans. We must be so bad at making rational decisions that prices typically are set just below a psychologically significant level for example $2.99. This of course assumes the market is correct in its assessment of us.
- NY_Entrepreneur 15y agoHe's mostly smoking funny stuff: He's talking applications of optimization. Okay. Optimization contributes problems, e.g., integer linear programming, in set NP-complete only if one insists on exact optimality down to the last tiny fraction of a penny of cost in the worst problems that can occur, even in principle, in execution time that grows no faster than a polynomial in the size of the problem. That's a LOT of very special and quite unrealistic context. E.g., it's not the least bit clear that finance needs to attack the worst case problems. Even if so, finance, anywhere close to reality, doesn't need to get solutions that save all of the last tiny fraction of a penny. If relax worst case problems and saving the last tiny fraction of a penny, then the situation is MUCH different. E.g., once I got a feasible solution to an ILP with 40,000 constraints and 600,000 variables within 0.025% of optimality on a 90 MHz Intel processor in 905 seconds. More generally, here's an easy approach to the ILP problems: Just drop the integer constraints, solve with LP, and then round to integer values. For the LP solution, if insist, then use a polynomial LP solver. Crude? Sometimes. Always crude? No. He's making a common mistake: He's assuming that because in general ILP is in NP-complete that good work on all practical ILP problems has to be too challenging, and that's nonsense.
- bugsy 15y agoJust the concept of the proposition of this paper is pretty amazing. The author Philip Maymin is a serious bad ass for doing this proof. What a dude.
- adas 15y agoshut up!!!
- adas 15y agoFUCK YOU
- adas 15y agoYOU'RE GAY
- adas 15y agoASSS
- adas 15y agoPENIS