[EM] Multiwinner Methods Request

[Greg Nisbet]

So far the following multiwinner methods have been suggested or I know of:

CPOSTV

Schulze STV

QBS (this is what I meant by Proportional Borda, sorry!)
http://en.wikipedia.org/wiki/Quota_Borda_system

QanythingS (look at the description of QBS, it effectively allows a
black box single winner method to be used in place of Borda Count).

Naive Adaptations -- you can do this with just about anything. Not
proportional at all but enh.

STV various ballot transfer rules

IRNRSTV (**)

BordaSTV (**)

Sainte-Lague (and the 1.4 divisor variant)

Largest Rem (various quotas)

D'hondt

All party-flavored methods can be made with open/closed/free lists too
so its great.

SNTV

Limited vote

Block vote

Preferential Block

RRV

PAV

PRV

Cumulative vote

Districted crap

MMP (combination of districted crap and some party alloc.)

Asset Voting (*)

Forest Simmons' methods:
http://www.rangevoting.org/cgi-bin/DoPassword.cgi (I'll include a copy
of the page at the bottom if you don't feel like joining CRV)

===================

I do need some single winner methods as well to test for QanythingS,
districted crap, and naive crap. I'm not suggesting all [insert large
number] that we have ever discussed. FPTP and Range make the list.
Schulze too. Any other suggestions? (I'd like to limit it to about ten
if that's OK).

=======================================



Puzzle #15 (open ¨C multiwinner EP & PR voting systems):
Puzzle statement: The goal of a "multiwinner voting system" is to,
from the "votes," determine W winners from C candidates where 0<W<C.
The system is "proportional" (PR) if, supposing the voters and
candidates each are colored one of a finite number of colors (i.e.
voter Joe is "green," candidate Mary is "black"), and supposing each
voter prefers each candidate of his own color above all others (and
says so in his vote), then the winning slate of candidates will have
the same color composition as the voters (up to unavoidable
integer-roundoff effects and limitations caused by perhaps too few
candidates existing of some color). For example, the famous
Hare/Droop-STV system [single transferable vote with "Droop quotas"
and "reweighting"] invented by Hare and Droop in 1800s England, is PR.
That is, if there are 60% red, 30% black, and 10% white voters, then
we will automatically get 6,3, and 1 red, black, and white winners
respectively in a Hare/Droop-STV election with W=10 assuming enough
candidates of each color are available. The voting system is required
to depend upon the votes only, hence does not know the candidate- or
voter-colors. "Votes" are either preference orderings or numerical
scores (and perhaps other things would also be permissible). The
system is "efficiently parallelizable" (EP) if an election with an
enormous number of voters can be handled by efficient combination of
subresults computed in each election district from only the votes in
that district, and these subresults consist of a very small amount of
data compared to the large number of votes that they summarize. For EP
to hold, we require all this data to be transmitted unidirectionally,
i.e. voters¡údistrict-agency¡úcentral-agency. For example the plurality
system is EP because each district can simply compute the total vote
counts for each candidate, then pass only these subtotals on to the
central election agency.

Question: Does there exist a nontrivial multiwinner voting system
which is both PR and EP? (And if "yes," then please construct one!)

Answer (by Forest W. Simmons 1 Feb 2007)
In puzzle 15 at http://rangevoting.org/PuzzlePage.html Warren D. Smith
had posed the open problem of whether there could be a multiwinner
voting method which both

enjoyed provable "proportionality"
was "countable in precincts" which only had to pass on "subtotals" to
central tabulation, i.e. a much smaller amount of info than passing
along all ballots.
There had been methods (like Hare/Droop reweighted STV, and reweighted
range voting RRV) satisfying #1, and there also were methods (like
multiwinner plurality voting) satisfying #2, but nothing satisfying
both.

Well, Forest Simmons in a rather hard-to-decipher email to me solving
my puzzle 15 (but I did decipher it!) invented a new class of methods
which enjoy both properties at the same time. Hot. And furthermore,
they, at least at first glance, look damn good. I will describe two
Simmons methods below. The first is an analogue of STV and is based on
rank-order ballots. It looks at least at first glance to be better
than STV. The other is an analogue of reweighted-range-voting and is
based on range-type ballots. It looks at first glance to be better
than RRV. One can then also make plenty of other Simmons-type methods
once one sees his basic ideas.

SIMMONS-BORDA METHOD:

**Voters:**
1. Let there be C candidates and V voters.
2. Each voter submits a strict-rank-order ballot ranking all C
candidates in order.
**Precincts:**
3. Reinterpret each ballot as a C-vector of the Borda score
it implies for each candidate K in entry K.
That is, if the ballot ranks the Kth candidate Rth, then
entry K of the vector is C-R.
4. For each candidate X:
vector-sum all the ballots that rank X top, and let the
resulting sum-vector be the Xth row of a CxC matrix M.
5. Transmit the matrix M to central tabulation. This is CxC
no matter how many voters there are in that precinct.
**Central tabulation:**
6. Sum all the matries M you receive from all precincts, to get
a summed-matrix S.
7. Reinterpret each C-vector row of S as a rank-order ballot
(ordering the candidates in order of decreasing vectr-entry)
but a WEIGHTED rank order ballot.  That is, each such ballot
not only gives a rank-ordering of the C candidates, but
also comes with a real number weight.  (The weight is the largest
entry in the vector.)
8. So we now have (in the view of central tabulation) C weighted
rank order ballots, in a C-candidate election. Use a PR-STV
method to handle this election. (Note: PR-STV methods can
accept weighted ballots not just ballots. They reweight as they
proceed.) It now computes and announces the winners as usual.

SIMMONS-RANGE METHOD:

**Voters:**
1. Let there be C candidates and V voters.
2. Each voter submits a range-type C-vector ballot scoring all C
candidates within some fixed allowable score range such as [0,99].
**Precincts:**
3. For each candidate X:
Let the Xth row of a matrix M be the sum, over all ballots
which rank X top or co-equal top, of
      BallotVector / (# of coequal-topranked candidates in that ballot)
Also keep track, for each row of M, of its "weight" which is the sum
over all ballots used to make that row, of
      1 / (# of coequal-topranked candidates in that ballot).
4. Transmit the matrix M and th row weights to central tabulation. This is a
CxC matrix and a C-vector of weights no matter how many voters there
are in that
precinct.
**Central tabulation:**
5. Sum all the matries M you receive from all precincts, to get
a summed-matrix S.
6. Reinterpret each C-vector row of S as a range-type vector ballot.
7. So we now have (in the view of central tabulation) C weighted
range-esque ballots, in a C-candidate election.  Use RRV
method to handle this election. (Note: RRV can
accept weighted ballots just fine, after
tiny changes in the precise details of the algorithm.
Specifically just regard a ballot with weight W as equivalent to
the sum of W normal ballots, i.e. as a ballot in the range [0, 99*W]
instead of [0, 99].)
It now computes and announces the winners as usual.

WHY IT WORKS:

The idea is that if every cast ballot happens to obey the
color-constraint (that every voter and every candidate has a "color"
and voters always rank their-color candidates ahead of all candidates
of other colors) then every ballot ranking a red candidate top,
automatically will rank all red candidates above all non-red candidates.
And the vector sum of such a set of red-top ballots, also will
automatically do that. That's key. So now, if the color
constraints hold, then we can just use the regular
color-proportionality theorems obeyed by RRV and STV to assure
proportional representation of color classes. If the color
constraints do not hold, that also is OK because the usual
proportionality theorems only claim to work if they do hold.

EXAMPLE OF SIMMONS-RANGE:

in precinct 1:
voter1:  A=99 B=40 D=30 C=0
voter2:  B=99 A=70 C=50 D=0
voter3:  D=99 A=B=C=0
in precinct 2:
voter4:  C=99 B=40 D=30 A=0
voter5:  D=99 A=50 B=40 C=0
voter6:  A=99 B=C=D=0
[Note: the color classes are {A,B}, {C}, and {D} and we shall hold a
4-candidate 2-winner 6-voter election.]
The matrix M from precinct 1, and its row-weights:
99 40 0  30    ;1
70 99 50 0     ;1
0  0  0  0     ;0
0  0  0  99    ;1
The matrix M from precinct 2, and its row-weights:
99 0  0  0     ;1
0  0  0  0     ;0
0  40 99 30    ;1
50 40 0  99    ;1
summed matrix S=M1+M2:
198 40 0  30   ;2
 70 99 50 0    ;1
 0  40 99 30   ;1
 50 40 0  198  ;2
where the numbers after the semicolons
count how many ballots went into that matrix row.
Now central regards this as a 4-candidate 4-voter election and
runs "reweighted range voting."  The first winner is A because
the summed ballot vectors (sum of matrix row-vectors) is
318 219 149 259
and A has the largest sum 318.
RRV now reweights the ballots by multiplying them by 99*y/(99*y+x)
where x is the score  that ballot had for A and y is the number
of original ballots that got agglomerated to make this super-ballot.
[Other reweighting formulas such as 99*y/(99*y-49+x) would also be possible,
but I digress.   This is a modified form of RRV to handle agglomerated ballots.]
The second winner is then D.
(I won't promise I made no arithmetic errors.)

In my opinion this is an excellent idea and it may overturn the whole
area of multiwinner election methods.
-Warren D. Smith Feb. 2007.



Return to puzzle page

Return to main page