Algorithms for Selecting the Optimum Dataset While Providing Personalized Privacy and Compensation to its Participants

摘要

The privacy preserving microdata sharing literature has proposed several techniques that allow a database administrator to share a dataset in a privacy preserving manner. This paper considers the implications of adding a market layer to that setting. In this setting, individuals (data providers) can receive a market-determined compensation in exchange for their information while they also receive a personalized privacy protection. The computational burdens of satisfying a variety of privacy requirements of individuals (sellers) and dataset requirements of the data receiver (buyer) are analyzed in this paper. The author presents a polynomial time reformulation procedure that proves that the "optimum information product" creation problem reduces to multiple-choice knapsack problem, which is a weakly NP hard problem. The problem of various instance sizes is solved using FICO Xpress 7.0 optimization software. The insights presented in the paper can be utilized for creating a market of individual information in different settings.