The Distortion of Binomial Voting Defies Expectation

• URL: http://arxiv.org/abs/2306.15657v2
• Date: Thu, 7 Dec 2023 22:45:14 GMT
• Title: The Distortion of Binomial Voting Defies Expectation
• Authors: Yannai A. Gonczarowski, Gregory Kehne, Ariel D. Procaccia, Ben Schiffer, Shirley Zhang
• Abstract summary: We study the expected distortion of voting rules with respect to an underlying distribution over voter utilities. Our main contribution is the design and analysis of a novel and intuitive rule, binomial voting.
• Score: 26.481697906062095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In computational social choice, the distortion of a voting rule quantifies the degree to which the rule overcomes limited preference information to select a socially desirable outcome. This concept has been investigated extensively, but only through a worst-case lens. Instead, we study the expected distortion of voting rules with respect to an underlying distribution over voter utilities. Our main contribution is the design and analysis of a novel and intuitive rule, binomial voting, which provides strong distribution-independent guarantees for both expected distortion and expected welfare.

Related papers

• DeepVoting: Learning Voting Rules with Tailored Embeddings [13.037431161285971]
  We recast the problem of designing a good voting rule into one of learning probabilistic versions of voting rules. We show that embeddings of preference profiles derived from the social choice literature allows us to learn existing voting rules more efficiently. We also show that rules learned using embeddings can be tweaked to create novel voting rules with improved axiomatic properties.
  arXiv  Detail & Related papers  (2024-08-24T17:15:20Z)
• Average-Case Analysis of Iterative Voting [33.68929251752289]
  Iterative voting is a natural model of repeated strategic decision-making in social choice. Prior work has analyzed the efficacy of iterative plurality on the welfare of the chosen outcome at equilibrium. This work extends average-case analysis to a wider class of distributions and distinguishes when iterative plurality improves or degrades welfare.
  arXiv  Detail & Related papers  (2024-02-13T00:46:46Z)
• The Decisive Power of Indecision: Low-Variance Risk-Limiting Audits and Election Contestation via Marginal Mark Recording [51.82772358241505]
  Risk-limiting audits (RLAs) are techniques for verifying the outcomes of large elections. We define new families of audits that improve efficiency and offer advances in statistical power. New audits are enabled by revisiting the standard notion of a cast-vote record so that it can declare multiple possible mark interpretations.
  arXiv  Detail & Related papers  (2024-02-09T16:23:54Z)
• Fairly Allocating Utility in Constrained Multiwinner Elections [0.0]
  A common denominator to ensure fairness across all such contexts is the use of constraints. Across these contexts, the candidates selected to satisfy the given constraints may systematically lead to unfair outcomes for historically disadvantaged voter populations. We develop a model to select candidates that satisfy the constraints fairly across voter populations.
  arXiv  Detail & Related papers  (2022-11-23T10:04:26Z)
• Bounding Counterfactuals under Selection Bias [60.55840896782637]
  We propose a first algorithm to address both identifiable and unidentifiable queries. We prove that, in spite of the missingness induced by the selection bias, the likelihood of the available data is unimodal.
  arXiv  Detail & Related papers  (2022-07-26T10:33:10Z)
• Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning [58.23459346724491]
  We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions. We draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties.
  arXiv  Detail & Related papers  (2022-05-16T17:40:22Z)
• The Impact of a Coalition: Assessing the Likelihood of Voter Influence in Large Elections [30.930621357547487]
  It has been widely believed that the influence of a small coalition of voters is negligible in a large election. We show that the likelihood is $Thetaleft(minleftfracBsqrt n, 1rightright)$ for many commonly-studied voting rules.
  arXiv  Detail & Related papers  (2022-02-13T21:27:22Z)
• Obvious Manipulability of Voting Rules [105.35249497503527]
  The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability.
  arXiv  Detail & Related papers  (2021-11-03T02:41:48Z)
• Assertion-Based Approaches to Auditing Complex Elections, with Application to Party-List Proportional Elections [21.883045335485317]
  We show that assertions with linear dependence on transformations of the votes can easily be transformed to canonical form for SHANGRLA. We illustrate the approach by constructing assertions for party-list elections using the D'Hondt method.
  arXiv  Detail & Related papers  (2021-07-25T22:52:49Z)
• Mundus vult decipi, ergo decipiatur: Visual Communication of Uncertainty in Election Polls [56.8172499765118]
  We discuss potential sources of bias in nowcasting and forecasting. Concepts are presented to attenuate the issue of falsely perceived accuracy. One key idea is the use of Probabilities of Events instead of party shares.
  arXiv  Detail & Related papers  (2021-04-28T07:02:24Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00:33Z)

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.