search

voting-tools / pref_voting

pref_voting is a Python package that can be used to study and run elections with different preferential voting methods (graded voting methods and cardinal voting methods are also included for comparison).
https://pref-voting.readthedocs.io/
MIT License
12 stars 4 forks source link

Speed up instant runoff PUT by immediately eliminating score-0 candidates #70

Closed DominikPeters closed 7 months ago

DominikPeters commented 7 months ago

When computing instant runoff PUT, it is safe to immediately eliminate all candidates that are never top-ranked, because every elimination order will start by eliminating those candidates (proof: clearly, the first candidate to be eliminated has score 0; because it has score 0, no votes get reassigned, so score-0 candidates remain score-0).

This leads to a large speed-up in profiles with many more candidates than voters.

I've also refactored some other parts of the code in iterative_methods, where plurality scores were sometimes needlessly repeatedly computed.

epacuit commented 7 months ago

Thanks! These changes looks great.