|
'''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|pairwise matchup]]. This is done by looking at voters' 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.<ref group=nb>[[Nanson's method|Nanson]] meets the [[Condorcet criterion]] and [[Instant-runoff voting]] meets the [[Condorcet loser criterion]].</ref> See the [[Pairwise counting#Condorcet|Condorcet section]] for more information on the use of pairwise counting in [[Condorcet methods]].
|}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.
== Terminology ==
See [[Pairwise preference#Definitions]].
The following terms are often used when discussing pairwise counting:
'''Pairwise matchup''': Also known as a head-to-head 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 [[Choose-one voting|choose-one voting]], though see the [[Pairwise counting#Cardinal methods|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 (or the former candidate is "pairwise preferred" to 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 beats-all 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|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|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 set ranking|Smith ranking]] that applies to groups of candidates, and which reduces to the Condorcet ranking when one exists.
== Condorcet ==
See [[Pairwise preference#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 set ranking|Smith ranking]] of candidates, such that the candidates at the top [[Pairwise counting#Terminology|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 criterion|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 ==
See [[Pairwise preference#Strength of preference]] and [[rated pairwise preference ballot]].
Cardinal methods can be counted using pairwise counting by comparing the difference in scores (strength of preference) between the candidates, rather than only the number of voters who prefer one candidate over the other. See the [[rated pairwise preference ballot]] article.
Note that pairwise counting can be done either by looking at the margins expressed on a voter's ballot, or the "winning votes"-relevant information (see [[Defeat strength]]). For example, a voter who scores one candidate a 5 and the other a 3 on a rated ballot can either be thought of as giving those scores to both candidates in the matchup (winning votes-relevant information) or as giving 2 points to the first candidate and 0 to the second (only the margins). For ranked and choose-one ballots, both margins and winning votes approaches yield the same numbers, since a voter can only give maximal support to at most one candidate in the matchup.
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 writable 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.<ref>{{Cite web|url=https://www.reddit.com/r/EndFPTP/comments/fcexg4/score_but_for_every_pairwise_matchup/|title=r/EndFPTP - Score but for every pairwise matchup|website=reddit|language=en-US|access-date=2020-04-05}}</ref>
==Notes==
[[File:Pairwise counting procedure.png|thumb|The procedure for pairwise counting with various ballot formats and examples.]]
Pairwise counting can be used to understandtally the results of [[Choose-one voting]], [[Approval voting]], [[Score voting]], and [[:Category:Pairwise counting-based voting methods|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 <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.
|}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.
Multi-winner methods that use pairwise counting, such as [[CPO-STV]] 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.
|