[EM] New multi-seat method: Transferable Cumulative Vote with Approval Loser Elimination (TCVALE)

[Dan Bishop]

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.