Timezone: »

Permute-and-Flip: A new mechanism for differentially private selection
Ryan McKenna · Daniel Sheldon

Tue Dec 08 07:20 AM -- 07:30 AM (PST) @ Orals & Spotlights: Social/Privacy

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.

Author Information

Ryan McKenna (University of Massachusetts, Amherst)
Daniel Sheldon (University of Massachusetts Amherst)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors