Private data can often be valuable, and so companies or agencies may be willing to pay individuals in order to access their data. Determining the correct amount to pay each user turns out to be extremely challenging: pay too little and the more privacy-sensitive individuals may choose not to participate, resulting in an unrepresentative sample, while paying too much is expensive.
Ghosh and Roth (EC '11) initiated the formal study of this question using tools and concepts from game theory and differential privacy. They consider players who have (1) a single private data bit that an authority wants to purchase and (2) a "privacy valuation" that models how much the player cares about privacy. The authority must elicit the privacy valuation from the players and then choose which players to purchase data from, and at what price. One of the main challenges they point out is that the privacy valuation and the data may be correlated: for example, if I test positive for chlamydia, I would likely value the privacy of my test result more than if I tested negative.
Continuing this line of research, we prove two main results:
- We strengthen a previous negative result of [GR'11], and show that when the player's privacy valuation may be arbitrarily correlated with their data, there is no mechanism solving the problem that is accurate, individually rational, truthful, and makes finite payments.
- We consider a restricted way in which privacy valuation and data may be correlated that we call "monotone", which is natural in many settings. For example, in the case of chlamydia test results, monotonicity states that individuals should not have a higher privacy valuation when testing negative than when testing positive. We exhibit a mechanism with good guarantees when allowing monotone correlation between the privacy valuation and data.
This is based on joint work with Kobbi Nissim and Salil Vadhan.