Batch Elimination option for STV

[yezr]

We now have some jurisdictions using RCTab for STV. We've had requests to implement batch elimination in STV.

Current Behavior

In IRV I have a checkbox for "Use Batch Elimination". When I switch the Winner Election Mode to Multi-Winner that option is greyed out.

Expected Behavior

The checkbox for "Use Batch Elimination" remains as a toggleable option for STV. When enabled, candidates are batch eliminated when possible.

Open Questions

• Batch elimination in IRV is fairly straightforward. What exactly is the math for batch eliminating in STV?

[greg-dennis]

There is one notable subtlety. In single-seat elections, batch elimination applies to the largest set of candidates which together do not have more votes than the next highest vote-getter. But if you follow the same rule with STV, you might alter the result, since a candidate in that batch may put another candidate over threshold earlier than they otherwise might.

I guess the safe rule is: the largest set of candidates which together do not have more votes than the next highest voter-getter and do not have more than the difference between the election threshold and the highest vote-getter?

[yezr]

the largest set of candidates which together do not have more votes than the next highest voter-getter and do not have more than the difference between the election threshold and the highest vote-getter

So that second part is making sure everyone we're getting ready to batch eliminate together couldn't jump to be elected in that round? Do you have any examples with rankings we could put into a test?

[artoonie]

FWIW, I hate batch elimination. Condensing rounds should be done in results reporting, not during tabulation. But my preferences don't impact what's in statute :)

[yezr]

Matching statute is for sure important if someone requires this.

Also, many jurisdictions have post-election audit requirements. When hand counting RCV results for an audit or recount, batch elimination can make a not-insignificant difference in the amount of work required to do that. Showing that RCTab supports lightening the load, even a little, can be a big boost to buy-in.

[greg-dennis]

Can someone check my work? Here's an example of a 4 seat election with 1000 voters, quota is 201 votes:

201 ballots: A
201 ballots: B
200 ballots: C>E
151 ballots: D
150 ballots: E
 50 ballots: F>C>D
 46 ballots: G>E
  1 ballots: G>C>D

If we eliminate one candidate at a time, the rounds proceed as follows:

1. A and B are elected in the first round with no surplus.
2. G is eliminated
3. C is elected with no surplus
4. F is eliminated
5. D is elected

Winners are A, B, C, and D

If we batch eliminate using the criteria for single-seat elections, without regard to putting another candidate over threshold:

1. A and B are elected in the first round with no surplus.
2. F and G are batch eliminated
3. C is elected with a 50 vote surplus; ~39.84 votes transfer to E and ~10.16 votes transfer to D
4. E is elected

Winners are A, B, C, and E

There's probably a simpler example.

[greg-dennis]

A few more notes on this. It turns out the rule I suggested in #917 (comment) is also written up in Wikipedia's section on "bulk exclusions":

"Any candidates with a tally less than a breakpoint can be included in a bulk exclusion process provided the value of the associated running sum is not greater than the difference between the total value of the highest hopeful's tally and the quota."

I'll add one more benefit to having batch elimination as an option: it makes it less likely that ties for last place need to broken randomly. There are some jurisdictions, including the entire state of Massachusetts, where breaking ties by lot is not legal, so any ways to limit the likelihood of an exact tie is appreciated. To that end, some systems, including DemocracySuite from Dominion, provide a batch elimination option that only applies when candidates are tied for last place. I've filed a feature request in #921 in case you want to consider it.