Differentially Private Condorcet Voting
Zhechen Li, Ao Liu, Lirong Xia, Yongzhi Cao, Hanpin Wang
Abstract
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 (CMLAP), exponential Condorcet method (CMEXP), and randomized response Condorcet method (CMRR), where λ 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, CMRR satisfies (non-approximate) probabilistic Condorcet criterion, while CMLAP and CMEXP satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.
BibTeX
@article{Li_Liu_Xia_Cao_Wang_2023, title={Differentially Private Condorcet Voting}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25714}, DOI={10.1609/aaai.v37i5.25714}, abstractNote={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 (CMLAP), exponential Condorcet method (CMEXP), and randomized response Condorcet method (CMRR), where λ 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, CMRR satisfies (non-approximate) probabilistic Condorcet criterion, while CMLAP and CMEXP satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.}, number={5}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Li, Zhechen and Liu, Ao and Xia, Lirong and Cao, Yongzhi and Wang, Hanpin}, year={2023}, month={Jun.}, pages={5755-5763} }