Buying private data without verification

Arpita Ghosh, Katrina Ligett, Aaron Roth, Grant Schoenebeck

Introduction

In the era of big data, researchers often face a fundamental tension when collecting information on sensitive topics such as medical conditions, illegal activities, or controversial opinions. This challenge, termed the "Sensitive Surveyor’s Problem," arises from two primary obstacles: the data is inherently unverifiable, and participants are strategic agents who weigh the financial incentives of participation against the potential privacy costs of revealing their information.

Originally published in 2014 and updated in 2018, this research provides a theoretical framework to resolve this tension. The authors propose a mechanism that incentivizes truthful reporting of sensitive data by combining peer prediction with differential privacy, demonstrating that high accuracy can be achieved at a cost that diminishes as the population grows.

The Problem: Unverifiability and Privacy Sensitivity

Standard survey methods often fail when dealing with sensitive information for two reasons:

  1. Unverifiability: There is no "ground truth" database to verify a participant's answer. The surveyor must rely entirely on the participant's report.
  2. Strategic Privacy: Participants recognize that the survey's aggregate result might leak information about them. If the perceived "privacy cost"—the potential social or legal harm resulting from this leakage—exceeds the offered payment, a rational agent will either opt out or provide false data.

Previous literature typically assumed that data was either verifiable or that participants only cared about the privacy of the process rather than the result. This paper addresses the more complex reality where agents care about both their compensation and the information leaked by the final aggregate statistic.

The Mechanism: Peer Prediction and Joint Differential Privacy

To address these hurdles, the authors design a mechanism ($M_{P,n,\alpha,\beta,\epsilon}$) that integrates two sophisticated frameworks:

Peer Prediction

Peer prediction is a method used to elicit truthful information without external verification. It functions by rewarding participants based on how well their report predicts the reports of others. The authors utilize a modified Brier Scoring Rule, where a participant's expected payment is maximized when they report their information honestly, provided the model understands the general correlation of data within the population.

Joint Differential Privacy (JDP)

While standard Differential Privacy (DP) ensures an algorithm's output is insensitive to any single individual's data, Joint Differential Privacy (JDP) is a specialized variant. In this context, JDP ensures that the output seen by everyone except agent $i$ (such as the payments to others and the public result) remains private relative to agent $i$’s data. This is essential because while agent $i$ knows their own data, they must be assured that the collective results do not betray their specific contribution to others.

Implementation Steps

The mechanism operates through the following steps:

  1. Data Collection: The surveyor collects binary reports (bits) from participants.
  2. Aggregation with Noise: The surveyor calculates the average of these reports and adds Laplace noise to guarantee $\epsilon$-differential privacy.
  3. Rescaled Payments: Using this noisy aggregate, the surveyor calculates payments for each participant via a rescaled Brier score. The scaling is calibrated to be large enough to offset the participant's privacy cost but small enough to remain within a feasible budget.

Key Insights: The Role of Noise and the "Free" Survey

A central, counter-intuitive finding of this research is that noise is not merely an obstacle to accuracy but a tool for enablement. By adding noise to the aggregate, the surveyor provides a mathematical guarantee of privacy. This guarantee lowers the privacy cost for participants, encouraging honest participation. Consequently, a private survey with added noise can yield a more accurate estimate than a non-private survey where participants are incentivized to lie.

Furthermore, the authors explore the "outcome-based" privacy cost model. In this setting, as the number of participants ($n$) increases, the influence of any single individual on the final aggregate statistic diminishes. As a result, the individual privacy risk vanishes. The authors prove that the total expected cost to the surveyor is $O(1/n)$, meaning that in very large populations, the total budget required to ensure honesty effectively drops to zero.

Results and Accuracy

The paper provides formal proofs for several key properties:

  • Truthfulness as Equilibrium: Truthful reporting is shown to be a symmetric Bayes-Nash equilibrium.
  • Accuracy Guarantees: The mechanism produces an estimate that is $\alpha'$-accurate with high probability, where the error $\alpha'$ is a function of the noise required for privacy and the number of participants who choose to opt out.
  • Efficiency: The mechanism demonstrates that large-scale sensitive surveys are not only theoretically possible but economically efficient.

Limitations and Future Work

Despite its robust theoretical foundation, the mechanism has limitations that invite further study:

  • Equilibrium Selection: While truth-telling is an equilibrium, it may not be the only one. There is a risk of "bad" equilibria where participants coordinate to lie (e.g., everyone reporting 0) to minimize collective privacy costs.
  • Prior Knowledge: The surveyor must possess some prior knowledge of the data distribution (the marginal prior) to correctly calibrate the scoring rules.
  • Trust Assumptions: The model assumes a "trusted curator" who will not leak individual payment information, as observing another's payment could potentially reveal their private cost parameters.

By bridging the gap between economics and differential privacy, this work provides a vital path forward for collecting high-quality data on the world's most sensitive and difficult-to-track issues.

Summary updated

BibTeX
@inproceedings{ghosh2014buying,
  author = {Arpita Ghosh and Katrina Ligett and Aaron Roth and Grant Schoenebeck},
  title = {{Buying private data without verification}},
  booktitle = {EC},
  year = {2014},
  url = {https://openreview.net/forum?id=jW_RqyOhbg3},
}
Figure