差分隐私通过向输出注入随机噪声来保护个人数据隐私,但在选举等场景中,噪声可能导致错误结果,尤其是当胜负差距很小时。本文系统研究了在中央差分隐私和本地差分隐私模型下,多种常见投票规则(包括 Plurality、Condorcet、Maximin、Plurality with Runoff 和单记名可转让票 STV)保证私有机制以高概率返回正确获胜者所需的最小获胜优势(称为 decisive margin)。针对每种规则,作者设计了发布获胜者的差分隐私算法,并证明了这些算法所需的边界上界;同时,通过构造反例或信息论论证,证明了下界,说明非平凡的获胜优势是必要的,其中许多上界与下界在对数因子内匹配。特别地,对于 STV 规则,信息论上界与下界完全匹配,但作者进一步证明,这样的最优精确度保证在多项式时间内无法实现,除非假设 NP ⊆ BPP,这构成了一个罕见的计算复杂性现象:原本易于计算的任务,在同时要求差分隐私和效用保证后变得计算上不可行。本文的主要贡献在于系统地刻画了差分隐私投票中隐私与效用之间的基本权衡,揭示了不同投票规则的固有精度限制,并指出了计算复杂度与隐私约束之间的相互作用。该结果对设计隐私保护的选举系统、排名聚合或数据发布机制具有理论指导意义,帮助研究者理解隐私预算、噪声规模和输出精度之间的取舍。
💡 推荐理由: 为差分隐私投票机制提供理论精度界限,帮助设计者在隐私与正确性之间做权衡。指出 STV 下需额外计算成本,提醒实际应用需评估可行性。对研究隐私保护聚合算法的安全工程师有参考价值。
🎯 建议动作: 研究跟进