The Smoothed Satisfaction of Voting Axioms

• URL: http://arxiv.org/abs/2106.01947v1
• Date: Thu, 3 Jun 2021 15:55:11 GMT
• Title: The Smoothed Satisfaction of Voting Axioms
• Authors: Lirong Xia
• Abstract summary: 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.
• Score: 34.65163653153113
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the work towards a comprehensive picture of the smoothed satisfaction of voting axioms, to provide a finer and more realistic foundation for comparing voting rules. We adopt the smoothed social choice framework, where an adversary chooses arbitrarily correlated "ground truth" preferences for the agents, on top of which random noises are added. We focus on characterizing the smoothed satisfaction of two well-studied voting axioms: Condorcet criterion and participation. We prove that for any fixed number of alternatives, when the number of voters $n$ is sufficiently large, the smoothed satisfaction of the Condorcet criterion under a wide range of voting rules is $1$, $1-\exp(-\Theta(n))$, $\Theta(n^{-0.5})$, $ \exp(-\Theta(n))$, or being $\Theta(1)$ and $1-\Theta(1)$ at the same time; and the smoothed satisfaction of participation is $1-\Theta(n^{-0.5})$. 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.

Related papers

• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  We consider a perpetual approval voting method that guarantees that no voter is dissatisfied too many times. We identify a sufficient condition on voter behavior under which a sublinear growth of dissatisfaction is possible. We present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.
  arXiv  Detail & Related papers  (2024-12-20T19:58:55Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  We study the fixed-confidence best arm identification problem in the bandit framework. We propose a novel policy that combines Thompson sampling with a computationally efficient approach known as the best challenger rule.
  arXiv  Detail & Related papers  (2023-10-01T01:37:02Z)
• Breaking the Metric Voting Distortion Barrier [10.143374372425757]
  We consider the problem of metric distortion in social choice. Finding a randomized rule that guarantees distortion $3 - epsilon$ has been a major challenge in computational social choice. We give a rule that guarantees distortion less than $2.753$.
  arXiv  Detail & Related papers  (2023-06-30T17:56:33Z)
• 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)
• Differentially Private Condorcet Voting [26.959251649951103]
  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.
  arXiv  Detail & Related papers  (2022-06-27T06:55:22Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  We consider a multi-armed bandit setting where, at the beginning of each round, the learner receives noisy independent evaluations of the true reward of each arm. We derive different algorithmic approaches and theoretical guarantees depending on how the evaluations are generated.
  arXiv  Detail & Related papers  (2021-12-13T09:48:54Z)
• Truth-tracking via Approval Voting: Size Matters [3.113227275600838]
  We consider a simple setting where votes consist of approval ballots. Each voter approves a set of alternatives which they believe can possibly be the ground truth. We define several noise models that are approval voting variants of the Mallows model.
  arXiv  Detail & Related papers  (2021-12-07T12:29:49Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms [0.966840768820136]
  We consider the model selection task in the contextual bandit setting. Our proposal is the first one to be rate-adaptive for a collection of general black-box contextual bandit algorithms.
  arXiv  Detail & Related papers  (2020-06-05T18:55:16Z)

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.