# What computer science can teach economics

##### Nov 09, 2009 by Larry Hardesty

(PhysOrg.com) -- Computer scientists have spent decades developing techniques for answering a single question: How long does a given calculation take to perform? Constantinos Daskalakis, an assistant professor in MIT’s Computer Science and Artificial Intelligence Laboratory, has exported those techniques to game theory, a branch of mathematics with applications in economics, traffic management -- on both the Internet and the interstate -- and biology, among other things. 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.

Game theory is a way to mathematically describe strategic reasoning — of competitors in a market, or drivers on a highway or predators in a habitat. In the last five years alone, the in economics has twice been awarded to game theorists for their analyses of multilateral treaty negotiations, price wars, public auctions and taxation strategies, among other topics.

In , a “game” is any that correlates different player strategies with different outcomes. 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. And indeed, that pair of strategies is what’s called the “Nash ” for the game. Named for John Nash — who taught at MIT and whose life was the basis for the movie A Beautiful Mind — the Nash equilibrium is the point in a game where the players have found strategies that none has the incentive to change unilaterally. In this case, for instance, neither player can improve her outcome by going one direction more often than the other.

Of course, most games are more complicated than the penalty-kick game, and their Nash equilibria are more difficult to calculate. But the reason the Nash equilibrium is associated with Nash’s name — and not the names of other mathematicians who, over the preceding century, had described Nash equilibria for particular games — is that Nash was the first to prove that every game must have a Nash equilibrium. Many economists assume that, while the Nash equilibrium for a particular market may be hard to find, once found, it will accurately describe the market’s behavior.

Daskalakis’s doctoral thesis — which won the Association for Computing Machinery’s 2008 dissertation prize — casts doubts on that assumption. 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. And in those cases, Daskalakis believes, human beings playing the game probably haven’t found it either.

In the real world, competitors in a market or drivers on a highway don’t (usually) calculate the Nash equilibria for their particular games and then adopt the resulting strategies. Rather, they tend to calculate the strategies that will maximize their own outcomes given the current state of play. But if one player shifts strategies, the other players will shift strategies in response, which will drive the first player to shift strategies again, and so on. This kind of feedback will eventually converge toward equilibrium: in the penalty-kick game, for example, if the goalie tries going in one direction more than half the time, the kicker can punish her by always going the opposite direction. But, Daskalakis argues, feedback won’t find the equilibrium more rapidly than computers could calculate it.

The argument has some empirical support. Approximations of the Nash equilibrium for two-player poker have been calculated, and professional poker players tend to adhere to it — particularly if they’ve read any of the many books or articles on game theory’s implications for poker. The Nash equilibrium for three-player poker, however, is intractably hard to calculate, and professional poker players don’t seem to have found it.

How can we tell? Daskalakis’s thesis showed that the Nash equilibrium belongs to a set of problems that is well studied in computer science: those whose solutions may be hard to find but are always relatively easy to verify. The canonical example of such a problem is the factoring of a large number: The solution seems to require trying out lots of different possibilities, but verifying an answer just requires multiplying a few numbers together. In the case of Nash equilibria, however, the solutions are much more complicated than a list of prime numbers. The Nash equilibrium for three-person Texas hold ’em, for instance, would consist of a huge set of strategies for any possible combination of players’ cards, dealers’ cards, and players’ bets. Exhaustively characterizing a given player’s set of strategies is complicated enough in itself, but to the extent that professional poker players’ strategies in three-player games can be characterized, they don’t appear to be in equilibrium.

Anyone who’s into computer science — or who read “Explained: P vs. NP” on the MIT News web site last week — will recognize the set of problems whose solutions can be verified efficiently: It’s the set that computer scientists call NP. 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. (The cognoscenti will infer that it’s the set called NP-complete; but the fact that the Nash equilibrium always exists disqualifies it from NP-completeness. In fact, it belongs to a different set, called PPAD-complete.)

That result “is one of the biggest yet in the roughly 10-year-old field of algorithmic game theory,” says Tim Roughgarden, an assistant professor of at Stanford University. It “formalizes the suspicion that the Nash equilibrium is not likely to be an accurate predictor of rational behavior in all strategic environments.”

Given the Nash equilibrium’s unreliability, says Daskalakis, “there are three routes that one can go. One is to say, We know that there exist games that are hard, but maybe most of them are not hard.” In that case, Daskalakis says, “you can seek to identify classes of games that are easy, that are tractable.”

The second route, Daskalakis says, is to find mathematical models other than Nash equilibria to characterize markets — models that describe transition states on the way to equilibrium, for example, or other types of equilibria that aren’t so hard to calculate. Finally, he says, it may be that where the Nash equilibrium is hard to calculate, some approximation of it — where the players’ strategies are almost the best responses to their opponents’ strategies — might not be. In those cases, the approximate equilibrium could turn out to describe the behavior of real-world systems.

As for which of these three routes Daskalakis has chosen, “I’m pursuing all three,” he says.

Provided by Massachusetts Institute of Technology (news : web)

Explore further: Researchers use Twitter to predict crime

## Related Stories

#### Decision making, is it all 'me, me, me'?

Apr 28, 2008

People act in their own best interests, according to traditional views of how and why we make the decisions that we do.

#### Counterintuitive physics may help everyone drive home quicker

Oct 02, 2008

If you're trying to drive to a destination as quickly as possible, you might think that knowing the traffic conditions would help you choose the quickest route for yourself. Traffic reports and new GPS technologies ...

#### Game theory and machine learning offer better bidding strategies

May 13, 2009

(PhysOrg.com) -- By combining techniques from game theory and artificial intelligence, computer scientists at the University of Michigan have developed a better way to find the best bidding strategy in a simulated auction ...

#### In poker, psychologist places bets on skill

Mar 21, 2008

Is it luck of the draw in poker? No, says Michael DeDonno, a doctoral student from Case Western Reserve University. Based on findings from two psychology studies, he suggests putting your bets on skills over luck when playing ...

#### Computer Poker Program Knows When to Hold 'Em

Aug 06, 2008

(PhysOrg.com) -- Texas Hold'em poker has exploded in popularity over the past few years. Its popularity has extended to academic researchers, who are intrigued by the challenges of probabilities and decision-making in the ...

#### What's the role of Kupffer cells in non-alcoholic steatohepatitis?

Nov 03, 2008

Nonalcoholic steatohepatitis (NASH) is a disorder characterized by hepatic steatosis, inflammation and fibrosis with a risk of developing cirrhosis and hepatocellular carcinoma (HCC). The progression from simple steatosis ...

## Recommended for you

#### Researchers use Twitter to predict crime

Apr 20, 2014

Hidden in the Twittersphere are nuggets of information that could prove useful to crime fighters—even before a crime has been committed.

#### UT Dallas professor to develop framework to protect computers' cores

Apr 18, 2014

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

#### Researcher finds hidden efficiencies in computer architecture

Apr 18, 2014

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

#### Scientists apply new graph programming method for evolving exascale applications

Apr 18, 2014

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

## More news stories

#### Finnish inventor rethinks design of the axe

(Phys.org) —Finnish inventor Heikki Kärnä is the man behind the Vipukirves Leveraxe, which is a precision tool for splitting firewood. He designed the tool to make the job easier and more efficient, with ...

#### Japan's digital eyes show your emotions for you

Can't be bothered to show anyone what you're thinking? Then a Japanese scientist has the answer—a pair of digital eyes that can express delight and anger, or even feign boredom.

#### High court to hear dispute about TV over Internet

Thirty years ago, big media companies failed to convince the Supreme Court of the threat posed by home video recordings.

#### Airport security officers at TSA gaining insight from Sandia human behavior studies

A recent Sandia National Laboratories study offers insight into how a federal transportation security officer's thought process can influence decisions made during airport baggage screening, findings that ...

#### Review: With Galaxy S5, Samsung proves less can be more

Samsung Electronics Co. has produced the most formidable rival yet to the iPhone 5S: the Galaxy S5. The device, released over the weekend, is the fifth edition of the company's successful line of Galaxy S ...

#### Making graphene in your kitchen

Graphene has been touted as a wonder material—the world's thinnest substance, but super-strong. Now scientists say it is so easy to make you could produce some in your kitchen.

#### Bulletproof nuclei? Stem cells exhibit unusual absorption property

Stem cells – the body's master cells – demonstrate a bizarre property never before seen at a cellular level, according to a study published today from scientists at the University of Cambridge. The property ...

#### Study casts doubt on climate benefit of biofuels from corn residue

Using corn crop residue to make ethanol and other biofuels reduces soil carbon and can generate more greenhouse gases than gasoline, according to a study published today in the journal Nature Climate Change.

#### Poll: Big Bang a big question for most Americans

Few Americans question that smoking causes cancer. But they have more skepticism than confidence in global warming, the age of the Earth and evolution and have the most trouble believing a Big Bang created the universe 13.8 ...

#### Google Trends info is placed on inbox duty for subscribers

(Phys.org) —Google Trends has added a new service to its mix, where users can enter email subscriptions for Google Trends, and can be sent notifications on topics of interest, showing them what is popular ...