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

• Verifying Proportionality in Temporal Voting [29.69443607539022]
  We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates. We focus on the complexity of verifying whether a given outcome offers proportional representation.
  arXiv  Detail & Related papers  (2025-02-09T16:30:34Z)
• 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)
• 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)
• 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)
• 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)

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.