Stable Voting is PSPACE-Complete
arXiv:2607.14366
summary
The paper proves that determining the winner under the Stable Voting and Simple Stable Voting rules is PSPACE‑complete.
Abstract
Stable Voting and Simple Stable Voting, introduced by Holliday and Pacuit, are Condorcet-consistent voting rules defined recursively: a candidate wins if they would win after removing some opponent they beat, taking the pair with the largest margin first. The computational complexity of winner determination under these rules has been an open question. We resolve this problem: winner determination is PSPACE-complete under both Stable Voting and Simple Stable Voting.
Topics & keywords
#voting theory#computational complexity#pspace-completeness#condorcet-consistent voting#algorithmic social choiceStable VotingSimple Stable Votingwinner determinationPSPACE-completeCondorcet