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.

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.

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.

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.

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.

To identify which candidate wins a specific pairwise matchup, such as between candidates A and B, subtract the value of B>A from A>B. If the resulting value is positive, then candidate A won the matchup. If it is zero, then there is a pairwise tie. If the result is negative, then candidate B won the matchup. (See the Terminology section for details.)

Sometimes only the "dominance relation" (wins, losses, and ties) is shown, rather than the exact numbers. So for example, if A beat B in their pairwise matchup, it'd be possible to write "Win" (or a green checkmark) in the A>B cell and "Loss" (or a red X) in the B>A cell.

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.

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.

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.)

Pairwise counting also can 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.

Note that when a candidate is unmarked it is generally treated as if the voter has no preference between the unmarked candidates. 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.

Election examples

Here is an example of a pairwise victory table for the Burlington 2009 election:

			wi	JS	DS	KW	BK	AM
	AM	Andy Montroll (5–0)						5 Wins ↓
	BK	Bob Kiss (4–1)					1 Loss → ↓ 4 Wins	4067 (AM) – 3477 (BK)
	KW	Kurt Wright (3–2)				2 Losses → 3 Wins ↓	4314 (BK) – 4064 (KW)	4597 (AM) – 3668 (KW)
	DS	Dan Smith (2–3)			3 Losses → 2 Wins ↓	3975 (KW) – 3793 (DS)	3946 (BK) – 3577 (DS)	4573 (AM) – 2998 (DS)
	JS	James Simpson (1–4)		4 Losses → 1 Win ↓	5573 (DS) – 721 (JS)	5274 (KW) – 1309 (JS)	5517 (BK) – 845 (JS)	6267 (AM) – 591 (JS)
	wi	Write-in (0–5)	5 Losses →	3338 (JS) – 165 (wi)	6057 (DS) – 117 (wi)	6063 (KW) – 163 (wi)	6149 (BK) – 116 (wi)	6658 (AM) – 104 (wi)

To read this, take for example the cell where BK is compared to AM (the cell with BK on the left and AM on the top); "4067 (AM)" means that 4067 voters preferred AM (Andy Montroll) over BK (Bob Kiss), and "3477 (BK)" means that 3477 voters preferred BK over AM. Because AM got more votes than BK in that matchup, AM won that 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).

Pairwise counting can be used to tally the results of Choose-one voting, Approval voting, Score voting, and Category:Pairwise counting-based voting methods. In the first 3 methods, a voter is interpreted as giving a degree of support to each candidate in a matchup. Even IRV can be understood to some extent when observing its compliance with the dominant mutual third property.

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.

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.

It may help to put the % of the votes a candidate got in the pairwise matchup. So, for example:

	A	B
A	---	56%
B	44%	---

When looking at two candidates, a quick way to figure out the number of votes for the first candidate>second candidate and vice versa is to first locate the cell for "first candidate>second candidate", count the minimum number of cells diagonally one must go to be adjacent to the middle dividing line of the matrix (where there is a --- cell), and then going one cell further diagonally (meaning you'll be starting from the closest cell on the opposite side of that dividing line), go that number of cells further diagonally to reach the other cell. For example:

	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	---

Try locating A>D (the fifth cell in the second row). To find the reverse, D>A, first you check and see that you have to go one cell down and to the left to be adjacent to the middle dividing line. Then, starting from the cell one cell down and to the left of the middle dividing line, go one cell further down and to the left to reach D>A. In doing this, you would start at A>D, go down to B>C, then jumping over the middle dividing line to C>B, go down to D>A.

One of the notable aspects of pairwise counting is that it can be used to find a Condorcet winner or member of the Smith set in a simple manner without needing to be done with written ballots; see Category:Sequential comparison Condorcet methods for more information.

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).

The usual approach to pairwise counting is for the precinct vote-counters to mark all of the voter's preferences in each head-to-head matchup. This can be slow, and also can make it difficult to accommodate write-in candidates, 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. An alternative method of pairwise counting is the "negative votes/counting" approach: the precinct vote-counters simply indicate how many voters ranked/rated/marked a candidate on their ballot, and which candidates the voter ranked above (or equal to, depending on implementation) the candidates they marked. In other words, the vote-counters assume a voter prefers a candidate they marked in all matchups against other candidates, and then work to indicate which matchups this is not true for.

Note that this is faster when voters rank only a few of all candidates, and 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 vs A.

The negative counting approach requires even more markings when it is desired to have comprehensive vote totals, rather than only information about who won, tied, or lost each matchup. This is because if there are 2 candidates A and B, with 2 voters preferring A>B, 1 preferring B>A, and 5 voting A=B, then either it can be marked that A wins against B 2 to 1, or 7 to 6. This is because the voters who equally ranked A and B can be considered to be voting for both of them in their matchup. This is similar 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 issue is most relevant when trying to get accurate winning votes totals. To do so, either two markings can be made (1 negative vote for A>B and 1 for B>A) or one (1 negative marking for the A vs B matchup in general, which is later interpreted as a negative vote for both candidates).

Writeup on solving the write-in issue for pairwise counting:

Bonus: The votes for each candidate can be placed in the blank cell comparing themselves to themselves in the pairwise matrix i.e. A>A would contain A's votes [number of voters ranking them].

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. 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 write-in candidates they didn't rank on their ballot.