[ESD] Multiple winners methods

[Forest Simmons]

This is the first installment on the "Condorcet Flavored" PR methods that
I promised a few weeks ago.

As Joe Weinstein has pointed out more than once, all of the standard
ballot types including lone mark, approval, ranked (i.e. "preference"),
range, grade, and dyadic, can be converted into ratings on a scale of zero
to one without loss of information.

For that reason I will assume ballots of Cardinal Ratings on a scale of
zero to one, inclusive.  The reader may easily translate everything into
the setting of his/her favorite ballot style.

To get a Condorcet Flavored PR method our first task is to have a way of
comparing the PR desirability of two subsets of candidates.  In other
words, in a three winner election, given two three member subsets
A={A1,A2,A3} and B={B1,B2,B3}, how do we decide which of these gives
fairest representation of the voters?  In other words, which of the two
subsets A and B "covers" the electorate better according to the
information contained in the ballots?

Let's concentrate for a few minutes on the ballot of one voter.

By using the Cardinal Ratings on that ballot let's see if we can
ascertain the relative satisfaction to this voter of having subset A win
instead of subset B.

We need the notion of co-rating.  The co-rating is the rating subtracted
from one, the max possible rating.

Let k represent the sum of cardinal ratings on this ballot for the
members of subset A, and let m represent the sum of the complementary
ratings for the members of the set B-A.

If k is large, then the members of A have an high average rating
on this ballot.  If m is large, then the members of B which are not
members of A have high co-ratings (on average) which means that they are
undesirable.

Therefore, the larger the sum  k+m  the more desirable subset A relative
to subset B according to this ballot.

It is tempting to use this value (k+m) in the (A,B) position of the
pairwise matrix to be summed over all ballots.

However, that would not result in a PR system of representation as you can
see for yourself from standard examples of PR elections.

The reason this doesn't result in PR coverage is that the value (k+m)
gives equal weight to all of the layers of satisfaction, so to speak.

To achieve PR, the upper layers of satisfaction have to be increasingly
discounted, similar to the way that they are discounted in Proportional
Approval Voting (PAV), which gives a score of only 1 + 1/2 + ... + 1/n to
a subset with n layers of approval.

In the present context some type of increasing but concave down
transformation has to be applied to the value (k+m) to effect the desired
"discount."

It turns out that it is sufficient to replace the value (k+m) with
log(1+k+m), as you can see for yourself from standard examples of PR
elections.

In a later installment I will provide examples for the lazy, and I will
give further explanation of why it works.  But if you understand PAV, and
you realize that the derivative of log(1+x) is proportional to 1/(1+x),
then you will see that this transformation gives the proper discount for
the additional representation or satisfaction in going from x to x plus
delta x.

To summarize this installment so far, I have shown how to construct the
pairwise matrix for comparing subsets in their ability to provide
Proportional Representation according to the information in the ballots.

The Condorcet flavor that we desire requires us to make these comparisons
without regard to candidates outside the union of the two subsets A and B
being compared, so we make one modification in the above procedure:

On each ballot before calculating the values of k and m for the ordered
pair of subsets (A,B), the Cardinal Ratings are relativized [i.e. rescaled
so that the max and min ratings among the members of (A union B) are one
and zero, respectively, unless all of the ratings are identical, in which
case they are left untouched].


Suppose that there are K candidates in an election for W positions to be
filled. Once the pairwise matrix is constructed according to the above
instructions it is just a square matrix with C(K,W)^2 non-negative entries
which can be processed according to the rules of, say, SSD or Ranked
Pairs.

Of course, if K and W are too large, the binomial coefficient C(K,W) may
be so large as to make the computation intractable. So like PAV this
method has to be restricted to small values of W. For large values of W a
sequential version of this method, analogous to sequential PAV can be
used.

In the sequential version the first member of the winner's circle is
chosen by a single winner version of Condorcet.

Subsequent winners are added by comparing subsets consisting of the
current winner's circle augmented by one candidate using the method
described above.

In the class of non-partisan PR methods (i.e. non-list methods) when
possible good non-sequential methods like PAV and PR Condorcet should be
employed, since sequential methods (like PR-STV) cannot be relied upon to
give the same quality results.

This is analogous to bin packing, the traveling salesman problem, etc.
Sequential methods cannot be relied upon for optimal solutions, but the
intractability of the problems require sequential methods except when the
sets involved are relatively small.

Well, that's enough for one installment.

Forest

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em