Why do the non-fast versions of stable voting and simple stable voting exist?

[DominikPeters]

There exist both simple_stable_voting_faster and stable_voting_faster as well as simple_stable_voting and stable_voting. From the docs description, it seems like they compute the same set, so why do the non-fast versions exist? I'd either delete them or explain in the docs.

[ParadaCarleton]

My guess is they're for testing (probably using an easier-to-write, but non-optimized, algorithm). In that case it would make sense to move them to the testing folder.

[ParadaCarleton]

It seems like there's quite a few duplicated methods in the docs (i.e. different algorithms for the same method), which I think could probably be simplified by combining them into one function (with a keyword argument to pick the algorithm).

[epacuit]

Thanks! These are great points, and I do very much like the idea of having one name for a method with parameters to choose the algorithm. One of the reasons why we had it defined in the way that we do is that when we discuss the voting methods in papers, we wanted the the implementation to match as much as possible the description of the method. But, that is often not the fastest way to implement the method (e.g., for Beat Path it is better to use the variation of the Floyd-Warshall algorithm rather than the implementation based on the definition typically used in papers).

Another issue is that, for instance, for Stable Voting one can prove that the method is Condorcet consistent. But, it would look weird if you prove that a method is Condorcet Consistent when the first step of the method is "find a Condorcet winner and return it if it exists". So, for instance, for our paper on Stable Voting we wanted the implementation of stable_voting to match our discussion of the algorithm in our paper. But, when using the method in simulations, etc., it nice to have a slightly faster version.

[DominikPeters]

The abcvoting package also passes an algorithm parameter for functions that compute a rule (with a default going to the fastest available algorithm), which makes sense to me. Following the setup there, we would have a main function beat_path(profile, algorithm="floyd_warshall") which then goes conditions on the algorithm parameter and calls the function _beat_path_floyd_warshall(profile).

Such an approach is compatible with having a close-to-definition implementation, which could be named algorithm=reference or algorithm=basic or similar. A disadvantage of the current setup is that there can be confusion whether two different "rules" (two different methods) are supposed to be extensionally different or not. For example, the facts that stable_voting != simple_stable_voting and stable_voting == stable_voting_faster are not immediately clear.

[epacuit]

I like this approach, and I think we will implement that for pref_voting.

The relationship between stable_voting and simple_stable_voting is subtle. Wes and I conjectured that stable_voting and simple_stable_voting always produce the same results on uniquely weighted profiles (it's not too difficult to see that they produce different results when there are ties in the margins, but very difficulty to find examples when there are no ties in the margins). It turns out that this is true for 6 or fewer candidates, but not when there is more than 6 candidates. We are writing a paper about this.

[epacuit]

I've added the algorithm parameter to split_cycle, stable_voting, simple_stable_voting, ranked_pairs, and beat_path.

I decided to keep ranked_pairs_with_test as a separate function from ranked_pairs. ranked_pairs_with_test sometimes returns None when it seems like the algorithm will take too long. This is not a different algorithm for producing Ranked Pairs winners, but rather a simple heuristic to allow people to run ranked_pairs on profiles without taking forever to find the winners.