Practical Algorithms for Multi-Stage Voting Rules with Parallel Universes Tiebreaking
STV and ranked pairs (RP) are two well-studied voting rules for group decision-making. They proceed in multiple rounds, and are affected by how ties are broken in each round. However, the literature is surprisingly vague about how ties should be broken. We propose the first algorithms for computing the set of alternatives that are winners under some tiebreaking mechanism under STV and RP, which is also known as parallel-universes tiebreaking (PUT). Unfortunately, PUT-winners are NP-complete to compute under STV and RP, and standard search algorithms from AI do not apply. We propose multiple DFS-based algorithms along with pruning strategies, heuristics, sampling and machine learning to prioritize search direction to significantly improve the performance. We also propose novel ILP formulations for PUT-winners under STV and RP, respectively. Experiments on synthetic and real-world data show that our algorithms are overall faster than ILP.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Multiwinner Temporal Voting with Aversion to Change
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 s…
DeepVoting: Learning Voting Rules with Tailored Embeddings
Aggregating the preferences of multiple agents into a collective decision is a common step in many important problems across areas of computer science including information retrieval, reinforcement learning, and recommen…
Information RetrievalRecommendation SystemsUnifying Ensemble Methods for Q-learning via Social Choice Theory
Ensemble methods have been widely applied in Reinforcement Learning (RL) in order to enhance stability, increase convergence speed, and improve exploration. These methods typically work by employing an aggregation mechan…
DiversityQ-LearningReinforcement LearningReinforcement Learning (RL)Utilitarian Welfare and Representation Guarantees of Approval-Based Multiwinner Rules
To choose a suitable multiwinner voting rule is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an ``optimal'' subset of alternatives. In this paper, we provide a quan…
Estimating the Margin of Victory of an Election using Sampling
The margin of victory of an election is a useful measure to capture the robustness of an election outcome. It also plays a crucial role in determining the sample size of various algorithms in post election audit, polling…