Some possible ways to speed up computation of Condorcet PR methods

Continuing the discussion from:

This post will be about ways to reduce the number of outcomes that must be compared to get the deterministic winning result for a Condorcet PR method. The ideas that are more hypothetical/uncertain/unrefined will be noted with a ** ().

Worth noting that below, it’s written that Condorcet PR methods are Droop-proportional, but this actually hasn’t been proven. However, it’s possible to modify a Condorcet PR method to be Droop-proportional by first eliminating all outcomes that fail Droop PR, so use this modification as necessary.

The ideas already noted in the literature:

  • Candidates with a Droop quota of 1st choices must win. (Outcomes that don’t feature “must-win” candidates should be ignored)
  • The STV outcome can be checked to see if it can win all of its pairwise matchups.

Condorcet PR methods are Droop-proportional, therefore we can eliminate all outcomes that don’t feature proportionally correct combinations of candidates from Droop solid coalitions.
** (Finding Droop solid coalitions can be done with the following steps:

  • Eliminate all candidates who aren’t ranked 1st on any ballots, or who aren’t ranked above last place by at least a Droop quota of ballots. (A candidate may be ranked 2nd by everyone in their Droop coalition and thus eliminated by this step, but that doesn’t matter for the purposes of finding solid coalitions, because we only need to find at least one of a coalition’s preferred candidates to find the coalition, and it is guaranteed that one of the coalition-supported candidates will have 1st choice votes).

  • Sequentially add ranks in this algorithm until as many PR claims are assigned as seats to be filled, or all ranks have been added in:
    If there are candidates ranked 1st by a Droop quota of ballots, they have a Droop solid coalition, so mark that candidate as having a PR claim, mark their ballots as being a solid coalition, and then proportionally spend a Droop quota’s worth of those ballots. Then, look at both the 1st and 2nd ranks, and if a candidate is ranked by at least a Droop quota of ballots within these ranks, determine whether a Droop quota of the ballots that rank them are a Droop solid coalition (this can be done by checking whether, of the candidates that appear within the 1st and 2nd ranks of those ballots, a set of them can be brute-forcedly found that can a) get a Droop Quota of votes for them in a pairwise contest against all other candidates and b) can’t be shrunk further i.e. a subset of those candidates can’t do the same).

  • (Note on the previous step: If you eliminated a candidate in the first step, but that candidate is ranked by the ballots you’re examining, you’d have to re-include them to determine whether they also fit into a solid coalition, if one exists, within those ballots.)

  • If they are, then mark the candidates in the solid coalition as all having a (overlapping?) PR claim, mark those ballots as being in a solid coalition, and proportionally spend the ballots. If not, eliminate that candidate.

** (Note that if, say, 3 Droop Quotas:
put the same candidate as their 1st choice,
1 of the quotas puts their own preferred candidate as its 2nd choice, with the remaining 2 quotas putting a bunch of no-hopers 2nd,
and each of the 3 quotas puts their own uniquely preferred candidate as their 3rd choice,
then the unanimous 1st choice has a stronger proportionality claim than any quota’s 2nd or 3rd choice candidate, and therefore we can eliminate any outcomes that feature the candidates with weaker proportionality claims but not the higher ones. If, say, the 3 Droop Quotas ranked 2 candidates co-equal 1st, then the algorithm should properly identify that none of their 3rd choice candidates have a valid PR claim.)

** (One useful idea would be to identify a Droop quota or more of ballots where, if all candidates “guaranteed to lose” are deleted from the votes, that quota of ballots becomes a solid coalition. Such a quota’s preferred candidates would have PR claims.
It needs to be figured out how to determine when a candidate is “guaranteed to lose”, but there is probably some way that is fairly simple that can help quickly identify a few more proportionality claims.
One situation where this idea helps: 3 Droop Quotas of candidates all support “guaranteed to lose” candidates as their 1st choice, but all support the same candidate as their 2nd choice, and then each of the 3 quotas prefers their own candidate as 3rd choice. We’d be able to see that there are actually 3 proportionality claims here, and that the unanimous 2nd choice candidate has a stronger proportionality claim than any of the 3 candidates ranked 3rd.)

** (With regards to solid coalitions where a few candidates interrupt the coalition, I think it can be proven that either the candidates interrupting the coalition must win, or someone in the solid coalition must win.)

** (It’s possible, once solid coalition-preferred candidates are identified, to try all of the outcomes featuring one solid coalition’s preferred candidates, and discover that certain candidates in other solid coalitions can’t win in any permutation of outcomes featuring any of the first solid coalition’s preferred candidates. This works when looking at the second coalition, etc.)

It can at times be relevant to test certain outcomes before others i.e. if it can be ascertained algorithmically that one outcome is more likely to be a Condorcet winner than another, then test that outcome’s pairwise matchups first.