Herb 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.
"X reduces to P = NP, so Nyah!" is a tightly formulated theoretical statement. Work of this form is very important in advancing our basic understanding of the fundamental mathematical foundations behind computation.
It only become deeply unsatisfying and misleading for people who do not understand how to translate this information to the real world.
It seems from your post as you do have that understanding, but not the respect for the importance of the underlying math.
> It only become deeply unsatisfying and misleading for people who do not understand how to translate this information to the real world.
Not really. The OP is arguing that translating this statement to the real world adds nothing we did not know before. In comparing markets with NP-complete problems an interesting (but still trivial after you get the idea) paper "Computational Complexity and Information Asymmetry in Financial Products" by Arora et al.
And, also, the point of this paper is not really interesting. Even if it takes exponential time for the market to reflect _all_ the available information about something, all the efficient market hypothesis says is that the market will incorporate the information as fast as the fastest agent in incorporating that information. And this has nothing to do with P and NP (since a quadratic market can still be beat by a linear agent, and this is a market that is definitely in P).
In the real world, problem \in P isn't that enlightening. The constant factors matter.
I haven't looked into modern computational complexity research a whole lot, but I suspect it gets a disproportionate amount of attention because of the historical successes and importance of the field. Kind of like particle accelerators and NASA.
I would just like to point that constants are rarely the important point. Exponents are a huge deal. A lot of things are possible and fast because FFT is N log N versus N^2.
Great 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
Yeah, 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.)
Another 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.
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).
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.
When 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... . 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.
That's definitely true. It's only a counterproof to some extremely strong versions of the EMH that assume that you can buy any possible asset or derivative. http://en.wikipedia.org/wiki/Complete_market
I think SAT and travelling salesman are the wrong analogies, because solving both optimally can involve lots of backtracking.
Forgive me if I'm not understanding what you're getting at here. (I haven't read the paper). But, on first blush, it appears that 3-SAT is not mentioned for the purpose of analogy, but rather for use as a standard "reduction" (in the parlance of NP-Completeness proofs), in which case reducing to any NP-Complete problem is as good as reducing to any other. They're typically only chosen by whether they are amenable to some poly-time transformation, aren't they?
It's been a long time since I've had my course in this, so caveat emptor.
You are correct, but the author's big leap of faith is that our particular one case of the problem is intractable. I'm claiming the reduction from 3-SAT to his market problem is likely broken because the general market problem is subject to at least some additional constraints for it to reflect our reality. For example, you can't have MSFT stock rapidly alternating from $10 to $200 every day, which might be what happens during your 3-SAT reduction.
More importantly, I'm calling out the author's representation as bogus. He proves that anyone who represents the markets his way is trying to solve an NP-complete problem, and that given the problem is NP-complete the hedge funds and banks can't possibly have computed the solution.
I've read the paper now, and I'm still a little confused by the way that you have phrased your objections. More specifically, I don't understand how the form of your objections could constitute a valid criticism of any NP-Completeness proof whatsoever.
(While I don't feel qualified to verify the correctness of the author's reduction, the form of the proof feels like any other that I've read.)
...but the author's big leap of faith is that our particular one case of the problem is intractable.
What does "our particular one case of the problem" mean? Do you mean a particular case of the 3-SAT problem?
If so, reductions don't consider a particular case of 3-SAT (or whatever known NP-Complete problem type one is using for leverage). Rather, they transform any arbitrary 3-SAT problem statement, in poly time, into an equivalent statement in the problem domain under consideration. By showing a transformation of any arbitrary problem, it covers all 3-SAT cases: trivial and intractable. All possible problem statements thus covered, no leap of faith is required.
If not, what sort of problem (and particular case thereof) are you referring to?
Maybe you've ever seen the cool proof that "Tetris is NP-complete". I loved the paper and it was very entertaining. But it involved a much broader and general Tetris problem than the one found in Nintendo Gameboys, because the width and the height of the pit in the reduction was larger than all the console based tetris games I've ever seen.
My understanding is that Gameboy tetris, given the sequence of all future blocks as input and an empty pit starting state, is actually easy to solve computationally.
Similarly, I have to believe that the market as we know it contains some constraints, and all the historical data will abide by those constraints. To show the market problem is NP-hard, you would need all 3-SAT reductions to lead to a valid market problem. Going back to Tetris, IIRC, a large number of the reductions would lead to Tetris games that could not exist on Gameboy Tetris, because you would need a block-pit that is far taller than the game allows.
I think I'm following now. You're saying that the author is assuming a model of economies that is more complex than an actual economy. That could be the first time ever that I've heard such a thing about any model, let alone of an economy. :-)
The only assumption that I see him making is the weak form of the Efficient Market Hypothesis.
I'm curious...how do you feel about that hypothesis, anyway? I've thought the EMH was a pretty strange and obviously false hypothesis ever since I first heard of it in the 80s (in college).
Just look at this statement from the Wikipedia page on the subject: It is the assumption "...that prices on traded assets already reflect all available information, and instantly change to reflect new information." This is a flimsy foundation to build on, because it's assuming the instantaneous propagation of information between economic actors. By what mechanism? Quantum entanglement? Crazy action at a distance?
I realize it was probably first intended in the same way that one uses a point-mass in physics ("we know it can't exist, but it makes the math easier") but I don't think it's quite as harmless as that.
Anyway, I'm happy to see the author taking such a clever swing at it.
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.
But having an efficient market doesn't imply that an algorithm \in P exists for that problem ??
Efficient markets just imply decidability of the problem.
What 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."
I 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.
> 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.
Sorry, 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.
> 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
"seems"? Yes, we do have short-term focus in certain situations. However, I know 90 year-old farmers who plant orchards that won't be productive for 10 years.
And, you're assuming that "tightly controlled" produces benefits. Yes, there are often controls, but that's a long way from showing benefits from said controls. (Surely you're not going to argue that any system of tight controls produces benefits.)
And, as someone else pointed out, no one is stopping you from working on a long term basis. If you do it right, you'll get rich. If you do it wrong, probably not.
I'd like to see you get rich. However, I'm not willing to risk my money on your ideas because I've got my own.
I said "seems" because I didn't want to make the statement absolute and spend a bunch of time debating the point. Regardless of what is theoretically possible, what appears to happen in practice is a (terminal imo) short term focus.
The most important contributors to a company are said to be the share holders, but investment via stock is a very temporal affair. Just get in, try to enforce policy that will quickly generate increase stock value, then dump it before it crashes and move to the next.
And no, I don't think any random control is a help, just that no control what-so-ever is just as bad as all the wrong controls.
>I said "seems" because I didn't want to make the statement absolute and spend a bunch of time debating the point.
Since your argument depends on whether the statement is true and relevant, trying to avoid discussing it is "interesting".
You're assuming that the current stock system is the only way one can do things without regulation. You're wrong. You can set up a company in other ways, with almost any restriction on buying and selling by its owners that you'd like. All you have to do is get them to go along. If you're making them rich, they will. (For example, there are at least two classes of Google stock. The favored few own shares that are weighted differently when it comes to corporate decisions. One can also implement restrictions on buying and selling. IIRC, UPS has them.)
>And no, I don't think any random control is a help, just that no control what-so-ever is just as bad as all the wrong controls.
(1) The current situation is not "no controls".
(2) There's no reason to believe that "no controls" is anywhere near as bad as the wrong controls.
You 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.
Yay! 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!
This 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!
I wish we would stop talking about "left" or "right" politics. Neither are well-defined or rational. It leads to gross over-simplification of important issues by tempting people to dismiss policy X as "socialist" or "fascist" without logically looking at the facts.
Let's the example of financial market regulation you allude to. The reason why it could be a good idea is that a truly free market tends to undervalue risk. For example, if I bought a car from you and it was an optimal deal for both of us, neither of us considered the cost the rest of the population would incur in congestion, pollution, etc. That is considered systemic risk and because it is undervalued it tends to build up. My understanding here isn't full, but I assume those are the forces behind bubbles. Regardless, market regulation is a tool to address these concerns, not a political device to drive the US to socialism.
One of the reasons why I enjoy such articles is that they encourage critical thinking about what is so often mistakenly handled exclusively in the political arena.
The left vs. right spiel is nothing but a simple exploitation of the human tendency to not think about actual facts when a simple (and convenient) explanation seems readily available.
Of 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
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.
I appreciate the detailed post, but there was no need -- "/s" is often used to connote sarcasm, in written text. Recently, American politics has some groups label any regulation or public service as "socialism"; eg, "the FDA is socialism!". The parent post struck me as fitting this pattern, since it claims that regulations to prevent widespread market collapse are socialism.
Since you seem to be knowledgeable about it, I'd like to ask a question. I've usually heard "communism" used to describe State-owned industry, whereas "socialism" is worker-owned. For example, profit-sharing, privately-owned co-ops, or credit unions would be socialism, under this definition, and North Korea would be communist but certainly not socialist. Is this definition outmoded or incorrect? I'd like to have a more accurate vocabulary for discussing these sort of things.
Edit: Turned out to be a rather long reply with some background and descriptions of the differences and historical references. Outlines theoretical difference between socialism and communism as outlined by Marx, and then gets into why it's hard to nail down terminology in this sphere.
> "/s" is often used to connote sarcasm, in written text
Gotcha - missed the sarcasm that time.
> Recently, American politics has some groups label any regulation or public service as "socialism"; eg, "the FDA is socialism!"
Well, the FDA sucks in that it turns a huge blind eye to some horrible stuff while regulating some real petty, unnecessary stuff, and adds a lot of cost. For instance, fiber isn't considered an essential nutrient, so foods stripped of all fiber (most fast food) is perfectly legal, but other stuff is banned/controlled rather capriciously. But no, it's not socialism, just generic idiot bureaucracy.
> I've usually heard "communism" used to describe State-owned industry, whereas "socialism" is worker-owned.
Marx defined communism as a classless, rulerless society in perfect peace and harmony and infinite production and happiness and unity for everyone. However, he said the world would have to get through violent revolution. So it would be appropriate to say that socialism is government ownership of means of production, and workers control the government in some form or fashion.
> For example, profit-sharing, privately-owned co-ops, or credit unions would be socialism, under this definition
Nah, that's good ol' fashioned free enterprise right there, or capitalism if you prefer the term. I'm against socialism/communism because it doesn't work very well, but I'm very supportive of co-ops, worker ownership in a business, voluntary community-owned and sponsored projects, etc. None of that is socialism/communism, which includes threats of force/imprisonment/violence for doing subversive free market activities.
> North Korea would be communist but certainly not socialist. Is this definition outmoded or incorrect? I'd like to have a more accurate vocabulary for discussing these sort of things.
It's tricky to get a correct vocabulary, because people like to continually rebrand their political positions to sound more favorable. The Soviet countries called themselves Communist, but clearly didn't fit Marx's definition of ideal communism. That said, Marx's definition of ideal communism is literally impossible - people will always rank themselves, and when you take away the ability for people to rank themselves based on a particular criteria, they just pick something else. And often they pick something worse - party loyalty, military accomplishment, or academic accomplishment (except that academia is now controlled by the government, so academic work outside of the natural sciences all devolves into propaganda).
To give you an idea of the shifting lines and why it's hard to get a good vocabulary - Nazi Germany was clearly heavily socialist. "Nazi" is short for "Nazionalsocialiste". Hitler's party was the National Socialist German Worker's Party.
They actually did directly control a lot of industry. If you read some of Table Talk, which are basically minute-by-minute summaries of Nazi cabinet meetings recorded for preservation by Nazis, Hitler was constantly talking about planning the farming in Ukraine, or the chemicals production in Bavaria, or changing how the universities run in Vienna, or making cruises or automobiles more accessible to the people.
Clearly, clearly, clearly socialism under Marx's definition. They hated the Russians, but saying Hitler hated Communism isn't quite accurate - he constantly talked about how "Bolshevism" was a huge problem, that was the Russian implementation. He didn't knock socialism/communism-itself very often.
But what do sociologists typically label Nazi Germany these days? "Corporatist". Hmm, what's that? Turns out "corporatist" is socialism where the the company is fully owned by the government, but has some very loose semi-autonomous management. It's basically just normal socialism. Yet it's called "corporatism", which anyone who isn't a sociologist would associate with corporations/capitalism/etc. It's not. The NSDAP (Nazionalsocialiste Deutsche Arbetitet Partei - The National Socialist German Worker's Party - shorthand, Nazis) were clearly a heavily socialist government.
But people who generally favor state-ownership don't want that association, so they call it "corporatism", which is just unnecessarily misleading and false. For all the things socialism does poorly, it actually does perform as well as capitalism at making war. The reason is that you can have the leader order a bunch of separate industries to work together - you get all the country's brightest people working on war under socialism. Amazingly, the USA was able to convince its best and brightest to largely volunteer for the war effort, but this is a rare thing. Under socialism, it's usually a lot easier to make war than worrying about getting industry to voluntarily participate. That's about the only thing socialism does better though - it starts to move too slowly and stagnate when there's more than one goal for the government to pay attention to, or the goal isn't extremely straightforward. One of the biggest things that breeds laziness and complacency is lack of competition; that's solved during wartime by the enemy. So socialism does okay at war, and pretty poorly at fulfilling diverse and changing wants and needs.
Nationialsozialist. In analogue to Sozi, meaning socialist (or rather more specific to its German origin social democrat).
> The Soviet countries called themselves Communist [...]
Didn't they call themself socialist? As far as I know at least the GDR called itself socialist. I only ever hear English-speakers use the term "communist" for the east-block states. (See http://en.wikipedia.org/wiki/Real_socialism)
Whoa, while the state paving roads might be socialist under Marx's definition, doing so with a workforce of slaves who would be systematically murdered shortly thereafter is not.
I also reacted before I noticed the sarcasm. The thing is that it's quite common seeing such statements that actually are serious. Sweden is also not socialist country, if anything it's social democratic (nordic model), which should not be confused with democratic socialism. Norway is quite unique because of their riches from oil.
Please 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.
If 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.
It'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.
Like 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.
Ah, 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.
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.