Private Rank Aggregation under Local Differential Privacy

Ziqi Yan, Gang Li, Jiqiang Liu

Abstract

As a method for answer aggregation in crowdsourced data management, rank aggregation aims to combine different agents' answers or preferences over the given alternatives into an aggregate ranking which agrees the most with the preferences. However, since the aggregation procedure relies on a data curator, the privacy within the agents' preference data could be compromised when the curator is untrusted. Existing works that guarantee differential privacy in rank aggregation all assume that the data curator is trusted. In this paper, we formulate and address the problem of locally differentially private rank aggregation, in which the agents have no trust in the data curator. By leveraging the approximate rank aggregation algorithm KwikSort, the Randomized Response mechanism, and the Laplace mechanism, we propose an effective and efficient protocol LDP-KwikSort. Theoretical and empirical results show that the solution LDP-KwikSort:RR can achieve the acceptable trade-off between the utility of aggregate ranking and the privacy protection of agents' pairwise preferences.

1. Introduction

Rank aggregation is a fundamental process in crowdsourcing, voting, and recommendation systems, where individual preferences are merged into a single consensus ranking. Traditionally, this requires a central server (the curator) to collect exact rankings. Even if the server uses "Central Differential Privacy" (CDP) to ensure the final published list doesn't leak individual data, users must still trust the server with their raw, unencrypted preferences.

Comparison of Central and Local DP models for rank aggregation.

As awareness of data privacy grows, research is shifting toward Local Differential Privacy (LDP), where the server is assumed to be untrusted. In LDP, users add noise to their own data before it leaves their device. However, ranking data is high-dimensional and complex; if every user adds noise to their entire ranked list, the resulting data becomes too chaotic for the server to extract a useful aggregate ranking. This paper addresses this challenge by focusing on pairwise comparisons.

2. Methodology: The LDP-KwikSort Protocol

Instead of perturbing entire ranking lists, the proposed LDP-KwikSort protocol decomposes rankings into pairwise comparisons (e.g., "Do you prefer Item A over Item B?"). It builds upon KwikSort, an efficient algorithm that only requires pairwise preference counts to function.

The step-by-step workflow of the LDP-KwikSort protocol.

The protocol operates in four primary stages:

  1. Querying: The untrusted curator randomly selects $K$ pairs of items and asks each agent for their preference in each pair.
  2. Local Perturbation: Agents apply an LDP mechanism to their answers. The paper evaluates two variants: LDP-KwikSort:RR (using Randomized Response) and LDP-KwikSort:Lap (using the Laplace Mechanism).
  3. Post-processing: The curator collects noisy answers and uses Maximum Likelihood Estimation to estimate the true crowd preference for every pair.
  4. Aggregation: The curator feeds these estimated preferences into the KwikSort algorithm to generate the final aggregate ranking.

3. Key Insights and Results

The authors evaluated the protocol using real-world datasets (SUSHI, TurkDots) and synthetic data generated via the Mallows model.

The Privacy-Utility Trade-off: In LDP, a user has a total privacy budget ($\epsilon$). If the curator asks $K$ questions, the budget must be split $K$ ways. Asking more questions provides more data but forces the user to add more noise to each answer. The authors proved that the optimal number of questions to ask each user is $K \approx \epsilon / 2$. Asking more than this actually degrades the final result as noise becomes overwhelming.

Mechanism Performance: For binary pairwise questions, the Randomized Response mechanism (LDP-KwikSort:RR) consistently outperformed the Laplace mechanism in preserving the utility of the final ranking. The protocol scales well for smaller sets of items ($m \le 15$); for example, with 5,000 users ranking 10 sushi types, the protocol achieves accuracy very close to non-private baselines.

4. Conclusion

LDP-KwikSort:RR provides an effective solution for rank aggregation without a trusted curator, achieving a strong balance between privacy and utility. While the protocol requires larger user populations as the number of items increases, it represents a significant step forward for private crowdsourced data management. Future work will investigate handling strategic voting and implementing personalized privacy budgets.

Summary updated

Abstract

As a method for answer aggregation in crowdsourced data management, rank aggregation aims to combine different agents' answers or preferences over the given alternatives into an aggregate ranking which agrees the most with the preferences. However, since the aggregation procedure relies on a data curator, the privacy within the agents' preference data could be compromised when the curator is untrusted. Existing works that guarantee differential privacy in rank aggregation all assume that the data curator is trusted. In this paper, we formulate and address the problem of locally differentially private rank aggregation, in which the agents have no trust in the data curator. By leveraging the approximate rank aggregation algorithm KwikSort, the Randomized Response mechanism, and the Laplace mechanism, we propose an effective and efficient protocol LDP-KwikSort. Theoretical and empirical results show that the solution LDP-KwikSort:RR can achieve the acceptable trade-off between the utility of aggregate ranking and the privacy protection of agents' pairwise preferences.
BibTeX
@article{yan2020private,
  author = {Ziqi Yan and Gang Li and Jiqiang Liu},
  title = {{Private Rank Aggregation under Local Differential Privacy}},
  journal = {Int. J. Intell. Syst.},
  year = {2020},
  url = {https://openreview.net/forum?id=pkBk8WrNsGC},
}
Figure