MIT News - Nash equilibrium
https://news.mit.edu/rss/topic/nash-equilibrium
MIT news feed about: Nash equilibriumenFri, 18 Mar 2011 04:00:01 -0400Dueling algorithms
https://news.mit.edu/2011/dueling-algorithms-0318
If software companies design their algorithms with the sole intention of outperforming each other, the customer can be the loser.Fri, 18 Mar 2011 04:00:01 -0400https://news.mit.edu/2011/dueling-algorithms-0318Larry Hardesty, MIT News OfficeThere’s an old joke about two hikers on a trail, one wearing hiking boots and the other running shoes. “Why the running shoes?” the first hiker asks. “In case of bears,” the second answers. The first hiker laughs and says, “Running shoes won’t help you outrun a bear.” “I don’t need to beat the bear,” the second hiker says. “I just need to beat you.”<br /><br />When computer scientists design algorithms, they’re generally concerned with providing the best possible answer in the shortest amount of time. But for a web company in a competitive market, the best algorithm might just be the one that beats the other guy. At the Association for Computing Machinery’s 43rd Annual Symposium on Theory of Computing in June, Ankur Moitra, a PhD student in the Computer Science and Artificial Intelligence Laboratory, and colleagues will <a href="http://arxiv.org/pdf/1101.2883v1" target="_blank">present a new mathematical framework</a> for analyzing such “dueling algorithms.” The work could help answer questions such as when competition between web services helps meet social ends and when it undermines them, and it could also prove useful in the social sciences.<br /><br />To understand the idea of dueling algorithms, Moitra says, consider a search engine ranking the results of a query. The words of the query could be subject to multiple interpretations: “Cambridge,” for instance, could refer to several different cities. Suppose that in using a given search term, 40 percent of people mean one thing, 30 percent a second and 30 percent a third. A computer scientist designing a search algorithm in the abstract would probably prioritize the most likely interpretation. But in a commercial market, if that’s what the leading search engine does, a competitor might do well to prioritize the other two. Forty percent of its customers will be disappointed, but the other 60 percent will prefer the results they get to those provided by the market leader.<br /><br />Of course, the leader is unlikely to sit idle as the upstart steals its business. So it might evolve some hybrid ranking strategy, sprinkling some of the less likely interpretations among its top results. That, in turn, would prompt the competitors to revise their strategies, which would prompt another revision from the leader, and so on. Ultimately, the theory goes, the competitors in the market will converge on what economists call an equilibrium, a state in which no competitor has any incentive to change its strategy unilaterally. Any given contest could have many equilibria; which one emerges depends on how the contestants’ strategies evolve over time.<br /><br /><strong>Balance of power</strong><br /><br />Moitra and his colleagues at Northwestern University, the University of Toronto, the University of Pennsylvania, Israel’s Technion and Microsoft Research have developed methods for finding equilibrium strategies much more efficiently than was previously possible, at least for two-player, winner-take-all contests. Even these simple contests, however, yield enormously complex calculations. Finding equilibria generally requires comparing all possible strategies against each other. In the search engine example, that would mean comparing every ordering of search results against every other ordering. As the number of results gets larger, the complexity of the comparison increases exponentially.<br /><br />For several different types of contest, however, Moitra and his colleagues found ways to represent the results of different strategies probabilistically. That makes it much easier to calculate equilibria, but the strategies found to be in equilibrium are defined only by their statistics. So the researchers also had to provide computational methods for finding specific sets of strategies that match the statistical profiles of the equilibrium calculation.<br /><br />In their paper, the researchers consider several cases of dueling algorithms. Among them are two computers searching for an item in a database, two companies trying to hire employees from the same pool of applicants, and two racers trying to plot routes across a town with erratic traffic patterns. In each case they find that an equilibrium strategy for beating an opponent may not be a good strategy in the abstract: the company may not end up with the best possible employees, for instance, and the computer may not find the item in the database as efficiently as it could.<br /><br />According to Eva Tardos, Jacob Gould Schurman Professor of Computer Science at Cornell University, the researchers’ paper “is more the beginning of research than a definitive result or end product.” The researchers’ models make several simplifying assumptions — including the number of competitors — that make the math easier but limit their applicability. Nonetheless, “just raising the questions is an important step forward,” Tardos says. “With traditional optimization, you just want the algorithm to be as good as possible, versus wanting to beat the opponent. Clearly, there’s a tension between these goals. I think they are setting a research agenda to understand this tension.”<br /><br />Ankur Moitra, a PhD student in the Computer Science and Artificial Intelligence Laboratory.Photo: Patrick GilloolyWhat computer science can teach economics
https://news.mit.edu/2009/game-theory
Constantinos Daskalakis applies the theory of computational complexity to game theory, with consequences in a range of disciplines.Mon, 09 Nov 2009 03:01:00 -0500https://news.mit.edu/2009/game-theoryLarry Hardesty, MIT News OfficeComputer scientists have spent decades developing techniques for answering a single question: How long does a given calculation take to perform? <a href="http://people.csail.mit.edu/costis/">Constantinos Daskalakis</a>, 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.<br /><br />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. <br /><br />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.<br /><br />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 equilibrium” for the game. Named for John Nash — who taught at MIT and whose life was the basis for the movie <em>A Beautiful Mind</em> — 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.<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />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 them — 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.<br /><br />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. <br /><br />Anyone who’s into computer science — or who read <a href="/newsoffice/2009/explainer-pnp.html">“Explained: P vs. NP”</a> 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.)<br /><br />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.”<br /><br />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.”<br /><br />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.<br /><br />As for which of these three routes Daskalakis has chosen, “I’m pursuing all three,” he says.<br /><br />Constantinos Daskalakis, an assistant professor in MIT’s Computer Science and Artificial Intelligence Laboratory.Photo: Satyen Kale, Yahoo! Research