Jennifer Chayes

When Jennifer Chayes left her job at the University of California, Los Angeles, in 1997 to become a researcher at Microsoft’s labs in Redmond, she declared that it would take 100 years for her academic work to find real-world applications. But as managing director of the newly announced Microsoft Research New England lab in Cambridge, MA, she has parlayed her background in mathe­matical physics into research with broad implications for today’s Internet.

To Chayes, the trails left by countless social and business interactions on the Internet amount to enormous math problems. Solving those problems, she believes, will help computer scientists create online tools, such as search engines and social networks, that are more efficient and effective.

TR assistant editor Erica Naone met with Chayes at the still-empty offices of her new Cambridge lab to learn how a mathematician understands the Internet.

TR: What is the common theme in your research?

Jennifer Chayes: I’m particularly interested in self-organized networks, such as the World Wide Web and social networks. In self-organized networks, people or entities choose to enter the network on their own. There’s not some authority dictating the structure of the network, so that structure is constantly evolving.

Can you give me an example of how you try to understand a network?

There’s a whole area called game ­theory, which takes into account that people are selfish agents. [It also models their interactions and the possible outcomes, attempting to define the best result for each “player.”] Now researchers are starting to study game theory on networks, modeling the complex interactions among many selfish agents. Understanding the possible outcomes and behaviors of these networks is one of the next big mathematical challenges.

TR: Are there examples?

JC: [Online] advertisers bidding on a variety of keywords. Each advertiser is a self-interested party interacting with all other advertisers who bid on the same keywords. Each advertiser has a valuation for each word, and an overall budget. Since we don’t know how to deal with the repeated game on the network implicit in this set of interactions, we just do a separate auction on each keyword to assign ads to search words. Maybe if we could deal with some of these problems mathematically, we could come up with something that was actually more efficient than these separate auctions–better for the advertisers, better for the customers, better for the search engines.

TR: How would that help?

JC: If we more efficiently match up ads with queries when we perform the ad auctions, then the consumer is more likely to get what he or she is seeking, the advertiser is more likely to generate maximum sales per ad dollar, and the search engine is more likely to generate the maximum revenue per search. No search engine comes close to the optimum today. So there’s a lot of room for improvement.

TR: Where else might your work help?

JC: I think that recommendation systems are going to be as important as search algorithms [see “Recommendation Nation”]. In a recent piece of work, we came up with a list of desired properties for a recommendation system, and what we ended up doing was proving mathematically that there is no possible recommendation system that has all these desired properties. So I would have to choose which properties I am willing to give up and design recommendation systems that preserve the properties I want most.

TR: What kinds of properties?

JC: There’s transitivity. If I trust the recommendation of person B, and person B trusts the recommendation of person C, then I should trust the recommendation of person C.

TR: What about privacy? Can recommendation systems still let users keep control?

JC: Those are exactly the kinds of questions that we’re asking. We didn’t consider privacy in our work, but one could definitely add privacy to the list of properties, and then it might be possible to come up with a theorem saying, for example, you can’t have a recommendation system that will deliver all the information you want and have all the privacy.

TR: How might this research change the way we use these applications?

JC: It could be that at some point somebody could go onto a social network and say, “Here are the properties that I want for my recommendation system,” and a different person could go in and say, “Here are the properties that I want,” and they could get two different recommendation systems. In a similar way, search engines have been around for a while, but I think they’re still very far from exactly what we want, and over time we’ll be able to come up with search engines which are much more personalized. Then we would also have to figure it out on the back end. Can we accommodate all these different algorithms? I hope that at some point computations would be done differently for your search engine and recommendation system and for mine.