Multiwinner Temporal Voting with Aversion to Change

• URL: http://arxiv.org/abs/2408.11017v1
• Date: Tue, 20 Aug 2024 17:16:54 GMT
• Title: Multiwinner Temporal Voting with Aversion to Change
• Authors: Valentin Zech, Niclas Boehmer, Edith Elkind, Nicholas Teh,
• Abstract summary: We study two-stage committee elections where voters have dynamic preferences over candidates. At each stage, a committee is chosen under a given voting rule. We show a full complexity dichotomy for the class of Thiele rules.
• Score: 30.15852603215344
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin-Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e.g., we investigate the average number of changes in the committee as a function of changes in voters' preferences and the role of ties.

Related papers

• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIRE can audit IRV contests with any number of candidates, but the original implementation incurred memory and computation costs that grew superexponentially with the number of candidates. This paper improves the algorithmic implementation of AWAIRE in three ways that make it practical to audit IRV contests with 55 candidates, compared to the previous 6 candidates.
  arXiv  Detail & Related papers  (2024-07-23T13:28:00Z)
• Selecting the Most Conflicting Pair of Candidates [6.838139628413773]
  We study committee elections from a perspective of finding the most conflicting candidates, that is, candidates that imply the largest amount of conflict, as per voter preferences. By proposing basic axioms to capture this objective, we show that none of the prominent multiwinner voting rules meet them. A subsequent deepened analysis sheds more light on how they operate.
  arXiv  Detail & Related papers  (2024-05-09T16:00:20Z)
• 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)
• 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)
• The Complexity of Learning Approval-Based Multiwinner Voting Rules [9.071560867542647]
  We study the learnability of multiwinner voting, focusing on the class of approval-based committee scoring (ABCS) rules. Our goal is to learn a target rule (i.e., to learn the corresponding scoring function) using information about the winning committees of a small number of profiles. We prove that deciding whether there exists some ABCS rule that makes a given committee winning in a given profile is a hard problem.
  arXiv  Detail & Related papers  (2021-10-01T08:25:05Z)
• On component interactions in two-stage recommender systems [82.38014314502861]
  Two-stage recommenders are used by many online platforms, including YouTube, LinkedIn, and Pinterest. We show that interactions between the ranker and the nominators substantially affect the overall performance. In particular, using a Mixture-of-Experts approach, we train the nominators to specialize on different subsets of the item pool.
  arXiv  Detail & Related papers  (2021-06-28T20:53:23Z)
• 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.