A Utility-Theoretic Approach to Privacy in Online Services

1. Introduction

• Personal information can improve online services, but users and providers may also be uncomfortable with its access and use.Combining individually non-identifying data can narrow a user into a smaller group or identify them.Source: §1 · pp. 1–2
• The paper balances the benefits of personalization against the costs of sharing personal data, rather than excluding personal data or limiting analysis to users’ devices.The tradeoff is considered according to users’ preferences.Source: §1 · p. 2
• The framework models diminishing utility gains as submodularity and accelerating privacy costs as supermodularity.As more personal information is acquired, utility may add less while identification concerns become greater.Source: §1 · p. 2
• For web search, the method predicts the page a searcher will visit and selects attributes that improve prediction while making user identification difficult.The utility of an attribute set is its focusing power for the prediction task; the same probabilistic model quantifies identification risk.Source: §1 · p. 2
• Prominent “sweet spots” let users achieve most of the utility with minimal private-information sharing.The approach is evaluated on real-world search data and uses preferences elicited from a study with over 1,400 participants.Source: §1 · p. 3

2.1 Utility of Accessing Private Data

• Utility is the expected entropy reduction in predicted search intentions after observing selected user attributes alongside the query.The model predicts the target intention from the query and attributes, then uses that distribution to inform which search results to present.Source: §2.1 · pp. 3–4

2.2 Cost of Sharing Private Data

• Privacy cost includes identifiability risk, measured through expected loss over users’ identity distributions after observing selected attributes.The framework also adds subjective attribute sensitivity and other additive costs to identifiability cost.Source: §2.2 · p. 4

2.2.1 IDENTIFIABILITY LOSS FUNCTIONS

• The maxprob loss represents an adversary’s probability of correctly guessing the user, while the section also considers rescaled maxprob and probabilistic k-anonymity losses.The maxprob formulation assumes the adversary has access to the same data sources used to form the probability distribution.Source: §2.2.1 · p. 5

2.3 Optimizing the Utility-Privacy Tradeoff

• The approach seeks an attribute set with high utility and low privacy cost; the scalarized objective is NP-hard, and the stated guarantee is at least one-third of the optimum.The section says solutions achieving even slightly more than approximately 63% of the optimal score cannot be expected efficiently.Source: §2.3 · p. 6

2.4 Hard Constraints on Privacy Cost

• A hard cost constraint can instead maximize utility subject to C(A) ≤ B; the section notes that approximation guarantees apply only to the scalarized tradeoff.A k-anonymity constraint can provide per-user guarantees, but the stated approximation guarantees do not extend to the constrained problem.Source: §2.4 · p. 6

Utility and cost properties

• Under conditional independence of attributes given the target intention, utility is submodular; the section also reports empirical verification without that assumption.Submodularity formalizes diminishing gains from adding attributes as the selected set grows.Source: §3 · pp. 6–7
• If attributes are marginally independent and together characterize the user, maxprob identifiability cost is supermodular; empirical evaluation also verifies supermodularity without those assumptions.Attribute sensitivity is additive and therefore supermodular, so it preserves supermodularity when combined with maxprob identifiability cost.Source: §3 · p. 7

General utility-privacy tradeoff

• With nondecreasing submodular utility and nondecreasing supermodular cost, the scalarized objective U(A) − λC(A) is submodular and can be maximized as a set function.The formulation assumes only these structural properties of utility and cost.Source: §3 · p. 7

4. Optimization Algorithms

• LS returns a solution achieving at least 1/3 of the optimal score, using at most O(1 εn3 log n) function evaluations.The guarantee applies to nonnegative submodular objectives, which need not be nondecreasing.Source: §4 · p. 8

4.1 An Efficient Implementation

• Lazy local search selects elements greedily, uses lazy updates justified by submodularity, and can reduce running time by an order of magnitude.In the reported implementation, the algorithm usually terminates after one downward pass without removing an element.Source: §4.1 · p. 8

4.2 Evaluating Utility and Cost

• Rather than explicitly evaluating sums over the empirical training distribution at Ω(N2) cost for N training examples, LLS estimates utility U(A) and cost C(A) by sampling.When λ is such that Fλ(V) ≥ 0, sampled LLS efficiently finds a solution achieving at least a constant fraction of 1/3 times the optimal value.Source: §4.2 · p. 10

4.3 Computing Online Bounds

• Submodularity of utility and supermodularity of cost yield online bounds for an arbitrary current attribute set, including extensions for sampling error.The bound uses the attributes whose marginal utility exceeds their individual privacy-cost term.Source: §4.3 · p. 11

4.4 Finding the Optimal Solution

• Branch-and-bound and mixed-integer programming are presented as alternatives for finding an optimal solution while exploiting submodularity.These approaches do not require Fλ to be nonnegative.Source: §4.4 · p. 11

5. Search Log Data and Attributes

• The dataset contains 247,684 queries from 9,523 volunteers over 14 months; analysis retains 914 queries seen from at least 30 users and constructs 31 user/query attributes.Utility is measured as average reduction in click entropy, and no attribute uses more than three bits.Source: §5 · p. 11

5.1 Demographic Attributes

• Demographic attributes include gender, age group, occupation, and region, each discretized into at most three bits and voluntarily supplied at signup.Reporting rates were 86% for gender, 94% for age, and 57% for occupation.Source: §5.1 · p. 11

5.2 Search Activity Attributes

• Search-activity attributes capture repeated queries and clicks, search frequency, coarse network location, and query timing.For example, 70% of queries were repeated, while 31% of users queried from at least two zip codes and 40% of queries occurred during working hours.Source: §5.2 · p. 12

5.3 Topic Interests

• Topic-interest attributes are binary indicators of whether users visited sites in each of 16 Open Directory Project top-level categories.Topic classification was available for 96% of queries.Source: §5.3 · p. 12

6. Survey on Privacy Preferences

• The survey assessed preferences about sharing different personal attributes in return for improved search efficiency, with 1,451 responses to an online survey distributed within Microsoft.The scenario specified that information would be used for one query and discarded immediately afterward.Source: §6 · pp. 12–13

6.1 Questions about Individual Attributes

• More than 50% of participants said they would share every probed attribute if search performance doubled; region sharing drew 92.7% willingness, versus lower willingness for news-related interests.Marital status and having children drew the lowest willingness, at 54.4% and 52.6%, respectively.Source: Figure 1 · p. 13, §6.1 · p. 14

6.2 Questions about Identifiability

• Participants considered even topic-only search-activity storage more sensitive than sharing a city or birth year, and expressed preferences about the granularity of shared information.The survey also varied storage duration and guaranteed indistinguishability from k others.Source: §6.2 · p. 14, Figure 3 · p. 15

6.3 Questions about Utility

• The survey linked attribute sensitivity to the search-performance improvement required for sharing, then used sensitivity as a common currency for privacy cost and utility.Figure 5 reports medians and 25th and 75th percentiles for the k-discriminability and utility questions.Source: §6.3 · pp. 15–16, Figure 5 · p. 16

6.4 Questions about the Current State

• Respondents commonly believed search engines knew their country (96%) and stored all searches (86%), while fewer believed they knew occupation (16%), age (28%), or gender (34%).The authors identify these beliefs as a baseline for interpreting attribute-sensitivity classifications.Source: §6.4 · pp. 16–17, Figure 4 · p. 16

7.1 Computing Utility and Cost

• Click-entropy reduction leveled off at roughly 1.92 bits after the greedy ordering selected 14 attributes, illustrating diminishing returns.The reported order begins DOCC, ATLV, DAGE, ACTY, AQRY, ACLK, AWHR, TADT, AWDY, THOM, TCIN, DGDR, TGMS, and TREG.Source: §7.1 · p. 18
• Under minimum-incremental-cost ordering, cost rose slowly at first and then faster; k-anonymity flattened after 25 of 31 attributes, while cost behaved supermodularly in the low-cost region.The plateau occurred when enough information was available to reduce the candidate set to fewer than k = 100 people in most cases.Source: §7.1 · p. 18, Figure 9 · p. 19

7.2 Calibrating the Tradeoff with Assessed Preferences

• Preference calibration mapped location sensitivity to utility bits and aligned the survey and data cost curves at λ ≈ 5.12, within the 1 ≤ λ ≤ 10 tradeoff knee.Improvement by a factor of x was mapped to log2 x bits, and the sensitivity-to-utility mapping was approximately invariant to the scale used to assess sensitivity.Source: Figure 8 · p. 18, §7.2 · p. 19

7.3 Optimizing the Utility-Privacy Tradeoff

• The LLS solution retained six attributes and discarded DOCC because its sensitivity was high relative to the additional information it provided.The retained attributes were AFRQ, ATLV, AWDY, AQRY, ACLK, DAGE, and TSPT.Source: §7.3 · p. 20
• The optimized attribute set scored 0.83 with approximately 1.4 bits of click-entropy reduction, outperforming the tested heuristics.Search statistics scored 0.57 with utility 0.8; demographic attributes scored 0.3 despite utility 0.95, and topic interests scored -1.73.Source: §7.3 · pp. 20–21, Figure 11 · p. 20
• Lazy evaluation reduced runtime from 522.1 to 225.7 minutes; even an optimistic exhaustive-search estimate for sets of at most eight attributes was 50.1 years.The timings were measured on a 3 GHz desktop using a C# implementation.Source: §7.3 · p. 21, Figure 12 · p. 21

8. Related Work

• This version extends Krause & Horvitz (2008) with additional experiments, a detailed LLS discussion, and theoretical bounds.The paper also organizes prior work around its main concepts and methods.Source: §8 · pp. 21, 23

8.1 Personalized Search, Probabilistic Models for Search

• Prior personalized-search approaches include client-local reranking and privacy-preference parameters, but the cited approach does not trade off attribute-set costs and benefits or model discriminability across users.Local term-frequency reranking is described by Teevan et al. (2005); Xu et al. (2007) use minDetail and expRatio parameters.Source: §8.1 · p. 23

8.2 Value of Information in Probabilistic Models

• Earlier value-of-information methods include greedy approaches without theoretical guarantees; the authors position their method as the first principled, efficient, nonmyopic tradeoff of information value and privacy cost.The discussion also notes limits of prior methods based on large-sample evaluation, chain-structured models, or conditional-independence assumptions.Source: §8.2 · p. 23

8.3 Valuation of Private Information

• Prior privacy-valuation work includes auctions, incentive studies, and Shapley-value estimates; the latter is presented as a possible alternative for eliciting subjective sharing costs.The authors suggest it could potentially be combined with their optimization approach.Source: §8.3 · pp. 23–24

8.4 Mathematical Notions of Privacy

• Mathematical privacy notions such as k-anonymity and differential privacy quantify privacy risks, but the authors describe them as not designed around a specific utility and as complementary to their approach.The discussion notes limits on query classes for one cited differential-privacy approach, including click-probability estimation.Source: §8.4 · p. 24

8.5 Utility-Privacy Tradeoff

• Compared with privacy-preserving data-publishing methods, the authors quantify application-specific utility and cost in common units and report near-optimal guarantees for their algorithm.The cited publishing algorithms are described as lacking performance and approximation guarantees.Source: §8.5 · pp. 24–25

9.1 Location of private information

• Private information may reside with the client, service provider, or in the communication channel, and these choices shape implementation.The discussion identifies where and when optimization occurs as critical design choices.Source: §9.1 · p. 25, §9 · p. 25

9.2 Client-side Private Information

• Client-side personalization keeps private information local and avoids network transmission, but limits migration across machines and depends on the local machine’s security.The proposed methodology could help client services acquire and store only the most relevant information.Source: §9.2 · p. 25

9.3 Server-side Private Information

• On the server side, the methods can help balance sensitivity and service utility when deciding what behavioral data to log, how to anonymize it, or what profiles users provide.The authors present these as potential applications of the methodology.Source: §9.3 · p. 25

9.4 Channel-side Private Information

• For channel-side use, the methodology could select which private bits to transmit per request to maximize utility while minimizing privacy risk.Source: §9.4 · p. 25

9.5 A Priori vs. Dynamic Tradeoff Optimization

• The timing choice is between an a priori tradeoff made before system use and dynamic decisions made during online activity.The discussion frames when to optimize as an important design parameter.Source: §9.5 · p. 26, §9.5.1 · p. 26, §9.5.2 · p. 26

9.5.1 A PRIORI TRADEOFF OPTIMIZATION / PRIVACY-AWARE SERVICE DESIGN

• A priori selection fixes which private bits are used for logging, local profiles, or request protocols, and avoids inference attacks combining information across requests.Source: §9.5.1 · p. 26

9.5.2 DYNAMIC OPTIMIZATION

• Dynamic selection could use query-specific information and reduce the average private bits per request, but raises challenges from cross-request inference, computation, and eliciting user preferences.The authors note that an optimization may be needed for each request and that adaptive submodularity may offer relevant methods.Source: §9.5.2 · p. 26

• Identifiability cost can have an increasing-cost property, which also arises when algorithms’ computational costs grow superlinearly with the number of attributes.Source: §9.6 · p. 26
• Trading information, such as click-entropy reduction, against computational cost can have the same combinatorial structure as the paper’s utility–privacy tradeoff.Source: §9.6 · p. 26
• Lazy local search and sample-complexity analyses may also apply in these computational-cost settings.Source: §9.6 · p. 26

10. Conclusions

• The approach efficiently finds a provably near-optimal utility–privacy tradeoff for personalized services such as web search.Source: §10 · p. 27
• Click-entropy-reduction utility is submodular, while privacy cost is supermodular, with sensitivity and identifiability risk growing faster as more private information accrues.Source: §10 · p. 27
• The methodology was evaluated on real-world web-search data, and its tradeoff was calibrated using privacy and utility preferences from a study of over 1,400 participants.Source: §10 · p. 27
• The evaluation found that significant personalization can be achieved using only a small amount of user information.Source: §10 · p. 27

Appendix A. Proofs

• For the proof’s chosen identifiability cost, F1(A) equals U(A) and is nonnegative when |A| is at most n/2, but negative when |A| exceeds n/2.Source: Appendix A · p. 27
• A polynomial-time guarantee of at least (1 − 1/e) of the best utility under the size constraint would imply P = NP.Source: Appendix A · p. 27
• The identifiability-cost proof partitions V into A and B and establishes that Im(A) is supermodular.Source: Appendix A · pp. 27–28
• The sample-complexity proof carries additive error through earlier lemmas and applies the union bound to obtain confidence 1 − δ.Source: Appendix A · p. 28