Possible trick for counting SPAV (and cardinal PR) faster

So in keeping in line with my earlier idea of using negative numbers to do pairwise counting faster, I was thinking that in SPAV, there are actually two ways of finding the new vote totals when looking at a new round:

  • Traditional approach: Add up all of the ballots’ approvals again, reweighting certain ballots as necessary.
  • Negative approach: In each given round, put the ballots into piles depending on how much reweighting they have been through (i.e. all of the ballots with 1/2 weight left are in the same pile, etc.) If some ballots in a pile need to be reweighted, then reweight the ballot, move it to a new pile, and only count the difference in strength of approval for each candidate that ballot approves (from before its reweighting in the current round and after). These differences will be negative numbers which can be added up for each and every ballot. Once every ballot has been counted, the negative numbers are applied to (added to) the vote totals for each candidate from the previous round to find the current round vote total.

As an example of the second approach, suppose you have a winner in the first round of SPAV, and 30 of 100 ballots approve them. Because 70 ballots’ vote strengths won’t have changed, there is no need to re-count their approvals; for the 30 ballots, because they have now lost 1/2 of their weight, half of a negative vote is counted for each candidate that they approved. By first adding up all of the negative approvals, and then adding these to the vote totals from the previous round, you can then find how much approval each of those ballots’ approved candidates has lost because of their supporters’ ballots’ reweighting.

  • By doing this, you’re only making counting and reweighting marks for 30 ballots, rather than additionally making counting marks for 70 ballots.

If 20 ballots approve both the first-round and second-round SPAV winner, then these ballots are now at 1/3rd weight rather than 1/2. So now, 1/6th of a negative approval is counted for each of the candidates they approved (1/2 - 1/3). This (-1/6)th of a vote is then added to the vote totals (approval totals) from the second round to find the vote totals of the third round (i.e. with which you can find the third-round winner), and so on.

Here is a table showing how much weight a ballot has lost (i.e. amount of negative approval to be applied) from the previous round when it is at a certain amount of weight:

Number of winners a ballot has approved: 0 1 2 3 4 5
Amount of weight the ballot currently has: 1 (100%) 1/2 1/3 1/4 1/5 1/6
Amount of weight lost from previous round: 0 1/2 1/6 1/12 1/20 1/30

The pattern is for each additional winner approved, that’s 2*(number of winners approved) added to the denominator of amount of weight lost from the amount of weight lost for approving one less winner. So, for example, add 2*(2)=4 to 2 to get 1/6 weight lost for a ballot that approves 2 winners rather than 1, rather than 1/2 weight lost for a ballot that approves 1 winner rather than 0.

I suspect this type of negative counting is far too burdensome for score-based cardinal PR, and probably even for most other Approval PR methods, but it might help for SPAV.

P.S. Here is a counting trick for Approval voting that reduces the worst-case number of marks required to count a ballot from [number of candidates] to roughly half that: for each ballot that approves more than half of the candidates, because it can be thought of as disapproving fewer than half of the candidates, you can just count the ballot as “approving every candidate” (1 mark) and also count each candidate it disapproves. When the precincts send their totals, they send an additional count of how many voters approved every candidate and disapproved each individual candidate. One approval is added to each (non-write-in) candidate’s vote totals for every voter approving every candidate, and one approval is subtracted from a candidate’s vote total for every voter disapproving them.