Buying Data from Privacy-Aware Individuals: The Effect of Negative Payments

We study a market model where a data analyst uses monetary incentives to procure private data from strategic data subjects/individuals. To characterize individuals’ privacy concerns, we consider a local model of differential privacy, where the individuals do not trust the analyst so privacy costs are incurred when the data is reported to the data analyst. We investigate a basic model where the private data are bits that represent the individuals’ knowledge about an underlying state, and the analyst pays each individual according to all the reported data. The data analyst’s goal is to design a payment mechanism such that at an equilibrium, she can learn the state with an accuracy goal met and the corresponding total expected payment minimized. What makes the mechanism design more challenging is that not only the data but also the privacy costs are unknown to the data analyst, where the costs reflect individuals’ valuations of privacy and are modeled by “cost coefficients.” To cope with the uncertainty in the cost coefficients and drive down the data analyst’s cost, we utilize possible negative payments (which penalize individuals with “unacceptably” high valuations of privacy) and explore interim individual rationality. We design a family of payment mechanisms, each of which has a Bayesian Nash equilibrium where the individuals exhibit a threshold behavior: the individuals with cost coefficients above a threshold choose not to participate, and the individuals with cost coefficients below the threshold participate and report data with quality guarantee. By choosing appropriate parameters, we obtain a sequence of mechanisms, as the number of individuals grows large. Each mechanism in this sequence fulfills the accuracy goal at a Bayesian Nash equilibrium. The total expected payment at the equilibrium goes to zero; i.e., this sequence of mechanisms is asymptotically optimal.