Home' Technology Review : May June 2008 Contents Q&A
When Jennifer Chayes left her
job at the University of Cali-
fornia, 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
mathematical physics into research with
broad implications for today's Internet.
To Chayes, the trails left by count-
less social and business interactions on
the Internet amount to enormous math
problems. Solving those problems, she
believes, will help computer scien-
tists create online tools, such as search
engines and social networks, that are
more e cient and e ective.
TR assistant editor Erica Naone met
with Chayes at the still-empty o ces of
her new Cambridge lab to learn how a
mathematician understands the Internet.
TR: What is the common theme in your
Chayes: I'm particularly interested
in self-organized networks, such as the
World Wide Web and social networks. In
self-organized networks, people or enti-
ties choose to enter the network on their
own. There's not some authority dictat-
ing 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 mod-
els their interactions and the possible
outcomes, attempting to define the best
result for each "player."] Now research-
ers 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.
Are there examples?
[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 prob-
lems mathematically, we could come up
with something that was actually more
e cient than these separate auctions---
better for the advertisers, better for the
customers, better for the search engines.
How would that help?
If we more e ciently 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 opti-
mum today. So there's a lot of room for
Where else might your work help?
I think that recommendation systems
are going to be as important as search
algorithms [see "Recommendation Nation,"
p. 82]. 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 mathemati-
cally that there is no possible recommen-
dation 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.
What kinds of properties?
There's transitivity. If I trust the rec-
ommendation of person B, and person B
trusts the recommendation of person C,
then I should trust the recommendation
of person C.
What about privacy? Can recommendation
systems still let users keep control?
Those are exactly the kinds of ques-
tions that we're asking. We didn't con-
sider 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 recommenda-
tion system that will deliver all the infor-
mation you want and have all the privacy.
How might this research change the way
we use these applications?
It could be that at some point some-
body could go onto a social network and
say, "Here are the properties that I want
for my recommendation system," and
a di erent person could go in and say,
"Here are the properties that I want," and
they could get two di erent recommen-
dation 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
di erent algorithms? I hope that at some
point computations would be done dif-
ferently for your search engine and rec-
ommendation system and for mine.
Understanding online networks
Photograph by MARK OSTOW
Hear Jennifer Chayes s ideas on
Microsoft s Cambridge research lab:
Links Archive March April 2008 July August 2008 Navigation Previous Page Next Page