Optimal bounds for dissatisfaction in perpetual voting

• URL: http://arxiv.org/abs/2501.01969v1
• Date: Fri, 20 Dec 2024 19:58:55 GMT
• Title: Optimal bounds for dissatisfaction in perpetual voting
• Authors: Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer,
• Abstract summary: 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.
• Score: 84.02572742131521
• License:
• Abstract: In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proportionality over periods of time. In this paper, we consider the following question: is there a perpetual approval voting method that guarantees that no voter is dissatisfied too many times? We identify a sufficient condition on voter behavior -- which we call 'bounded conflicts' condition -- under which a sublinear growth of dissatisfaction is possible. We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.

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)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections. The margin of victory, or simply margin, is the smallest number of ballots that, if manipulated, can alter the set of winners. Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
  arXiv  Detail & Related papers  (2025-01-24T13:39:23Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the instantaneous reward before observing it.
  arXiv  Detail & Related papers  (2024-02-23T06:27:12Z)
• The Distortion of Binomial Voting Defies Expectation [26.481697906062095]
  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.
  arXiv  Detail & Related papers  (2023-06-27T17:50:58Z)
• 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)
• On the Complexity of Winner Determination and Strategic Control in Conditional Approval Voting [13.207754600697138]
  Conditional Minisum (CMS) is a voting rule for multi-issue elections with preferential dependencies. We show that CMS can be viewed as a solution that achieves a satisfactory tradeoff between expressiveness and computational efficiency.
  arXiv  Detail & Related papers  (2022-02-03T16:15:54Z)
• 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)
• 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)
• Adaptive Combinatorial Allocation [77.86290991564829]
  We consider settings where an allocation has to be chosen repeatedly, returns are unknown but can be learned, and decisions are subject to constraints. Our model covers two-sided and one-sided matching, even with complex constraints.
  arXiv  Detail & Related papers  (2020-11-04T15:02:59Z)

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.