How Private Are Commonly-Used Voting Rules?

Ao Liu, Yun Lu, Lirong Xia, Vassilis Zikas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationProceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)
PublisherPMLR
Pages629-638
Number of pages10
Publication statusPublished - 6 Aug 2020
Event36th Conference on Uncertainty in Artificial Intelligence 2020 - Virtual conference, Canada
Duration: 3 Aug 20206 Aug 2020
http://www.auai.org/~w-auai/uai2020/index.php

Conference

Conference36th Conference on Uncertainty in Artificial Intelligence 2020
Abbreviated titleUAI 2020
Country/TerritoryCanada
CityVirtual conference
Period3/08/206/08/20
Internet address

Fingerprint

Dive into the research topics of 'How Private Are Commonly-Used Voting Rules?'. Together they form a unique fingerprint.

Cite this