{"id":"651ffa56-e0de-4d7e-b3a3-5ce917266e2e","arxiv_id":"1908.04920","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"New local differential privacy mechanisms for vote aggregation reduce estimation error and bound manipulation risk, improving on Laplace noise for Borda counting.","lead":"This paper designs privacy-preserving ways to combine people's ranked votes so that the random noise added for privacy cannot be exploited by attackers to skew the outcome. It introduces two mechanisms, weighted sampling and an additive subset response, that claim lower estimation error and bounded manipulation risk compared to standard Laplace noise.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Additive mechanism's recursive sampler, as printed, does not implement Definition 6.1; implementation and experiments are unsupported.","rationale":"The reader's conditional verdict is appropriate, but the most load-bearing concern is not the output-domain validation assumption. The additive mechanism's theoretical soundness and usefulness bounds for k=1 appear correct, and the support-validation issue is a standard assumption that can be met by checking membership in the finite output set. The sharper, verifiable problem is that Algorithm 4, as printed, does not sample from the additive distribution for k>1. A small enumeration test demonstrates the mismatch for d=3, k=2. This does not invalidate the k=1 theoretical claims, so the verdict remains conditional rather than reject; however, the paper must either correct the p_j formula, supply a correctness proof, or state that the additive mechanism is only implemented for k=1. The reader's listed issues (k=1 near-optimality, missing recursive algorithm proof, synthetic-only experiments) are real but secondary; the recursive sampler flaw is concrete and directly testable, making it the single most load-bearing concern for the paper's implementation and experimental claims.","tokens_in":30562,"tokens_out":46186,"duration_ms":412228,"concrete_test":"Implement Definition 6.1 by exhaustive enumeration and Algorithm 4 exactly as printed for d=3, k=2 with Borda weights and e^ε=2.718; compare the induced distributions over 2-subsets. If the printed algorithm yields (0.579, 0.396, 0.025) instead of (0.487, 0.333, 0.179), the sampler is wrong. Then rerun the additive mechanism experiments using either direct enumeration for the chosen k or a corrected recursive sampler, and report whether the claimed 50% error reduction and soundness improvements persist.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical bounds for the additive mechanism are proved for the distribution in Definition 6.1, but the paper also claims an O(d·k) implementation via Algorithm 3/4 (Appendix 10.6). As typeset, Algorithm 4's p_j formula is incorrect for k>1. For d=3, k=2, Borda weights w=[2,1,0], and e^ε=2.718, Definition 6.1 gives subset probabilities (0.487, 0.333, 0.179) for subsets {1,2}, {1,3}, {2,3}. Using z_j from Algorithm 3 and the printed p_j formula yields p_1=s, p_2=z_3, and output probabilities (0.579, 0.396, 0.025). The correct p_j for sampling subsets with probability proportional to the sum of their z_j is C(d-j,k-1)z_j + C(d-j-1,k-2)Σ_{j'>j}z_{j'}; the printed formula subtracts an extra z_j. Thus, for general k, the recursive algorithm does not sample from the additive mechanism. This is load-bearing because the paper presents the additive mechanism as an implementable polynomial-time construction and validates it experimentally; if the sampler is wrong, the experimental results and the O(d·k) complexity claim do not correspond to the analyzed mechanism. The k=1 theoretical analysis is unaffected, so the headline theoretical comparison stands, but the practical and experimental claims require repair.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies local differential privacy for aggregate vote reporting under positional voting rules. It introduces two attack notions (data amplification and view disguise), defines usefulness and soundness metrics, analyzes the Laplace mechanism, and proposes two mechanisms: a weighted sampling mechanism and an additive subset-sampling mechanism. The central claims are that, for Borda voting with d candidates, the weighted sampling mechanism halves the mean squared error bound relative to Laplace and reduces the maximum-magnitude risk from +∞ to O(d^3/(nε)), while the additive mechanism improves the MSE bound from O(d^5/(nε^2)) to O(d^4/(nε^2)) and gives finite O(d^2/(nε)) manipulation risk bounds. Theoretical proofs are given for LDP and unbiasedness of both mechanisms, and synthetic experiments are reported for Borda and Nauru rules.","tokens_in":30823,"tokens_out":10764,"duration_ms":108344,"significance":"If the claims hold, the paper makes a useful contribution to local private data aggregation: it identifies a soundness dimension that is usually ignored, proposes concrete mechanisms with closed-form, parameter-derived MSE and risk bounds, and demonstrates that finite-support mechanisms can dominate the Laplace baseline on both usefulness and soundness. Strengths include the explicit attack definitions, the exact sensitivity bound in Lemma 4.1, the closed-form parameter optimization in Theorem 5.4, and the fact that the theoretical comparisons are not fitted to experimental data. However, the additive mechanism's usefulness claim rests on the unproved near-optimality of k=1, and, more importantly, the printed recursive sampler does not sample from the distribution in Definition 6.1 for k>1, so the implementation and experimental validation of the additive mechanism are currently unsupported. The theoretical k=1 analysis remains defensible and the conceptual contribution is significant, but the practical claims need substantial repair.","major_comments":[{"comment":"The recursive sampler does not implement Definition 6.1 for k>1. Definition 6.1 requires sampling each size-k subset T with probability proportional to z(T)=Σ_{j∈T} z_j, so Pr[min(T)=j] should be C(d-j,k-1) z_j + C(d-j-1,k-2) Σ_{j'>j} z_{j'} up to normalization. Algorithm 4 line 3 instead computes p_j = C(d-j,k-1)(z_j + (Σ_{j'>j} z_{j'} − z_j)(k−1)/(d−j)), which subtracts z_j inside the parenthesized term. For d=3, k=2, e^ε=2.718, and Borda weights w=[2,1,0], Definition 6.1 gives subset probabilities (0.487, 0.333, 0.179) for subsets {1,2}, {1,3}, {2,3}, whereas Algorithm 4 produces (0.579, 0.396, 0.025). Thus the O(d·k) implementation claimed in §6.1 and the experimental results in §8 for the additive mechanism do not correspond to the mechanism whose bounds are proved in Theorems 6.2–6.5. The authors need to correct Algorithm 4, provide a correctness proof that it samples from Definition 6.1, and re-run the affected experiments.","section":"§6.1 / Appendix 10.6, Algorithm 4"},{"comment":"The theorem is stated as a general bound for the additive mechanism, but the proof analyzes only the case k=1, and the claim that 'k=1 is near to optimal for many voting rules except extremal cases' is asserted without proof. Since the headline O(d^4/(nε^2)) MSE improvement for the additive mechanism depends on k=1 being near-optimal, the authors should either prove this claim under explicit conditions on the score vector w, or restrict the usefulness theorem to k=1 and state clearly that the general parameter-k bound is not established.","section":"§6.2, Theorem 6.4"},{"comment":"The finite riskMM and riskDD guarantees for the proposed mechanisms are defined with respect to the output domain D_{\\tilde v}, but the paper does not specify how the aggregator verifies that a submitted vector belongs to the finite support of the mechanism. For the additive mechanism the support is the set of vectors with exactly k entries equal to a_k−b_k and d−k entries equal to −b_k; for the weighted sampling mechanism the support is also finite. If an adversary may submit an arbitrary real vector and the aggregator does not check support membership, then both the maximum magnitude and the domain diameter for these mechanisms are unbounded, and the claimed finite O(d^3/(nε)) and O(d^2/(nε)) improvements over the Laplace mechanism are not realized. The paper should specify the validation procedure, analyze its cost and false-rejection rate, or explicitly state a threat model in which the aggregator can authenticate genuine mechanism outputs.","section":"§3.4 / §6.3, Theorem 6.5"}],"minor_comments":[{"comment":"The text says 'the Laplace mechanism in Algorithm 2' but these statements concern the weighted sampling mechanism; please correct the naming for clarity.","section":"§5.2, Lemma 5.3 and Theorem 5.4"},{"comment":"The proof writes riskMM = |ak−bk|+(d−1)|bk|, while the theorem statement correctly has k|ak−bk|+(d−k)|bk|; the displayed proof should match the statement.","section":"§6.3, Theorem 6.5 proof"},{"comment":"The normalizer Φ is garbled as typeset and appears to contain an extraneous factor n and ambiguous parentheses; please rewrite the definition in a form that can be checked directly against the normalization used in the proof of Theorem 6.2.","section":"Definition 6.1"},{"comment":"The 'Naive Sampling' baseline is compared in several figures but has no pseudo-code and no formal statement of its privacy or unbiasedness properties, and no code or data are provided for the synthetic experiments; this makes the experimental comparison difficult to reproduce.","section":"§8, Experiments"}],"recommendation":"major_revision","confidential_remarks":"The core theoretical comparison for k=1 appears internally consistent, and I do not see a circularity problem in the error and risk derivations. The main obstacle is that the additive mechanism's only described implementation is incorrect for k>1, which invalidates the experimental validation as currently presented and the O(d·k) implementation claim. Given the correct recursive sampling formula is a local fix and the k=1 theoretical story survives, this is best handled as a major revision rather than a rejection. The authors should also be asked to disclose code or detailed pseudorandom seeds for reproducibility, and to tighten the threat model around support verification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real mechanism-design paper with a mostly correct theoretical core, but the efficient sampler for the additive mechanism is wrong as printed, so the implementation and experimental claims need repair. The k=1 analysis survives, which keeps the headline comparison intact.\n\nWhat's new: the weighted-sampling-with-intercept mechanism and the additive (subset-sampling) mechanism are genuinely new relative to the Laplace baseline and the naive |v|/|v|_1 sampling. The attack taxonomy (data amplification vs view disguise) is a useful way to organize soundness concerns in LDP aggregation. The LDP and unbiasedness proofs for the two mechanisms as defined appear internally consistent, and the MSE and risk bounds are derived from the definitions rather than fitted to data. Prior-work citations are used as baselines, not as load-bearing premises. That's worth crediting.\n\nWhere it's soft:\n\n1. The stress-test is right. Algorithm 4's p_j formula is incorrect for k>1. For d=3, k=2, Borda weights [2,1,0], e^ε≈2.718, Definition 6.1 gives subset probabilities (0.487,0.333,0.179), while the printed formula gives (0.579,0.396,0.025). The correct p_j is C(d-j,k-1) z_j + C(d-j-1,k-2) Σ_{j'>j} z_{j'}; the printed version effectively subtracts an extra z_j. So the O(d·k) sampler does not sample from the additive mechanism. If the experiments used k>1, they tested a different procedure. Since the paper recommends k=1 for Borda and Theorem 6.4's analysis is k=1, the theoretical comparison still stands, but the practical claim requires either a corrected sampler or a k=1-only claim.\n\n2. Theorem 6.4 asserts k=1 is near-optimal without proof. Given that the usefulness proof only covers k=1, the paper needs to either prove this or soften the claim. This is a real gap, though not a fatal one.\n\n3. The soundness guarantees rely on the adversary's inputs lying in the mechanism's output support D_{\\tilde v}. The paper never says how an aggregator verifies support membership for the finite mechanisms, nor the false-rejection cost. Without that, a malicious client sending arbitrary real vectors breaks the finite risk bounds. This should be stated and justified, not left implicit.\n\n4. Experiments are synthetic-only, with no code or data. That's less serious than the above, but it does mean the 50% error-reduction claim is unverifiable from the paper alone.\n\nWho it's for: people working on LDP mechanisms for preference or ranking aggregation. It deserves a serious referee; I'd accept it for review and push for major revision rather than desk reject. If the sampler is fixed and the k=1 claim is made precise, this becomes a solid within-subfield contribution.","headline":"Real mechanism-design contribution with a mostly sound theory, but the additive sampler is buggy as printed; referee it and demand a fix.","tokens_in":31393,"tokens_out":4728,"would_cite":true,"duration_ms":40684,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","91B12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Local differential privacy can make vote aggregation both more accurate and harder to manipulate than Laplace noise does.","keywords":["local differential privacy","vote aggregation","Borda voting","soundness","data amplification attack","view disguise attack","weighted sampling","additive mechanism"],"falsifier":"Submit an out-of-support vector, say a single private view with one entry equal to $10^6$, into the proposed mechanisms' aggregation without any filter; if the estimated average scores shift by more than the proved $O(d^3/(n\\epsilon))$ or $O(d^2/(n\\epsilon))$ maximum-magnitude bound, the guarantee as stated fails. A concrete experiment would measure realised $\\mathrm{risk}_{\\mathrm{MM}}$ under such submissions and compare it with the proved bound.","tokens_in":30348,"feed_emoji":"🗳️","tokens_out":6433,"duration_ms":59340,"temperature":0.7,"pith_summary":"This paper tackles a gap in local differential privacy for voting: the standard Laplace-noise approach protects privacy but makes the aggregated scores fragile to two attacks. In a data amplification attack, an adversary's fraudulent vote has its effect on the average scores magnified because the privacy noise gives private views unbounded magnitude; in a view disguise attack, an adversary sends a crafted vector that looks like a legitimate randomised view and can shift the outcome arbitrarily. The paper formalises these attacks with three risk metrics and then proposes two mechanisms, weighted sampling and additive, whose outputs lie in a bounded domain. It proves that for Borda voting with $d$ candidates the weighted sampling mechanism cuts the mean squared error bound in half and shrinks maximum manipulation risk from infinity to $O(d^3/(n\\epsilon))$, while the additive mechanism improves the error bound from $O(d^5/(n\\epsilon^2))$ to $O(d^4/(n\\epsilon^2))$ and bounds expected and maximum risk by $O(d^2/(n\\epsilon))$. If these claims hold, privacy-preserving vote aggregation can be both more accurate and more robust to manipulation than the naive baseline.","feed_headline":"Two mechanisms cut vote-poll error and cap manipulation risk","feed_subtitle":"For Borda voting, replacing Laplace noise with bounded sampling turns infinite manipulation risk into finite bounds and improves error…","key_machinery":"The machinery is the conversion of a numerical scored vote into a bounded random object before aggregation. In the weighted sampling mechanism, a rank $j^*$ is sampled with mass $m_j$, the selected candidate's indicator undergoes binary randomised response, and the result is rescaled by $\\frac{\\sqrt{e^\\epsilon}+1}{\\sqrt{e^\\epsilon}-1}\\cdot\\frac{w_{j^*}-c}{m_{j^*}}+c$ to stay unbiased; the intercept $c$ and masses $m_j$ are chosen to minimise $\\sum_j (w_j-c)^2/m_j$, giving the median-based bound. In the additive mechanism, a subset $S$ of size $k$ is output with probability proportional to the sum of scores in $S$ minus the minimum subset score, and the private view is $a_k[C_j\\in S]-b_k$ with coefficients chosen for unbiasedness. The soundness metrics are the maximum and expected $\\ell^1$ magnitude of a single private view divided by $n$, and the $\\ell^1$ diameter of the output domain; the finite supports of the two new mechanisms are what make these quantities finite and small.","core_discovery":"The paper's central claim is that usefulness and soundness are not opposed in local private vote aggregation: replacing unbounded additive noise with bounded sampling-based output improves both at once. The Laplace mechanism has infinite maximum magnitude risk and infinite output-domain diameter; the proposed mechanisms replace the continuous unbounded output with a finite support, and the paper proves that the worst-case effect of one manipulated view becomes finite and explicit. The weighted sampling mechanism interprets the scored vote as probabilistic data, samples a rank with probability proportional to its shifted weight, and applies binary randomised response to that rank. The additive mechanism samples a subset of candidates with probability linear in the subset's total score, which is a specialised weighted random sampling problem solved by a recursive $O(d\\cdot k)$ algorithm. For Borda counts, the proven mean squared error bounds are $O(d^5/(n\\epsilon^2))$ for weighted sampling and $O(d^4/(n\\epsilon^2))$ for additive, with maximum magnitude risks $O(d^3/(n\\epsilon))$ and $O(d^2/(n\\epsilon))$, respectively, instead of the Laplace mechanism's infinity.","pith_inferences":["The paper leaves open how an aggregator verifies that a submitted vector lies in the mechanism's finite output support; a natural extension is to design cheap, non-interactive support proofs or signed outputs and to measure their cost and false-rejection rate.","The same sampling-plus-randomised-response template should transfer to other aggregation tasks with bounded score vectors, such as quality scoring or recommendation aggregation, where the finite-support property would give bounded manipulation risk by the same argument.","One could test the additive mechanism against an optimal adversary who knows the aggregator's filter threshold; the paper's experiments use a confidence-interval filter for Laplace, so an explicit comparison of best-response attacks across mechanisms would sharpen the soundness claims."],"forward_implications":["For Borda voting, the mean squared error of the estimated average score drops from $O(d^5/(n\\epsilon^2))$ under Laplace to $O(d^4/(n\\epsilon^2))$ under the additive mechanism, a factor of $d$ improvement in candidate-count scaling.","Maximum manipulation risk under data amplification becomes finite: $O(d^3/(n\\epsilon))$ for weighted sampling and $O(d^2/(n\\epsilon))$ for additive, instead of infinity for Laplace, so a single fraudulent vote has a bounded worst-case effect on averaged scores.","The additive mechanism's maximum and expected magnitude risks coincide, meaning its worst-case and average manipulation power are the same; the paper notes Laplace and weighted sampling do not share this property.","The relation $\\mathrm{risk}_{\\mathrm{EM}} \\le (\\sqrt{d\\cdot n\\cdot \\mathrm{err}_{\\mathrm{MSE}}}+\\sum_j |w_j|)/n$ implies that a mechanism with good usefulness usually also has good soundness, so the two goals are complementary rather than opposed.","Experiments on Borda and Nauru rules with $d$ from 4 to 32 and $n$ up to 1,000,000 report about 50% average estimation-error reduction and improved robustness to adversarial votes or views at fractions from 0.1% to 5%.","The negative result that hard $\\mathrm{risk}_{\\mathrm{DD}}$ constraints can make unbiased $\\epsilon$-LDP mechanisms nonexistent suggests a follow-up: relax unbiasedness slightly and quantify the resulting usefulness-soundness Pareto frontier."],"supporting_citations":[{"why":"Supplies the Laplace mechanism baseline whose usefulness and soundness bounds the paper quantifies and improves upon.","marker":"[24]"},{"why":"Provides the binary randomised response sub-routine and proof template used inside the weighted sampling mechanism.","marker":"[31]"},{"why":"Gives the local privacy model and lower-bound framework that motivates the usefulness analysis.","marker":"[20]"},{"why":"Supplies the categorical estimation techniques adapted for the sampled rank in the weighted sampling mechanism.","marker":"[41]"},{"why":"Supplies the sampling-then-randomised-response paradigm for set-valued data that the weighted sampling mechanism extends.","marker":"[58]"},{"why":"Supplies the weighted reservoir sampling problem that the additive mechanism's recursive algorithm solves.","marker":"[28]"},{"why":"Provides the exponential-mechanism template from which the additive mechanism's probability design is adapted.","marker":"[51]"},{"why":"Grounds the contrast between bounded/local and unbounded differential privacy that explains the soundness gap.","marker":"[45]"}],"fun_headline_variants":["Bounded noise fixes vote privacy: error down 50%, risk finite","Private voting: sampling instead of Laplace cuts error, caps attacks","Two new mechanisms for local-DP voting: less error, no infinite risk","Replace Laplace with sampling: vote accuracy up, manipulation risk bounded"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The soundness theorems assume the adversary can only submit private views inside the mechanism's output domain $D_{\\tilde v}$; the paper does not specify how an aggregator verifies that a submitted vector belongs to that finite support.","fun_headline_variants_meta":{"raw":{"variants":["Bounded noise fixes vote privacy: error down 50%, risk finite","Private voting: sampling instead of Laplace cuts error, caps attacks","Two new mechanisms for local-DP voting: less error, no infinite risk","Replace Laplace with sampling: vote accuracy up, manipulation risk bounded"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000206,"raw_usage":{"total_tokens":1473,"prompt_tokens":1100,"completion_tokens":373,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":716,"completion_tokens_details":{"reasoning_tokens":297}},"tokens_in":716,"tokens_out":373,"duration_ms":4605,"temperature":1.0,"reasoning_tokens":297,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:30:40.390208+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Submit an out-of-support vector, say a single private view with one entry equal to $10^6$, into the proposed mechanisms' aggregation without any filter; if the estimated average scores shift by more than the proved $O(d^3/(n\\epsilon))$ or $O(d^2/(n\\epsilon))$ maximum-magnitude bound, the guarantee as stated fails. A concrete experiment would measure realised $\\mathrm{risk}_{\\mathrm{MM}}$ under such submissions and compare it with the proved bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the binary randomised response sub-routine and proof template used inside the weighted sampling mechanism."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the local privacy model and lower-bound framework that motivates the usefulness analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the categorical estimation techniques adapted for the sampled rank in the weighted sampling mechanism."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sampling-then-randomised-response paradigm for set-valued data that the weighted sampling mechanism extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the weighted reservoir sampling problem that the additive mechanism's recursive algorithm solves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the exponential-mechanism template from which the additive mechanism's probability design is adapted."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Grounds the contrast between bounded/local and unbounded differential privacy that explains the soundness gap."}],"review_version":1}