{"id":"9e371b9e-70cd-4aed-acb8-e080b0c701e5","arxiv_id":"1908.04486","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"LDP-KwikSort:RR provides locally differentially private rank aggregation, with an error bound under Mallows data and the best empirical utility when each agent answers about half the privacy budget in pairwise queries.","lead":"LDP-KwikSort lets a server combine many people's ranked preferences into one aggregate ranking while each person's full ordering stays private, because people answer only a few noisy pairwise comparisons. The randomized-response version kept more accuracy than a Laplace-noise version and worked with an untrusted server, which matters for crowdsourcing platforms that collect sensitive preferences.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 as printed does not implement randomized response; reports are independent of the agent's true answer, so Theorem 2's utility bound does not apply to the described protocol.","rationale":"The reader's conditional verdict and missing-pair critique are reasonable, but the most load-bearing problem is a different protocol-versus-analysis mismatch. The pseudocode in Algorithm 1 is internally inconsistent with the proof of Theorem 2 and with the surrounding text: it omits the dependence on the agent's true pairwise answer, converting randomized response into a data-independent Bernoulli mechanism. If taken literally, the estimated comparison profile is pure noise, the sign-error probability is 1/2, and the claimed error bound collapses. This concern is independent of the coverage/missingness issue raised by the reader, so I mark partial agreement. The paper does have independent value: the privacy theorem is straightforward and the general architecture is coherent, and the missing-pair concern is also worth addressing. However, since the central utility theorem is stated for a protocol that the printed Algorithm 1 does not describe, the manuscript should be accepted only after the pseudocode is corrected to the intended RR rule and the theoretical/empirical results are re-verified against that corrected protocol.","tokens_in":21110,"tokens_out":6185,"duration_ms":64907,"concrete_test":"Run the paper's Mallows synthetic experiment (e.g., n=5000, m=10, θ=0.5 or 0.75, ϵ=1.0 and 2.0, K chosen near ϵ/2) implementing Algorithm 1 exactly as printed: for each query draw g uniform and output 1 if g≤p_rr else 0, never reading oik. Compute the error rate (Eq. 4) and average normalized Kendall tau over 30 trials. If error rate stays near 0.5 and Kendall tau near the random-ranking baseline, while the corrected RR version (output oik with probability p_rr and 1−oik otherwise) reproduces the paper's Figure 5 trend, the utility theorem applies only to the corrected randomizer, not to the algorithm as written.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Algorithm 1 (Local Perturbation in LDP-KwikSort:RR) draws g uniformly from [0,1] for each query and sets ~oik←1 if g≤p_rr else ~oik←0. The agent's true answer oik never appears. Thus the reported bit is Bernoulli(p_rr) regardless of the preference. Theorem 2's proof instead assumes randomized response: 'each agent reports his/her true answer ... with probability p_rr ... and false ... with probability q_rr', giving p=p_M·p_rr+q_M·q_rr for agreement with the ground truth. Under the literal algorithm, p=p_rr independent of p_M, so p−q=0, Eq. (3)'s exponent is 0, P_ι≈1/2, and the pairwise sign error is at best random. Since KwikSort uses only the signs of cmp_L, the aggregate ranking is no better than random, regardless of K or n. This is more basic than the missing-pair gap: it invalidates the utility theorem even if every pair were answered by exactly n*=nK/C(m,2) agents. The privacy claim still holds because output independent of data is private, but the central utility claim does not.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces LDP-KwikSort, a protocol for rank aggregation under local differential privacy. The curator asks each agent K pairwise comparison queries; the agent perturbs each answer with randomized response (RR) or Laplace noise, and the curator estimates the aggregate pairwise comparison profile and runs the KwikSort algorithm to produce a ranking. The main theoretical claims are Theorem 1 (ε-LDP for the RR instantiation and ε-LiDP for the Laplace instantiation), Theorem 2 (a utility bound for LDP-KwikSort:RR under the Mallows model, with error below 6μ with high probability, where μ is minimized near K = ε/2), and Theorem 3 (an analogous bound for LDP-KwikSort:Lap). The paper also reports experiments on three real-world datasets and Mallows-generated synthetic data, comparing against non-private KwikSort and the central-model DP-KwikSort.","tokens_in":21366,"tokens_out":9184,"duration_ms":95626,"significance":"If the central claims were fully supported, the paper would make a useful contribution: it is, to my knowledge, the first to formulate rank aggregation under the local model of differential privacy, and the idea of leveraging KwikSort to reduce the number of pairwise queries per agent is natural and relevant. The privacy guarantee for the Laplace variant is standard and sound, and the experiments on real crowdsourcing datasets are a strength. However, the utility analysis as written does not apply to the RR algorithm actually specified, because that algorithm ignores the agent's true answer; the utility theorem also relies on assumptions about response counts and independence that the protocol does not satisfy. These issues are load-bearing rather than cosmetic.","major_comments":[{"comment":"Algorithm 1 as printed does not implement randomized response. In lines 2–8, the agent draws g uniformly from [0,1] and sets the reported bit to 1 if g ≤ p_rr and to 0 otherwise; the true answer o_ik never appears. Thus the reported bit is Bernoulli(p_rr) independent of the agent's preference. The proof of Theorem 2, however, assumes that each agent reports the true answer with probability p_rr and the false answer with probability q_rr, leading to p = p_M p_rr + q_M q_rr for agreement with the ground truth. Under the literal algorithm, p = p_rr, so p − q = 0, the exponent in Eq. (3) is zero, P_ι ≈ 1/2, and the sign of the estimated comparison is no better than random for every pair. Consequently, the utility guarantee of Theorem 2 does not hold for the described protocol, and K ≈ ε/2 as an optimal query count is unsupported by that argument. The privacy claim remains true because a data-independent output is private, but the central utility claim fails even if every pair were answered by exactly n* = nK/C(m,2) agents.","section":"Section 4.3, Algorithm 1; Theorem 2 and Eq. (3)"},{"comment":"The utility proof assumes that for each pair (a_j, a_l) there are exactly n* = nK/C(m,2) respondents and that the noisy per-pair counts are independent Bernoulli variables. The protocol in Section 4.2 and Algorithm 2 has each agent answer K randomly selected pairs, so the number of respondents per pair is random and can be zero; pairs with no respondents have ~C_{a_j a_l} = ~C_{a_l a_j} = 0, which corresponds to an effectively random sign. Moreover, if one agent answers several pairs, the resulting pairwise error indicators X_ι are correlated, so the Chernoff bound in Lemma 2, which requires independent Poisson trials, cannot be applied as written. These are first-order effects, not approximation artifacts: for large m or small n, a substantial fraction of pairs will receive no answers. The theorem must either analyze the actual random assignment of pairs to agents or explicitly state and justify a design in which every pair receives n* responses that are independent across pairs.","section":"Section 5.2.1, Theorem 2 proof and Algorithm 2"},{"comment":"The paper defines p_M as a single constant such that for every pair (a_j, a_l), the relative order of the pair agrees with the ground truth with probability p_M and disagrees with probability q_M = 1 − p_M, with θ = 1 − q_M/p_M. This is not a property of the standard Mallows model cited as [35]. In the Mallows model with Kendall-tau distance, the marginal probability that a given item precedes another item in the generated ranking is not constant across pairs; for example, for m = 3 and θ = 0.5 the probability that item 1 precedes item 2 differs from the probability that item 1 precedes item 3. Consequently, the expression for P_ι in Eq. (3) is not a valid per-pair error probability for all pairs under the Mallows model, and the subsequent bound μ = Σ P_ι ≤ 2(m choose 2) exp(...) requires an argument that either uses pair-specific probabilities and takes a maximum or justifies a different model. This issue affects the formal content of Theorem 2 and, through it, the theoretical rationale for the recommended choice K ≈ ε/2.","section":"Section 5.2.1, Mallows model definition"}],"minor_comments":[{"comment":"The displayed ratio for the RR mechanism is written as 2 p_rr / (1 − p_rr) = e^{ε_k}; for standard randomized response the correct ratio is p_rr / (1 − p_rr) = e^{ε_k}. The theorem statement is unaffected, but the proof as written is algebraically incorrect.","section":"Section 5.1, Theorem 1 proof"},{"comment":"The pseudocode does not record which pair each ~o_ik refers to; the classification loop increments ~C_{a_j a_l}(L) or ~C_{a_l a_j}(L) without specifying a mechanism for mapping the query index k to the pair (a_j, a_l). This is an implementation detail, but it should be made explicit because the protocol uses different random pairs for different agents.","section":"Algorithm 2"},{"comment":"The text says DP-KwikSort is “based on the local model of DP,” but Section 6.1.1 and the central-model definition state that DP-KwikSort is a central-model algorithm. This appears to be a typographical error and should be corrected.","section":"Section 6.3"},{"comment":"The Chernoff bound is stated for R ≥ 6μ, but the theorem applies it with R = 6μ; if R must be an integer, this requires a short justification or a ceiling on R. This is minor relative to the issues above but should be cleaned up.","section":"Lemma 2 usage"}],"recommendation":"major_revision","confidential_remarks":"The algorithm-vs-theorem mismatch in Section 4.3 is the kind of issue that could be a simple pseudocode typo, but as submitted it invalidates the main utility theorem. The authors should be asked to correct Algorithm 1 to use the true answer in the randomized response step, to re-derive the utility analysis under the actual random-pair assignment, and to reconcile the Mallows-model pairwise probability assumption. If the empirical results were obtained with a different (correct) implementation, that should be stated explicitly. These are substantive but fixable issues, so major revision rather than rejection seems appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The punchline: this paper is the first to formulate rank aggregation under local differential privacy, and the overall architecture is reasonable. But the version on arXiv has a bug at the center: Algorithm 1's 'randomized response' randomizer does not read the agent's true answer. It draws g ~ U[0,1] and sets the report to 1 if g ≤ p_rr, else 0, independent of oik. Privacy then holds trivially, but Theorem 2 is proved under standard RR, where the true answer is reported with probability p_rr. For the literal algorithm the signal p - q is zero, the exponent in the bound disappears, and the pairwise comparison is at chance level. This is not a footnote; it invalidates the main utility guarantee as written.\n\nWhat's good: the problem is new, the choice of KwikSort as a base is natural, the privacy composition argument is standard and correct if the randomizer is what the prose says it is, and the experiments cover both real and synthetic data with a sensible query-selection heuristic. The related-work review is honest and correctly identifies the empty niche. Those deserve credit.\n\nThe soft spots, in order of severity. First, the bug above. Second, Theorem 2 assumes exactly n* = nK/C(m,2) responses per pair, but the protocol samples K random pairs per agent, so for large m or small n most pairs get zero responses. The proof never confronts missingness or the dependence from one agent answering multiple pairs. Third, experiments report means over 30 runs without error bars, and the 'error rate' is about pairwise sign errors, not final ranking quality. Minor: the 'approximately K = epsilon/2' claim is only approximate for small non-integer epsilon.\n\nBottom line: the paper deserves a serious look because the problem and framework are useful, but the current text cannot be accepted as is. A fix to Algorithm 1 (report true answer with prob p_rr, opposite with prob 1 - p_rr) and a utility analysis that actually tracks the random sampling of pairs would address the core. I'd recommend the authors do that revision and then resubmit; my own verdict is skeptical until then.","headline":"First local-DP rank aggregation paper, but Algorithm 1 as printed never uses the agent's true answer, so the main utility theorem doesn't apply to it; fixable but load-bearing.","tokens_in":21834,"tokens_out":4427,"would_cite":false,"duration_ms":42755,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims rank aggregation can be made locally differentially private without a trusted curator, with randomized pairwise answers and a provable error bound.","keywords":["local differential privacy","rank aggregation","KwikSort","randomized response","Laplace mechanism","Mallows model","pairwise comparisons","Kendall tau distance"],"falsifier":"Run LDP-KwikSort:RR on Mallows-generated rankings with $m=45$ alternatives, $n=5000$ agents, $\\epsilon=2$, and $K=1$, and record the fraction of pairs $(a_j, a_l)$ with zero respondents and the empirical sign-error rate of $\\widehat{\\mathrm{cmp}}(L)$. If the fraction of unqueried pairs is substantial while the Theorem 2 bound predicts error below $6\\mu$ with probability $1-2^{-6\\mu}$, then the bound and protocol disagree in a way that would falsify the utility guarantee as stated.","tokens_in":20902,"feed_emoji":"🔒","tokens_out":5409,"duration_ms":47823,"temperature":0.7,"pith_summary":"Rank aggregation over crowdsourced preferences usually requires a trusted curator who sees everyone's full rankings. This paper claims that the curator can be untrusted: each agent can randomly perturb answers to pairwise comparison queries, and the server can still recover an aggregate ranking with acceptable accuracy. The proposed protocol, LDP-KwikSort, comes in two variants, one built on randomized response and one on the Laplace mechanism, and the randomized-response variant satisfies epsilon-local differential privacy while the Laplace variant satisfies epsilon-local individual differential privacy. The authors prove an error bound under a Mallows model of ranking preferences and show empirically that the randomized-response variant is close to the central-model private baseline while protecting each agent's pairwise preferences.","feed_headline":"Private rank aggregation now works without a trusted curator","feed_subtitle":"A randomized-response protocol keeps per-agent comparisons private while the aggregate ranking stays close to the non-private baseline.","key_machinery":"The machinery is KwikSort, an approximate rank aggregation algorithm that only needs the aggregate pairwise comparison profile $\\mathrm{cmp}(L) = (C_{a_j a_l}(L) - C_{a_l a_j}(L))$ for each pair; the sign of each entry decides the relative order, and KwikSort sorts with a randomized pivot to get an $11/7$-approximation to the Kemeny optimal ranking. LDP-KwikSort perturbs each agent's pairwise answer with either Randomized Response or Laplace noise, then the curator estimates $\\widehat{\\mathrm{cmp}}(L)$ from the noisy counters and feeds it to KwikSort. The Mallows model provides the generative assumption under which the sign of $\\widehat{\\mathrm{cmp}}(L)$ matches $\\mathrm{cmp}(L)$ with high probability, and Hoeffding and Chernoff bounds turn that per-pair probability into the global error bound.","core_discovery":"The paper's central claim is that locally private rank aggregation is feasible: instead of trusting the curator with full rankings, each agent answers K randomly chosen pairwise comparison queries with a locally randomized response. Theorem 1 states that LDP-KwikSort:RR satisfies epsilon-LDP and LDP-KwikSort:Lap satisfies epsilon-LiDP. Theorem 2 states that when rankings come from the Mallows model, the estimate of the aggregate pairwise comparison profile has error below $6\\mu$ with probability at least $1 - 2^{-6\\mu}$, where $\\mu = 2\\binom{m}{2} \\exp\\left(-\\frac{\\epsilon^2 K}{(\\epsilon+2K)^2} \\cdot \\frac{{\\theta^*}^2 n}{m(m-1)}\\right)$ and $\\theta^* = \\frac{\\theta}{2-\\theta}$. The Laplace variant has an analogous bound with a different exponent. The paper further claims that the error is minimized near $K = \\epsilon/2$, and that experiments on real and synthetic data show LDP-KwikSort:RR keeps aggregate ranking utility close to DP-KwikSort and non-private KwikSort.","pith_inferences":["The paper's Theorem 2 assumes every pair is answered by exactly $n^* = nK/\\binom{m}{2}$ independent agents, but Algorithm 1 has each agent answer only $K$ randomly chosen pairs; when $K$ is small relative to $\\binom{m}{2}$, many pairs receive zero answers and the comparison is effectively a coin flip, so the bound may be optimistic in exactly the regime the paper recommends for large $m$ or small ","A direct extension would replace uniform random pair sampling with a covering design or repeated sampling so that every pair is queried at least once, which would make the theorem's assumption match the protocol and likely improve practical accuracy.","The analysis could be tightened by accounting for the correlation among the $K$ answers from the same agent; treating all $nK$ answers as independent likely overstates the effective sample size.","If the missing-data gap is closed, a similar protocol could be applied to other pairwise aggregation problems, such as tournament-style preference elicitation or peer grading, where an untrusted aggregator is the norm."],"forward_implications":["If the protocol works as claimed, crowdsourcing platforms can collect ranking preferences from agents who do not trust the platform, with each agent's pairwise comparisons protected by local differential privacy.","The recommended operating point $K \\approx \\epsilon/2$ follows directly from the analysis, giving practitioners a concrete rule for setting the number of queries per agent.","The randomized-response variant is the better of the two solutions in the experiments, so a practical deployment need not rely on Laplace noise to reach acceptable utility.","Utility improves as the number of agents or the privacy budget grows, and degrades as the number of alternatives grows, matching the intuition that more information outweighs noise.","Because KwikSort only needs pairwise comparisons, the protocol inherits a low per-agent cost of $O(K)$ computation and $O(\\log K)$ communication."],"supporting_citations":[{"why":"Supplies the KwikSort approximate rank-aggregation algorithm and its 11/7 approximation guarantee, which the protocol feeds with estimated pairwise comparisons.","marker":"[2]"},{"why":"Introduces the rank aggregation formulation used to define the comparison-based sorting approach that the protocol builds on.","marker":"[1]"},{"why":"Provides DP-KwikSort, the central-model differentially private baseline that LDP-KwikSort is compared against in the experiments.","marker":"[21]"},{"why":"Provides the randomized response mechanism that LDP-KwikSort:RR uses as its local randomizer.","marker":"[49]"},{"why":"Defines the Mallows ranking model used for the synthetic data and for the utility bound in Theorem 2.","marker":"[35]"},{"why":"Supplies the formal definition of local differential privacy used in Theorem 1.","marker":"[4]"},{"why":"Provides the differential privacy foundation and Laplace mechanism background that the paper builds on.","marker":"[17]"}],"fun_headline_variants":["LDP-KwikSort: local-DP rank aggregation without trusted curator","Randomized response enables private rank aggregation from untrusted curator","LDP-KwikSort: aggregate rankings privately, no trust needed","Local DP for rank aggregation: privacy without curator trust"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every pair of alternatives receives exactly $n^* = nK/\\binom{m}{2}$ independent noisy answers, each with the same probability of being truthful; the actual protocol instead has each agent answer only $K$ random pairs, leaving many pairs unanswered and linking answers within an agent, so the proven error bound does not cover the protocol as run.","fun_headline_variants_meta":{"raw":{"variants":["LDP-KwikSort: local-DP rank aggregation without trusted curator","Randomized response enables private rank aggregation from untrusted curator","LDP-KwikSort: aggregate rankings privately, no trust needed","Local DP for rank aggregation: privacy without curator trust"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001027,"raw_usage":{"total_tokens":4317,"prompt_tokens":925,"completion_tokens":3392,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":541,"completion_tokens_details":{"reasoning_tokens":3321}},"tokens_in":541,"tokens_out":3392,"duration_ms":23007,"temperature":1.0,"reasoning_tokens":3321,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:41:58.818209+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run LDP-KwikSort:RR on Mallows-generated rankings with $m=45$ alternatives, $n=5000$ agents, $\\epsilon=2$, and $K=1$, and record the fraction of pairs $(a_j, a_l)$ with zero respondents and the empirical sign-error rate of $\\widehat{\\mathrm{cmp}}(L)$. If the fraction of unqueried pairs is substantial while the Theorem 2 bound predicts error below $6\\mu$ with probability $1-2^{-6\\mu}$, then the bound and protocol disagree in a way that would falsify the utility guarantee as stated.","supporting_citations":[{"cited_title":"Aggregating inconsistent information: ranking and clustering","cited_arxiv_id":null,"evidence_quote":"Introduces the rank aggregation formulation used to define the comparison-based sorting approach that the protocol builds on."},{"cited_title":"Differentially private rank aggregation","cited_arxiv_id":null,"evidence_quote":"Provides DP-KwikSort, the central-model differentially private baseline that LDP-KwikSort is compared against in the experiments."},{"cited_title":"Non-null ranking models","cited_arxiv_id":null,"evidence_quote":"Defines the Mallows ranking model used for the synthetic data and for the utility bound in Theorem 2."},{"cited_title":"Practical locally private heavy hitters","cited_arxiv_id":null,"evidence_quote":"Supplies the formal definition of local differential privacy used in Theorem 1."},{"cited_title":"The algorithmic foundations of differential privacy.Foundations and Trends in Theoretical Computer Science , 9(3-4):211–407, 2014","cited_arxiv_id":null,"evidence_quote":"Provides the differential privacy foundation and Laplace mechanism background that the paper builds on."}],"review_version":1}