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.
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.
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).
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.
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
(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.)
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.
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.
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.
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.
(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?
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.
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.
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.
"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.
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.
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.
"TLDR: Markets aren't efficient"
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.
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.
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.
> "/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)
Can anyone suggest more (fluffy) reading on the market efficiency hypothesis? I'd like a fuller grasp of the material covered in the paper.