Practical Algorithms for STV and Ranked Pairs 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 and heuristics to prioritize search
direction to significantly improve the performance using machine learning. 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 significantly faster than ILP, while there are a few
cases where ILP is significantly faster for RP.
