itamaro
commented
11 years ago I have been working on this during the hackathon.
Went with the suggested existing implementation (https://github.com/bradbeattie/python-vote-core) which seemed fine (possibly found a bug in the library, see https://github.com/bradbeattie/python-vote-core/issues/15). Before diving into modifying the algorithm to support dynamic calculation (which is premature optimization), we decided to first check if the existing implementation could be used "as-is" with sufficient performance.
The chosen library implements several voting methods, some are "single winner methods" (including the classical Schulze Method), and some are "ordering methods" (including the Schulze Proportional Representation Method).
- During the first day of the hackathon, we wrote a wrapper class for SchulzeMethod, that allows adding votes "online" (while internally building a histogram of ballots, which is the input for the Schulze algorithm).
- We tested performace of the SchulzeMethod algorithm for various amounts of candidates (5..12), for increasing amounts of ballots (10k, 20k, .., 50k), and found the runtime is sub-linear in ballot-count, and possibly-exponential in candidate-count. Runtimes were in the order of 1sec. A single run of SchulzeMethod with 100 candidates on 10k ballots took about 50sec.
- We tested performace of the SchulzeMethod algorithm for various amounts of candidates (5..12), for increasing amounts of ballots (10k, 20k, .., 50k), and found the runtime is sub-linear in ballot-count, and possibly-exponential in candidate-count. Runtimes were in the order of 1sec. A single run of SchulzeMethod with 100 candidates on 10k ballots took about 50sec.
On the second day, we realized that we need and ordering method, and not just a single winner method, so we switched to SchulzePR. Unfortunately, SchulzePR is much heavier... For ~7 candidates it takes an order of 3sec for 10k votes. Still sub-linear in ballot-count, but also still exponential in candidate-count. It took around 15sec for 10 candidates, and we didn't have the patience to wait for the completion with 30 candidates... (after ~15min)
Interestingly, SchulzePR just gives the resulting order (which needed some post-processing in order to consider ties properly). We also wanted to get pair-wise preferences from the data, which is generated by the classical SchulzeMethod. So, since it's much faster than SchulzePR, we call them both, so we can return the order and a pair-matrix. Another interesting property to calculate from the data would be - given the resulting order, for each group x in the order, overlay the order with the ratio between votes favoring group x over group x+1. This is still not implemented, but pretty straight forward, as we already have all the pair-wide data...
udishapiro
bradbeattie
Schulze method (there's a Heb page too) is about combining lists of preferences. Every voter casts a partially sorted list, meaning she can group items she sees in the same level of preference together – 1,(2,3,4),5 (Note that sorting in a group is doable but doesn’t change the ballot since 1,(4,2,3),5 means the same).
There’re several implementations of engines that calculate the final order of the augmented preferences, but as much as we understand they all assume two-stage process - a preliminary casting of ALL the ballots, and only then a single calculation.
Our system uses the algorithm for cumulative sort of issues and proposals, and therefore we need a dynamic Schulze engine, that efficiently updates the cumulative list as new ballots (or updated ones) are casted.
Two changes are therefore needed:
The task includes:
Integration of engine to a ballot casting UI and the usage of the outcome in the system will be done afterwards.