Differentially Private Condorcet Voting

• URL: http://arxiv.org/abs/2206.13081v1
• Date: Mon, 27 Jun 2022 06:55:22 GMT
• Title: Differentially Private Condorcet Voting
• Authors: Zhechen Li, Ao Liu, Lirong Xia, Yongzhi Cao, Hanpin Wang
• Abstract summary: We propose three classes of randomized voting rules based on the well-known Condorcet method. By accurately estimating the errors introduced by the randomness, we show that $CMEXP_lambda$ is the most accurate mechanism in most cases. We regard differential privacy as a voting axiom, and discuss its relations to other axioms.
• Score: 26.959251649951103
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 three classes of randomized voting rules based on the well-known Condorcet method: Laplacian Condorcet method ($CM^{LAP}_\lambda$), exponential Condorcet method ($CM^{EXP}_\lambda$), and randomized response Condorcet method ($CM^{RR}_\lambda$), where $\lambda$ represents the level of noise. By accurately estimating the errors introduced by the randomness, we show that $CM^{EXP}_\lambda$ is the most accurate mechanism in most cases. 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, $CM^{RR}_\lambda$ satisfies (non-approximate) probabilistic Condorcet criterion, while $CM^{LAP}_\lambda$ and $CM^{EXP}_\lambda$ satisfy strong lexi-participation. Finally, we regard differential privacy as a voting axiom, and discuss its relations to other axioms.

Related papers

• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm. DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms. We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  This paper considers the best policy identification problem in online Constrained Markov Decision Processes (CMDPs) We are interested in algorithms that are model-free, have low regret, and identify an approximately optimal policy with a high probability. Existing model-free algorithms for online CMDPs with sublinear regret and constraint violation do not provide any convergence guarantee to an optimal policy.
  arXiv  Detail & Related papers  (2023-09-27T04:33:09Z)
• Proportional Aggregation of Preferences for Sequential Decision Making [20.374669324368625]
  We study the problem of fair sequential decision making given voter preferences. In each round, a decision rule must choose a decision from a set of alternatives where each voter reports which of these alternatives they approve. We formalize this aim using axioms based on Proportional Justified Representation.
  arXiv  Detail & Related papers  (2023-06-26T17:10:10Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  We study risk-sensitive Reinforcement Learning (RL), focusing on the objective of Conditional Value at Risk (CVaR) with risk tolerance $tau$. We show the minimax CVaR regret rate is $Omega(sqrttau-1AK)$, where $A$ is the number of actions and $K$ is the number of episodes. We show that our algorithm achieves the optimal regret of $widetilde O(tau-1sqrtSAK)$ under a continuity assumption and in general attains a near
  arXiv  Detail & Related papers  (2023-02-07T02:22:31Z)
• Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
  We study the private continual summation problem (a.k.a. the counter problem) We show that the concurrent shuffle model allows for significantly improved error compared to a standard (single) shuffle model.
  arXiv  Detail & Related papers  (2023-01-29T20:42:54Z)
• Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
  We study the Prophet Inequality and Pandora's Box problems in the Multi-Armed Bandits model. Our results give near-optimal $tildeO(mathsfpoly(n)sqrtT)$ total regret algorithms for both Prophet Inequality and Pandora's Box.
  arXiv  Detail & Related papers  (2022-11-16T00:10:35Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• PAC Mode Estimation using PPR Martingale Confidence Sequences [5.623190096715942]
  We consider the problem of correctly identifying the mode of a discrete distribution $mathcalP$ with sufficiently high probability. We propose a generalisation to mode estimation, in which $mathcalP$ may take $K geq 2$ values. Our resulting stopping rule, denoted PPR-ME, is optimal in its sample complexity up to a logarithmic factor.
  arXiv  Detail & Related papers  (2021-09-10T18:11:38Z)
• The Smoothed Satisfaction of Voting Axioms [34.65163653153113]
  We focus on characterizing the smoothed satisfaction of two well-studied voting axioms: Condorcet criterion and participation. Our results address open questions by Berg and Lepelley in 1994 for these rules, and also confirm the following high-level message: the Condorcet criterion is a bigger concern than participation under realistic models.
  arXiv  Detail & Related papers  (2021-06-03T15:55:11Z)
• Bandits with many optimal arms [68.17472536610859]
  We write $p*$ for the proportion of optimal arms and $Delta$ for the minimal mean-gap between optimal and sub-optimal arms. We characterize the optimal learning rates both in the cumulative regret setting, and in the best-arm identification setting.
  arXiv  Detail & Related papers  (2021-03-23T11:02:31Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.