论文标题
置入式挡片：一种用于差异私人选择的新机制
Permute-and-Flip: A new mechanism for differentially private selection
论文作者
论文摘要
我们考虑差异私人选择的问题。鉴于有限的候选项目和每个项目的质量分数，我们的目标是设计一种差异化机制，该机制返回具有尽可能高的分数的项目。该任务的最常用机制是指数机制。在这项工作中，我们基于对隐私约束的仔细分析，为该任务提出了一种新的机制。我们机制的预期得分始终与指数机制一样大，并且可以提供高达两倍的改进。我们的机制易于实现，并在线性时间内运行。
We consider the problem of differentially private selection. Given a finite set of candidate items and a quality score for each item, our goal is to design a differentially private mechanism that returns an item with a score that is as high as possible. The most commonly used mechanism for this task is the exponential mechanism. In this work, we propose a new mechanism for this task based on a careful analysis of the privacy constraints. The expected score of our mechanism is always at least as large as the exponential mechanism, and can offer improvements up to a factor of two. Our mechanism is simple to implement and runs in linear time.
