Vote-counting: election-system analysis

[lpetrich]

So -- and I don't know whether this is apropos to what I just wrote -- I like the idea of sequentially eliminating losers until there is an eventual winner.

Interesting variation on IRV. One eliminates those that do best in last place rather than those who do worst in first place. It has already been invented: it's Coombs's method. But the count that you then posted was IRV.

Coombs's method:

• Round 1
  • Sausage: 37
  • Anchovies: 16
  • Artichoke: 0
  • Mushrooms: 0
  • Peppers: 0
• Round 2
  • Anchovies: 29
  • Peppers: 16
  • Artichoke: 10
  • Mushrooms: 0
• Round 3
  • Peppers: 34
  • Artichoke: 12
  • Mushrooms: 9
• Round 4
  • Artichoke: 28
  • Mushrooms: 27
• Round 5
  • Mushrooms: 55

Another variation is to eliminate the Condorcet loser, if there is one, while falling back to eliminating the one with the lowest first-place or highest last-place count.

For IRV, Benham's method is IRV with checking for a Condorcet winner at each stage. If one is found, then that one is the overall winner.

 

[lpetrich]

Condorcet ranking - Electowiki -- a Condorcet sequence, where each member is a Condorcet winner relative to the later ones.

My five-topping example has such a sequence: mushrooms, artichoke, peppers, anchovies, sausage

That sequence does not always exist, but two similar sorts of sequences always exist, sequences of Smith strong-winner sets and Schwartz weak-winner sets, since those sets always exist. Smith set - Electowiki, Schwartz set - Electowiki If the sets have one member each, then one gets a Condorcet sequence.

Strong winner: beats all the others.
Weak winner: beats or ties with all the others.

A weak Condorcet winner is an individual candidate who beats or ties with all the others. There can be more than one: top candidates that are tied with each other.

 

[lpetrich]

I'll now consider the question of which counting methods will always put the Smith set on top.

If the method's winner is the Condorcet winner (Condorcet criterion), then that may happen, otherwise, it won't. Likewise, if the method's winner is in the Smith set (Smith criterion or generalized Condorcet criterion), then that may happen, otherwise, it won't. So we look at Copeland, Kemeny-Young, ranked-pairs, and Schulze, because they satisfy both criteria.

Copeland's method involves calculating a score that is (# victories) - (# defeats). For N candidates and M Smith-set members, the score for Smith-set members is greater than (N - 2M), since each member must tie or beat at least one other member. The score for nonmembers is at most (N - 2M), since every member beats ever nonmember. Thus, Copeland's method satisfies Smith-on-top.

Schulze's method involves looking for beatpaths, and using their strengths to sort the candidates. There are always beatpaths from inside the Smith set to outside it, but not the opposite. Thus, Schulze satisfies Smith-on-top.

Ranked-pairs does likewise, because an inside-to-outside pair is sorted to before its corresponding outside-to-inside pair.

For Kemeny-Young, the proof is much like for Copeland's method. For each Smith-set member, the score is (internal) + M*(N-M)*V for V voters. For each nonmember, the score is 0 + (internal), where (internal) < M*(N-M)*V, since it may be tied or defeated by other nonmembers. Thus, this method satisfies Smith-on-top.

So all four satisfy Smith-on-top.

 

[lpetrich]

I'll return to the five-topping problem and try to find the Smith-set sequence, the sequence of sets of strong winners.

Initially:

	Anchovies	Artichoke	Mushrooms	Peppers	Sausage
Anchovies	0	26	22	16	37
Artichoke	29	0	27	43	37
Mushrooms	33	28	0	36	37
Peppers	39	12	19	0	37
Sausage	18	18	18	18	0

Mushrooms are the Condorcet / one-on-one winner, so we eliminate it:

	Anchovies	Artichoke	Peppers	Sausage
Anchovies	0	26	16	37
Artichoke	29	0	43	37
Peppers	39	12	0	37
Sausage	18	18	18	0

Artichoke wins here, so that one goes:

	Anchovies	Peppers	Sausage
Anchovies	0	16	37
Peppers	39	0	37
Sausage	18	18	0

Peppers win:

	Anchovies	Sausage
Anchovies	0	37
Sausage	18	0

Sausage wins:

	Anchovies
Anchovies	0

Anchovies trivially win, and they are the Condorcet loser.

So what we have here is a Condorcet sequence: mushrooms, artichoke, peppers, sausage, anchovies

Top preferences: sausage: 18, anchovies 12, peppers 10, artichoke 9, mushrooms 6

Sequential-runoff reverse dropout order: peppers, sausage, anchovies, artichoke, mushrooms

Borda count: artichoke 191, mushrooms 189, peppers 162, anchovies 156, sausage 127

So the orders are very different.

 

[lpetrich]

I finally found out what "contingent vote" and "supplementary vote" are.

In the contingent vote, the voters rank all the candidates.
First round: top preferences are counted, top two of them selected.
Second round: all but those two are dropped from the ballots, then they are recounted.

Supplementary vote: ballots have only first and second preferences.
Sri Lankan contingent vote: ballots have first, second, and third preferences.

Thus being related to two-round top-two runoff.


Likewise, instant runoff voting in practice is often restricted to the voters' top 3 or 4 or 5 choices.

 

[lpetrich]

I've found these articles that compare methods by criteria:

•  Comparison of electoral systems
•  Condorcet method
•  Tideman alternative method

I found some weird ones, like Anti-Plurality or Anti-FPTP -- single choice in a single round, but a vote is for which candidate does *not* get one's vote. I will illustrate with an example:

Pizza toppings again.

• Sausage: 5
• Peppers: 4
• Artichoke: 3

Anti-Plurality: a vote for sausage counts for everything but sausage: peppers and artichoke.

• Sausage: 4 + 3 = 7
• Peppers: 5 + 3 = 8
• Artichoke: 5 + 4 = 9

 

[lpetrich]

Some criteria look imprecise, but they can be given precise definitions. Clone independence, for instance. "Clones" can be defined as sets of candidates with contiguous rankings or ratings, no others in between them. If they push each other down, then that's spoilers, something that FPTP is notorious for suffering from. If they push each other up, then that's teams, something that the Borda count suffers from. A third effect is crowds, affecting others' performance.

Resolvability is how well the method avoids ties. If a method's numerical quantities are O(# votes), then it is much more resolvable than if its numerical quantities are O(# candidates). That's where the Copeland method fails. In fact, in these tables, it's the only nonrandom method to fail that criterion. The Copeland method is simple: using the Condorcet table, count (# wins) - (# losses) for each candidate. The one with the highest score is the winner.

 

[lpetrich]

The theory of vote-counting algorithms is sometimes called "social choice theory", and there is now a sizable amount of professional literature on it.

I've found lots of algorithms for ranked ballots, and most of them are easy to code and run very fast on present-day computer hardware. So one can run several of them on one's ballots to see what they produce. Like that five-topping example.


Sequential runoff or instant runoff involves finding a loser in each round and then dropping that loser from subsequent rounds. The usual way of finding the loser is whichever candidate has the fewest top-preference votes, but there are other ways.

One can use the Condorcet (one-on-one) loser, if there is one, with a fallback to the usual sequential-runoff method.

One may also test for the presence of a Condorcet (one-on-one) winner before continuing.

In the Tideman alternative method, one finds the Smith set (strong winner) or the Schwartz set (weak winner) at each step, and if it does not have only one member, then drop the candidate with the fewest top-preference votes.


There are some methods that are Condorcet-compliant without using the Condorcet matrix. In Nanson's method, one does the Borda count, then drops all the candidates whose mean rating is less than the overall mean rating, then repeats until one is down to one candidate. Baldwin's method is similar, but it drops the candidate with the lowest mean rating at each step. Both methods work because the Condorcet winner always has a mean rating at least half of the overall mean rating.


I've found this oddity: the Bucklin method. If one does not get a majority of votes with the top preferences, one adds the counts of second preferences, then third ones, etc. until one gets a majority. If more than one does so, then the one with the largest number of votes is the winner.

 

[lpetrich]

The Kemeny-Young algorithm is a Condorcet method with solution time O(n!) in the general case with n candidates. The algorithm:

It starts with the Condorcet matrix D(i,j), where candidate i beats candidate j. It involves calculating every permutation P of the candidates, and then calculating overall score
D(P) = sum over (j later than i in P) of D(i,j)

The winning permutation P is the one with the largest D(P).

It's easy to see why this algorithm has solution time O(n!) -- that is from the number of permutations of n objects being n!.

But there may be algorithms that are faster in many special cases.

Kemeny-Young Optimal Rank Aggregation in Python

Turns the problem into an integer linear-programming problem:

Minimize sum of D(i,j)*b(i,j)
for variables b(i,j) (i,j range over candidates, j != i)
where
b(i,j) is in {0,1}
b(i,j) + b(j,i) = 1
b(i,j) + b(j,k) + b(k,i) >= 1

The solution space has size 2^(n*(n-1)/2) and that is larger than n! for n >= 3.

Algorithm: branch and bound - requires calculating bounds for objective function for each choice. If one choice's range is outside the other one's range, then one knows where to go.

I've also found Experiments with Kemeny Ranking: What Works When?

States the Borda count in terms of the Condorcet matrix:
For candidate i, sum over j of D(i,j)

States Copeland's method as:
For candidate i, sum over j of sgn(D(i,j) - D(j,i))

sgn(x) is the signum function: for x > 0, sgn(x) = 1, for x = 0, sgn(x) = 0, for x < 0, sgn(x) = -1

 

[lpetrich]

Some advocacy organizations:

• Condorcet Canada Initiative | Instant Round-Robin Voting - supports ranked-pairs
• FairVote - supports IRV
• RangeVoting.org - Center for Range Voting - front page - supported rated voting / score voting
• STAR Voting - "Score Then Automatic Runoff" - rated then top-two
• The Center for Election Science | Fairer, More Representative Elections

Why not Instant-Runoff Voting (IRV)? - Condorcet Canada Initiative - criticizes IRV for not using all one's preferences. But doing so would violate later-no-harm and later-no-help, where one's later choices don't affect the outcomes of one's earlier choices. That is why the Condorcet criterion violates both LNH's. So IRV satisfies both LNH's and violates Condorcet.

Is Ranked-Pairs the best Condorcet system? - Condorcet Canada Initiative

Condorcet-IRV: at each IRV round, first look for the Condorcet winner. If there isn't one, then drop the top-preference loser. "Not a big deal if we’re counting by computer, but I don’t buy-in to the idea of a second, different tally when there are good systems that work well without."

The author ended up with ranked-pairs vs. Schulze beatpath, and he decided that RP is easier to follow. But it requires more complicated coding, so I'd prefer Schulze on coding complexity. The Floyd-Warshall algorithm is a big win for Schulze: O(n^3).

For anyone who balks at the coding complexity of RP or Schulze, then the author suggests minimax: the winner is the candidate whose largest defeat is the smallest. However, is not cloneproof -- it can misrank some set of similar candidates relative to a similar single candidate.

 

[lpetrich]

Looking at the FAQ page at Ranked Choice Voting / Instant Runoff- FairVote - the FAQ page contains some responses to criticisms of IRV, what it calls RCV.

10. What kind of candidates win RCV elections?

Candidates do best in RCV elections when they attract a strong core of first-choice support while also reaching out for second and even third choices. Candidates win when they appeal to the greatest number of voters. RCV prevents candidates from winning by only appealing to a small base of voters.

RCV will not elect a candidate who is “everyone’s second choice” because a candidate with little or no first-choice support would not advance past the first elimination round.

Rated voting, like the Borda count for ranked voting, is able to elect "everyone's second choice", because that one's rating can produce an overall rating greater than the overall ratings of the top choices.

"22. Does RCV satisfy the monotonicity criterion?" FV states about gaming an election with non-monotonicity (ranking a candidate lower to help them):

Doing so successfully would require a highly unusual set of circumstances and a detailed and accurate understanding of how the electorate will rank the candidates. Because this is prohibitively difficult, the issue of monotonicity under RCV is largely academic - it has never had any impact on any RCV campaign and is unlikely to have any impact in the future.

"23. How often does RCV elect the Condorcet winner?" - nearly all the time.

How is RCV better than Approval, Score or Condorcet voting methods? - FairVote

On the theoretical front, approval and score voting fail a critical test that voting theorists call the majority criterion. This is the simple property that a candidate who is the first choice of an absolute majority of voters should always win. RCV, Condorcet methods, and even plurality voting satisfy this, but approval and score do not. Under approval or score, a candidate could be the first choice of 99 percent of voters and still lose in theory.

If voters are divided on their top candidate but unified on their second choice, then in rated voting, that second choice will win.

RCV is also one of the few methods that satisfy a property called later-no-harm, which we believe is necessary in the context of high-stakes, competitive elections. Namely, under RCV a vote for your second choice cannot hurt the chances your first choice will be elected; a vote for your third choice does not hurt the chances of your first or second choice; and so on. This is not true under approval, score, or Condorcet voting — a vote for a later choice works against an earlier choice. When a voting system violates later-no-harm, voters face pressure to bullet vote, meaning to cast a vote for only one's first choice. Case in point: approval voting was used to elect the Dartmouth Board of Trustees, but once the Trustees elections became mildly competitive, they abandoned approval due in part to concerns over bullet voting. The more voters bullet vote, the closer the system will resemble plurality in practice, and then we're back to square one in terms of improving our voting system.

Dartmouth alumni oust approval voting 82% to 18% - FairVote

We also consider the Condorcet criterion to be important. This is the property that the candidate that would win a head-to-head race against every other candidate should always win. While RCV, approval, and score voting may fail to elect the Condorcet candidate, in practice RCV has done so in virtually every single election. Due to strategic vulnerabilities of Condorcet methods, including later-no-harm, and the additional complexity Condorcet requires to resolve cycles, we strongly prefer RCV for political elections.

There's no way to have both Condorcet and LNH at the same time, so one has to make a choice.

 

[lpetrich]

New Lessons from Problems with Approval Voting in Practice - FairVote

Two recent uses of the approval voting method by the Independent Party of Oregon and the Independent Voters Network show that it has value in certain uses, but is a far more problematic electoral method than ranked choice voting for electing candidates in meaningfully contested elections. These uses show that tactical voters can flip outcomes, and, due to that reason, most voters treat the election like a traditional plurality voting election and vote for only one. While in competitive RCV elections for important offices some nine in ten voters will rank more than one candidate, in approval voting elections that number plunges to less than half indicating support for more than one candidate, and often far less.

Sightline’s Guide to Methods for Electing an Executive Officer - Sightline Institute
Their ranking:

1. IRV - "It allows a diversity of candidates from major and minor parties to run and win votes. It nurtures more positive campaigns. It rewards candidates for building bridges to many voters and blocks extreme candidates from becoming the only mayor or president that a city or country has. And it has momentum in the United States."
2. STAR - "score runoff" -- needs real-world experience
3. Top-Two Runoff, Approval
4. FPTP - plurality voting
5. Rated voting - score voting - "seems particularly undesirable, because it might incentivize even more negative campaigns and result in divisive, extreme candidates winning office even more often than does Plurality Voting."

Glossary of Methods for Electing Executive Officers - Sightline Institute
Notes a case of vote splitting in top-two runoffs in Washington State in the 2016 State Treasurer election: 3 Democrats vs. 2 Republicans, meaning that only the Republicans advanced.

Approval Voting is not very good for competitive elections:

Experience indicates that many voters “bullet vote”—vote for only one candidate—in Approval Voting elections. For example:

• The Institute of Electrical Engineers stopped using approval voting in 2002 because 80 percent of members were bullet voting.
• In a Mathematical Association of American election, 79 percent of voters bullet voted.
• The Independent Party of Oregon recently held an Approval Voting presidential primary, and more than 70 percent of voters bullet voted.
• Dartmouth College’s student body has used approval voting since 2011, and most voters for student body president bullet vote. In 2015 and 2017, likely everyone bullet voted (there were fewer votes than ballots cast), in 2016 more than 92 percent bullet voted, and in 2014 at least 82 pecent bullet voted.
• In a 2009 Dartmouth Alumni Association election that did not release full data, between 19 and 60 percent of voters bullet voted. However, a faction of Dartmouth alumni with extreme views apparently succeeded in electing several candidates to the Board of Trustees by getting their supporters to bullet vote while others naively approved more candidates. After several of these surprising wins, the association put a referendum on the alumni ballot in 2010, and alumni voted 81 percent to 19 percent to eliminate approval voting. In the 2010 plurality election, the extreme candidate lost by 70 percent to 30 percent, suggesting that strategic approval voting had elected unrepresentative candidates.

Approval Voting works well in many non-election scenarios, such as polls or ratings where people are expressing an opinion or narrowing in on satisfactory options (as in the UN Security Council process) but not electing a single winner. For example, in its online election, the Independent Party of Oregon also asked voters to use Approval Voting to identify multiple policy priorities, and voters averaged nearly four votes each. YouTube, and now Netflix use thumbs up or thumbs down rating systems where viewers can express approval or disapproval of multiple people, videos, or shows. Approval Voting can also be an easy and fair way to make decisions in lower-stakes group situations—everyone raises a hand for every option they find acceptable, and no compicated tallying is needed.

 

[lpetrich]

Rated voting has a problem when people feel strongly about something:

No governmental elections have ever used Score Voting. Amazon, Yelp, and other online platforms use a 5-star Score Voting system. YouTube and Netflix previously used a 5-star Score voting system, but both eventually switched to a simplified thumbs-up/thumbs-down Approval Voting system. In 2009, YouTube realized that most users of its 5-star Score Voting system were giving either 1 star or 5 stars. This year, Netflix also switched from Score to Approval Voting, perhaps in part because the company realized that a mobilized block of users who intensely disliked a particular show were able to damage its average rating. For example: far-right activists all gave Amy Schumer’s show 1 star, overwhelming her other positive ratings.

Even in a low-stakes situation like rating a TV show, users polarized around the highest and lowest scores. In a high-stakes election, the pressure to strategically vote is strong because giving a middling score to a candidate you moderately support could cause your favorite to lose. Voters in an election would likely give their favorite candidate the highest score and all other candidates the lowest.

Much like approval voting -- it tends to degenerate into bullet voting.

 

[lpetrich]

rcvtheory.com - Single-Winner Comparison

	IRV	Cond	Top2	FPTP	Appr	Rtd
Majority Cohesion	+++	+++	000	---	---	---
Spoiler Resistance	+++	+++	000	---	000	000
Strategic Resistance	+++	000	000	000	---	---
Condorcet Efficiency	000	+++	000	---	---	---
Count Simplicity	---	---	+++	+++	+++	000
Fair Multi-winner	+++	000	---	---	000	000
Well-Tested	+++	---	+++	+++	---	---

Cond = Condorcet methods, Top2 = Two-Round Runoff, FPTP = Plurality Voting, Appr = Approval Voting, Rtd = Rated / Score / Range Voting

Majority Cohesion - Mutual Majority Criterion: if there is some set S of candidates such that at least half of voters prefer every member of S to every nonmember, then the winner must come from S.

rcvtheory.com - Spoiler Resistance Analysis

rcvtheory.com - Strategic Resistance Analysis

Condorcet Efficiency - IRV elected Condorcet winners (one-on-one winner) most of the time, even if not all the time. IRV, Top-Two, and Condorcet also satisfy the Condorcet Loser Criterion -- never electing the Condorcet loser (one-on-one loser).

Count Simplicity - I'd rate them:

• FPTP, Approval, Rated
• Top-Two
• IRV
• Condorcet methods (they vary widely)

Fair Multi-winner - is there some multiseat generalization? For IRV there is: Single Transferable Vote. For FPTP, Single Non-Transferable Vote, Bloc Vote. The latter is also a partial generalization of approval voting. Not much multiseat rated or Condorcet voting.

Well-Tested - how much use has it gotten in real-world situations? Like in governments and in organizations.

 

[lpetrich]

Back to rcvtheory.com - Strategic Resistance Analysis

• Bullet voting: to insincerely express a preference for only a single candidate to increase the probability that candidate wins. Everything this analysis says of bullet voting applies equally to any degree of insincere preference truncation, e.g. expressing a preference for 2 candidates when one's sincere preference includes 3.
• Burying: to insincerely express a lower preference for a candidate to decrease the probability that candidates is elected. A voter that is burying normally intends to defeat the strongest opponent of their sincere favorite.
• Compromising: to insincerely express a higher preference for a candidate to increase the probability that candidate is elected. A voter that is compromising normally intends to elect their "compromise candidate" (the beneficiary of the insincere higher preference) when they deem their sincere favorite unlikely to win.
• Push-over: to insincerely express a higher preference for a candidate to increase the probability that a different candidate wins. A voter that is using push-over normally intends for the "push-over candidate" (the beneficiary of the insincere higher preference) to defeat the strongest opponent to their sincere favorite, before their sincere favorite then defeats the push-over candidate.

Let us now look at various kinds of strategy:

• Sincere order: no preference-order inversions necessary.
• Campaign incentive: interest in encouraging one's voters to do the strategy.
• Zero knowledge: no need of details of others' voting.
• Counterstrategy: will opponents be encouraged to do likewise?

	Comp	PsOv	Bury	Bullet
Sincere order				+++
Campaign incentive		+	+++	+++
Zero knowledge	+		+	+++
Counterstrategy			+++	+++

 

[lpetrich]

• Bullet voting: Very likely
• Burying: Likely
• Compromising: Somewhat likely
• Push-over: Not likely

About push-over: "A campaign would need to convince a surgical subset of their supporters — not too few, not too many — to invert their preferences while everyone else votes honestly."

Which one is vulnerable to what strategy:

	IRV	Cond	Top2	FPTP	Appr	Rtd
Bullet voting		+			+++	+++
Burying		+++			+++	+++
Compromising	+	+	+	+++	+++	+++
Push-over	+	+	+

Their assessment:

• Ranked Choice Voting: Very High Resistance
• Two-round Runoff: High Resistance
• Plurality Voting: Moderate Resistance
• Condorcet Methods: Moderate Resistance
• Approval and Range Voting: Very Low Resistance

They rate FPTP moderate because bullet voting, burying, and push-over don't apply to it. But compromising is a common FPTP strategy.

 

[lpetrich]

I discovered that one can indeed create polls in Reddit. But single-choice ones only.

I also found out about Maximize Affirmed Majorities, and it's a variant of Ranked Pairs: MAM procedure definition

For standard RP, one sorts pairs of candidates (i,j) by Condorcet-matrix value C(i,j) (most winners) and then by minus its transpose - C(j,i) (fewest losers).

For MAM, one selects pairs of candidates (i,j) where C(i,j) > C(j,i) and sorts them as described above. This is (almost?) equivalent to using a modified Condorcet matrix for all pairs (i,j): D(i,j) = C(i,j) if C(i,j) > C(j,i) and 0 otherwise.


For adding pairs to the working set of them, as I have decided to cal it, I'd originally used this algorithm:
Testing whether a graph is acyclic

But there are two more that I've found, Kahn's algorithm and depth-first sorting, at  Topological sorting Also at Topological Sorting - GeeksforGeeks (depth first) Kahn's algorithm for Topological Sorting - GeeksforGeeks

For V vertices and E edges, their space requirement is O(V) and their time requirement O(V+E). That is what gives O(n^4) for n candidates in ranked pairs / MAM.

 

[lpetrich]

Topological sorting has an additional nice feature. It returns a sorted list of nodes / candidates, so one does not need an additional sorting step.

Seems like I should try to implement it. Depth-first looks relatively simple, though both it and Kahn have recursive steps, and for large graphs, that creates a big recursion stack. Mathematica has a recursion limit that defaults to 1024. So I should try to figure out how to do it iteratively, perhaps with an array that can serve as a recursion stack.

 

[lpetrich]

For topological sorting, one can do it incrementally, testing each new edge by using it as a starting point and checking to see if one eventually reaches it again.


I'll now consider a more practical issue: aggregation of the ballots and partial counts of them for each method. The aggregation is done by making counts of each distinct kind of vote.

For single-choice voting, aggregating the votes is easy: one count value for each candidate. That is also what one needs for partial counts. For n candidates, one needs a data structure with size n.

For approval voting, it is more complicated. There are 2^n possible votes, so an aggregate of approval votes will have maximum size 2^n. In practice, it may be much smaller, especially if many voters choose only one or two or some other small fraction of some large n. For rated voting with r possible ratings, the maximum size of a vote aggregate will be r^n. Approval voting is clearly a special case of rated voting, with only two possible ratings.

For approval-voting or rated-voting summation, one needs size n, a size which also works for partial counts.

If one wants a median count for rated voting, one needs size r*n, for the count of each number of kinds of ratings that each candidate received.

If one wants to try something like reweighted approval voting or rated voting, one will need all the ballots or else an aggregate of them. The reweighting is done to make it proportional, like what is done with some versions of STV, a multiseat extension of IRV. That reweighting is done to reduce the weights of each ballot that has contributed to some candidate's victory. That is done to avoid being a multiseat extension of FPTP. That is, to permit other blocs of candidates to be represented other than that winner's bloc.


For ranked votes, the aggregate's maximum size is n! (n factorial), something that gets very big very quickly. If one has a truncated ballot with length m, then the total number is the falling factorial of n by m: n*(n-1)*(n-2)*...*(n-m+1).

Since the voters themselves may truncate their votes, one must add up over all ballot lengths: FF(n,0) + FF(n,1) + FF(n,2) + ... + FF(n,m) where m is the maximum length.

For maximum length 3, one gets 1 + n + n*(n-1) + n*(n-1)*(n-2)

For IRV, one needs all the ballots or else an aggregate of them. That's what's needed for partial counts.

 

[lpetrich]

The Borda count is essentially turning ranked votes into rated ones, so one carries over the rated-vote partial-count results into this case.


For methods that use the Condorcet matrix, partial counts can easily be partial counts of that matrix, a matrix with size n^2. Strictly speaking, one can omit this matrix's main diagonal, since it is all zeros. That gives us n*(n-1) values. But for representing it in memory, it's easier to let the diagonal be present.


As to vote counting with such partial results, that is very fast with present-day computer hardware, except if one wants to do something very compute-intensive like the Kemeny-Young method.