## Condorcet Internet Voting Service |
About CIVS Public polls Create new poll Security and privacy FAQ |

## Proportional Representation in CIVS |

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, 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, 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*.
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*. 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 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.