Privacy, Personalization, and the Web: A Utility-Theoretic Approach

Online offerings such as web search face the challenge of providing high-quality service to a large, heterogeneous user base. Recent efforts have highlighted the potential to improve performance by introducing methods to personalize services based on special knowledge about users. For example, a user’s location, demographics, and past search and browsing may be useful in enhancing the efficiency and accuracy of web search. However, reasonable concerns about privacy by both users and providers limit access by services to such information. We explore the rich space of possibility where people can opt to share, in a standing or a real-time manner, personal information in return for expected enhancements in the quality of an online service. We present methods and studies on addressing such tradeoffs between privacy and utility in online services. We introduce concrete and realistic objective functions for efficacy and privacy and demonstrate how we can efficiently find a provably near-optimal optimization of the utility-privacy tradeoff. We evaluate our methodology on data drawn from a large-scale web search log of people who volunteered to have their logs explored so as to contribute to enhancing search performance. In order to incorporate personal preferences about privacy and utility, and the willingness to trade off revealing some quantity of personal data to a search system in returns for gains in efficiency, we performed a user study with 1400 participants. Employing utility and preference data from the real-world data, we show that a significant level of personalization can be achieved using only a small amount of information about users.