Vote-counting: election-system analysis

[lpetrich]

This is about systems of counting votes, both actually used and theoretically proposed.  Comparison of electoral systems has a big comparison of them, using a variety of criteria. We've had threads on some methods:

• Ranked Choice Voting on the Ballot in New York City
• Maine could have avoided this with approval voting.
• Proportional Representation for the United States?
• How will Instant Runoff Voting in Maine effect voting reform?
• Who uses proportional representation?
• Evaluating voting methods
• What voting system(s) do you like? Poll for multiseat elections
• What voting system(s) do you like? Poll for single-seat elections
• Condorcet Proportional Representation or Single Transferable vote.

Elections are to be interpreted broadly -- votes for *anything*.

I'll start off with a very simple method, first-past-the-post or plurality voting. Imagine you and 11 friends want to vote on what topping you want to put on a pizza. It seems easy. Everybody votes for a topping, and whichever topping gets the most votes is the topping that the pizza gets.

Let's say that one has sausage and green peppers. Easy. 5 of your group want sausage and 7 want pepper. Pepper wins, and everybody has pepper pizza.

Let's say that the vegetarians want more variety. They make artichoke a possibility. The meat lovers are satisfied with sausage, however. So they vote on what to put on their pizza. 5 want sausage, 4 want pepper, and 3 want artichoke. It's the sausage that gets put on the pizza. The vegetarians lost because of the spoiler effect: vote splitting from similar candidates.

 

[lpetrich]

That is a reason for interest in alternatives to FPTP. Though they are more complicated, some of them are immune to the spoiler effect. They all involve each voter being able to cast more than one vote, and some FPTP defenders defend FPTP by interpreting "one person one vote" too literally. But the spirit of that slogan is that everybody in some election must have equivalent voting power -- have the same ballot and be weighted the same.


A simple solution is to allow voting for more than one candidate -- approval voting. One then adds up the vote as with FPTP. Back to the pizza. With approval voting, the votes are: sausage 5, green pepper 2, artichoke 1, GP+AC 4. That gives totals sausage 5, green pepper 6, artichoke 5. Green pepper wins.

A fancier version is to use values between 0 and 1 -- rated vote.

A version that is used in elections of the Secretary General of the United Nations adds disapproval to approval. So one can vote (approve, neutral, disapprove). That is equivalent to a rated vote with values 0, 1/2, and 1.

Cumulative voting is where everybody gets some number of votes, and that they can be distributed how one likes on the ballot -- concentrated in some favorite candidate or spread out between more than one candidate. This is equivalent to a rated vote with values that sum up to 1.

 

[lpetrich]

An alternative to such vote multiplicity is multiple elections -- runoffs.

A simple sort is a top-two runoff or a two-round/two-ballot system. In the first election, all the candidates compete, and the top two of them then compete in a second election. This second election is sometimes skipped if the first election gives a candidate with the majority of the vote.

Thus, in that pizza example, we start with sausage 5, green pepper 4, artichoke 3. Artichoke drops out, and sausage and green pepper go head-to-head, getting sausage 5, green pepper 7.

An alternative is the exhaustive ballot or sequential runoff, where in each round of voting, the candidate that did the worst is dropped before continuing. The vote ends when one candidate is left or else when one candidate has gotten a majority of the votes.

-

Can one compress these elections into one election? Yes one can, by doing ranked-choice or preference voting. One ranks the candidates by one's preference: first choice, second choice, etc.

With only a second vote, one gets a system called variously the contingent vote or the supplementary vote. The first preferences are counted first, and if no candidate wins a majority, then all but the top two are eliminated, and if any second-preference top-two ones are then revealed by this elimination, then they are included in the count. It is a compressed version of top-two runoff.

For more levels of preference, it's instant runoff voting, a compressed version of sequential runoff.

-

For preference / ranked-choice voting, there are numerous ways of counting the ballots.

A simple one is the Borda count. For n candidates, one's top choice gets weight n, one's next choice weight (n-1), one's next choice weight (n-2), and so forth. Essentially turning the vote into a kind of rated vote.

 

[lpetrich]

There is a theoretically interesting criterion called the "Condorcet criterion". It involves having a "Condorcet winner", the candidate who beats every other candidate if the ballots are interpreted as sets of one-on-one contests where the more preferred one wins, a sort of virtual round robin. One can add up the outcomes of the contests to make a "Condorcet matrix" and then work for there.

Some sets of ballots may not have a Condorcet winner, and some methods do not necessarily produce such a winner when one is present -- all the methods that I've discussed previously.

I've found several examples of how different vote-counting methods can give different results. Math Alive — Voting & Social Choice — Lab 1 and L27 - Does the Majority always rule? have the same preference ballots under different names.

How Many	1st	2nd	3rd	4th	5th
18	Sausage	Artichoke	Mushrooms	Peppers	Anchovies
12	Anchovies	Mushrooms	Artichoke	Peppers	Sausage
10	Peppers	Anchovies	Mushrooms	Artichoke	Sausage
9	Artichoke	Peppers	Mushrooms	Anchovies	Sausage
4	Mushrooms	Anchovies	Artichoke	Peppers	Sausage
2	Mushrooms	Peppers	Artichoke	Anchovies	Sausage

 

[lpetrich]

Top One (First Past the Post, Plurality)

• Sausage: 18
• Anchovies: 12
• Peppers: 10
• Artichoke: 9
• Mushrooms: 6

Sausage

Top-Two Runoff:

• Round 1
  • Sausage: 18
  • Anchovies: 12
  • Peppers: 10
  • Artichoke: 9
  • Mushrooms: 6
• Round 2
  • Anchovies: 37
  • Sausage: 18

Anchovies

 

[lpetrich]

Sequential Runoff:

• Round 1
  • Sausage: 18
  • Anchovies: 12
  • Peppers: 10
  • Artichoke: 9
  • Mushrooms: 6
• Round 2
  • Sausage: 18
  • Anchovies: 16
  • Peppers: 12
  • Artichoke: 9
• Round 3
  • Peppers: 21
  • Sausage: 18
  • Anchovies: 16
• Round 4
  • Peppers: 37
  • Sausage: 18
• Round 5
  • Peppers: 55

Peppers

Borda Count:

• Artichoke: 191
• Mushrooms: 189
• Peppers: 162
• Anchovies: 156
• Sausage: 127

Artichoke

 

[lpetrich]

Condorcet matrix:

	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

Condorcet Winner:

Mushrooms

Mushrooms beat anchovies 33-22, artichoke 28-27, peppers 36-19, sausage 37-18

The different results of the different vote-counting methods is something related to Arrow's Theorem, derived by economist Kenneth Arrow. It states that there can be no algorithm for counting preference votes that always satisfies certain nice theoretical properties.

But that does not seem to be much of a problem in practice.

 

[Bomb#20]

A modest proposal: Reverse Sequential Runoff

Round 1

• Sausage: 37
• Anchovies: 18
• Peppers: 0
• Artichoke: 0
• Mushrooms: 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

Matches the Condorcet winner in your example, and, I think, usually. Always produces an outcome, unlike Condorcet. Easier to explain to people than Condorcet.

 

[lpetrich]

Having a Condorcet winner is a property that is satisfied by several algorithms for counting preference votes.

The Schulze beatpath method tries to find a sequence of candidates where the smallest margin of victory along that sequence is as large as possible. It seems like it runs in factorial time, needing O(n!) operations for n candidates, but a version of something called the Floyd-Warshall algorithm reduces it to O(n^3).

The Copeland method counts up how many victories each candidate has over other candidates while subtracting that number of defeats. The highest score gives the winner.

The minimax method finds the best performance of other candidates against each one. The lowest of these best performances gives the winner.

The Kemeny-Young method goes through every permutation of the candidates, then for each permutation, adds up the scores for each candidate's victory over later candidates in the permutation. The highest total score gives the winner.

The Dodgson method does permutations of the ballot entries, the same permutation for each one. For each permutation, it finds the Condorcet winner, if there is one, and the one with the smallest "permutation distance" of its permutation gives the winner. The "permutation distance" is the minimum number of interchanges needed to go from the identity permutation to that permutation. That distance is (size of permutation) - (number of cycles in it).

The Kemeny-Young and Dodgson methods both run in O(n!) time, since they need to go through every possible permutation of n entities.

The Tideman ranked-pairs algorithm first sorts each pair of candidates by how well one of them beats the other, and then starts with the best-performing one of these. It then attaches the best remaining one that does not produce a loop, making a Directed Acyclic Graph. When it is done, the top one is the winner.

The maximum-lotteries algorithm essentially generalizes the notion of Condorcet winner to make partial Condorcet winners. It does so by doing some linear programming. I implemented that one with the simplex algorithm. The highest partial fraction gives the winner. Linear programming is, in general, NP-complete, meaning that there is no known algorithm guaranteed to work in polynomial time for it.

I have some implementations: lkpetrich/Preference-Voting: For counting votes in preference voting. Implements a large number of algorithms.

 

[Bomb#20]

The maximum-lotteries algorithm essentially generalizes the notion of Condorcet winner to make partial Condorcet winners. It does so by doing some linear programming. I implemented that one with the simplex algorithm. The highest partial fraction gives the winner. Linear programming is, in general, NP-complete, meaning that there is no known algorithm guaranteed to work in polynomial time for it.

Linear programming is not NP-complete. There are polynomial algorithms for it, such as Karmarkar's algorithm.

Also, that's not what NP-complete means. A problem being NP-complete means all the other NP problems are reducible to it. There are a variety of NP problems that have no known polynomial algorithms but that aren't NP-complete; the most famous is the problem of finding the prime factors of large composite numbers. If somebody finds a polynomial solution for that next year, it will kill RSA encryption and make a mess of the internet credit card economy, but it won't solve the traveling salesman problem. It's an asymmetrical situation -- if somebody finds a polynomial solution for the traveling salesman problem next year, that will automatically also provide a solution for factoring RSA keys.

 

[lpetrich]

Now to considering some of the criteria in  Comparison of electoral systems

First, what I called rated voting in this thread is called score voting in that article - it's giving every candidate a numerical value in some range, then adding up those values.

Majority Criterion (MC) - whichever candidate is ranked or rated the highest by a majority of voters is the winner.

Most methods satisfy it, but rated voting doesn't. Here is a counterexample for it.

You and your friends vote on pizza toppings by giving each one a numerical rating. Unrated ones are assumed to be zero. You vote as follows:

• 7: sausage 1, anchovies 0.75
• 5: pepper 1, anchovies 0.75

The total vote: sausage 7, peppers 5, anchovies 9. So anchovies win, even though it wasn't the majority top choice.

Related is the mutual majority criterion (MMC), where the winner will always be in some group of candidates that is preferred over the others. It implies the MC, and also the majority loser criterion (MLC), that the least-preferred candidate will always lose. For the MC, the group size is a single member, and for the MLC, the group size is all but some member. The converse is not necessarily true. Some methods satisfy the MC and/or the MLC but not the MMC.

The above example is a counterexample for the MLC, since anchovies are the least preferred but winning.

Method	MC	MLC	MMC
FPTP	X
T2 runoff	X	X
Seq runoff	X	X	X
Rated
Borda		X
Schulze*	X	X	X
Minimax	X

T2 = top-two, Seq = sequential (IRV/AV)
* also Copeland, Kemeny-Young, ranked pairs

 

[lpetrich]

Condorcet criterion - turn the rankings or ratings into a virtual round robin, and the winner and loser of it are the Condorcet winner and loser. A method will satisfy this criterion if the winner is the Condorcet winner. A related criterion is the Condorcet loser criterion, where the Condorcet loser never wins.

FPTP violates both criteria, and top-two runoff, sequential runoff, and the Borda count satisfies only the Condorcet loser criterion. Minimax satisfies only the Condorcet criterion, and Schulze, Copeland, Kemeny-Young, and ranked pairs s

• Neither: FPTP, approval voting, rated voting
• Loser only: top-two runoff, sequential runoff, Borda count
• Winner only: Minimax (some variants)
• Both: Schulze, Copeland, Kemeny-Young, ranked pairs

The Condorcet matrix for the previous example:

	Sausage	Peppers	Anchovies
Sausage	0	7	12
Peppers	5	0	12
Anchovies	0	0	0

The Condorcet winner is sausage and the Condorcet loser is anchovies. But in this rated vote, anchovies win, providing counterexamples for both criteria.

On the subject of the Condorcet matrix, one can derive some theoretically interesting subsets of the candidates with it, the  Smith set and the  Schwartz set

• Dominating set - every candidate in it beats every candidate outside of it
• Smith set - smallest dominating set
• Undominated set - every candidate in it is unbeaten by every candidate outside of it
• Schwartz-set component - every undominated set with no proper subset that is also an undominated set
• Schwartz set - union of all Schwartz-set components

Dominating sets are nested. Schwartz-set components are disjoint. The Schwartz set is always a subset of the Smith set. Schwartz-set members in different components are tied with each other.

The Smith set can have more than one member from ties (A = B) and/or cycles (A > B > C > A). If the Schwartz set has more than one member, then those members form a cycle, the "top cycle".

If a Condorcet winner exists, then the Smith and Schwartz sets have only one member: that winner.

If the Smith set has only one member, then it is the Condorcet winner. If the Schwartz set has only one member, then it is at least a "weak Condorcet winner".

A weak Condorcet winner beats or is tied with all the others, while a weak Condorcet loser is beaten by or is tied with all the others. There can be more than one of each.

 

[lpetrich]

Is the winner unaffected by adding or removing any of these candidates?

Independence of Smith-dominated alternatives (ISDA) - Any that are outside the Smith set (smallest dominating set)

Independence of irrelevant alternatives (IIA) - Any non-winner

Local independence of irrelevant alternatives (LIIA) - The biggest loser

-

Monotonicity criterion - will a candidate stop winning if one raises the ranking or rating of it on some of its ballots? Or start winning if one lowers some of its rankings or ratings?

That criterion is satisfied for every method but the runoff-based methods: top-two and sequential. That's because it's possible to find monotonicity-violating examples. I'll use the Wikipedia article's example and make it pizza toppings.

A = anchovies, P = peppers, S = sausage
A P 28, A S 5, P A 16, P S 16, S A 5, S P 30

Round 1: A 33, P 32, S 35
Peppers drop out
Round 2: A 49, S 51
Sausage wins

Now change at least two A S voters to S A, pushing up sausage and pushing down anchovies
A P 28, A S 3, P A 16, P S 16, S A 7, S P 30

Round 1: A 31, P 32, S 37
Anchovies drop out
Round 2: P 60, S 40
Peppers win

So bumping up sausage in some of the preferences makes it lose.

 

[lpetrich]

Consistency criterion - if some sets of ballots all have the same winner, will counting them together still give that winner?

Participation criterion - if one refuses to participate, will that never help one's favorite candidate?

Reversal symmetry - if one reverses the rankings or ratings, will the original winner then lose?

Runoff methods violate not only monotonicity, but also consistency, participation, and reversal.

Later-no-harm criterion - adding a ranking or a positive rating to a less-preferred candidate will not make a more preferred candidate lose

Later-no-help criterion - adding a ranking or a positive rating to a less-preferred candidate will not help a more preferred candidate win

Runoff methods satisfy those two.

No favorite betrayal - does not never need to rank or rate a candidate above their favorite to help their favorite win?

Runoff methods violate that one also.

-

Vote-counting methods can only have some out of a certain set of criteria: Condorcet, ISDA, IIA, consistency, participation, later-no-harm, and no favorite betrayal. From the table in Wikipedia, I infer these sets of criteria that exclude each other:

(Cond, ISDA)
(IIA, NFB) and/or (Cons, Part)
(LNH)

 

[lpetrich]

Here are some examples of instant-runoff voting (preference voting + sequential runoff) violating some of the criteria, taken from Wikipedia and recast as pizza toppings.

A = anchovies, P = peppers, S = sausage

Consistency violation:

Set 1:
A P S 4, P A S 2, S P A 4
Round 1: A 4, P 2. S 4 -- peppers drop out
Round 2: A 6, S 4 -- anchovies win

Set 2:
A P S 4, P A S 6, S A P 3
Round 1: A 4, P 6, S 3 -- sausage drops out
Round 2: A 7, P 6 -- anchovies win

Combined:
A P S 8, P A S 8, S A P 3, S P A 4
Round 1: A 8, P 8, S 7 -- sausage drops out
Round 2: A 11, P 12 -- peppers win

Instead of anchovies winning for both together, peppers win.

Participation violation:

Full participation:
A P S 5, P S A 4, S A P 6
Round 1: A 5, P 4, S 6 -- peppers drop out
Round 2: A 5, S 10 - sausage wins

With two of the first set of voters not voting:
A P S 3, P S A 4, S A P 6
Round 1: A 3, P 4, S 6 -- anchovies drop out
Round 2: P 7, S 6 -- peppers win

When those two go from abstaining to participating, the winner goes from their second choice (peppers) to their third choice (sausage).

Reversal violation:

Original:
A P S 5, P S A 4, S A P 2
Round 1: A 5, P 4, S 2 -- sausage drops out
Round 2: A 7, P 4 -- anchovies win

Reversed:
S P A 5, A S P 4, P A S 2
Round 1: A 4, P 2, S 5 -- peppers drop out
Round 2: A 6, S 5 -- anchovies win

So anchovies win in both cases.

 

[lpetrich]

I'll now turn to some more down-to-earth criteria, criteria related to the counting of the votes.

An obvious amount is the amount of calculation needed. Some methods require much more than others. For N candidates:

• Constant O(1) - random drawing (sortition)
• Linear O(N) - FPTP, approval, rated, Borda, each round of runoff
• Quadratic O(N^2) - IRV, Copeland, minimax
• Cubic O(N^3) - Schulze
• Quartic O(N^4) - ranked pairs
• Factorial O(N!) - Kemeny-Young, Dodgson
• Usually polynomial - maximal lotteries (uses linear programming - simplex algorithm: worst case exponential, usual case polynomial)

The first five are examples of polynomial time, meaning that the run time is some polynomial in N. For large N, the highest-power term will dominate.

FPTP has the virtue of very low computational complexity, though most of the other O(N) methods here are not much worse. IRV gets O(N^2) because of its worst case of (N-1) rounds of counting.

But with present-day computers' capabilities, one can do any polynomial-time method of counting, and even factorial-time ones if the number of candidates is not too large. Some organizations now use the Schulze method internally, for instance.


Resolvability is whether the calculation seldom has to break ties. This is the case for most methods, since most of their numerical values are on the order of the number of votes. Copeland's method is an exception, since it makes a sort of intermediate Condorcet matrix where every victory becomes +1 and every defeat -1.

 

[lpetrich]

Summability relates to the size of a method's data structure for adding up the results of the ballots to produce intermediate results.

Summable-structure sizes:

• Linear O(N) - FPTP, approval, rated, Borda, each round of runoff if done separately
• Quadratic O(N^2) - contingent vote (top-two runoff on one ballot), anything that uses a Condorcet matrix
• Factorial O(N!) - IRV (sequential runoff on one ballot), Dodgson's method

These methods use a Condorcet (virtual round robin) matrix: Schulze, Copeland, minimax, Kemeny-Young, ranked pairs, maximum lotteries

In practice, IRV is often implemented with voters entering only their top 3 or 5 or some such number of preferences. For top-p preferences for p << N, the summable-structure size becomes O(N^p).


Now for where some of the names come from.

Looking under  Borda count, I find

The Borda count was developed independently several times, as early as 1435 by Nicholas of Cusa,[2][3][4] but is named for the 18th-century French mathematician and naval engineer Jean-Charles de Borda, who devised the system in 1770.

It is essentially translating preference votes into rated votes.

It uses, for n candidates, n, n-1, n-2, ... -- one's kth vote gets (n-k+1)

For not voting for all the candidates, one can simply cut off, but that gives a way of gaming it: voting for one's top choice only (bullet voting).

Modified Borda replaces n with the number of candidates voted for.

There is a variant of the Borda count called the Dowdall system, where one's votes get values 1, 1/2, 1/3, ... -- one's kth vote gets 1/k.

Under  Condorcet method, I find

Condorcet voting methods are named for the 18th-century French mathematician and philosopher Marie Jean Antoine Nicolas Caritat, the Marquis de Condorcet, who championed such voting systems. However, Ramon Llull devised the earliest known Condorcet method in 1299.[7] It was equivalent to Copeland's method in cases with no pairwise ties.[8]

I found the phrase "virtual round robin" in a description at a site called "Better Polls".

 

[lpetrich]

Independence of clones criterion - this refers to candidates with similar voter appeal. Such multiple candidates can have these effects:

• Spoilers - they harm each other by splitting the vote for that sort of candidate
• Teams - they help each other
• Crowds - they interfere with other candidates

Several methods are vulnerable to spoilers: FPTP, top-two runoff, minimax, Kemeny-Young

Top-two is not as vulnerable to spoilers as FPTP, but it is vulnerable.


This method is vulnerable to teams: Borda

This method is vulnerable to both teams and crowds: Copeland

Several methods are not affected by multiple similar candidates: approval, rated, IRV, Schulze, ranked pairs


Whether some candidates are spoilers has been a contentious issue in some US Presidential races: John Anderson in 1980, Ross Perot in 1992 and 1996, Ralph Nader in 2000, Gary Johnson and Jill Stein in 2016.

 

[lpetrich]

Having taken on single-seat methods, I now consider multiple-seat methods. Returning to pizza toppings, let us consider the case of more than one topping that one can put on one's pizza. How would you and your friends select which toppings to put on it?

A simple approach would be to take some single-seat method and extend it to multiple seats. Most single-seat methods create rankings or ratings of all the candidates, and one can use the top ranked or rated candidates for one's seats.


The single non-transferable vote extends first-past-the-post to multiple seats by having every voter vote for only one candidate, as in FPTP.

Thus, if you decide to have 3 toppings on your pizza and you and your friends vote 5 for sausage, 3 for anchovies, 2 for mushrooms, 6 for peppers, and 2 for artichoke, the winners are peppers, sausage, and anchovies.

One can also extend approval voting to multiple seats. In some methods, one has a maximum number of votes that one can cast. If less than the number of candidates, it is the limited vote. If equal, it is the bloc vote / multiple non-transferable vote / plurality-at-large vote.


A way of extending rated voting to multiple seats is cumulative voting. The total of one's ratings has some maximum value. A simple version is equal-and-even cumulative voting. where if one votes for m of the candidates, one's votes for them have weights 1/m. Another one is sometimes called multi-voting or dot voting. One has some number of votes or points, which one can distribute as one wants. Thus, if one is an anchovy lover, one can cast all one's votes for anchovies, while if one is a vegetarian, one can divide one's votes among peppers and artichoke and onions and olives.


A variation of multiseat approval voting is sequential proportional approval voting or reweighted approval voting. It is a multi-round system with weighting of ballots that is updated with each round. Initially, the weights are all 1 and the votes counted in approval-voting fashion. Its winner I will call W1. Then the weights of all the ballots with votes for W1 are set to 1/2 with the others remaining 1. The votes are counted again and the winner of non-W1 candidates is W2. The ballots are then weighted 1/3 for votes for both W1 and W2, 1/2 for either W1 or W2, and 1 for neither.

In general, the weighting is 1/(m+1) where the ballot has votes for m of the previous winners. This could be extended to rated votes rather easily:
1/(1 + sum of ratings of every winner)

where the ratings are between 0 and 1 inclusive. This is called reweighted range voting, though with my terminology, it is "reweighted rated voting".

There is also something called proportional approval voting. It goes through all the possible outcomes and compares each outcome to each ballot. For each ballot-outcome pair, it calculates a satisfaction function from the number of votes in the ballot that it got right in the outcome. The Wikipedia article on it mentioned this formula for n matches: 1 + 1/2 + 1/3 + ... + 1/n.

For c candidates and s seats, one has to go through c!/s!/(c-s)! possibilities.

 

[lpetrich]

In satisfaction approval voting, if one has voted for n candidates, then one's ballot is weighted by 1/n. That is equivalent to turning the vote into equal-and-even cumulative voting, as far as I can tell from the description of it in Wikipedia.


One can extend instant runoff voting to multiseat elections with preferential bloc voting. That is doing an IRV count to find the first winner, then dropping that candidate from the ballots, then doing another IRV count. This procedure is repeated until all the seats are filled. This procedure can be done with any vote-counting algorithm that gives a single winner Find the winner, remove that candidate from the ballots, repeat until all the seats are filled. For rated ballots, that may be done all at once, but for ranked (preference) ballots, one has to redo the count without the winners as one finds them.


A more direct way of extending IRV to multiseat elections is the single transferable vote.

It uses ranked-choice or preference voting, and it has sequential-runoff counting, but with dropping winners in addition to losers. When all the seats are filled, the counting ends.

A winner is recognized in the following way. Before counting, a victory quota Q is computed, usually:
Q = (total number of votes) / ((number of seats) + 1)

At each round of counting, if the candidate with the most votes has more votes V than Q, then that candidate is a winner. Then the ballots which gave that candidate that victory are de-emphasized, because they have done their part. One can do this in two ways:

• Random dropping of round(Q) ballots from those ballots.
• Reweighting of those ballots. The weight of each of them is multiplied by (V-Q)/V. Before the first round, all the ballots have weight 1.

The second one is deterministic, something that makes the vote counting repeatable. It also lacks the sampling variability of random dropping, something that may make results that may be interpreted as miscounts.


There is a rather complicated method called CPO STV that compares every possible outcome to every other possible outcome, using a rather complicated procedure. This gives a Condorcet matrix of comparisons, and one then uses some Condorcet method to find the winner.

A related one, Schulze STV, only compares sets of outcomes that only differ by one candidate.