[EM] CPO-STV shortcuts

[James Green-Armytage]

Rob Speer wrote:

>But has anyone devised a method to compare entire slates of candidates
>that reaches a decision without, well, comparing every possible slate of
>candidates?

I (James) reply:
	As far as I know, CPO-STV is the best proportional method available in
terms of fairness of results, responsiveness, fluidity, utility,
precision, etc., but it is also the most computationally expensive by far.
	However, it is possible to use shortcuts in CPO-STV that would reduce the
computational cost.

	I have come up with a few ideas for such shortcuts, and 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. 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, or a
complete Schwartz set. If you find a Schwartz set, then you can use a
completion method to determine the winner, 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. (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 each 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. My intuition is that it is possible, but
the above is the best I have come up with so far.
	As far as I know, this shortcut method should work whether one uses a
Droop or Hare quota, and it 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.

	Anyway, I welcome any criticisms, comments, suggestions, or alternate
ideas that might work better for the same purpose.

-- James Green-Armytage