While a lot of mathematical research seems to be math for math’s sake, every once in a while a piece of research will hit upon something that is fundamentally important to what is going on in the real world as the Complexity of Games research by Constantinos Daskalakis from MIT has. Daskalakis’s work classifies the complexity of finding certain Nash Equilibrium problems and shows that some of them will still not be solved by the heat death of the universe and therefore causing some problems for economical game theorists who espouse finding the Nash Equilibrium of an economic system as the best way of dealing with our economic problems. MIT News has a great write up of Daskalakis’s work, as well as a nice little explanation of game theory:
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 Nobel Prize 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 game theory, a “game” is any mathematical model 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.
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.
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 computer science 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.”