Differentially Private Condorcet Voting

Designing private voting rules is an important and pressing problem for trustworthy democracy. In this paper, under the framework of differential privacy, we propose a novel famliy of randomized voting rules based on the well-known Condorcet method, and focus on three classes of voting rules in this family: Laplacian Condorcet method (${\text{CMLAP}}_{\lambda }$), exponential Condorcet method (${\text{CMEXP}}_{\lambda }$), and randomized response Condorcet method (${\text{CMRR}}_{\lambda }$), where $\lambda$ represents the level of noise. We prove that all of our rules satisfy absolute monotonicity, lexi-participation, probabilistic Pareto efficiency, approximate probabilistic Condorcet criterion, and approximate SD-strategyproofness. In addition, ${\text{CMRR}}_{\lambda }$ satisfies (non-approximate) probabilistic Condorcet criterion, while ${\text{CMLAP}}_{\lambda }$ and ${\text{CMEXP}}_{\lambda }$ satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.