Difference between revisions of "Pairwise counting"
(→Notes) 
(Shorten and generalize point about pairwise counting efficiency) 

Line 338:  Line 338:  
==Notes== 
==Notes== 

+  [[File:Pairwise counting procedure.pngthumbThe procedure for pairwise counting with various ballot formats and examples.]] 

−  [[File:Pairwise counting procedure.pngthumbThe procedure for pairwise counting with various ballot formats and examples.]]One potentially useful trick is to, for each voter who has only one 1st choice, report who their 1st choice is, and then skip the pairwise counting for all matchups involving that candidate. So for example, if 3 voters vote A>B>C, then only the fact that there are 3 1st choices for A and 3 voters who prefer B>C need be recorded; this is because a voter prefers their 1st choice to all others, so it can be inferred that 3 unique 1st choices for A means 3 votes for both A>B and A>C. This can be used to save a lot of time for votecounting in elections where most voters only report a few of their top preferences. It is possible to do this even for voters who equally rank multiple candidates 1st; someone who votes A=B>C>D could either be considered to support (A, B) or be considered two separate voters voting A and B each as their 1st choice. Note that the latter approach, while it won't change the margin in the matchup between A and B, and thus won't change who wins in their matchup, will make the vote totals inaccurate. For example, if there was a matchup of 2 to 1 in favor of A>B, and then 100 A=B voters are added to the election, then the matchup would become 102 to 101, which maintains the margin but changes the ratio from 66.66% in favor of A to just over 50%. So to balance this out, it's possible to record a negative vote in the A vs. B matchup to counter the fake positive vote added by treating the indifferent voter as separate voters i.e. 100 votes would be subtracted from both A>B and B>A. 

+  
+  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 <math>O(Vc^2)</math> 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 <math>O(Vc^2)</math> times, but a ballot only has to be consulted <math>Vc</math> 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: 
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: 
Revision as of 10:22, 31 March 2020
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.
Most, but not all, election methods that meet the Condorcet criterion or the Condorcet loser criterion use pairwise counting.^{[nb 1]} 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*(N1) 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^{[1]} or outranking matrix^{[2]} table (though it could simply be called the "candidate headtohead matchup table") such as below.
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
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) 





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 squaregrid table displays the candidates in the same order in which they appear above.
... 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.
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, which appears in the Notes section, 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 Chooseone 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  Writein (0–5)  5 Losses →  3338 (JS) –
165 (wi) 
6057 (DS) –
117 (wi) 
6063 (KW) –
163 (wi) 
6149 (BK) –
116 (wi) 
6658 (AM) –
104 (wi) 
Terminology
The following terms are often used when discussing pairwise counting:
Pairwise matchup: Also known as a headtohead matchup, it is when voters are asked to indicate their preference between two candidates or winner sets, with the one that voters prefer winning. It is usually done on the basis of majority rule (i.e. if more voters prefer one candidate over the other than the number of voters who have the opposing preference, then the candidate preferred by more voters wins the matchup) using chooseone voting, though see the Cardinal methods section for alternative ways. Pairwise matchups can be simulated from ranked or rated ballots and then assembled into a table to show all of the matchups simultaneously; see above.
Pairwise win/beat and pairwise lose/defeated: When one candidate receives more votes in a pairwise matchup/comparison against another candidate, the former candidate "pairwise beats" the latter candidate, and the latter candidate "pairwise loses." Often this is represented by writing "Pairwise winner>Pairwise loser"; this can be extended to show a beatpath by showing, for example, "A>B>C>D", which means A pairwise beats B, B pairwise beats C, and C pairwise beats D (though it may or may not be the case, depending on the context, that, for example, A pairwise beats C).
Pairwise winner and pairwise loser: The candidate who pairwise wins a matchup is the pairwise winner of the matchup (not to be confused with the pairwise champion; see the definition two spots below). The other candidate is the pairwise loser of the matchup. (Note that sometimes "pairwise loser" is also used to refer to a Condorcet loser, which is a candidate who is pairwise defeated in all of their matchups).
Pairwise tie: Occurs when two candidates receive the same number of votes in their pairwise matchup. (Note that sometimes it is also called a tie when there is pairwise cycling, though this is different; see the definition two spots below.)
Pairwise champion: Also known as a beatsall winner or Condorcet winner, it is a candidate who pairwise beats every other candidate. Due to pairwise ties (see above) and pairwise cycling (see below), there is not always a pairwise champion.
Pairwise cycling: Also known as a Condorcet cycle, it is when within a set of candidates, each candidate has at least one pairwise defeat (when looking only at the matchups between the candidates in the set). Note that some cycles can be symmetrical i.e. you can swap the candidates' names without changing the result. (See the Condorcet paradox article for an example, and the neutrality criterion for more information). Such cycles are sometimes called ties.
Minimal pairwise dominant set: Also known as the Smith set, it is the smallest group of candidates who pairwise beat all others. The pairwise champion will always be the only member of this set when they exist.
Pairwise order/ranking: Also known as a Condorcet ranking, it is a ranking of candidates such that each candidate is ranked above all candidates they pairwise beat. Sometimes such a ranking does not exist due to the Condorcet paradox. As a related concept, there is always a Smith ranking that applies to groups of candidates, and which reduces to the Condorcet ranking when one exists.
Condorcet
In a pairwise comparison matrix/table, often the color green is used to shade cells where more voters prefer the former candidate over the latter candidate than the other way around, the color red is used to shade cells where more voters prefer the latter candidate over the former candidate than the other way around, and some other color (often gray, yellow, or uncolored) is used to shade cells where as many voters prefer one candidate over the other as the other way around (pairwise ties).
Pairwise comparison tables are often ordered to create a Smith ranking of candidates, such that the candidates at the top pairwise beat all candidates further down the table, all candidates directly below the candidates at the top pairwise beat all candidates further down the table, etc.
In the context of Condorcet methods:
 A Condorcet winner is a candidate for whom all their cells are shaded green.
 The Smith set is the smallest group of candidates such that all of their cells are shaded green except some of the cells comparing each of the candidates in the group to each other.
 The Schwartz set is the same as the Smith set except some of their cells may be shaded the color for pairwise ties.
 A Condorcet loser is a candidate for whom all their cells are shaded red.
 The weak Condorcet winners and weak Condorcet losers are candidates for whom all of their cells are shaded either green (for the weak Condorcet winners) or red (for the weak Condorcet losers) or the color for pairwise ties.
Cardinal methods
Cardinal methods can be counted using pairwise counting by comparing the difference in scores (strength of preference) between the candidates.
See the Order theory#Strength of preference article for more information. Essentially, instead of doing a pairwise matchup on the basis that a voter must give one vote to either candidate in the matchup or none whatsoever, a voter could be allowed to give something in between (a partial vote) or even one vote to both candidates in the matchup (which has the same effect on deciding which of them wins the matchup as giving neither of them a vote, as it does not help one of them get more votes than the other).
The Smith set is then always full of candidates who are at least weak Condorcet winners i.e. tied for having the most points/approvals. Note that this is not the case if voters are allowed to have preferences that wouldn't be writeable on a cardinal ballot i.e. if the max score is 5, and a voter indicates their 1st choice is 5 points better than their 2nd choice, and that their 2nd choice is 5 points better than their 3rd choice, then this would not be an allowed preference in cardinal methods, and thus it would be possible for a Condorcet cycle to occur. Also, if a voter indicates their 1st choice is 2 points better than their 2nd choice, that this likely automatically implies their 1st choice must be at least 2 points better than their 3rd choice, etc. So there seems to be a transitivity of strength of preference, just as there is a transitivity of preference for rankings. ^{[3]}
Note that when designing a ballot to allow voters to indicate strength of preference in pairwise matchups, it could be done by allowing the voters to rank or score the candidates themselves, and then indicate "between your 1st choice(s) and 2nd choice(s), what scores would you give to each in a pairwise matchup?" or "between the candidates you scored (max score) and the candidates you scored (max score  1), what scores would you give in their pairwise matchups?", etc. Here is an example of one such setup: https://www.reddit.com/r/EndFPTP/comments/fcz3xd/poll_for_2020_dem_primary_using_scored_pairwise/￼￼ and some discussion: https://www.reddit.com/r/EndFPTP/comments/fimqpv/comment/fkkldcl?context=1
Another way of designing pairwise matchups to incorporate strength of preference is to allow the voter to indicate, for each pair of candidates, how they would score both of the candidates.
Notes
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 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 times, but a ballot only has to be consulted 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  A>B  A>C 
B  B>A  35  B>C 
C  C>A  C>B  20 
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   
Multiwinner methods that use pairwise counting, such as CPOSTV and Schulze STV, instead of doing pairwise matchups between individual candidates, do pairwise matchups between sets of candidates (called winner sets).
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. ↑ Nanson meets the Condorcet criterion and Instantrunoff voting meets the Condorcet loser criterion.
References
 ↑ Mackie, Gerry. (2003). Democracy defended. Cambridge, UK: Cambridge University Press. p. 6. ISBN 0511062648. OCLC 252507400.
 ↑ Nurmi, Hannu (2012). Felsenthal, Dan S.; Machover, Moshé (eds.). "On the Relevance of Theoretical Results to Voting System Choice". Electoral Systems. Springer Berlin Heidelberg: 255–274. doi:10.1007/9783642204418_10. ISBN 9783642204401. Retrieved 20200116.
 ↑ https://www.reddit.com/r/EndFPTP/comments/fcexg4/score_but_for_every_pairwise_matchup/