[EM] New multi-seat method: Transferable Cumulative Vote with Approval Loser Elimination (TCVALE)
Dan Bishop
daniel-j-bishop at neo.tamu.edu
Tue Apr 25 22:08:43 PDT 2006
Antonio Oneala has recently spoken in favor of Proportional Approval
Voting (PAV). Unfortunately, adoption of PAV is likely to be hindered
by the computational complexity of the "list all the possible outcomes"
step. Which led me to ask, "How can we achieve proportional
representation with approval-style ballots in polynomial time?" Of
course, one approximate way is to use cumulative voting, where N
approval votes on one ballot = 1/N vote for the N candidates). But this
could be improved:
1. Use an STV-like method to transfer excess votes from candidates with
a lot of them, to make the results more proportional.
2. Approval Voting is independent of irrelevant alternatives (assuming
people don't change their votes when the candidate set changes). So use
that, rather than the cumulative votes, to decide the elimination order
for candidates.
*** TCVALE DEFINITION AND EXAMPLE ***
Consider an election for 3 seats with the ballots
20: A
25: AB
35: ABC
20: XYZ
10: YZ
10: Z
STEP 1: Compute the approval votes for each candidate.
A: 80
B: 60
C: 35
X: 20
Y: 30
Z: 40
In ascending order of approval, the candidates are X, Y, C, Z, B, A.
STEP 2: Compute the quota (example will use N-B). The quota is based on
the number of *voters* (who each get one cumulate vote), not the number
of approval votes.
Q = V/(S+1) = 120/(3+1) = 30
STEP 3: Each ballot with N non-eliminated candidates gives 1/N of a vote
to each of the candidates.
20: 1 A
25: 1/2 A + 1/2 B
35: 1/3 A + 1/3 B + 1/3 C
20: 1/3 X + 1/3 Y + 1/3 Z
10: 1/2 Y + 1/2 Z
10: 1 Z
Adding the votes gives:
A: 44 + 1/6
B: 24 + 1/6
C: 11 + 2/3
X: 6 + 2/3
Y: 11 + 2/3
Z: 21 + 2/3
Total votes: 120
STEP 4: If a candidate exceeds the quota, declare them elected. If the
number of elected candidates equals the number of seats, then stop. If
no candidate exceeds the quota, eliminate the candidate with the lowest
approval among those not yet declared elected, restore elected
candidates to the ballots, restore all the ballot weights to 1, and go
to Step 8.
In the example, A is declared elected.
STEP 5: Compute the weight of each candidate. For candidates who exceed
quota, the weight is (extra votes)/(total votes). For other candidates,
the weight is 1.
A: (14 + 1/6) / (44 + 1/6) = 17/53
B, C, X, Y, Z: 1
STEP 6: Weight each ballot by the average of the weights of the
non-eliminated candidates it approves.
A: weight = 17/53
AB: weight = (17/53 + 1) / 2 = 35/53
ABC: weight = (17/53 + 1 + 1) / 3 = 41/53
XYZ: weight = (1 + 1 + 1) / 3 = 1
YZ: weight = (1 + 1) / 2 = 1
Z: weight = 1
The reweighted ballots are:
340/53: A
875/53: AB
1435/53: ABC
20: XYZ
10: YZ
10: Z
Total votes: 90
STEP 7: Remove elected candidates from the ballots.
340/53: (exhausted)
875/53: B
1435/53: BC
20: XYZ
10: YZ
10: Z
STEP 8: Recompute the quota based on the weight of the *nonexhausted
ballots*. If you came here from Step 7 (i.e., have subtracted the votes
of elected candidates), use the number of seats *remaining* instead of
the total number of seats.
Nonexhausted ballot weight = 90-340/53 = 4430/53 = 83 + 31/53
New quota: (83 + 31/53) / (2 + 1) = 4430/159 = 27 + 137/159
STEP 9: Go back to Step 3.
[step 3]
875/53: 1 B
1435/53: 1/2 B + 1/2 C
20: 1/3 X + 1/3 Y + 1/3 Z
10: 1/2 Y + 1/2 Z
10: 1 Z
B: 3185/106 = 30 + 5/106 (exceeds quota by 695/318 votes)
C: 1435/106 = 13 + 57/106
X: 20/3 = 6 + 2/3
Y: 35/3 = 8 + 1/3
Z: 65/3 = 21 + 2/3
Total votes: 4430/53 = 83 + 31/53
[step 4]
B is declared elected.
[step 5]
B: weight = (695/318)/(3185/106) = 139/1911
C, X, Y, Z: weight = 1
[step 6]
B: weight = 139/1911
BC: weight = (139/1911 + 1) / 2 = 1025/1911
XYZ, YZ, Z: weight = 1
Reweighted ballots are:
875/53 * 139/1911 = 17375/14469: B
1435/53 * 1025/1911 = 210125/14469: BC
20: XYZ
10: YZ
10: Z
Total votes: 8860/159
[step 7]
210125/14469: C
20: XYZ
10: YZ
10: Z
[step 8]
Nonexhausted ballot weight: 788885/14469
Seats remaining: 1
New quota = (788885/14469) / (1 + 1) = 788885/28938 = 27 + 7559/28938
[step 9 -> step 3]
210125/14469: 1 C
20: 1/3 X + 1/3 Y + 1/3 Z
10: 1/2 Y + 1/2 Z
10: 1 Z
C: 210125/14469 = 14 + 7559/14469
X: 20/3 = 6 + 2/3
Y: 35/3 = 11 + 2/3
Z: 65/3 = 21 + 2/3
[step 4]
No candidate meets the quota. Eliminate X, the candidate with the
lowest approval. The status of each candidate is now:
A: elected
B: elected
C: in play
X: eliminated
Y: in play
Z: in play
Restore the ballots to their original state, except for the eliminated
candidates.
20: A
25: AB
35: ABC
30: YZ
10: Z
[step 8]
With no exhausted ballots, the quota returns to the original 30.
[step 9 -> step 3]
20: 1 A
25: 1/2 A + 1/2 B
35: 1/3 A + 1/3 B + 1/3 C
30: 1/2 Y + 1/2 Z
10: 1 Z
A: 265/6 = 44+1/6 (exceeds quota by 14+1/6)
B: 145/6 = 24+1/6
C: 35/3 = 11+2/3
Y: 15
Z: 25
Total votes: 120
(Note that with neither Y nor Z meeting quota, the only transfers are
the same ones done earlier. A and B will be declared elected, and no
others. That brings us to...)
[step 4]
The next-lowest approved candidate, Y is eliminated. The status of each
candidate is now:
A: elected
B: elected
C: in play
X: eliminated
Y: eliminated
Z: in play
The original ballots without the eliminated candidates are:
20: A
25: AB
35: ABC
40: Z
Z has 40 votes, more than a quota, so is declared elected.
The winning candidates are A, B, and Z, as one would intuitively expect.
More information about the Election-Methods
mailing list