McCormick Magazine


Opportunities at the intersection of game theory and computer science


fortnow"A small band of economists and computer scientists, unified by an appreciation for mathematical beauty and a common vision, is amassing at Northwestern University. Your mission, should you choose to accept it, is to join this elite group in the time-honored search for truth, beauty, and science. The fate of the Internet and global electronic commerce rests in the balance."

Rarely do recruitment posters for PhD programs parody movie trailers — but then again, rarely has a new group garnered the excitement that the newly formed Economics Group in the Department of Electrical Engineering and Computer Science has generated over the past year.

The group bridges the gap between two fields that have long shared many similarities — even a founder. In the 1940s and 1950s the work of noted mathematician John von Neumann gave rise to both computer science and game theory. Now, as the Internet provides new challenges to old theories and an entirely new way to observe human interaction, the two fields are increasingly intertwined.

At McCormick, three new hires have made this intersection between game theory and computer science a considerable strength. Leveraging the historic prominence of the Kellogg School of Management's work in game theory, the Department of Electrical Engineering and Computer Science (EECS) looks to assume leadership in this quickly developing field.

As Nicole Immorlica, assistant professor, settles into her new position at McCormick this fall, she joins Jason Hartline, assistant professor, and Lance Fortnow, professor of electrical engineering and computer science, to form the new Economics Group at McCormick. Also key to the development of the group is Rakesh Vohra, the John K. and Helen Kellogg Professor of Managerial Economics and Decision Sciences at Kellogg. Thanks to a joint appointment in EECS, Vohra links that department to Kellogg, which has been a leader in game theory for decades. The success of Kellogg's faculty in this area should help the interaction flourish.

"We have the largest group of people doing game theory at any one institution in the world," says Vohra. "This new area helps cement Northwestern's reputation in game theory. This is a growing field, and we now have a substantial strength that we didn't have before."

Predicting presidents and precipitation
immorlica and hartlineIn the run-up to the 2008 presidential election, new polls surfaced several times a week, often switching favor between John McCain and Barack Obama. But the polls often lagged several days behind many major events — such as the oft-discussed postconvention "bounce." To avoid that delay, Fortnow considers a different method: prediction markets.

If you take any future event — like an election — create a stock that pays out only if the event comes to fruition, then trade it, the pricing of the security is an indicator of the likelihood of an event. These prediction markets have been shown to be quite accurate — better than polls and experts.

"The markets react immediately to news, but a proper poll can take three days," Fortnow says. "The markets move very quickly. They figured out that Joe Biden was going to be the Democrats' vice presidential pick before the announcement."

Several corporations also use prediction markets to forecast sales and pick release dates for products. Fortnow's research considers the theoretical models of these markets with the aim of understanding how they aggregate information so well. He also studies the effect of market manipulation on these markets and ways to design the markets and their presentation in order to maximize their usefulness.

Fortnow's other work in prediction is a collaboration with Rakesh Vohra. Together they've studied the accuracy of predictions, including one that affects each of us every day: weather. When the local TV weather forecaster predicts a 25 percent chance of rain, and then it rains, how do you judge the accuracy of the forecast? "If I say there's a 25 percent chance, and it rains, I'm not incorrect," Vohra explains. "The fact that it rained is not itself evidence of a bad forecast."

Since the 1950s economists have devised many ways to judge the accuracy of a forecast. One popular method, calibration, assigned a score to forecasts, with a score of 0 being perfect. But in the 1990s Vohra determined that it was possible to obtain a score of 0 even with no knowledge of the weather — raising doubts about the value of the score. "If I don't need to know anything to look good according to this measure, what does that say about the measure?" Vohra says.

Further research showed that all of the methods of determining the accuracy of a forecast fell victim to this problem. Recently Fortnow and Vohra have studied the computational complexity of devising ways to fool the system. "We looked at how complicated it was to construct the forecasts that would game the test," Vohra says. "Based on that information, we argued that someone gaming the test was somewhat impractical."

Advertising auctions
Internet search engines sell the advertisements that appear next to your search results. The advertising content displayed is the result of a complex auction that considers the popularity of your search terms, your location, the price advertisers are willing to pay to reach you, and the likelihood that you will click on a given result. But if you are a company such as Microsoft, Google, or Yahoo, how do you design these auctions in order to maximize your revenue? And how do you perform these massive computations in real time?

Online auctions are a relatively new phenomenon — and one that has put a new spin on economic auction theories. Understanding how to value online goods presents new challenges that require different solutions — which are exactly what Nicole Immorlica intends to find.

"In online algorithms you don't know the actions of the buyers but you need to design a solution," Immorlica says.

Every person assigns a real value to a given object — whether it's an ad on Google or a sweater on eBay. But when asked to state that value, a person is unlikely to provide that information. The only thing that you can count on is that buyers will act in their own self-interest. "You have to solicit information from users, and they can manipulate what they say," Immorlica explains. "We're trying to approximate a value in the absence of true information."

Immorlica also studies social networks, capitalizing on the vast amount of information that the Internet has made readily available. The Internet keeps a running log of collaborations — making it possible to see how groups form and dissolve around specific problems or projects. By understanding how these collaborations form and operate, it may be possible to encourage a specific behavior by applying those principles to the offline world.

"We're trying to understand how we can engineer social networks to introduce properties that we would like to see, such as diversity," Immorlica says. "In the housing market, for example, what effect do government policies have on increasing diversity in specific neighborhoods? Does it help to give subsidies to poor classes or to provide education about the values of diversity?"

What Immorlica likes most about this work is that it focuses on people. "I'm interested in understanding how and why things are the way they are and how we can affect them to make life better for everybody involved," she says. "It's compelling to think of people being in control of their own actions, but depending on how we design the systems in which people interact, we can affect the outcome. I want to try to make these systems work well and optimally."

Mechanism design
EECS posterWhen a city planner lays out the traffic scheme for a city — which streets are one-way or two-way — he's essentially designing a game. And when you're stuck in traffic on the way home, both you and the city planner have lost.

That's how Jason Hartline explains the complex topic of mechanism design, his primary area of research. Mechanism design is the process of setting the rules and incentives of a system so that a certain objective is obtained. In the traffic example, it's setting the rules of the road so that when all drivers behave in their own interest, everyone gets to their destination quickly. And if the system isn't designed optimally, gridlock results. "Mechanism design is setting up a game so that when people behave selfishly, good things happen." Hartline explains.

Northwestern has been a pioneer in the field of mechanism design. Many major advances in the field came from Kellogg in the 1970s: For example, 2007 Nobel laureate Roger Myerson was awarded the prize for work he did at Northwestern during that time. "One of the reasons why I moved to Northwestern is that it has traditionally been a center for this area," Hartline says.

As a computer scientist, Hartline approaches mechanism design differently than his economist colleagues. "I tend to view design questions the way computer scientists tend to view design questions," he says. "If you want a computer system to solve some problem, you want to solve it every time, and you want it to be good no matter what. In economics, the typical approach is to design a mechanism for a particular stylized setting. My work tries to design a single mechanism that works in all settings, not just a particular one."

One of the ways that Hartline does this is to focus on approximating an optimal solution instead of focusing on the optimal solution itself. "When an optimal solution is complicated, maybe a simple one is approximately optimal — and maybe this simple solution is much more reasonable and realistic in the real world," Hartline says. "In the real world complicated things don't tend to happen; instead, very simple things tend to work."

By approximating an optimal solution, it's also possible to limit the computational power needed to arrive at an answer — a key concern for computer scientists who are interested in solving problems quickly and under the constraints of a given computer system.

Looking to the future
Fortnow, Hartline, and Immorlica all say that the opportunity to build a program from scratch was one of the things that brought them to Northwestern — though it also presents a significant challenge. "Students tend to be wary about coming to a group that doesn't have a history," Fortnow says. "Some of it will come with time."

Hartline thinks the group is up to the challenge. "To be at an institution with the best economists and game theorists is what brought me here," he says. "I wanted to go somewhere with an excellent economics group where I can have a high-level interaction and then make the computer science part happen. It's a challenging undertaking to go to a computer science department where there is no presence in the area that you work in. Having the three of us here is a great beginning. We are here to put together a really strong group."

—Kyle Delaney