How Private Are Commonly-Used Voting Rules?

Ao LIU, Yun Lu, Lirong Xia, Vassilis Zikas
Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 124:629-638, 2020.

Abstract

Differential privacy has been widely applied to provide privacy guarantees by adding random noise to the function output. However, it inevitably fails in many high-stakes voting scenarios, where voting rules are required to be deterministic. In this work, we present the first framework for answering the question:“How private are commonly-used voting rules?" Our answers are two-fold. First, we show that deterministic voting rules provide sufficient privacy in the sense of distributional differential privacy (DDP). We show that assuming the adversarial observer has uncertainty about individual votes, even publishing the histogram of votes achieves good DDP. Second, we introduce the notion of exact privacy to compare the privacy preserved in various commonly-studied voting rules, and obtain dichotomy theorems of exact DDP within a large subset of voting rules called generalized scoring rules.

Cite this Paper

BibTeX
@InProceedings{pmlr-v124-liu20b, title = {How Private Are Commonly-Used Voting Rules?}, author = {LIU, Ao and Lu, Yun and Xia, Lirong and Zikas, Vassilis}, booktitle = {Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)}, pages = {629--638}, year = {2020}, editor = {Peters, Jonas and Sontag, David}, volume = {124}, series = {Proceedings of Machine Learning Research}, month = {03--06 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v124/liu20b/liu20b.pdf}, url = {https://proceedings.mlr.press/v124/liu20b.html}, abstract = {Differential privacy has been widely applied to provide privacy guarantees by adding random noise to the function output. However, it inevitably fails in many high-stakes voting scenarios, where voting rules are required to be deterministic. In this work, we present the first framework for answering the question:“How private are commonly-used voting rules?" Our answers are two-fold. First, we show that deterministic voting rules provide sufficient privacy in the sense of distributional differential privacy (DDP). We show that assuming the adversarial observer has uncertainty about individual votes, even publishing the histogram of votes achieves good DDP. Second, we introduce the notion of exact privacy to compare the privacy preserved in various commonly-studied voting rules, and obtain dichotomy theorems of exact DDP within a large subset of voting rules called generalized scoring rules.} }
Endnote
%0 Conference Paper %T How Private Are Commonly-Used Voting Rules? %A Ao LIU %A Yun Lu %A Lirong Xia %A Vassilis Zikas %B Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) %C Proceedings of Machine Learning Research %D 2020 %E Jonas Peters %E David Sontag %F pmlr-v124-liu20b %I PMLR %P 629--638 %U https://proceedings.mlr.press/v124/liu20b.html %V 124 %X Differential privacy has been widely applied to provide privacy guarantees by adding random noise to the function output. However, it inevitably fails in many high-stakes voting scenarios, where voting rules are required to be deterministic. In this work, we present the first framework for answering the question:“How private are commonly-used voting rules?" Our answers are two-fold. First, we show that deterministic voting rules provide sufficient privacy in the sense of distributional differential privacy (DDP). We show that assuming the adversarial observer has uncertainty about individual votes, even publishing the histogram of votes achieves good DDP. Second, we introduce the notion of exact privacy to compare the privacy preserved in various commonly-studied voting rules, and obtain dichotomy theorems of exact DDP within a large subset of voting rules called generalized scoring rules.
APA
LIU, A., Lu, Y., Xia, L. & Zikas, V.. (2020). How Private Are Commonly-Used Voting Rules?. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), in Proceedings of Machine Learning Research 124:629-638 Available from https://proceedings.mlr.press/v124/liu20b.html.

Related Material