CIVS supports an experimental mode in which it can be used to select multiple candidates while enforcing proportional representation. We refer to the possible sets of selected candidates as committees. The goal is to pick the best committee in a proportional way. Roughly speaking, this means that a set of voters can only influence a fraction of the selected committee that is proportional to the number of voters in that set.
For example, suppose that 60% of the voters want candidates a, b, c, d, and e, in that order, but the other 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, electing these five (a, b, c, d, e) is the right way to run the election. However, if the goal is to find a five-person committee that fairly represents the whole population, the committee abcde gives 40% of the population no representation at all. By contrast, the proportional representation algorithm used by CIVS elects the committee abcxy, achieving perfect proportional representation.
In general, if there are n blocs of voters who always choose candidates from their disjoint factions, the number of candidates from a given faction in the selected committee is proportional to the number of voters, except that the number of candidates may be rounded up or down.
Lifting preferences from candidates to committees is achieved through what we call f-preferences. A given voter has an f-preference for one possible committee A over another, B, if the voter prefers A to B when considering in each committee only the f candidates most preferred by that voter. For example, a voter has a 1-preference for committee A over committee B if the voter' favorite candidate in committee A is preferred by that voter over the voter's favorite candidate in committee B. The voter has a 2-preference for committee A over committee B if the two favorite candidates on committee 1 are preferred over the two favorite candidates on committee B. Determining whether a given voter prefers one pair (or generally, set) of candidates over another set is a separate issue that is discussed below.
Example. Suppose that a voter's ballot contains the ranking a > b > c > d > e. That is, candidate a is most preferred and candidate e is least preferred among those listed. Such a voter has a 1-preference for committee abc over committee bcd, because looking at the favorite candidate in each committee, we see a > b. In fact, the voter also has a 2-preference and a 3-preference, because b > c and also c > d. Considering instead the committees abe and ade, the voter has no 1-preference (the most-preferred candidate in each committee is a), but does have a 2-preference and a 3-preference for abe over ade because b>d, and therefore ab is preferred over ad (the 2-preference) and also abe is preferred over ade (the 3-preference).
A Condorcet method requires that we be able to be able to compare two choices pairwise, and derive the strength of the voters' preference between each pair. In this case the choices are committees rather than candidates. To compare two committees, we compute the aggregate f-preference of the voters for all values of f between 1 and k. The aggregate f-preference for committee A over committee B is the number of voters with an f-preference for A over B.
Suppose that the aggregate f-preference for committee A over committee B is v and that there are n voters overall. Then the aggregate f-preference for committee A over committee B is proportionally valid if v(k+1)/n ≥ f, or equivalently, if v/n ≥ f/(k+1). That is, the fraction of the voters with the preference must be at least as large as a fraction f/(k+1) of the committee on which the preference is being expressed.
To decide whether committee A is preferred over committee B, we find the largest f such that v voters have a proportionally valid aggregate f-preference for one of the two committees. This v we call the proportional preference for committee A over B. The aggregate k-preference for committee A over B we call the nonproportional preference, whether it is proportionally valid or not.
To find the committee that wins the election, we use some Condorcet method. The choice of Condorcet method is orthogonal to this proportional method, because it can be used with any Condorcet method applied at the committee level. Condorcet methods require that choices can be compared pairwise according to some total order; in this case, the committees are compared pairwise according to the proportional preferences between them. For k=1, this voting method is simply an ordinary Condorcet method. For larger k, it yields proportional results.
As an additional refinement, it is helpful to break ties between the proportional preferences of two committees by using the nonproportional preferences. This rule allows majorities to have their choice when the minority is indifferent.
Example. In the initial example, voters in the 60% bloc have no proportionally valid preference for abcde over abcxy because their maximum proportionally valid preference is a 3-preference (because 3/6 ≤ 60% < 4/6). The 40%, on the other hand, have a valid 2-preference for abcxy (because 2/6 ≤ 40% < 3/6). Therefore, abcxy beats abcde by an aggregate 2-preference of 40%–0%, and in fact, abcxy is the winning committee. Thus proportionality is achieved.
The factor (k+1) may be surprising in the condition for proportional validity, but it actually agrees with proportional representation election methods 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. With this algoritm, 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, both of which are 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.
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 exactly 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.
We deferred the question of how to decide whether a voter prefers one set of f candidates over another, where a set of candidates is a subset of a committee. In proportional representation mode, there is only one difference from the voter's perspective. 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. In combined-weights mode, the voter gives a nonnegative weight to each candidate instead of ranking the candidates. 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 x, y, and z, in that order, but would end up (because of the other voters' preferences) choosing between x and the pair yz. The algorithm can't tell just from the rankings whether the voter would prefer to have the better candidate x or greater representation under yz. Using weights, this can be determined: if x is given a weight of 10 and y and z have weights 8 and 6 respectively, then the voting algorithm will work on the voter's behalf towards electing yz in preference to x, because 14 > 10. However, if y and z were instead given weights 4 and 2, the voter would have expressed that x is preferred to yz because 6 < 10.
Best candidate. In best-candidate mode, the voter's goal is to get a single very good candidate elected, 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, x would be preferred to yz in either case, because x is preferred to y. If the most-preferred candidate in each committee is equally preferred, then the second-most preferred candidate is used, and so on up to candidate f.
The election method described above can be evaluated in a brute-force form by computing a preference matrix for all f in 1..k. This 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.