Practical Algorithms for Multi-Stage Voting Rules with Parallel Universes Tiebreaking

Authors

  • Jun Wang Rensselaer Polytechnic Institute
  • Sujoy Sikdar Rensselaer Polytechnic Institute
  • Tyler Shepherd Rensselaer Polytechnic Institute
  • Zhibing Zhao Rensselaer Polytechnic Institute
  • Chunheng Jiang Rensselaer Polytechnic Institute
  • Lirong Xia Rensselaer Polytechnic Institute

DOI:

https://doi.org/10.1609/aaai.v33i01.33012189

Abstract

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 realworld data show that our algorithms are overall faster than ILP.

Downloads

Published

2019-07-17

How to Cite

Wang, J., Sikdar, S., Shepherd, T., Zhao, Z., Jiang, C., & Xia, L. (2019). Practical Algorithms for Multi-Stage Voting Rules with Parallel Universes Tiebreaking. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2189-2196. https://doi.org/10.1609/aaai.v33i01.33012189

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms