Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

What Computer Science Can Teach Economics

ScuttleMonkey posted more than 4 years ago | from the just-build-better-computers dept.

Math 421

eldavojohn writes "A new award-winning thesis from an MIT computer science assistant professor showed that the Nash equilibrium of complex games (like the economy or poker) belong to problems with non-deterministic polynomial (NP) complexity (more specifically PPAD complexity, a subset of TFNP problems which is a subset of FNP problems which is a subset of NP problems). More importantly there should be a single solution for one problem that can be adapted to fit all the other problems. Meaning if you can generalize the solution to poker, you have the ability to discover the Nash equilibrium of the economy. Some computer scientists are calling this the biggest development in game theory in a decade."

cancel ×

421 comments

Sorry! There are no comments related to the filter you selected.

Reads like string theory (1, Funny)

Anonymous Coward | more than 4 years ago | (#30039160)

Biggest development in a decade! We haven't figured out how yet though!

Wait a minute (2, Insightful)

Rick the Red (307103) | more than 4 years ago | (#30039706)

Poker is a game?

Re:Reads like string theory (2, Funny)

Mr2cents (323101) | more than 4 years ago | (#30039716)

If all else fails, at least we can still exchange a few funny stories about crashes...

Re:Reads like string theory (0)

Anonymous Coward | more than 4 years ago | (#30039820)

Poker? I haven't even kissed 'er!

No shit (0)

phantomcircuit (938963) | more than 4 years ago | (#30039182)

Shocker economics problems are beyond the relatively simple equations that were being used to model entire markets.

NO SHIT

Re:No shit (3, Insightful)

megamerican (1073936) | more than 4 years ago | (#30039452)

That's why the goal [wikipedia.org] is to dumb down the average person and limit his choices until we're at the level of a THX 1138/Brave New World society.

The problem is not an efficient algorithm (3, Interesting)

iamacat (583406) | more than 4 years ago | (#30039216)

Polynomial time approximate, probabilistic or special case solutions to NP problems are wide spread. The problem is that real human being in economics can not be easily described by an equation - and when they can be, they quickly change their behavior based on that knowledge. What both computer scientists and economists need to learn is stop being geeks addicted to a single theory and start dealing with people.

Re:The problem is not an efficient algorithm (3, Insightful)

GigsVT (208848) | more than 4 years ago | (#30039316)

The emergent intelligence of the market will likely never be able to be simulated.

A centralized model can't react in real time to factors that change by the minute or by the second like human actors can.

What was desirable to us one minute ago may no longer be desirable to us.
What was desirable one minute ago to me may have never been desirable to you!

No formula can ever quantify that value. It's subjective.

Re:The problem is not an efficient algorithm (2, Insightful)

Smoke2Joints (915787) | more than 4 years ago | (#30039428)

the point is, however, that its probable that a certain product or commodity will be desirable by somebody, or even a group of somebodies, at some point in time, based on past interactions in the marketplace.

Re:The problem is not an efficient algorithm (1)

icebike (68054) | more than 4 years ago | (#30040182)

the point is, however, that its probable that a certain product or commodity will be desirable by somebody, or even a group of somebodies, at some point in time, based on past interactions in the marketplace.

And of course, the marketplace is the best engine for measuring said probability.

Trying to use game theory to evaluate the behavior of people in an attempt to explain the behavior of the market is, at best, some sort of first or second derivative approach.

Re:The problem is not an efficient algorithm (1)

astar (203020) | more than 4 years ago | (#30040214)

Well, you said probable. But I paid top dollar for a bunch of buggy whips. Know any buyers?

The point here is that new tech devalues old tech.

Anyway, on past (distance past) interactions in the market, I should be to find a buyer. If nothing else, I should be able to rely on the bigger fool theory like eveyone else. Then again, that has not worked out so well lately. But there is always the government to bail me out.

Re:The problem is not an efficient algorithm (2, Interesting)

NeutronCowboy (896098) | more than 4 years ago | (#30039562)

I'd say it goes beyond that: humans can't react to those factors either. Where do you think the current credit meltdown came from? Humans were not able to model the credit market behavior, just as much as the mathematical models were unable to do so.

It is not even subjective - I'd argue it's almost quantum mechanical: the mere act of looking at a market changes its behavior. The advantage of modeling quantum mechanical systems though is that they don't change their rules just to spite you. The certainty for the momentum of a particle changes in a particular fashion when its location is analyzed, no matter how many times you perform that measurement. The particle doesn't change its behavior to screw over the investigator.

Re:The problem is not an efficient algorithm (2, Informative)

icebraining (1313345) | more than 4 years ago | (#30040160)

Actually, some were [wordpress.com] . The people in charge just didn't listen to the right people.

Re:The problem is not an efficient algorithm (1)

Red Flayer (890720) | more than 4 years ago | (#30039596)

A centralized model can't react in real time to factors that change by the minute or by the second like human actors can.

That's false, I think. If you already have the algorithm, and the same access to data that the human actors have, then the model is faster than the human actors... provided you have the computational equipment. Humans need to execute decisions, which can take far longer than a sufficiently powerful computer.

The problem is that it'd take trillions or more years to arrive at the Nash equilibrium (which defines your model) for a system as complex as the economy.

What was desirable to us one minute ago may no longer be desirable to us.
What was desirable one minute ago to me may have never been desirable to you!

No formula can ever quantify that value. It's subjective.

And that's a completely different problem, one that is currently being tackled by a number of people. By the way, that's why its dangerous to use economic models developed for commodities when dealing with non-commodity goods, there are a ton of extra inputs into deriving something as "simple" as a demand curve for non-commodity goods.

Right. (1)

Estanislao Martnez (203477) | more than 4 years ago | (#30039602)

The emergent intelligence of the market will likely never be able to be simulated.

Right. A true believer must take it on faith.

Re:The problem is not an efficient algorithm (1)

poetmatt (793785) | more than 4 years ago | (#30039708)

well, causation is something that can be easily predicted up to a margin, but the rest of this, not so much.

Re:The problem is not an efficient algorithm (1)

j1mmy (43634) | more than 4 years ago | (#30039814)

actually, it has nothing to do with reaction time. you hinted at the correct issue: desirability

you can program a computer to model desirability within an economic actor, but it will never be more than a simplified model of the real thing. the possibility for tangential expansion of error is enormous.

The implication is, can money be accurate? (1)

tjstork (137384) | more than 4 years ago | (#30039900)

What you are really saying is, in other words, is that money can never be really accurate, and it follows that the trend towards globalization and consolidation of currencies is a mistake. This makes some intuitive sense. If Japanese cars are better than American cars, then why do they cost more in America?

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30039956)

The emergent intelligence of the market will likely never be able to be simulated.

why?

you got a +4 insightful (for now...) and maybe I feel the same, but I still don't see a rational argumento for that assetion ...

Re:The problem is not an efficient algorithm (1)

astar (203020) | more than 4 years ago | (#30040108)

A central model is not the problem. This result has a bit of generality. Or emergent intelligence of the market, if such a thing exists. But you might want to criticize equilibrium assumptions or even axiom based systems.

Re:The problem is not an efficient algorithm (4, Informative)

zach_the_lizard (1317619) | more than 4 years ago | (#30039348)

There are entire schools of economics that criticize the mainstream schools using this very line of reasoning. IIRC, the Austrian school economists (Mises, Menger, et. al) never use any sort of math at all, except in trying to determine things such as the rate of inflation. There are others, too, but their names escape me at the moment.

Re:The problem is not an efficient algorithm (0, Flamebait)

Anonymous Coward | more than 4 years ago | (#30039434)

the Austrian school economists (Mises, Menger, et. al) never use any sort of math at all, except in trying to determine things such as the rate of inflation.

That's because their absurd notions don't stand up to mathematical scrutiny.

"We don't use math because what we say can be disproven by math"

Re:The problem is not an efficient algorithm (1)

zach_the_lizard (1317619) | more than 4 years ago | (#30039598)

That's because their absurd notions don't stand up to mathematical scrutiny. "We don't use math because what we say can be disproven by math"

What sort of conclusions have they come to that are A) absurd and B) demonstrated to be absurd with the application of math? I hear many economists dismiss them out of hand, but I have seen very few actually go into depth as to why they must be absurd. Bryan Caplan has a critique of the Austrians, but his is one of the few I've read.

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30039758)

Hmm, maybe the dismissal of rent-seeking by monopolies as immaterial, since the Austrian school invokes the Deus Ex Machina of innovation to supplant monopolies?

All monopoly rent-seeking is dismissed by Austrians as a just reward for the act of obtaining a monopoly, and the damages of that rent-seeking is ignored.

Re:The problem is not an efficient algorithm (1)

zach_the_lizard (1317619) | more than 4 years ago | (#30039798)

Do you have a source for the assertion that Austrians view monopolies as being non-evil?

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30039970)

Why not go to the fountain of sputum itself? [mises.org]

Here [independent.org] 's a link to a place you can buy some hard copy if you want it.

And here's another source for you: Carl Menger and the Origins of Austrian Economics, by Max Alter. Westview Press, Boulder, CO, 1990. Pp. viii, 256. $74.00. ISBN 0-8133-0945-X.

Re:The problem is not an efficient algorithm (4, Interesting)

gerddie (173963) | more than 4 years ago | (#30039514)

Well, I'm not surprised there is such school. My impression is, that economists in general don't have a good grasp of math, specifically, they don't seem to understand the exponential function, otherwise they would not speak of "growth" all the time.
I'm not saying one should not take human behavior into account, but at least they should get the boundary conditions right, and one of those is that our resources are limited.

Re:The problem is not an efficient algorithm (4, Informative)

Red Flayer (890720) | more than 4 years ago | (#30039808)

I'm not saying one should not take human behavior into account, but at least they should get the boundary conditions right, and one of those is that our resources are limited.

That does not mean that additional wealth cannot be created without infusion of additional resources.

I know it's counterintuitive for most people with a "hard science" background... I struggled with it as an undergrad. But economics is not a zero-sum game. I give you $150 and you give me an hour of labor. We've both benefited by the trade. If we are really acting freely, we've both benefited (or we wouldn't have engaged in the trade), so we are both wealthier than we were before. This is the fundamental basis of perpetual economic growth... given a free market* in which to pursue trades, wealth increases as trades are made.

* Free as in some-kind-of-approximation-of-an-ideal-free-market, not free as in no-legal-restrictions-on-activity.

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30039944)

I thought growth came from fractional reserve banking.
bank to someone -> here is loan
bank to someone -> please deposit your loan
someone to bank -> ok
bank to someone else -> here is a loan derived from the money loaned to the first someone who kindly gave us some free money

Re:The problem is not an efficient algorithm (1)

need4mospd (1146215) | more than 4 years ago | (#30040248)

It doesn't matter if wealth grows at an exponential rate if debt grows at an exponential rate that is greater. Graph two lines out, one at a 5% increase, the other at an 8% increase out 30 years for a clear picture of what happens, or I should say, what happened. Most of the "wealth creation" we've had recently is false wealth, or pulled forward demand. Created thanks to free flowing credit. We've reached a point where servicing the debt that payed for that "wealth" is becoming increasingly painful to do.

Re:The problem is not an efficient algorithm (-1)

Anonymous Coward | more than 4 years ago | (#30039854)

It's not just an impression. Most of them are scientifically illiterate. There are innumerable proofs of this fact, but suffice it to say that when every now and then real mathematicians take a look at their naive mathematical models, they usually demonstrate that they predict evolutions completely different from what economists think they do, or even that the model is basically absurd. See for instance Debreu-Sonnenschein-Mantel.
Apart from that, you're absolutely right about the exponential. It's the way markets and especially stock exchanges usually behave (bubble, crash, bubble, crash), and this can readily be understood by considering that the way it works is that people alter the price at which they will buy or sell shares according not to the value they think they represent (dividends) but to how fast their price goes up or down. In other terms, they link a function to its derivative. Duh. Only an economist can't understand that.

Re:The problem is not an efficient algorithm (4, Informative)

Marcika (1003625) | more than 4 years ago | (#30039874)

Well, I'm not surprised there is such school. My impression is, that economists in general don't have a good grasp of math, specifically, they don't seem to understand the exponential function, otherwise they would not speak of "growth" all the time. I'm not saying one should not take human behavior into account, but at least they should get the boundary conditions right, and one of those is that our resources are limited.

Your impression is wrong. Every economist knows about Thomas Robert Malthus [wikipedia.org] and Malthusian economics -- for the pre-industrial era his model best explains demographics and the limits of growth. It only so happened that just after he published his thoughts, the industrial revolution happened and technological progress pushed the boundaries of growth further and further - in an exponential manner.

Would you dare to make an exact forecast where the limits of growth lie? Limited by fossil fuels? Or a single planet's worth of solar energy? Maybe a Dyson sphere's worth of solar energy? Technological progress moves the goalposts rapidly enough that you have to assume exponential growth punctuated by occasional catastrophes - at least for the next 50 years.

Re:The problem is not an efficient algorithm (1)

westlake (615356) | more than 4 years ago | (#30039936)

I'm not saying one should not take human behavior into account, but at least they should get the boundary conditions right, and one of those is that our resources are limited.

But those limits are not so easily fixed or defined.

The microchip is the perfect example.

It doesn't exist before 1958. It's economic, technological and social impact scarcely felt before the 1980s.

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30040140)

This is why standard economics solved the problem by negating the existence of time.

Re:The problem is not an efficient algorithm (2, Interesting)

yali (209015) | more than 4 years ago | (#30040118)

My impression is, that economists in general don't have a good grasp of math

I don't think the biggest problem is economists' grasp of math. Rather, it's that (a) the people implementing the economists' mathematical theories don't have a good grasp of the math [wired.com] , and (b) economists don't have a good grasp of the people their math is supposed to model [nytimes.com] .

Re:The problem is not an efficient algorithm (1)

Lord Ender (156273) | more than 4 years ago | (#30039540)

Is that a "school" or a couple ranting old kooks?

Re:The problem is not an efficient algorithm (1)

zach_the_lizard (1317619) | more than 4 years ago | (#30039732)

One of them won a Nobel prize, so I'd have to say they're not totally crazy.

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30039992)

Please google a few minutes about the (non-)existence and meaning of a Nobel prize for economics.

Re:The problem is not an efficient algorithm (2, Insightful)

Red Flayer (890720) | more than 4 years ago | (#30040084)

FWIW... just because someone was awarded a Nobel Prize doesn't make their ideas inviolate.

Even Rothbard heavily criticized Friedman (not to mention Krugman et al).

Re:The problem is not an efficient algorithm (4, Insightful)

NeutronCowboy (896098) | more than 4 years ago | (#30039370)

I was about to say the same thing. Unlike poker, the rules of the games are altered based on the current knowledge about the state of the game. This means that as soon as someone proclaims "We know the rules of Economics!", someone else is going to look at those rules and either game them to their benefit, or rewrite them to better suit their own purpose.

Computer Scientists - and Economists - have a habit of assuming that they just need to find the proper model for human behavior, and all the problems will be solved. That's because that's how it works in a science: you assume the rules don't change in an arbitrary fashion. Humans, however, do. This makes any prediction of human behavior a statistical undertaking at best. Your success will be measured by how much better you compared to a random decision making process. At worst, the statistical anomaly completely wrecks your model - see the Black Swan Theory in Economics.

Re:The problem is not an efficient algorithm (1)

caffeinemessiah (918089) | more than 4 years ago | (#30039554)

This means that as soon as someone proclaims "We know the rules of Economics!", someone else is going to look at those rules and either game them to their benefit, or rewrite them to better suit their own purpose.

Which means that economists will always have a profession, and more concretely, a job. Now THAT's job security (just talk to any humanities scholar going up for tenure)...

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30039606)

Computer Scientists - and Economists - have a habit of assuming that they just need to find the proper model for human behavior, and all the problems will be solved. That's because that's how it works in a science: you assume the rules don't change in an arbitrary fashion.

If you just assume then it is not science. Science is about testing your assumptions.

This makes any prediction of human behavior a statistical undertaking at best.

Just like statistical mechanics for example, which serves very well as a description of the bulk properties of materials.

Re:The problem is not an efficient algorithm (1)

NeutronCowboy (896098) | more than 4 years ago | (#30039666)

If you just assume then it is not science. Science is about testing your assumptions.

Even science has some untestable working assumptions.
1) There is no old guy with a beard in the sky who arbitrarily changes the rules.
2) Humans have enough intelligence and sensory input to build a consistent model of the world.

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30040178)

1) And what would we do if there was one? What could we do? As long as science seems to work, it is worth doing. We can't know if the rules will stay the same. If they do, great, if not, we have no information that would allow us to do anything else. No sense in seriously considering an option we cannot prepare for, or investigating something that cannot be known.

2) Science attempts to build a consistent model of the world. It does not assume that it will succeed. Nonetheless it seems dumb not to try our best.

Science does not really have any untestable working assumptions. It is not concerned with what is "true" as much as with what is useful, and usefulness serves as its ultimate test. We trust science because it has proven useful to us in making sense of the world. There is no question that it *could* fail us and the two items you listed are cases where it would (the latter of which could even be deemed probable). Nonetheless there is nothing we can do about these things, no way we could mitigate them or prepare ourselves to them, so even if we assumed they were very likely, we would have no reason to do anything differently. Basically, decision making has to be invariant to them, so all assumptions are orthogonal.

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30040200)

Science can't test the assumption that cause and effect itself isn't working. Like Dr. Sagan said, science depends on the idea that the universe is a Cosmos, not a Chaos. That's what arbitrary change implies, chaos, change without rules, and you cant figure out what the underlying rules are if there simply aren't any.
      To put it another way, science starts with the idea that rules exist, as one of its axioms. it can't logically prove or disprove such an axiom, since it starts from it. You could start from other axioms, sure, and make a logical proof or disproof of the theorem that there are rules for the particular area of study, but while that may be a formally logical proof, it's not a scientific one, because it doesn't start from the axioms of science. (Yes, science and logic are different things).
      Caffinemessiah shouldn't add that there can somehow be statistical undertakings. For the arbitrary change he describes, no rules at all, not even statistical or probabilistic rules, would apply.
      There are many practical limitations on science. The non-arbitraryness of cause and effect is just one. For another, it is impossible to prove by the scientific method that the scientific method itself does a better job of determining facts or predicting outcomes than any other possible method could.

Re:The problem is not an efficient algorithm (1)

TheNarrator (200498) | more than 4 years ago | (#30039754)

I was about to say the same thing. Unlike poker, the rules of the games are altered based on the current knowledge about the state of the game. This means that as soon as someone proclaims "We know the rules of Economics!", someone else is going to look at those rules and either game them to their benefit, or rewrite them to better suit their own purpose.

So really economics is best modeled as mutating finite automata, with the economist being an actor in the simulation. Maybe Steven Wolfram was onto something with his rantings about finite automata describing the natural world much better than equations.

Re:The problem is not an efficient algorithm (1)

MichaelSmith (789609) | more than 4 years ago | (#30039924)

I have heard similar arguments about applying metrics to the management of software development. This is the scenario where you set a standard of 100 lines of code per day or 0.5 bugs per hour or something, then evaluate engineers against it.

Once the algorithm is known the engineers just work around it.

Re:The problem is not an efficient algorithm (1)

mishehu (712452) | more than 4 years ago | (#30039968)

Hmmm this make it seems like Economics is more in line with Quantum Mechanics than with simple NP equations... Once you're observed the system, you've changed it.

Re:The problem is not an efficient algorithm (1)

dpuu (553144) | more than 4 years ago | (#30039988)

Being human, some computer scientists and economists probably do make unwarranted assumptions. But the fact that humans can alter the rules of the game might not be relevant here: if there is an underlying meta-game whose rules constrain how the rules can be altered, then that is the model who's Nash equilibrium is sought. It seems, to me, unlikely that this will be an infinite regress: humans are ultimately restricted by the laws of physics. Even though any model of that meta-game would probably to too complex to be represented as any arrangement of all the subatomic particles in a human brain, it would be interesting if it were possible to characterize any of its properties mathematically.

Re:The problem is not an efficient algorithm (1)

Fulcrum of Evil (560260) | more than 4 years ago | (#30040014)

This means that as soon as someone proclaims "We know the rules of Economics!", someone else is going to look at those rules and either game them to their benefit, or rewrite them to better suit their own purpose.

So what you're saying is that it's really just Calvinball.

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30040252)

That's because that's how it works in a science: you assume the rules don't change in an arbitrary fashion. Humans, however, do. This makes any prediction of human behavior a statistical undertaking at best.

The Nash equilibrium is a "statistical undertaking". The purpose of it is to find the decision that is most likely to be the best decision given the probability of the other actors' decisions. It doesn't necessarily assume that the rules do not change. Read the Wikipedia article linked in the summary.

Not quite... (3, Insightful)

Estanislao Martnez (203477) | more than 4 years ago | (#30039506)

Polynomial time approximate, probabilistic or special case solutions to NP problems are wide spread. The problem is that real human being in economics can not be easily described by an equation - and when they can be, they quickly change their behavior based on that knowledge.

No, I'd say that we're dealing here with two facets of the same problem: the unreality of Homo economicus. The classic objection to economic theory is that people don't act "rationally" in the sense that economic theory requires them to do; even when given all the information that should be necessary to make a decision, they often make an "irrational" one. The objection this sort of applied CS research brings to reinforce that is that economics not only assumes perfect rationality, but also, that "perfect information" requires that arbitrarily complex computations be performed in arbitrarily short times. This is because to have "perfect information," you must compute all of the consequences of all of the information you've explicitly seen.

In fact, I'd say that the irrationality and the computational complexity objections overlap. There's bound to be a lot of cases where the "irrational" decisions come from a failure to compute the consequences of the information that's explicitly given. (There are certainly other cases where it's not, like on the experiments where somebody is asked to split $100 between themselves and another participant, on the condition that if the other party doesn't agree with the split, neither one gets anything.)

Re:The problem is not an efficient algorithm (0)

Anonymous Coward | more than 4 years ago | (#30039626)

The answer is 42...

Re:The problem is not an efficient algorithm (2, Insightful)

omuls are tasty (1321759) | more than 4 years ago | (#30040052)

I'm sure it's great to repeat cliche lines when it comes to economics and computer science, and I know it's super popular with the recent quant economics and stock market debacle. But it'd be kind of nice if people knew what a Nash equilibrium is in the first place. If I use a Nash equilibrium strategy, it doesn't matter *how* you change your behaviour, you can't benefit from it. Think minimax algorithm in zero-sum games.

This is a perfectly sound mathematical concept, in a mathematical sense it's as true as anything else in mathematics. And this is an important and interesting result we found about it. There's no need to label anybody as "geeks addicted to a single theory". It's the same as saying that we "need to stop being addicted to believing that 1+1 equals 2 and start dealing with people".

Our applications of the theory can be more or less successful, and any application of game theory to anything as complicated as economics can only be an approximation. But there's no need to spit on this result because of that.

Re:The problem is not an efficient algorithm (1)

StanSitwell (1082861) | more than 4 years ago | (#30040198)

Polynomial time approximate, probabilistic or special case solutions to NP problems are wide spread

That's not saying much. Exact, general case, deterministic, polynomial time solutions to NP problems are even more wide spread. A problem is in NP if its answer is verifiable in polynomial time. Thus, any problem in P is also in NP. You're confusing NP with NP-Complete.

big... words.. brain... (1)

el_tedward (1612093) | more than 4 years ago | (#30039238)

*fail*

Re:big... words.. brain... (0)

Anonymous Coward | more than 4 years ago | (#30039374)

H = w * L^3.14

H=headache
w=number of large words greater than 5 letters
L=average length of large words (in letters)

Hayek (4, Insightful)

homer_s (799572) | more than 4 years ago | (#30039248)

By showing that some common game-theoretical problems are so hard that they'd take the lifetime of the universe to solve, Daskalakis is suggesting that they can't accurately represent what happens in the real world.

Hayek [wikipedia.org] showed that about 50 years ago:
"The curious task of economics is to demonstrate to men how little they really know about what they imagine they can design." (The Fatal Conceit, p. 76)

Unfortunately, there is a lot of designing going on right now.

Re:Hayek (4, Informative)

zach_the_lizard (1317619) | more than 4 years ago | (#30039424)

And his teacher, Mises, before him in his work Human Action devoted an entire section of that massive tome to just this very topic: that humans are not equations.

From said tome:

No laboratory experiments can be performed with regard to human action. We are never in a position to observe the change in one element only, all other conditions of the event remaining unchanged. Historical experience as an experience of complex phenomena does not provide us with facts in the sense in which the natural sciences employ this term to signify isolated events tested in experiments. The information conveyed by historical experience cannot be used as building material for the construction of theories and the prediction of future events. Every historical experience is open to various interpretations, and is in fact interpreted in different ways.

The postulates of positivism and kindred schools of metaphysics are therefore illusory. It is impossible to reform the sciences of human action according to the pattern of physics and the other natural sciences. There is no means to establish an a posteriori theory of human conduct and social events. History can neither prove nor disprove any general statement in the manner in which the natural sciences accept or reject a hypothesis on the ground of laboratory experiments. Neither experimental verification nor experimental falsification of a general proposition is possible in its field.

My bet: (1)

faragon (789704) | more than 4 years ago | (#30039270)

NP is O( (n^2) * log(n) )

Re:My bet: (0)

Anonymous Coward | more than 4 years ago | (#30039586)

If it were, it would be deterministic, hence not NP.

another intersection of CS and econ (5, Interesting)

WhiteDragon (4556) | more than 4 years ago | (#30039300)

Here's a proof that detecting "toxic assets" is impossible [dailykos.com] (or at least NP)

Re:another intersection of CS and econ (0, Flamebait)

John Whitley (6067) | more than 4 years ago | (#30039468)

I note that you over-condensed the linked article's statement to a meaning much different than your summation. Some more info from that article:

scientists have proved that it is possible to create complex financial bundles [...] that hide bad assets in such a way that no computer or human can detect the bad assets.

Even worse? Even after a buyer loses their shirt on the investment, it is impossible for the buyer to prove that they were sold junk, which makes it impossible to regulate.

This indicates against allowing complex financial bundles, as they create vulnerabilities in the financial system. More interesting details at the parent article's link, including links to other analysis as well as the original publication.

Re:another intersection of CS and econ (1)

WhiteDragon (4556) | more than 4 years ago | (#30040288)

I note that you over-condensed the linked article's statement to a meaning much different than your summation.

That is true. Since what I said was basically the headline text of the article I linked to, I feel the over-condensation was justified.

Re:another intersection of CS and econ (2, Interesting)

cananian (73735) | more than 4 years ago | (#30039762)

Interesting link -- but CS does provide mechanisms for creating "trust worthy" bundles securities, in the form of one-way functions. If the seller says, "I distributed the asset types among these securities using a random number generator built on a cryptographically secure one-way function with the following seed", it is possible to have a high degree of confidence that the distribution really is random. The seller can rejigger the seed but the one-way function (statistically) prevents more than a certain amount of tampering. (Of course, you can still try to tamper with the ordering or identity of the input securities -- discuss!)

Re:another intersection of CS and econ (0)

Anonymous Coward | more than 4 years ago | (#30039886)

Lots of problems in NP are very easy to solve.... Maybe you mean NP-Complete.

Its easy! (5, Funny)

Monkeedude1212 (1560403) | more than 4 years ago | (#30039306)

Meaning if you can generalize the solution to poker, you have the ability to discover the Nash equilibrium of the economy

The general solution to poker is to end the game with everyone elses money to make yourself richer. Some people have already applied this strategy to the economy.

Only works with real money (4, Insightful)

Chemisor (97276) | more than 4 years ago | (#30039574)

Once you factor debt and fractional reserves into the picture, the game changes quite a bit. The current crisis is that the players bet WAY more than they had, and they are all afraid to call, since they secretly know that EVERYBODY is bluffing. So the game (and the stock market) keeps going up as the players trying to outbluff each other with "I'll see your billion and raise you three more". And it will keep going up until somebody has to actually put something of value in the pot.

Re:Only works with real money (2, Interesting)

betterunixthanunix (980855) | more than 4 years ago | (#30040130)

Except that investors routinely bet more than they have, and in fact, this is a fundamental tenet of a modern economy. This is how banks manage to make money; they loan out money they do not technically have, with the understanding that in most cases they will get it back with a profit. Many businesses operate in this way, taking out loans for periodically required large investments (like fertilizer and fuel for a farm), making enough of a profit to repay the loan, with interest, and pay their employees, but not enough of a profit to stop the loan cycle. In general, it is OK to take these risks...

The real issue is determining what level of risk is too high. If a bank issues too many loans, and there is a difficult economic year, the bank may find itself short of money to issue when you make a withdrawal; usually this means the bank will take a loan to cover its position, but if all the banks are in the same position, there is a financial crisis. The recent crisis happened, in part, because of the issuing of derivatives on loans -- contracts that amount to an insurance policy on loans -- which substantially magnified the impact of declining housing prices (because the insurance policies were being paid out too quickly, and the companies that issued them found themselves unable to cover their positions). If you are wondering how such a thing could happen in a country where the government decides the maximum amount of money banks can loan out, the answer is that the derivatives (credit default swaps) were not being regulated in any meaningful way.

The moral of the story? Relying on high risk investments as a major source of income is a stupid idea. High risk investments should constitute a small fraction of revenue, and should be backed up by lower risk investments.

Federal Reserve (0)

Anonymous Coward | more than 4 years ago | (#30039308)

How does the Federal Reserve fit into that equation?

Obligatory (4, Insightful)

Yvan256 (722131) | more than 4 years ago | (#30039338)

Economics involves people. So...

"To summarize the summary of the summary: people are a problem." - Douglas Adams

Re:Obligatory (3, Funny)

at_slashdot (674436) | more than 4 years ago | (#30039502)

I think that Stalin said that this problem is fixable...

Re:Obligatory (0)

Anonymous Coward | more than 4 years ago | (#30040048)

No people, no problem.

Yadda-Yadda-Yadda: But...... (0)

Anonymous Coward | more than 4 years ago | (#30039352)

is P = NP ?

Yours In Novosibirsk,
Kilgore Trout

Huh? (1)

NoYob (1630681) | more than 4 years ago | (#30039380)

Daskalakis, working with Christos Papadimitriou of the University of California, Berkeley, and the University of Liverpool’s Paul Goldberg, has shown that for some games, the Nash equilibrium is so hard to calculate that all the computers in the world couldn’t find it in the lifetime of the universe.

It sounds all Greek to me.

Re:Huh? (1)

oldhack (1037484) | more than 4 years ago | (#30039488)

That was my thought when I was walking around a Greek city for the first time (Salonika): math city.

CS (1, Insightful)

Anonymous Coward | more than 4 years ago | (#30039420)

I take it that computer science would be the most common major among those in slashdot? This explains the libertarians commenting on health care reform.

Article misrepresents complexity theory (2)

kramer2718 (598033) | more than 4 years ago | (#30039458)

From the article: "By showing that some common game-theoretical problems are so hard that they’d take the lifetime of the universe to solve, Daskalakis is suggesting that they can’t accurately represent what happens in the real world." But he didn't actually show this. He showed (again from TFA): "Daskalakis proved that the Nash equilibrium belongs to a subset of NP consisting of hard problems with the property that a solution to one can be adapted to solve all the others." I.e. computing the Nash equilibrium is NP-complete. These problems have no efficient solution if (and only if) P != NP. That is if there is a polynomial (efficient) solution for any of these, then there is a polynomial time solution for all. We don't know WHETHER THAT'S TRUE. Computer scientists suspect very strongly that there is no polynomial time solution for these problems, but it isn't known for sure.

"Non-Deterministic" (0)

Jane Q. Public (1010737) | more than 4 years ago | (#30039492)

"More importantly there should be a single solution for one problem that can be adapted to fit all the other problems."

Not so. There is a reason this class of problems is called "non-deterministic". That is because there is no way to determine, ahead of time, whether a finite solution for this problem exists!

This discovery means that * IF * there is a solution to one problem belonging to the class, then that solution should be applicable to things like the economy or poker. But it does not, in any way, imply that there "should" be, or "is", a solution. That remains to be seen.

Thank You Very Much For Corroborating (0)

Anonymous Coward | more than 4 years ago | (#30039608)

My equation P = NP in Yadda-Yadda-Yadda above.

Yours In Novosibirsk,
K. Trout

Re:"Non-Deterministic" (2, Informative)

scheme (19778) | more than 4 years ago | (#30039684)

Not so. There is a reason this class of problems is called "non-deterministic". That is because there is no way to determine, ahead of time, whether a finite solution for this problem exists!

No, that's just wrong. The problems are called non-deterministic polynomial (NP) because they can be solved in polynomial time by a non-deterministic turing machine. A non-deterministic turing machine is a turing machine that can take go into multiple states and accepts an input if any of it's states end up leading to an accept state. Think superposition of states with a wave collapse if you're a physicist.

All of these problems have finite solutions and in fact one of the requirements is that a NP problem has a solution that can be checked in polynomial time by a deterministic turing machine.

A simpler way to say it... (1)

tjstork (137384) | more than 4 years ago | (#30040082)

Is that you can think of a non-deterministic machine as the inverse of a deterministic machine. For my own education into the problem, I wrote a program that simulated an instruction set running backwards, but in the complete set sense.

So, if I put in a program to multiply, I could feed it two inputs A and B and get the multiplied value C. If I supplied C, the machine would be crunched "backwards" to get the various possibilities of A and B. Of course, in order for this to work without an explosion of possibilities, you would need a "magic" engine that knows the exact choice needed to arrive at a correct answer A and B at each step of the machine.

The next plan would have been to see if it were possible, given the bits of the solution set of C, and the engine, and the known symbols, to construct an uber table that can look up each of the steps of the engine... Now, how does one build that magic engine? That was what seemed to me the crux of the whole problem and unfortunately I got frustrated with it and walked away about a year. The whole mess is in source forge...

http://sourceforge.net/projects/bicomp/ [sourceforge.net]

I feel a round 2, coming on.

Re:"Non-Deterministic" (1)

offrdbandit (1331649) | more than 4 years ago | (#30039818)

You are mistaken. By "single solution" they are not referring to a "solution" to the problem, but a "solution" to the problem of calculating the solution. That is, the class of problems are related in such a way that an efficient algorithm for one is an efficient algorithm for all (because each problem can be decomposed in polynomial time time into "sister" problems of the same class).

risk vs uncertainty (1)

Hognoxious (631665) | more than 4 years ago | (#30039520)

There was a short article in t'Economist recently. The difference is that in poker, there's a finite set of outcomes - you can't have a hand that has both the pi of jodhpurs and the duke of pretzels in it. In economics, unforeseen and even unforeseeable situations can and do occur.

Bloatware (0, Troll)

jameskojiro (705701) | more than 4 years ago | (#30039532)

Bloatware = Current Government

Time to re-install windows on a freshly formatted hard drive, ala. Revolution.....

Wikipedia's Altered Theory of Computation (3, Funny)

Halotron1 (1604209) | more than 4 years ago | (#30039552)

Now would be a GREAT time to go alter the wikipedia articles on NP completeness and such, then watch the aftermath on slashdot as the n00bs go do their research and learn what it is for the first time!

any class works (1)

hort_wort (1401963) | more than 4 years ago | (#30039628)

You want to learn economics? Figure out how to afford the textbooks and supplementary math software you need to take the course. Done.

It's always easy to learn how to spread out a dollar when you're broke. I can see how the MIT guys might have trouble with it though.

Nice setup (5, Funny)

istartedi (132515) | more than 4 years ago | (#30039646)

What can CS teach ECON?

How to crash routinely and have people shrug it off as normal.

Re:Nice setup (1)

VocationalZero (1306233) | more than 4 years ago | (#30039904)

You've got that backwards; ECON has been crashing long before CS even existed.

I believe in the Prep-H theroy of economics (1)

Virtucon (127420) | more than 4 years ago | (#30039650)

Apply to finger and then apply to your butt.

Why? Because all your money disappears like so many hemorrhoids. It gets itchy and needs to be gotten rid of. Spending your money makes the itch go away, just like Prep-H.

Always mount a scratch economy (0)

Anonymous Coward | more than 4 years ago | (#30039654)

So, this economist and... (2, Insightful)

fintler (140604) | more than 4 years ago | (#30039674)

So, this economist and a computer scientist are sitting at a bar.... and these 5 girls walk in....

Oh really? (1)

xednieht (1117791) | more than 4 years ago | (#30039676)

The only thing you need to know about game theory is how to cheat and tell credible lies - game over. Where's my stinking award?

Economics can never be modeled succesfully (1)

trybywrench (584843) | more than 4 years ago | (#30039698)

The problem with economics is the act of constructing a model changes reality. As soon as you take action based on your model, your model (and your actions) now become inputs to the system. You're doomed to forever chase a moving target, the more perfect the model the faster it becomes irrelevant. At best you can take some low hanging fruit with statistics preying on the ignorance of those less sophisticated. Goldman Sachs and the other HFT banks have this approach down to a science with the day trading crowd. GS's models are sufficient to trade in the noise of day traders and take them to the cleaners, that's why there's the saying "the fastest way to make a small fortune day trading is to start with a large forture". Modeling economics on a large scale though is a fool's errand.

ummm (2, Insightful)

nomadic (141991) | more than 4 years ago | (#30039746)

Some computer scientists are calling this the biggest development in game theory in a decade."

Computer scientists and economists? What about the actual mathematicians?

He said it is a dismal science (0)

Anonymous Coward | more than 4 years ago | (#30039852)

I am with Linus on this one
Linus is right
The man makes sense
He is absolutely correct on this one

Three person games (1)

samwhite_y (557562) | more than 4 years ago | (#30040050)

I am pleased to see this result. It agrees with some of my own suspicions. Let me describe a simple three person game (players A, B, and C). Here is the rule for each player when it is their turn.

A player must take $1.00 away from one opponent and give at least half of it to the other opponent. Whatever is not given to the other opponent can be kept by the acting player.

Each player in turn gets to choose which player to steal a $1.00 from and how much of it they will keep (they can keep at most half) and how much to give to the other opponent. Assume you do 50 rounds of this game (each player is visited 50 times).

Here is the problem: construct an optimal strategy for each player.

What makes this problem so difficult is the issue of collusion. If two players decide to gang up on another player, they can both profit at that other player's expense. But if you assume that none of the players have friendships or other factors that might induce collusion, then the only way to get collusion is to offer "bribes". A bribe can be both an offer to not take away a $1.00 and it can be an offer to give more than the standard half of the $1.00 to the other opponent. An optimal strategy is based on deciding who is likely to be giving you better bribes in the future and how do you induce such behavior with your own bribes.

Now, here is the part I consider exciting. The claim is that calculating the Nash Equilibrium is hard (in a computer calculating sense) for three person games, this one being an example. The claim is actually stronger than that. Getting even somewhat close to a Nash Equilibrium is hard (if it were not, then you would evolve slowly towards the Nash equilibrium by slowly refining "good" solutions into "better" ones -- that would be most likely doable in polynomial time). In other words, not only is it hard to calculate the perfect strategy, it is hard to even calculate a good one.

To see why that might be the case, let us assume that the three players have chosen a strategy which causes player A to think "it really does not matter if I choose to steal $1.00 from one opponent or another -- my expected outcome is the same." Then player B could offer just 0.01 more of a bribe to induce player A to favor B over C consistently. In other words, a very small adjustment in strategy by one player can have a huge potential impact on their future expected out come. It is this instability of outcome which is the mark of an NP computational problem. A small wiggle in inputs creates huge "chaotic" changes in outputs.

Side note: This "large change" in outcome based on small change in input is at the heart of what makes factoring large numbers hard. If you multiply two large numbers together, and change just one digit in one number, it will have a large and somewhat unpredictable (until you actually calculate it -- but then that means you are still having to try out all different products to factor a number) outcome.

We've been here before . . . (0)

Anonymous Coward | more than 4 years ago | (#30040146)

It was the MIT and Ivy League mathematicians who got the economy into its current troubles. This sounds like nothing more than a new set of 'quants.' But, then again, there will always be the next big thing.

overstated (1)

jipn4 (1367823) | more than 4 years ago | (#30040246)

The implications of such a result are overstated:

* It's easy to construct markets in which finding the optimal solution is NP-hard, and many real-world problems are already of that form--for example, any economic decision that involves an NP-hard optimization problem.

* Participants already don't find optimal solutions even given infinite computational resources simply because people lack the necessary information to find optimal solutions to begin with.

* NP-hardness is nearly useless in characterizing the difficulty of real-world problems anyway. Being NP-hard doesn't mean that problems of interest are necessarily hard. And many problems in P don't have practical algorithms for large problem instances.

It's interesting that simple 2 person games can be hard as well, but that doesn't fundamentally change what was already known: markets often don't function optimally because of computational limitations.

Mind Surfer (0)

Anonymous Coward | more than 4 years ago | (#30040258)

I can't remember the name of the author, but inside it's deranged drug-trip of a storyline the author hypothesized basically this exact type of formula, eventually resulting in one of the characters almost getting killed after making a killing on dealer-slanted cardgames based on results of the formula, mentally calculated I believe.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>