# Rate-Optimal Rank Aggregation with Private Pairwise Rankings

arXiv: https://arxiv.org/abs/2402.16792 · HTML: https://mlsanity.com/paper/2402.16792/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 51 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## Builds on (most cited first, 15 of 15)

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [The Application of Differential Privacy for Rank Aggregation: Privacy and Accuracy](https://mlsanity.com/paper/1409.6831/) (2014)
- [Distribution-Invariant Differential Privacy](https://mlsanity.com/paper/2111.05791/) (2021)
- [Private Rank Aggregation under Local Differential Privacy](https://mlsanity.com/paper/1908.04486/) (2019)
- [Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method](https://mlsanity.com/paper/2109.13743/) (2021)
- [Robust Estimation of Discrete Distributions under Local Differential Privacy](https://mlsanity.com/paper/2202.06825/) (2022)
- [Adversarial Top-K Ranking](https://mlsanity.com/paper/1602.04567/) (2016)
- [Private Rank Aggregation in Central and Local Models](https://mlsanity.com/paper/2112.14652/) (2021)

## Built on by (most cited first, 1 of 1)

- [Privacy-Preserving Dynamic Assortment Selection](https://mlsanity.com/paper/2410.22488/) (2024)

## Abstract (arXiv)

In various real-world scenarios, such as recommender systems and political surveys, pairwise rankings are commonly collected and utilized for rank aggregation to derive an overall ranking of items. However, preference rankings can reveal individuals' personal preferences, highlighting the need to protect them from exposure in downstream analysis. In this paper, we address the challenge of preserving privacy while ensuring the utility of rank aggregation based on pairwise rankings generated from a general comparison model. A common privacy protection strategy in practice is the use of the randomized response mechanism to perturb raw pairwise rankings. However, a critical challenge arises because the privatized rankings no longer adhere to the original model, resulting in significant bias in downstream rank aggregation tasks. To address this, we propose an adaptive debiasing method for rankings from the randomized response mechanism, ensuring consistent estimation of true preferences and enhancing the utility of downstream rank aggregation. Theoretically, we provide insights into the relationship between overall privacy guarantees and estimation errors in private ranking data, and establish minimax rates for estimation errors. This enables the determination of optimal privacy guarantees that balance consistency in rank aggregation with privacy protection. We also investigate convergence rates of expected ranking errors for partial and full ranking recovery, quantifying how privacy protection affects the specification of top-K item sets and complete rankings. Our findings are validated through extensive simulations and a real-world application.