Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
Math Science

What Computer Science Can Teach Economics 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."
This discussion has been archived. No new comments can be posted.

What Computer Science Can Teach Economics

Comments Filter:
  • by zach_the_lizard ( 1317619 ) on Monday November 09, 2009 @06:26PM (#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:Hayek (Score:5, Informative)

    by zach_the_lizard ( 1317619 ) on Monday November 09, 2009 @06:34PM (#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.

  • by scheme ( 19778 ) on Monday November 09, 2009 @06:59PM (#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.

  • by Red Flayer ( 890720 ) on Monday November 09, 2009 @07:13PM (#30039808) Journal

    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.

  • by Marcika ( 1003625 ) on Monday November 09, 2009 @07:18PM (#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.

  • by icebraining ( 1313345 ) on Monday November 09, 2009 @07:40PM (#30040160) Homepage

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

  • by VampireByte ( 447578 ) on Monday November 09, 2009 @08:35PM (#30040752) Homepage

    I have graduate degrees in both Computer Science and Economics and this commonality was so obvious to me over a decade ago that it wouldn't have seemed worth writing about. Hell, you even study Von Neumann in both of these fields at the undergraduate level.

  • by zach_the_lizard ( 1317619 ) on Monday November 09, 2009 @08:57PM (#30040960)
    Friedman wasn't an Austrian in any sense of the word. Hayek, though, is who I'm talking about. And Rothbard, Hayek, and Mises all had their own disagreements. Rothbard dedicates a tiny section of one of his books (For a New Liberty?) to a critique of Mises's claim that economics lacks value judgements, for example.
  • Re:No shit (Score:3, Informative)

    by Gorobei ( 127755 ) on Monday November 09, 2009 @09:34PM (#30041236)

    Don't be shocked, the MIT article doesn't even get the simple example of game theory right:

    One of the simplest examples is the penalty-kick game: In soccer, a penalty kick gives the offensive player a shot on goal with only the goalie defending. The goalie has so little reaction time that she has to guess which half of the goal to protect just as the ball is struck; the shooter tries to go the opposite way. In the game-theory version, the goalie always wins if both players pick the same half of the goal, and the shooter wins if they pick different halves. So each player has two strategies -- go left or go right -- and there are two outcomes -- kicker wins or goalie wins.

    It's probably obvious that the best strategy for both players is to randomly go left or right with equal probability; that way, both will win about half the time.

    Wrong. This model of a a real-world game ignores the fact that the goalie has an option: where he stands. MIT should stick to the prisoner's dilemma, sports are not their area of expertise :)

    The best strategy is not random left/right. It is for the goalie to position himself off-center such that the shooter goes left or right with non-equal probabilities, and the goalie dives with non-equal probabilities.

  • Re:Hayek (Score:5, Informative)

    by khallow ( 566160 ) on Monday November 09, 2009 @09:52PM (#30041344)

    No laboratory experiments can be performed with regard to human action.

    One of the most profoundly stupid statements ever uttered by an economist. Sure you can't stick the global economy in a beaker and have controls and the other paraphernalia of controlled lab tests, the highest standard of science. But you can experiment with human action at the individual or small group in a controlled lab. It's routinely done these days. There is such a thing as experimental verification and falsification.

  • Re:Bullshit! (Score:3, Informative)

    by david_thornley ( 598059 ) on Tuesday November 10, 2009 @11:45AM (#30046234)

    Completely wrong. Lots of people buy bits all the time. If I buy an album from iTunes for $9.99, we have to assume that album is probably worth $9.99 to me, and hence I'm better off with it. In the meantime, other people divvy up my ten bucks, and since they spent almost nothing they're better off. Hence, wealth has been created. It doesn't matter if I pay for it or get it for free, as long as I find value in it. For negligible transaction cost, I've got something worth at least ten bucks to me.

    Of course, this can't be extended indefinitely, since we hit the law of diminishing returns. I can listen to only so much music, read so many books, and so on, and I do need things like food and clothing. This means that we can't increase wealth indefinitely by sharing software.

    So, we conclude that wealth isn't fixed, we can do some things that increase wealth without significant cost, or things that increase wealth at a cost, but we can't increase it arbitrarily.

  • Re:Bullshit! (Score:3, Informative)

    by ShakaUVM ( 157947 ) on Tuesday November 10, 2009 @04:15PM (#30050698) Homepage Journal

    >>That software did not come out of thin air. Yes, the copies you made were essentially free but resources were initially consumed to produce it. The value of copies of that product when access and distribution are nearly free is essentially zero.

    The "value" of something (sorry to break it to you) is whatever someone is willing to pay for it.

    If I think MATLAB is worth $1,000, but I can find a used copy for $100, am I now effectively $900 richer or $100 poorer? By your definition, I would be poorer (since it has an "inherent" value of $0, according to you). Also, by your funky definition, wealth would only decrease. But in an actual objective sense, since I need MATLAB in order to run my business and make more money elsewhere.

    Your weird definition would also say I came out $900 ahead if I got MATLAB on a physical DVD, but lost money on the transaction if it was fully digital, which is rather silly if you think about it - I get the same software either way.

    I'd recommend you reflect on your definitions of wealth and value.

The only possible interpretation of any research whatever in the `social sciences' is: some do, some don't. -- Ernest Rutherford