Stable Voting is PSPACE-Complete
This establishes the worst-case computational hardness of these voting rules for election administrators and computational social choice theorists.
The paper resolves the open problem of the computational complexity of winner determination under Stable Voting and Simple Stable Voting, proving it is PSPACE-complete.
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.