Achievement

We use game theory to analyze the robustness of online recommender systems. In online recommender systems, users with a vested interest in having certain items promoted or lowered may attempt to manipulate the recommendations, perhaps by creating a number of fake `sybil' or `shill' accounts. A recent design, the Influence Limiter, is provably robust against attacks by a bounded number of shills, but this robustness comes at the cost of a performance loss: In guarding against attack, the algorithm potentially discards information from genuine raters, and the quantity of information discarded grows with the number of shills it must be robust against. We prove that the tradeoff between robustness and efficiency in the Influence Limiter is essential: Any recommender algorithm robust against n shills must discard about log n information from each genuine rater in the system in the worst case. (Resnick and Sami, 2008)