How to Compute over Private Data

Опубликовано 8 августа 2016, 17:55

Over the past decade, rapid development in computing technology and the Internet has given rise to new challenges in large-scale computational problems. In particular, many computational problems that arise from electronic commerce rely on the private data of self-interested agents. So the algorithms not only need to deal with usual computational resource limitations but also the new constraints imposed by social, economic, and personal considerations. On the one hand, algorithmic mechanism design studies the game-theoretic perspective of private data, aiming to incentivize truthful behavior by ensuring that truth-telling maximizes the ``one-shot'' utilities of the agents, i.e., the utilities directly generated from the outcome of the mechanism. On the other hand, differential privacy considers the privacy perspective of private data, focusing on the agents' concern on the potential leak of their private data by the mechanism, which may harm their utilities in the future. Finally, there has been a recent direction of research aiming to handle both perspectives simultaneously by combining the techniques from both fields. In this talk, I will give an overview of my contributions to these three topics. (1) For the game-theoretic perspective, we advance the technique of black-box reductions in mechanism design, reducing a large family of mechanism design problems to the better-understood algorithm design problems, including all problems in Bayesian setting and all single-parameter and symmetric problems in prior-free setting. (2) For the privacy perspective, we introduce the technique of low-sensitivity metric embedding and propose efficient and differentially private mechanisms for a sub-class of query release problems. Our result is among the first to circumvent the known impossibility results for general query release problems. (3) Finally, we propose the first general technique for designing mechanisms that handle both the game-theoretic and the privacy perspectives simultaneously for any mechanism design problems.