Overview

CIVS supports an experimental mode in which it can be used to select multiple candidates while enforcing proportional representation. Roughly speaking, a set of voters can only influence the selection of a fraction of the selected candidates that is proportional to the number of voters.

For example, suppose that 60% of the voters want candidates A, B, C, D, and E, in that order, and 40% want X, Y, Z, U, and V. Ordinary Condorcet voting will rank A, B, C, D, and E higher than the other five candidates, because a majority likes them better. For some tasks, this is the right way to run the election. However, if the election is selecting a five-person committee to represent the whole population, 40% would have no representation at all. The proportional representation algorithm used by CIVS would elect the candidates A, B, C, X, and Y (we will write this result as ABCXY), achieving perfect proportional representation.

Determining the winning committee

The rule used is a generalization of ordinary Condorcet voting. First, preferences expressed on individual candidates are lifted to obtain preferences on whole committees of k members. Then Condorcet methods are used to pick the “best” committee. The trick is to lift the preferences in a way that doesn't simply let a majority dictate the composition of the committee. We say that a given voter has an f-preference for possible committee A over another, B, if the voter prefers A to B when considering only the f most preferred candidates on each committee. We can compare any two possible committees for all values of f from 1 to k by determining for each voter and each value of f whether they have an f-preference for one of the two committees over the other, and summing up the number of voters with a preference for one and the number with a preference for the other. Suppose that the number of voters with a preference for committee 1 is v and there are n voters overall. Then an f-preference for committee 1 is valid if v(k+1)/n ≥ f. Invalid preferences are usually ignored in deciding the winner; to decide whether committee 1 is preferred over committee 2, we find the largest f such that v voters have a valid f-preference for one of the two committees. This v becomes the strength of the preference in the ordinary Condorcet sense; this is called the proportional preference here. If there is no proportional preference for one committee over the other, then the full k-preference (the nonproportional preference) is used to break the tie. This rule allows majorities to break ties in cases where the minority is indifferent.

For k=1, this voting scheme is simply the ordinary Condorcet scheme. For larger k, it yields proportional results. In the above example, the 60% have no valid preference for ABCDE over ABCXY because their maximum valid preference is a 3-preference (because 3/6 ≤ 60% < 4/6). The 40%, on the other hand, have a valid 2-preference for the second result (because 2/6 ≤ 40% < 3/6), so ABCXY is the winning committee, as desired.

The factor (k+1) may be surprising in the validity condition, but it actually agrees with proportional representation voting schemes developed elsewhere; it is analogous to the Droop quota used by many STV election methods. Suppose the factor were changed to k. In that case, a set of voters would be unable to influence the selection of a candidate unless they were large enough to form a bloc of size n/k. For example, suppose that k=2 and a bare majority favors candidates A and B, while a slightly smaller minority favors C and D. In this case the minority would have no valid preference for C and the winners would be AB. However, the right result is clearly AC. As long as the minority has least 1/3 of the voters, it will be represented by C. If the minority has less than 1/3, then we can view the majority as consisting of two blocs deserving representation, and both larger than the minority. So in that case the right result is AB, which is achieved because a 2/3 majority has a valid 2-preference in this case.

When the fraction of voters in each bloc don't match perfectly with the attainable fractions of seats, there is always some unfairness because some voters will be overrepresented and some underrepresented. Using a k+1 factor balances this unfairness so that a voter is overrepresented by at most a (k+1)/k factor. In the example just given, at the 1/3 point the majority (2/3) bloc has 50% (3/2) overrepresentation if it wins and the minority (1/3) bloc also has 50% overrepresentation if it wins. Using a different criterion for when a proportional preference is valid would result in a higher level of overrepresentation in some cases.

Determining a voter's preference

There is also the question of how to decide whether a voter prefers one committee over another. In proportional representation mode, there is only one difference from the voter's perspective: instead of ranking the candidates, the voter gives a nonnegative weight to each candidate. The voting algorithm decides which of two committees would be preferred by a candidate using one of two criteria, combined weights or best candidate:

Combined weights. The voter's goal is to maximize the sum of weights of selected candidates. This is an appropriate criterion for elections where the quality of all the candidates is important to the voters, such as the election of an actual committee that will be voting on some issues. Weights make it possible to compare sets of candidates with different cardinality. For example, suppose that a voter wants candidates A, B, and C, in that order, but would end up (because of the other voters' preferences) choosing between A and the pair BC. The algorithm can't tell just from the rankings whether the voter would prefer to have the better candidate A or greater representation under BC. Using weights this can be determined: if A is given a weight of 10 and B and C have weights 8 and 6 respectively, then the voting algorithm will (on the voter's behalf) work towards electing BC in preference to A, because 14 > 10. However, if B and C were instead given weights 4 and 2, the voter would have expressed that A is preferred to BC because 6 < 10.

Best candidate. With this criterion, the voter's goal is to get a single very good candidate elected possible, and the quality of other elected candidates is a strictly secondary consideration. This is appropriate for an election where the voter really only cares about the best candidate: for example, the selection of a set of entree dishes for a menu, where the voter will only eat one of the entrees. Here, two committees are compared using their best candidates (according to the voter); other candidates are considered only if the voter has no preference between the best candidates. In the examples above, A would be preferred to BC in either case, because A is preferred to B.

Algorithm

The voting scheme described above can be evaluated in a brute-force form by computing a preference matrix for all f in 1..k, where the matrix has size C(c,k)×C(c,k), where c is the number of candidates, and C is the combinatoric choose function. The storage and computational overhead of this brute-force computation is prohibitive for even moderately large n and k. Therefore, this is not how the actual CIVS implementation works.

The current technique for identifying the winning committee is less expensive but may be incomplete. The current implementation performs a local search through the space of committees to identify the Schwartz set of committees: all committees that are beaten only by other committees in the set. (However, the correctness of the algorithm depends on a currently unproved conjecture: that if improvement of a committee is possible, it can be done by replacing one member at a time.) The beatpath winner algorithm is run using all committees explored during the search for the Schwartz set. An interactive form also allows comparison of any two sets. However, the output of the system in this mode must be currently be interpreted with some caution: while no counterexamples have been found, there is no proof that the current implementation always finds the winning committee according to the above criteria.