James Green-Armytage 

Computational Conservation in CPO-STV

Part One: Computational shortcuts for comparison of pairs of outcomes by single transferable vote

 

It is possible to use shortcuts in CPO-STV that would reduce the computational cost. Below is a revised sequence I have written for how to conduct a CPO-STV tally in a computationally conservative manner.

                The short of it is this: Outcomes don't need to be considered if they don't contain all of the candidates who achieve a surplus without any others being eliminated. Also, outcomes don't need to be considered if they contain a candidate who is not viable (see steps 1e-1j). The tally can then begin from a semi-arbitrary starting point, based on the results of a plain STV or sequential STV election. If no other outcomes beat or tie this outcome, then it is the final result. If other outcomes beat or tie it, then you search to see if any outcomes beat or tie *those* outcomes. You keep this up until you find either a clear Condorcet winner outcome, or a complete Schwartz set of outcomes. If you find a Schwartz set, then you can use a completion method to determine the winning outcomes, ignoring all the outcomes not in the Schwartz set.

 

[beginning of definition]

 

Part 1: Outcomes can be dismissed from consideration.

1a.           Begin from a state where all ballots are distributed to those candidates who rank first on those ballots. This is the starting point of any STV tally, or state S0.

1b.           If there are any candidates who have a quota before any others are eliminated, any outcomes that don't contain all of these candidates can be dismissed from consideration.

1c.           Distribute surpluses until no surpluses remain to be distributed. This is state S1.

1d.           "n" is the number of seats that the election will fill.

1e.           Given state S1, there are n candidates who have more top choice votes than all other candidates. This is the "n set".

1f.            "r1" is the number of top choice votes held by the candidate in the n set who has the fewest top choice votes.

1g.           If there are any candidates who are ranked on fewer than r1 ballots, then these candidates can be eliminated, and any outcomes containing these candidates can be dismissed from consideration.

1h.           Furthermore, if there are any candidates who are not ranked above *at least one* member of the n set on at least r1 ballots, then these candidates can be eliminated, and any outcomes containing these candidates can be dismissed from consideration.

1i.            Elimination of candidates in steps 1g, 1h, 1k, and 1l produces state S2. If any candidates in S2 have a surplus, then all surpluses are distributed to non-eliminated candidates until there are no surpluses left to distribute. This produces S3.

1j.            Steps 1e-1h can be repeated, using S3 as a starting point rather than S1. If any further candidates can be eliminated because of the transferred surplus, then step 1i can be repeated, followed by a repetition of steps 1e-1h. The repetition stops when either steps 1e-1h or 1i produce no change. The resulting state can be called SX.

 

(Note: None of the outcomes deemed irrelevant during part 1 will need to be considered in part 2. However, in part 2, state SX itself is *not* assumed as a starting point. True, candidates eliminated during part 1 may be assumed to be eliminated in part 2. However, surpluses transferred in part 1 should not automatically be transferred in part 2, because the rules of CPO-STV state that surpluses are not transferred under all circumstances.)

 

Part 2: Outcomes can be compared in a semi-arbitrary sequence, and consideration of new outcomes can stop when a clear Condorcet winner or complete Schwartz set has been found.

2a.           Conduct an initial STV count, producing outcome A.

2b.           Compare outcome A to all other non-dismissed outcomes. If no outcomes beat or tie outcome A, then outcome A is a clear winner, and the election is decided.

2c.           If there are any outcomes (outcome B, for example) which beat or tie outcome A, store both outcomes A and B, along with the results of their pairwise competition.

2d.           Then, compare outcome B with all other non-dismissed outcomes, to see if any outcomes beat or tie outcome B. If no outcomes beat or tie outcome B, then it is a clear winner, and the election is decided.

2e.           If there are outcomes which beat or tie outcome B, or if there are other outcomes which beat or tie outcome A, then these are outcomes C, D, E, etc.

2f.            Compare all such outcomes with all other non-dismissed outcomes. If more outcomes are found which beat or tie these, then compare them with all other non-dismissed outcomes, and so on.

2g.           Continue this process until you have either found a clear winner, or have found a complete Schwartz set. (Here, the Schwartz set is the union of minimal undominated sets. Note that the Schwartz set will not necessarily contain outcomes A, B, C, etc., although it is likely that it will.)

2h.           If a clear winner is found, then the election is decided.

2i.            If a complete Schwartz set is found, then dismiss all outcomes not in the Schwartz set from consideration.

2j.            Given the Schwartz set, conduct your preferred Condorcet completion method, for example ranked pairs or beatpath.

2k.           The outcome which wins this completion method is the final result of the election.

 

Note: In some cases it may save more time to do a "sequential STV" count as the preliminary count in step 2a, because a clear sequential STV winner is more likely to be a CPO-STV winner than a plain STV winner would be. (The definition of sequential STV I am using is at

[http://www.electoral-reform.org.uk/publications/votingmatters/15P4.htm].) If a loop is found between multiple outcomes, then the process from 2b could continue from any of these outcomes. I would say that sequential STV would make a better starting point for the above process than plain STV.

 

[end of definition]

 

                So, those are the ideas for shortcuts that I have come up with so far.

                I found the process of eliminating candidates from consideration to be the most difficult part. As far as I know, my method (steps 1e-1h, etc.) cannot exclude any viable candidates. Whether another method can exclude more candidates than this from the beginning, still without excluding any viable candidates, I don't know.

                This shortcut method should work whether one uses a Meek or Warren surplus rule.

                Exactly how much these shortcuts would reduce the computational cost of a CPO-STV election, I don't know. Whether it would make a tally that required a supercomputer possible on a personal computer, or a tally that required several days possible in a few hours, I'm not sure.

 

 

Part Two: Local CPO-STV

 

Here is a proposal for a computationally cheaper (although slightly compromised, of course) version of CPO-STV. It could be called "local CPO-STV," or CPO-STV lite. Perhaps I am wrong, but I see this method as being marginally more elegant and decisive than sequential STV, while maintaining a fairly moderate computational cost.

 

Part one: Identify non-viable candidates and outcomes. (See “CPO-STV shortcuts.”)

 

Part two: Begin with an initial outcome, and search for an outcome with local stability through one-candidate substitutions.

1. Do an initial STV count, producing an initial outcome ("outcome A").

2. Compare outcome A with all one-candidate substitutions from A (all possible outcomes that differ from outcome A only by the substitution of one candidate, except for those already dismissed from consideration in part one). If outcome A beats all of its one-candidate substitutions, then it has local stability and is declared to be the final result.

3. If outcome A is beaten or tied by another outcome or other outcomes ("outcome B", "outcome C", etc.), such outcomes are added to the "set of contending outcomes", or "contender set".

4. All outcomes in the contender set are compared with all of their one-candidate substitutions, excepting those that have been dismissed from consideration, and those which are already in the contender set.

                If any such one-candidate substitution outcomes beat or tie the member of the contender set that they are being compared with, then they are added to the contender set.

5. When no members of the contender set are beaten or tied by a one-candidates substitution not already in the set, then the set is closed.

6. All candidates in the contender set are compared to one another, and the winning outcome is decided by a Condorcet completion method (such as ranked pairs or beatpath).