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.

By admin