Online Mechanism Design for Differentially Private Data Acquisition

We address a problem involving a buyer seeking to train a logistic regression model by acquiring data from privacy-sensitive sellers. Along with compensating the sellers for their data, the buyer provides differential privacy guarantees to them where the payments depend on the privacy guarantees. In addition, each seller has a different privacy sensitivity associated with their data, which is the cost per unit of loss of privacy. The buyer transacts sequentially with the sellers, wherein the seller will disclose their privacy sensitivity, and the buyer immediately provides a payment and guarantees differential privacy. After receiving the payment, the seller provides their data to the buyer. The buyer's goal is to optimize a weighted combination of test loss and payments, i.e., achieve a tradeoff between getting a good ML model and limiting its payments. Additionally, the buyer must design the payments and differential privacy guarantees in an online fashion. Further, the online problem is historydependent, which adds to the challenge. Consequently, we design a payment mechanism that ensures incentive compatibility and individual rationality and is asymptotically optimal. Additionally, we also provide experimental results to validate our findings.