Mechanism Design for Utility-Aware Personalized Privacy Guarantees

The widespread adoption of data-driven services, including networked data collection and analysis systems, has greatly enhanced convenience and decision-making, but it has also raised growing concerns about the trade-off between fine-grained utility and personalized privacy guarantees. Personalized Differential Privacy (PDP) offers a flexible framework by allowing users to specify individualized privacy budgets. However, existing sampling-based PDP mechanisms often rely on coarse risk modeling assumptions that treat individual data characteristics uniformly, leading to suboptimal utility and inefficient privacy expenditure. In this paper, we propose the Utility-Aware Sampling Mechanism (UASM), a principled PDP implementation that enables fine-grained, user-centric privacy control while explicitly optimizing utility. First, UASM formalizes policy-assisted secret specifications, allowing confidentiality to be determined through a combination of baseline protection rules and personalized privacy preferences, and combines them with individualized privacy budgets. Second, UASM employs a two-stage utility-aware sampling strategy to calibrate noise: (i) an optimal global threshold selected to reduce unnecessary privacy-budget wastage while respecting users’ declared budgets, and (ii) a sensitivity-aware refinement stage that allocates privacy loss according to each record’s influence on query accuracy. Formal privacy analysis demonstrates that UASM provides rigorous privacy guarantees and promotes fairer privacy expenditure under heterogeneous privacy requirements. Extensive experiments on synthetic and real-world datasets, including network-oriented downstream tasks, show that UASM achieves a superior privacy-utility trade-off over state-of-the-art PDP baselines, underscoring its practical effectiveness.