8 ms·
Markets are efficient if and only if P = NP
- memoryfault 17y agoHe can prove that, but he can't use LaTeX?
- clay 17y agoHe wrote it for a finance journal. That's how they do.
- rw 17y agoHoly shit. This is the paper that I've had intuitive glimpses of for over two years. Well done.
- rw 17y agoLesson learned: even you can sound like a crackpot.
- Herring 17y agogood reddit discussion a while back. http://www.reddit.com/r/Economics/comments/b1w3n/markets_are_efficient_if_and_only_if_p_np_and_he/c0kji78 http://www.reddit.com/r/Economics/comments/b1w3n/markets_are... "TLDR: Markets aren't efficient"
- deleted 17y ago[deleted]
- fadmmatt 17y agoHerb Simon noted the optimal solution is often infeasible a long time ago. He argued that economic agents rarely finding a satisfying solution to their constraints, and instead choose a "satisficing" or "good-enough" solution. Simon also noted that the satisficing solution found by humans is often close to the optimal solution. He got (and deserved) a Nobel prize for these two observations. I find work of the flavor "X reduces to P = NP, so Nyah!" to be deeply unsatisfying and misleading. For problems of human importance, good-enough solutions to NP problems can often be found in a reasonable amount of time. In fact, state-of-the-art SAT solvers are mind-bogglingly fast (on average). They can find solutions in seconds, where the theoretical worst case solution time is many-fold the expected lifetime of the universe. Generating a hard instance of SAT is actually hard to do. One of the few reliable techniques we know of is to encode prime factorization into a circuit. This is good news for crypto, but bad news for anyone looking to show the real-world intractability of a process by reducing it to P=NP. Few processes in nature actually mimic prime factorization or graph isomorphism.
- houseabsolute 17y agoAnother factor is that the weak inefficient market hypothesis (as far as I know) isn't a claim that we can't find the method for analyzing past prices. It's a claim that there is no possible method because the future price of a security is for all purposes stochastically independent of past prices. No matter what algorithm you use, NP, P, or any other algorithmic space, you can never reliably predict the value of a variable that is independent of its previous values. I'm not positive that this defeats the argument this guy was making (not a computer scientist, only a programmer), but from what I could gather it seems to.
- andrewljohnson 17y agoGreat commentary about the actual ramifications of NP problems. This reminds me of a company I used to do some marketing work - CombineNet. They would basically take a large, multi-participant marketplace (for example, several hospitals buying a billion dollars in goods from pharma companies and medical device manufacturers). CombineNet's technology wouldn't guarantee the optimal buy to the hospitals, but it usually could, and in the cases that it couldn't, it could get very close to optimal and specify how close the answer was. I'm not a mathematician, but I think they were solving a "clearing problem?" Coincidentally, the founder of CombineNet was a professor at the same school as Herb Simon... Carnegie Mellon. Sandholm also wrote a heads-up Texas Hold'em bot that derived its strategy from the rules, and beat a ton of other heads-up poker bots handily. I think articles about this showed up on HN a while back: http://portal.acm.org/citation.cfm?id=1402350 http://portal.acm.org/citation.cfm?id=1402350
- MaysonL 17y agoFor those without acm access, also available at http://www.cs.cmu.edu/~sandholm/texas.aaai06.pdf http://www.cs.cmu.edu/~sandholm/texas.aaai06.pdf
- _delirium 17y agoYeah, this has led to the odd situation in AI that reducing to SAT is how you show a problem is easy--- there's a whole cottage industry of people speeding up algorithms by reducing them to SAT, and it's often seen as a promising result for your computational tractability if you can do so. (And the biggest problems, when they arise, are usually actually in the reduction itself---it takes too damn long to write out the SAT problem. Once you've got the SAT problem written out, solving it is rarely an issue.)
- TrevorBurnham 17y agoThis is certainly an interesting bit of mathematics, but I hope it won't be upheld by those on the political left as an argument for more stringent market regulation. After all, socialism is inefficient whether P = NP or not!
- natrius 17y agoIf you don't think that more--or at the very least, different--financial regulation is necessary, then you must be a time traveler from 2006. I hope you didn't accidentally catch an episode of Lost during your stay. Talk about spoilers.
- jmillikin 17y agoOf course; that's why socialist countries such as Germany and Sweden are seeing their economies collapse, while strongly capitalist countries such as the US have enjoyed uninterrupted growth. If socialism were efficient, overhead costs of important services such as transportation and health care would be dramatically lower in socialist economies. /s
- coryl 17y agoPlease provide some evidence of Germany/Sweden and their economies collapsing. As far as I can generally recall, most of Europe is "socialist" and has better healthcare, education, crime rate, quality of life, etc.
- grk 17y agoApparently there's a big need for the sarcasm font.
- deleted 17y ago[deleted]
- lionhearted 17y ago> socialist countries such as Germany and Sweden Whoa, whoa, whoa - Germany is not a socialist country, not even close. They spend their tax revenues less corruptly which is why they have better social services, but the state doesn't own important industries. Actually, the state used to own most of the construction, chemical, automobile, etc industries as a legacy of the WWII era, but they consciously privatized them and those industries thrived. Social services and socialism isn't the same thing. Sweden is closer to socialism, but still not right. There are real socialist countries in the world - if you wanted to choose some examples, you could pick a handful that run okay, such as Norway where about one-third of industry is state-owned, but you'd also want to look at North Korea which is 100% socialist. Likewise, to get a balanced not-talking point comparison, you'd look at 2000's United States, but also 1790's to 1990's USA, compare pre WWII-Japan to post WWII-Japan (capitalism), pre-WWII Germany to post-WWII Germany, Hong Kong, Singapore, Deng Xiapong's market reforms in China, and so on. The most interesting case for capitalism to me is England. Capitalist before WWII, its most socialist post-WWII, ending in the 1980's when Thatcher privatized and sold off most of state-owned industry. The most telling thing to me is what happened to the "council houses" - those are low income housing for the poor. They sold it to the poor for a nominal cost - basically just give it away. Now privately owned, the poor people took much better care of the housing, crime went down, destruction rates went down, etc, etc, etc. Anyway, long story short - if you pick a 10 year period of history, 3 countries you've cherrypicked, sure, you can come to whatever conclusion you want. Free enterprise/private ownership has really soundly outperformed state-owned enterprise in almost every absolute quality of life metric. You'd have to start getting into relative quality of life to make the case for socialism, but the case that, "It'd be better for everyone to be worse off for people to be more similar" is a hard case to make.
- yummyfajitas 17y agoDupe. This paper is new, but the result is not. The paper Betting on Permutations by Pennock, Chen, Fortnow and Nikolova already proves this. Consider a race between n runners. Now consider a prediction market accepting bets of the form "X will finish before Y". They prove that the market maker/auctioneer problem is NP hard. Conversely, if markets are efficient, then they solve the market maker/auctioneer problem.
- Spark23 17y agoBut having an efficient market doesn't imply that an algorithm \in P exists for that problem ?? Efficient markets just imply decidability of the problem.
- greenlblue 17y agoI don't get it. He reduces one unverifiable claim to another one.
- mlinsey 17y agoIf you find a proof that a problem is NP-complete that's not reducing one unverifiable claim to another one, be sure to let us know!
- greenlblue 17y agoLike I said, I don't get it. At least some of the reductions reformulate the problem so it can be attacked by some new tools. What's the point of reducing it to the efficient market hypothesis? That seems like an empirical claim rather than a mathematical one.
- mlinsey 17y agoAh, now I understand the motivation of your comment better. But I think if you read through just the introduction of the paper and consider that it was written in a finance journal and not a CS journal, showing the efficient market hypothesis to be NP-complete was ment to provide an insight into the efficient market hypothesis, not to provide any insight on the the P vs. NP problem.
- emilind 17y agoI don't want to say this is unoriginal, but I'm surprised that the usual suspects are missing in bibliography: "computable economics", "Philip Mirowski", "K. Vela Velupillai", "Barkley Rosser", etc.
- emilind 17y agoAlso Clower and Howitt.
- xenophanes 17y agoWhat it really means is, "Markets aren't as efficient as if God used his omnipotence to organize everything. But they are as efficient as actually possible. It's not like the Government can calculate P=NP stuff better."
- ytinas 17y agoI don't buy that they are as efficient as actually possible. I wish there were some means of trying out different resource allocation strategies, but I think people who are doing so well in the current setup will do whatever it takes to maintain status quo.
- randallsquared 17y agoYou can try them out in simulation. The hard part is making people actually care about the outcome if you use real people as the actors, but game writers already do fairly well at this.
- anamax 17y ago> I don't buy that they are as efficient as actually possible. It doesn't much matter if they aren't without something that is more efficient. Consider the following line of "reasoning". (1) "X is a problem and we must do something." (2) "Y is something." (3) "Therefore we must do Y." The "fact" that markets are not as efficient as possible does not imply that we should use something else instead. We should only use something that is actually better.
- ytinas 17y agoSorry, I obviously wasn't clear enough. What I meant was: Capitalism is a system to manage resources. Since it seems to end up with an extremely short term focus when it isn't tightly controlled, I wonder if there aren't possible alternative systems that would do a better job. We can't know if we never try.
- eru 17y ago
- jmount 17y agoThis article is a dup of: http://news.ycombinator.com/item?id=1124782 http://news.ycombinator.com/item?id=1124782 and I repost my comment from there: The paper linked to is a low quality imitation of the current literature. Among its flaws it has the common fallacy that if a problem has a large number of states than inspecting all the states is always hard. I strongly recommend instead some of the interesting actual work on Nash Equilibria and Correlated Equilibria: "Nash equilibria: Complexity, symmetries, and approximation" Contantinos Daskalakis, Computer Science Review (2009) vol. 3 (2) pp. 87-100 "Computing Correlated Equilibria in Multi-Player Games" Christos H Papadimitriou, (2009).
- Eliezer 17y ago"Efficient markets" are better named inexploitable markets or anti-inductive markets.
- lyudmil 17y agoI really enjoyed reading this. It is always satisfying to find connections between my interests. Can anyone suggest more (fluffy) reading on the market efficiency hypothesis? I'd like a fuller grasp of the material covered in the paper.
- eru 17y agoBenoit Mandelbrot did some interesting stuff in this direction. (Sorry, can't remember more details at the moment.)
- leelin 17y agoSummary of paper: A.) First several pages are random fluff: Explains P, NP, NP-Hard, NP-Complete, history of P=NP, examples of NP-complete problems, examples of market efficiency, and other very uninteresting stuff that feels like it's trying to fill out pages. B.) Makes this central argument: 1.) If markets are efficient, then no one can come up with a consistently profitable trading strategy based on analyzing historical data. 2.) Model historical data as a sequence of days where the market can go up or down on any given day. 3.) Model a trading strategy as being long, short, or neutral the market on any given day, to be started after recognizing some pattern for the previous N days. 4.) To determine from historical data whether a profitable strategy exists, you'd need to try all combinations of being long, short, or neutral over some time horizon, while looking for all market patterns. Trying all such combinations is O(3^N) or O(2^N), depending on whether you believe the expensive part is finding the strategy or finding the pattern. 5.) To verify that you have a winning strategy, you merely need to simulate the strategy over your historical data, which only takes O(N). 6.) Therefore, it is in NP. Similarly, it is NP-Hard because we can reduce 3-SAT to a market / trading problem. Therefore, "does a profitable strategy based on historical data exist?" is in NP-complete. 7.) Because our model shows finding the existence of a profitable strategy is NP-complete, then either P=NP or markets are inefficient. C.) A few comments of my own: 1.) Suppose we believe the argument. The amount of historical data is finite, so maybe some hedge funds brute-forced a solution and removed the market inefficiencies they've found. 2.) I think SAT and travelling salesman are the wrong analogies, because solving both optimally can involve lots of backtracking. A* search on a landscape with reliable heuristics might be a better analogy. In trading markets, you don't need to try all 3^N combinations because just as in search algorithms, you have heuristics that can help prune large parts of your search space (if a strategy starts off losing money, no need to keep exploring all the 3^N combinations under it). 3.) The author assumes everyone represents and models the market his way. Maybe a more clever representation makes the problem tractable. Checkers is a solved game now, even though there are in theory infinitely many possible game histories to test.
- jplewicke 17y agoWhen I first saw the headline, I assumed it was going to be about the CDO packing problem discussed at http://rjlipton.wordpress.com/2009/10/22/helping-wall-street-cheat-with-theory/ http://rjlipton.wordpress.com/2009/10/22/helping-wall-street... . The basic idea is that if you're buying a Collateralized Debt Obligation, you can't tell whether the people structuring the deal have intentionally given you an unfair share of bad loans, even when you know a lot about each of the loans in particular. There's also a fairly trivial argument for the incomputability of the EMH: for each Turing machine, issue bonds that compound interest in perpetuity and pay it off if the Turing machine halts. Since the value of the bond is positive if the Turing machine halts and zero if it doesn't, in an efficient market investors will price the bonds in a way that solves the halting problem.
- Estragon 17y agoYay! Since we know markets are efficient, this long-standing computer-science conjecture has been resolved! Now we can break crypto systems by simply setting up an appropriate marketplace!
- stcredzero 17y agoIsn't this what academic crypto is supposed to be? Also the NIST contests for crypto standards are also like this.
- cabalamat 17y agoIt's this sort of crap that gets economics a bad name. Real-world markets are rarely (if ever) maximally efficient, regardless of whether P=NP or not, for all sorts of reasons to do with human psychology, friction, etc.