Differentially Private Approval-Based Committee Voting

Zhechen Li, Zimai Guo, Lirong Xia, Yongzhi Cao, Hanpin Wang
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:3556-3580, 2026.

Abstract

In this paper, we investigate tradeoffs among differential privacy ({DP}) and several representative axioms for approval-based committee voting, including justified representation, proportional justified representation, extended justified representation, Pareto efficiency, and Condorcet criterion. Without surprise, we demonstrate that all of these axioms are incompatible with {DP}, and thus establish both upper and lower bounds for their two-way tradeoffs with {DP}. Furthermore, we provide upper and lower bounds for three-way tradeoffs among {DP} and every pairwise combination of such axioms, revealing that although these axioms are compatible without {DP}, their optimal levels under {DP} cannot be simultaneously achieved. Our results quantify the effect of {DP} on the satisfaction and compatibility of the axioms in approval-based committee voting, which can provide insights for designing voting rules that possess both privacy and axiomatic properties.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-li26b, title = {Differentially Private Approval-Based Committee Voting}, author = {Li, Zhechen and Guo, Zimai and Xia, Lirong and Cao, Yongzhi and Wang, Hanpin}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {3556--3580}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/li26b/li26b.pdf}, url = {https://proceedings.mlr.press/v337/li26b.html}, abstract = {In this paper, we investigate tradeoffs among differential privacy ({DP}) and several representative axioms for approval-based committee voting, including justified representation, proportional justified representation, extended justified representation, Pareto efficiency, and Condorcet criterion. Without surprise, we demonstrate that all of these axioms are incompatible with {DP}, and thus establish both upper and lower bounds for their two-way tradeoffs with {DP}. Furthermore, we provide upper and lower bounds for three-way tradeoffs among {DP} and every pairwise combination of such axioms, revealing that although these axioms are compatible without {DP}, their optimal levels under {DP} cannot be simultaneously achieved. Our results quantify the effect of {DP} on the satisfaction and compatibility of the axioms in approval-based committee voting, which can provide insights for designing voting rules that possess both privacy and axiomatic properties.} }
Endnote
%0 Conference Paper %T Differentially Private Approval-Based Committee Voting %A Zhechen Li %A Zimai Guo %A Lirong Xia %A Yongzhi Cao %A Hanpin Wang %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-li26b %I PMLR %P 3556--3580 %U https://proceedings.mlr.press/v337/li26b.html %V 337 %X In this paper, we investigate tradeoffs among differential privacy ({DP}) and several representative axioms for approval-based committee voting, including justified representation, proportional justified representation, extended justified representation, Pareto efficiency, and Condorcet criterion. Without surprise, we demonstrate that all of these axioms are incompatible with {DP}, and thus establish both upper and lower bounds for their two-way tradeoffs with {DP}. Furthermore, we provide upper and lower bounds for three-way tradeoffs among {DP} and every pairwise combination of such axioms, revealing that although these axioms are compatible without {DP}, their optimal levels under {DP} cannot be simultaneously achieved. Our results quantify the effect of {DP} on the satisfaction and compatibility of the axioms in approval-based committee voting, which can provide insights for designing voting rules that possess both privacy and axiomatic properties.
APA
Li, Z., Guo, Z., Xia, L., Cao, Y. & Wang, H.. (2026). Differentially Private Approval-Based Committee Voting. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:3556-3580 Available from https://proceedings.mlr.press/v337/li26b.html.

Related Material