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!)
In puzzle 15 at /PuzzlePage.html Warren D. Smith had posed the open problem of whether there could be a multiwinner voting method which both
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.