Collecting Preference Rankings Under Local Differential Privacy

In this paper, we initiate the study of collecting preference rankings under local differential privacy. The key technical challenge comes from the fact that the number of possible rankings increases factorially in the number of items to rank. In practical settings, this number could be large, leading to excessive injected noise. To solve this problem, we present a novel approach called SAFARI. The general idea is to collect a set of distributions over small domains which are carefully chosen based on the riffle independent model to approximate the overall distribution of users' rankings, and then generate a synthetic ranking dataset from the obtained distributions. By working on small domains instead of a large domain, SAFARI can significantly reduce the magnitude of added noise. Extensive experiments on real datasets confirm the effectiveness of SAFARI.