Pairwise counting

Pairwise counting is the process of considering a set of items, comparing one pair of items at a time, and for each pair counting the comparison results. In the context of voting theory, it involves comparing pairs of candidates or winner sets (usually using majority rule) to determine the winner and loser of the pairwise matchup. This is done by looking at voters' (usually ranked or rated) ballots to count, for each pair of candidates, which one they indicated a preference for, if they did. The pairwise preference article discusses how pairwise comparison information can be used.

A GIF for pairwise counting with a ranked ballot. Click on the image and then the thumbnail of the image to see the animation.

Most, but not all, election methods that meet the Condorcet criterion or the Condorcet loser criterion use pairwise counting. See the Condorcet section for more information on the use of pairwise counting in Condorcet methods.

Examples

Example without numbers

As an example, if pairwise counting is used in an election that has three candidates named A, B, and C, the following pairwise counts are produced:

• Number of voters who prefer A over B
• Number of voters who prefer B over A
• Number of voters who have no preference for A versus B
• Number of voters who prefer A over C
• Number of voters who prefer C over A
• Number of voters who have no preference for A versus C
• Number of voters who prefer B over C
• Number of voters who prefer C over B
• Number of voters who have no preference for B versus C

Alternatively, the words "Number of voters who prefer A over B" can be interpreted as "The number of votes that help A beat (or tie) B in the A versus B pairwise matchup".

If the number of voters who have no preference between two candidates is not supplied, it can be calculated using the supplied numbers. Specifically, start with the total number of voters in the election, then subtract the number of voters who prefer the first over the second, and then subtract the number of voters who prefer the second over the first.

These counts can be arranged in a pairwise comparison matrix or outranking matrix table (though it could simply be called the "candidate head-to-head matchup table") such as below.

Pairwise counts

	A	B	C
A		A > B	A > C
B	B > A		B > C
C	C > A	C > B

In cases where only some pairwise counts are of interest, those pairwise counts can be displayed in a table with fewer table cells.

Note that since a candidate can't be pairwise compared to themselves (for example candidate A can't be compared to candidate A), the cell that indicates this comparison is always empty.

In general, for N candidates, there are 0.5*N*(N-1) pairwise matchups. For example, for 2 candidates there is one matchup, for 3 candidates there are 3 matchups, for 4 candidates there are 6 matchups, for 5 candidates there are 10 matchups, for 6 candidates there are 15 matchups, and for 7 candidates there are 21 matchups.

Example with numbers

Tennessee's four cities are spread throughout the state

Imagine that Tennessee is having an election on the location of its capital. The population of Tennessee is concentrated around its four major cities, which are spread throughout the state. For this example, suppose that the entire electorate lives in these four cities, and that everyone wants to live as near the capital as possible.

The candidates for the capital are:

• Memphis, the state's largest city, with 42% of the voters, but located far from the other cities
• Nashville, with 26% of the voters, near the center of Tennessee
• Knoxville, with 17% of the voters
• Chattanooga, with 15% of the voters

The preferences of the voters would be divided like this:

42% of voters (close to Memphis)	26% of voters (close to Nashville)	15% of voters (close to Chattanooga)	17% of voters (close to Knoxville)
Memphis Nashville Chattanooga Knoxville	Nashville Chattanooga Knoxville Memphis	Chattanooga Knoxville Nashville Memphis	Knoxville Chattanooga Nashville Memphis

These ranked preferences indicate which candidates the voter prefers. For example, the voters in the first column prefer Memphis as their 1st choice, Nashville as their 2nd choice, etc. As these ballot preferences are converted into pairwise counts they can be entered into a table.

The following square-grid table displays the candidates in the same order in which they appear above.

Square grid

	... over Memphis	... over Nashville	... over Chattanooga	... over Knoxville
Prefer Memphis ...	-	42%	42%	42%
Prefer Nashville ...	58%	-	68%	68%
Prefer Chattanooga ...	58%	32%	-	83%
Prefer Knoxville ...	58%	32%	17%	-

The following tally table shows another table arrangement with the same numbers.

Tally table

All possible pairs of choice names	Number of votes with indicated preference			Margin
Prefer X over Y	Equal preference	Prefer Y over X
X = Memphis Y = Nashville	42%	0	58%	-16%
X = Memphis Y = Chattanooga	42%	0	58%	-16%
X = Memphis Y = Knoxville	42%	0	58%	-16%
X = Nashville Y = Chattanooga	68%	0	32%	+36%
X = Nashville Y = Knoxville	68%	0	32%	+36%
X = Chattanooga Y = Knoxville	83%	0	17%	+66%

Example using various ballot types

[See File:Pairwise_counting_procedure.png for an image explaining all of this).

Suppose there are five candidates A, B, C, D and E.

Sufficiently expressive ballot types

Ranked ballots

Using ranked ballots, suppose two voters submit the ranked ballots A>B>C, which means they prefer A over B, B over C, and A over C, with all three of these ranked candidates being preferred over either D or E. This assumes that unranked candidates are ranked equally last.

Rated ballots

Now suppose the same two voters submit rated ballots of A:5 B:4 C:3, which means A is given a score of 5, B a score of 4, and C a score of 3, with D and E left blank. Pairwise preferences can be inferred from these ballots. Specifically A is scored higher than B, and B is scored higher than C. It is known that these ballots indicate that A is preferred over B, B over C, and A over C. If blank scores are assumed to mean the lowest score, which is usually a 0, then A and B and C are preferred over D and E.

In a pairwise comparison table, this can be visualized as (organized by Copeland ranking):

	A	B	C	D	E
A	---	2	2	2	2
B	0	---	2	2	2
C	0	0	---	2	2
D	0	0	0	---	0
E	0	0	0	0	---

(star.vote offers the ability to see the pairwise matrix based off of rated ballots.)

Choose-one and Approval ballots

Pairwise counting also can technically be done using Choose-one voting ballots and Approval voting ballots (by giving one vote to the marked candidate in a matchup where only one of the two candidates was marked), but such ballots do not supply information to indicate that the voter prefers their 1st choice over their 2nd choice, that the voter prefers their 2nd choice over their 3rd choice, and so on.

Dealing with unmarked/last-place candidates

Note that when a candidate is unmarked it is generally treated as if the voter has no preference between the unmarked candidates (a candidate who is marked on the ballot is considered explicitly supported, and a candidate who is unmarked is implicitly unsupported). When the voter has no preference between certain candidates, which can also be seen by checking if the voter ranks/scores/marks multiple candidates in the same way (i.e. they say two candidates are both their 1st choice, or are both scored a 4 out of 5), then it is treated as if the voter wouldn't give a vote to any of those candidates in their matchups against each other.

Dealing with write-in candidates

A comprehensive approach is to, in each precinct, count the number of ballots that explicitly rank each (non-write-in) candidate. When a write-in candidate is found on a ballot, then before that ballot is counted, the number of votes each non-write-in candidate gets against the write-in candidate is the number of ballots they were so far ranked on. The ballot is then counted, and the write-in candidate is treated as a non-write-in candidate from that point onwards (from the perspective of this algorithm). When the pairwise vote totals are summed up from each precinct, then if in one precinct a write-in candidate wasn't marked by any voters but in another they were, then similarly the number of votes each candidate in the first precinct is treated as getting against the write-in candidate are the number of ballots that ranked them in the first precinct.

The below-discussed negative counting approach automatically handles write-ins, and requires less markings than the above-mentioned approach when equal-rankings are counted as a vote for both candidates in a matchup.

Notes

Green arrows point from the loser of the matchup to the winner. Yellow arrows indicate a tie. Red arrows (not shown here) indicate the opposite of green arrows (i.e. who lost the matchup).For example, the B>A matchup points to A>B with a green arrow because A pairwise beats B (head-to-head).

Quicker ways to do pairwise counting

Also see the negative vote-counting approach below, which can be quicker than the regular approach depending on how it's implemented.

Sequentially examining each rank on a voter's ballot

The naive way of counting pairwise preferences implies determining, for each pair of candidates, and for each voter, if that voter prefers the first candidate of the pair to the second or vice versa. This requires looking at ballots $O(Vc^{2})$ times. If reading a ballot takes a lot of time, it's possible to reduce the number of times a ballot has to be consulted by noting that if a voter ranks X first, he prefers X to everybody else; if he ranks Y second, he prefers Y to everybody but X, and so on. The Condorcet matrix still has to be updated $O(Vc^{2})$ times, but a ballot only has to be consulted $Vc$ times at most. If the voters only rank a few preferences, that further reduces the counting time.

Techniques for when one is collecting both rated and pairwise information

If using pairwise counting for a rated method, one helpful trick is to put the rated information for each candidate in the cell where each candidate is compared to themselves. For example, if A has 50 points (based on a Score voting ballot), B has 35 points, and C has 20, then this can be represented as:

	A	B	C
A	50 points	A>B	A>C
B	B>A	50 points	B>C
C	C>A	C>B	50 points

This reduces the amount of space required to store and demonstrate all of the relevant information for calculating the result of the voting method.

Pairwise counting used in unorthodox contexts

Pairwise counting can be used to tally the results of Choose-one voting, Approval voting, and Score voting; in these methods, a voter is interpreted as giving a degree of support to each candidate in a matchup, which can be reflected either using margins or (in the case of Score) the voter's support for both candidates in the matchup. See rated pairwise preference ballot#Margins and winning votes approaches for an example.

Defunct sections

Election examples

See Pairwise preference#Election examples

Terminology

See Pairwise preference#Definitions.

Condorcet

See Pairwise preference#Condorcet.

Cardinal methods

See Pairwise preference#Strength of preference and rated pairwise preference ballot.

Negative vote-counting approach

Negative vote-counting approach for pairwise counting (Note: Regular approach may be better in some use cases; see cited discussions in text to the left).

GIF for negative counting. Click on the image and then the thumbnail of the image to see the animation.

There are two steps to the negative counting approach: the information captured by the vote-counters, and the math done to find the final result.

1. Vote-counting: The precinct vote-counters count the following values for a given candidate:
   • The number of voters who ranked/rated/marked a candidate on their ballot.
   • In each head-to-head matchup, the number of voters who explicitly ranked that candidate below the other candidate ("explicitly" meaning they also marked both candidates on their ballot).
2. Math: The final number of votes for the first candidate against the second candidate in each head-to-head matchup is then found by subtracting the second value for the first candidate from the first value.

The ballots marking each candidate can be placed in the blank cell comparing themselves to themselves in the pairwise matrix i.e. for candidate A, the cell A>A would contain the number of voters ranking A.

Note: When using this approach, there is an important caveat when dealing with voters who explicitly rank two candidates equally; see the #Dealing with equal-ranking section below.

Example

If 10 voters vote A>B and 5 voters vote B, then A is explicitly marked on 10 ballots and B on 15, with B being explicitly ranked below A on 10 ballots, and A being explicitly ranked below B on 0 ballots. The number of votes in favor of each candidate is then:

• A>B is (10-0)=10 votes.
• B>A is (15-10)=5 votes.

Dealing with equal-ranking

The negative counting approach, depending on implementation, can require even more markings when equal-ranking is allowed, and it is desired to have comprehensive vote totals, rather than only information about who won, tied, or lost each matchup (i.e. the pairwise margins). This is because if there are 2 candidates A and B, with the votes being:

2 A>B

1 B>A

5 A=B

then either it can be marked that A wins against B by:

• 2 votes to 1
• 7 votes to 6

This is because the voters who equally ranked A and B can be considered to, in the A vs B matchup, either be voting for:

• Neither of them (similar to choose-one FPTP voting; this is the traditional pairwise counting approach).
• Both of them (similar to Approval voting).

This is related to how, in Approval voting, if A has 30 approvals and B 20, and no other information is supplied, then it is impossible to know whether the 20 voters who approved B also approved A or not. This can change who wins if using the winning-votes version of a Category:Defeat-dropping Condorcet method, because not only does it matter who wins the matchup, but also exactly how many voters genuinely preferred the winner to the loser.

Example of the two approaches to equal-ranking

If a voter had ranked 9 of 10 candidates as their 1st choices, and the 10th candidate was unranked (i.e. implicitly ranked last), then at least 9 marks must be made in both approaches, to indicate that 1 voter has ranked each of the 9 candidates who are the voter's 1st choice. In addition:

Explicitly equal-ranked candidates both get a vote

No extra work needs to be done.

Equal-ranked candidates don't get votes

For each matchup, the following number of markings can be made for two candidates A and B:

• 2 markings can be made (1 negative vote for A>B and 1 for B>A). (Note that in essence, this approach involves counting the number of voters who explicitly ranked a given candidate below or equal to the other candidate, rather than only below.)
• 1 negative marking can be made for the A vs B matchup in general, which is later interpreted as a negative vote for both candidates.

In this example, there are 0.5*(9*8)=0.5*72=36 matchups to count between equally-ranked candidates. Accordingly, either 36*2=72 or 36 markings can be made.

Dealing with last-place candidates

It is not necessary to mark that a voter ranked a candidate if they ranked that candidate as their last choice, because this means they wouldn't vote for that candidate in any matchups.

Write-in candidates

This advice is less relevant when write-ins are allowed, however, because even if a voter ranks a candidate last among the candidates named on their ballot, they are still implicitly ranking that candidate above all of the write-in candidates they didn't rank on their ballot.

Comparison to the regular approach

Comparison between the regular approach and negative counting:

• The regular approach: The precinct vote-counters manually count all of the voter's preferences in each head-to-head matchup; in other words, a candidate is assumed to be preferred only in the matchups where the vote-counters mark them as being so.
  • This can be slow, and also can make it difficult to accommodate write-in candidates (see the above section), since the vote-counters won't know ahead of time who those candidates are, and thus won't be able to indicate preferences in those matchups.
• Negative counting approach: The vote-counters mark a candidate as being ranked on a ballot, assume the voter who marked them prefers that candidate in every matchup, and then show which matchups this is not true for.

Note that this negative counting is faster when voters rank only a few of all candidates, and potentially slower otherwise. For example, a voter who votes A>B when there are 10 candidates can be assumed to vote for A and B in every matchup, except they don't prefer B>A. Usually, this would require manually marking those positive preferences, resulting in 9 marks to show A being preferred to all other candidates, and 8 marks to show B preferred to all candidates except A. But negative counting only requires 3 marks: 1 each for A and B to indicate they are preferred in every matchup, and 1 to indicate that this isn't the case for B>A.

Connection to cardinal methods

This approach can be considered an Approval voting-based or cardinal approach, because when explicit equal-rankings are counted as a vote for both candidates in the matchup, then each voter that votes Approval-style (i.e. explicitly ranks some candidates 1st and all others implicitly last) will have their ballot counted like an Approval ballot (i.e. all approved candidates receive one mark, and all disapproved candidates receive no marks).

Using with strength of preference

Negative vote-counting can be used to count weak pairwise preferences (i.e. if a voter only wants to give 0.4 votes in a matchup, rather than 1 vote; see Rated pairwise preference ballot#Implementations) by counting only a "partial ballot" marking a candidate, and partial (i.e. weighted or fractional) negative votes in certain matchups. In other words, it is treated as if only a partial voter supported a candidate (see KP transform).