COLLOQUIUM
               Computer Science Department, Boston University

Speaker: Prof. Ashish Goel
         Stanford University
         www.stanford.edu/~ashishg

Title: Towards robust reputation systems

Date:  January 21, 2005
Time:  11:15 am
Place: MCS 135 (for directions, see www.cs.bu.edu/colloquium)

Abstract:

We will study the robustness of reputation systems in several settings.

Eigenvector based methods in general, and Google's PageRank algorithm for
rating web pages in particular, have become an important component of
information retrieval on the Web. These methods measure the reputation of a
web-page as its stationary distribution in an associated random walk. Such
methods are susceptible to collusions by groups of web-page owners
interested in increasing the ranks of their web-pages. We will present
metrics, hardness results, and algorithms for the problem of detecting
colluding web-pages.  In particular, we will define the amplification ratio
of a set of web-pages as the amount of "extra reputation" this set
generates for itself. We prove that the problem of finding sets with high
amplification is formally hard, and then under certain assumptions on the
mixing time of the web graph, obtain a polynomial time algorithm for
identifying a colluding web-page.

We then discuss the phenomena of ballot stuffing and bad mouthing in eBay
like reputation systems. We prove that these phenomena can be mitigated
provided the reputation premium is small compared to the transaction costs.

This represents joint work with Hui Zhang, Kahn Mason, Ramesh Govindan,
Benjamin Van Roy, and Rajat Bhattacharjee.

Brief biography:

Ashish Goel is an Assistant Professor of Management Science and Engineering
and (by courtesy) Computer Science at Stanford University.  He received his
PhD in Computer Science from Stanford in 1999, and was an Assistant
Professor of Computer Science at the University of Southern California from
1999 to 2002.  His research interests lie in the design, analysis, and
applications of algorithms.  Professor Goel is a recipient of an Alfred
P. Sloan faculty fellowship (2004-06), a Terman faculty fellowship from
Stanford, and an NSF Career Award (2002-07).

Host: John Byers