New techniques for computation over private data
Zhiyi Huang · Scholarly Commons (University of Pennsylvania) · 2013
Rapid development in computing technology and the Internet has given rise to new challenges in large-scale computational problems. In particular, many problems that arise from electronic commerce rely on the private data of self-interested agents. So the algorithms need to deal with both limited computational resources and some new challenges imposed by social, economic, and personal considerations of the agents. 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 agents' utilities from the outcome of the mechanism. On the other hand, differential privacy considers the privacy perspective, focusing on the agents' concern on the potential leak of their private data, which may harm their utilities in the future. Finally, a recent direction of research considers handling both perspectives simultaneously. Our contributions are threefold. (1) For the game-theoretic perspective, we advance the technique of black-box reductions in mechanism design by reducing mechanism design problems to the better-understood algorithm design problems for all problems in the Bayesian setting and all single-parameter and symmetric problems in the 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 answering distance queries. 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 can handle both the game-theoretic and the privacy perspectives simultaneously for any mechanism design problems.