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.

本文探讨了在多轮投票中怎样处理平局，并提出了计算同时使用STV和RP（平行宇宙Tiebreaking机制）的候选赢家的算法，通过启发式、采样和机器学习来优化搜索方向以及采用DFS-based算法、修剪策略等方式加速计算，同时还提出了新的ILP公式，实验证明该算法整体快于ILP。

多阶段投票规则实用算法及并行宇宙决胜法