Stochastic Privacy

Online services such as web search and e-commerce ap-plications typically rely on the collection of data about users, including details of their activities on the web. Such personal data is used to maximize revenues via targeting of advertisements and longer engagements of users, and to enhance the quality of service via per-sonalization of content. To date, service providers have largely followed the approach of either requiring or re-questing consent for collecting user data. Users may be willing to share private information in return for incen-tives, enhanced services, or assurances about the nature and extent of the logged data. We introduce stochastic privacy, an approach to privacy centering on the sim-ple concept of providing people with a guarantee that the probability that their personal data will be shared does not exceed a given bound. Such a probability, which we refer to as the privacy risk, can be given by users as a preference or communicated as a pol-icy by a service provider. Service providers can work to personalize and to optimize revenues in accordance with preferences about privacy risk. We present pro-cedures, proofs, and an overall system for maximizing the quality of services, while respecting bounds on pri-vacy risk. We demonstrate the methodology with a case study and evaluation of the procedures applied to web search personalization. We show how we can achieve near-optimal utility of accessing information with prov-able guarantees on the probability of sharing data