Difference between revisions of "Pairwise counting"

From Electowiki
Jump to navigation Jump to search
(→‎Dealing with write-in candidates: I think educational images/GIFs should always go as high up in the page as possible. Feel free to discuss this on the talk page.)
 
(75 intermediate revisions by 4 users not shown)
Line 1: Line 1:
'''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.
+
'''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' (usually [[Ranked ballot|ranked]] or [[Rated ballot|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.<ref group=nb>[[Nanson's method|Nanson]] meets the [[Condorcet criterion]] and [[Instant-runoff voting]] meets the [[Condorcet loser criterion]].</ref>
+
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]].
   
== Example without numbers ==
+
== Procedure ==
  +
  +
=== 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:
 
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:
   
Line 16: Line 20:
 
* Number of voters who have no preference for B versus C
 
* 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|pairwise matchup]]".
Often these counts are arranged in a ''pairwise comparison matrix''<ref name=":0">{{Cite book|url=https://books.google.com/?id=q2U8jd2AJkEC&lpg=PA6&pg=PA6|title=Democracy defended|last=Mackie, Gerry.|date=2003|publisher=Cambridge University Press|isbn=0511062648|location=Cambridge, UK|pages=6|oclc=252507400}}</ref> or ''outranking matrix<ref>{{Cite journal|title=On the Relevance of Theoretical Results to Voting System Choice|url=http://link.springer.com/10.1007/978-3-642-20441-8_10|publisher=Springer Berlin Heidelberg|work=Electoral Systems|date=2012|access-date=2020-01-16|isbn=978-3-642-20440-1|pages=255–274|doi=10.1007/978-3-642-20441-8_10|first=Hannu|last=Nurmi|editor-first=Dan S.|editor-last=Felsenthal|editor2-first=Moshé|editor2-last=Machover}}</ref>'' table such as below.
 
  +
  +
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''<ref name=":0">{{Cite book|url=https://books.google.com/?id=q2U8jd2AJkEC&lpg=PA6&pg=PA6|title=Democracy defended|last=Mackie, Gerry.|date=2003|publisher=Cambridge University Press|isbn=0511062648|location=Cambridge, UK|pages=6|oclc=252507400}}</ref> or ''outranking matrix<ref>{{Cite journal|title=On the Relevance of Theoretical Results to Voting System Choice|url=http://link.springer.com/10.1007/978-3-642-20441-8_10|publisher=Springer Berlin Heidelberg|work=Electoral Systems|date=2012|access-date=2020-01-16|isbn=978-3-642-20440-1|pages=255–274|doi=10.1007/978-3-642-20441-8_10|first=Hannu|last=Nurmi|editor-first=Dan S.|editor-last=Felsenthal|editor2-first=Moshé|editor2-last=Machover}}</ref>'' table (though it could simply be called the "candidate head-to-head matchup table") such as below.
 
{| class="wikitable"
 
{| class="wikitable"
 
|+Pairwise counts
 
|+Pairwise counts
Line 41: Line 49:
 
In cases where only some pairwise counts are of interest, those pairwise counts can be displayed in a table with fewer table cells.
 
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.
== Example with numbers ==
 
  +
  +
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 ====
  +
 
{{Tenn_voting_example}}
 
{{Tenn_voting_example}}
As these ballot preferences are converted into pairwise counts they can be entered into a table.
+
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 uses the popularity sequence calculated by the [[Kemeny-Young Maximum Likelihood Method|Condorcet-Kemeny method]], which does calculations that ensure that the sum of the pairwise counts in the upper-right triangular area cannot be increased by changing the sequence of the candidates.
 
  +
The following square-grid table displays the candidates in the same order in which they appear above.
 
{| class="wikitable"
 
{| class="wikitable"
 
|+Square grid
 
|+Square grid
Line 77: Line 91:
 
| -
 
| -
 
|}
 
|}
  +
The following tally table shows another table arrangement.
 
  +
The following tally table shows another table arrangement with the same numbers.
 
{| class="wikitable"
 
{| class="wikitable"
 
|+Tally table
 
|+Tally table
! rowspan="2&quot;" |All possible pairs
 
of choice names
 
! colspan="3" |Number of votes with indicated preference
 
 
|-
 
|-
  +
! rowspan="2&quot;" | All possible pairs<br />of choice names
|
 
  +
! colspan="3" | Number of votes with indicated preference
|'''Prefer X over Y'''
 
  +
!Margin
|'''Equal preference'''
 
|'''Prefer Y over X'''
 
 
|-
 
|-
  +
! style="text-align:left" | Prefer X over Y
|X = Memphis
 
  +
! style="text-align:left" | Equal preference
Y = Nashville
 
  +
! style="text-align:left" | Prefer Y over X
|42%
 
|0
 
|58%
 
 
|-
 
|-
|X = Memphis
+
| align="left" | X = Memphis<br />Y = Nashville
  +
| align="left" | 42%
Y = Chattanooga
 
  +
| align="left" | 0
|42%
 
  +
| align="left" | 58%
|0
 
|58%
+
| -16%
 
|-
 
|-
|X = Memphis
+
| align="left" | X = Memphis<br />Y = Chattanooga
  +
| align="left" | 42%
Y = Knoxville
 
  +
| align="left" | 0
|42%
 
  +
| align="left" | 58%
  +
| -16%
  +
|-
  +
| align="left" | X = Memphis<br />Y = Knoxville
  +
| align="left" | 42%
  +
| align="left" | 0
  +
| align="left" | 58%
  +
| -16%
  +
|-
  +
| align="left" | X = Nashville<br />Y = Chattanooga
  +
| align="left" | 68%
  +
| align="left" | 0
  +
| align="left" | 32%
  +
| +36%
  +
|-
  +
| align="left" | X = Nashville<br />Y = Knoxville
  +
| align="left" | 68%
  +
| align="left" | 0
  +
| align="left" | 32%
  +
| +36%
  +
|-
  +
| align="left" | X = Chattanooga<br />Y = Knoxville
  +
| align="left" | 83%
  +
| align="left" | 0
  +
| align="left" | 17%
  +
| +66%
  +
|}
  +
  +
==== Example using various ballot types ====
  +
  +
[See [[:File:Pairwise counting procedure.png|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 voting|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):
  +
{| class="wikitable"
  +
|+
  +
!
  +
!A
  +
!B
  +
!C
  +
!D
  +
!E
  +
|-
  +
|A
  +
| ---
  +
|2
  +
|2
  +
|2
  +
|2
  +
|-
  +
|B
 
|0
 
|0
  +
| ---
|58%
 
  +
|2
  +
|2
  +
|2
 
|-
 
|-
  +
|C
|X = Nashville
 
Y = Chattanooga
 
|68%
 
 
|0
 
|0
|32%
+
|0
  +
| ---
  +
|2
  +
|2
 
|-
 
|-
  +
|D
|X = Nashville
 
  +
|0
Y = Knoxville
 
|68%
+
|0
  +
|0
  +
| ---
 
|0
 
|0
|32%
 
 
|-
 
|-
  +
|E
|X = Chattanooga
 
Y = Knoxville
 
|83%
 
 
|0
 
|0
|17%
+
|0
  +
|0
  +
|0
  +
| ---
 
|}
 
|}
  +
([https://star.vote star.vote] offers the ability to see the pairwise matrix based off of rated ballots.)
   
  +
===== Inexpressive ballot types =====
==Notes==
 
{{reflist|group=nb}}
 
   
  +
====== Choose-one and Approval ballots ======
== References ==
 
  +
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 ===
  +
[[File:Approaches for handling write-in candidates in pairwise counting.png|thumb|837x837px]]
  +
The difficulty of handling [[Write-in candidate|write-in candidat]]<nowiki/>es depends on how a voter's preference between ranked and unranked candidates is counted.
  +
  +
# If the voter is treated as preferring ranked candidates over unranked candidates (which is the near-universal approach), then write-ins can be difficult to count using pairwise counting, because the vote-counters don't know who they are and thus can't directly record voter preferences in matchups between on-ballot mainstream candidates and write-in candidates.
  +
# If the voter is treated as having no preference between ranked and unranked candidates, then there are no issues to consider with counting write-in candidates under the regular approach.
  +
  +
Below are some ways of dealing with write-ins if unranked candidates are treated in the first way described above.
  +
  +
==== Non-comprehensive approaches ====
  +
  +
* Write-in candidates can be banned. This is the usual approach.
  +
** Write-in candidates can be allowed to run, but with the caveat that only the pairwise preferences of ballots that rank them contribute votes in pairwise matchups featuring them.
  +
*** A slight modification is to comprehensively count only those write-in candidates who are ranked on a significant number of ballots i.e. two rounds of counting may be necessary in each precinct sometimes, one to determine how many ballots write-ins are ranked on, and a second for the major write-ins.
  +
  +
==== Comprehensive approaches ====
  +
These approaches collect all of the pairwise information for write-in candidates i.e. there would be no change in vote totals if the write-in candidate suddenly became one of the on-ballot candidates.
  +
  +
* 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, give each non-write-in candidate a number of votes against the write-in equal to the number of ballots where that non-write-in candidate was explicitly ranked. Then count the ballot and treat the write-in candidate as a non-write-in candidate from that point onwards (from the perspective of this algorithm).
  +
**When creating a precinct subtotal, also record, for each candidate, how many ballots that candidate was explicitly ranked on.
  +
**When combining the pairwise vote totals 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 treat all the ballots from the first precinct to rank every explicitly ranked candidate above the write-in: for each candidate in the first precinct, against the write-in in the second, add the number of voters in the first precinct who explicitly ranked that non-write-in candidate. <ref>{{Cite web|url=https://electowiki.org/wiki/Talk:Condorcet_method|title=Condorcet method|date=2020-05-14|website=Electowiki|language=en|access-date=2020-05-14}}</ref><ref>{{Cite web|url=https://www.reddit.com/r/EndFPTP/comments/fsa4np/possible_solution_to_the_condorcet_writein_problem/fm7bgpd|title=r/EndFPTP - Comment by u/ASetOfCondors on ”Possible solution to the Condorcet write-in problem”|website=reddit|language=en-US|access-date=2020-05-14}}</ref>
  +
* The [[Pairwise counting#Negative vote-counting approach|negative vote-counting approach]] automatically handles write-ins, and requires less markings than the above-mentioned approach when explicit equal-rankings are counted as a vote for both candidates in a matchup. However, it requires a post-processing stage to convert the Condorcet matrix into the more familiar form before usage by Condorcet methods.
  +
  +
==Count complexity==
  +
==== Sequentially examining each rank on a voter's ballot ====
  +
[[File:Pairwise counting with ranked ballot GIF.gif|thumb|576x576px|A GIF for pairwise counting with a [[ranked ballot]], which shows how to sequentially count it one rank at a time. Click on the image and then the thumbnail of the image to see the animation.]]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. In other words, a ballot can be more quickly counted by examining candidates in each of its ranks sequentially from the highest rank on downward. The pairwise 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.
  +
  +
A special case of this speedup is to separately record the first preferences of each ballot, as in a [[First_past_the_post]] count. A voter who ranks a candidate X uniquely first must rank X above every other candidate and no other candidate above X, so there's no need to look at Y>X preferences at all.
  +
  +
===== Uses for first choice information =====
  +
(This actually collects more information than the usual pairwise approach; specifically, if no voters equally rank candidates 1st, then it is possible to determine who the [[FPTP]] winner is, and further, if it can be determined that there is only one candidate in the [[Dominant mutual third set]], then that candidate is the [[IRV]] winner.)
  +
  +
== 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:
  +
{| class="wikitable"
  +
|+
  +
!
  +
! 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.
  +
  +
==Negative vote-counting approach==
  +
See [[Negative vote-counting approach for pairwise counting]] for an alternative way to do pairwise counting. The negative counting approach can be faster than the approach outlined in this article in some cases; for example, a voter who votes A>B when there are 10 candidates requires 9+8=17 markings to be made to count their ballot under the usual approach, but only 3 in the negative counting approach.
  +
  +
== Defunct sections ==
  +
These sections were at one time part of this particle, but have been shifted to the [[Pairwise preference]] article. They are kept here only to avoid breaking any links pointing to them.
  +
  +
=== 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]].
  +
  +
===Notes===
  +
Image to right shows interpretation of ranked ballot.
  +
==References==
 
<references />
 
<references />
  +
  +
==Notes==
  +
<references group="nb" />
  +
  +
[[Category:Majority-related concepts]]
  +
[[Category:Condorcet-related concepts]]

Latest revision as of 09:23, 25 May 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. 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.[nb 1] See the Condorcet section for more information on the use of pairwise counting in Condorcet methods.

Procedure[edit | edit source]

Examples[edit | edit source]

Example without numbers[edit | edit source]

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[1] or outranking matrix[2] 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[edit | edit source]

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)
  1. Memphis
  2. Nashville
  3. Chattanooga
  4. Knoxville
  1. Nashville
  2. Chattanooga
  3. Knoxville
  4. Memphis
  1. Chattanooga
  2. Knoxville
  3. Nashville
  4. Memphis
  1. Knoxville
  2. Chattanooga
  3. Nashville
  4. 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[edit | edit source]

[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[edit | edit source]
Ranked ballots[edit | edit source]

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[edit | edit source]

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

Inexpressive ballot types[edit | edit source]
Choose-one and Approval ballots[edit | edit source]

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[edit | edit source]

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[edit | edit source]

Approaches for handling write-in candidates in pairwise counting.png

The difficulty of handling write-in candidates depends on how a voter's preference between ranked and unranked candidates is counted.

  1. If the voter is treated as preferring ranked candidates over unranked candidates (which is the near-universal approach), then write-ins can be difficult to count using pairwise counting, because the vote-counters don't know who they are and thus can't directly record voter preferences in matchups between on-ballot mainstream candidates and write-in candidates.
  2. If the voter is treated as having no preference between ranked and unranked candidates, then there are no issues to consider with counting write-in candidates under the regular approach.

Below are some ways of dealing with write-ins if unranked candidates are treated in the first way described above.

Non-comprehensive approaches[edit | edit source]

  • Write-in candidates can be banned. This is the usual approach.
    • Write-in candidates can be allowed to run, but with the caveat that only the pairwise preferences of ballots that rank them contribute votes in pairwise matchups featuring them.
      • A slight modification is to comprehensively count only those write-in candidates who are ranked on a significant number of ballots i.e. two rounds of counting may be necessary in each precinct sometimes, one to determine how many ballots write-ins are ranked on, and a second for the major write-ins.

Comprehensive approaches[edit | edit source]

These approaches collect all of the pairwise information for write-in candidates i.e. there would be no change in vote totals if the write-in candidate suddenly became one of the on-ballot candidates.

  • 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, give each non-write-in candidate a number of votes against the write-in equal to the number of ballots where that non-write-in candidate was explicitly ranked. Then count the ballot and treat the write-in candidate as a non-write-in candidate from that point onwards (from the perspective of this algorithm).
    • When creating a precinct subtotal, also record, for each candidate, how many ballots that candidate was explicitly ranked on.
    • When combining the pairwise vote totals 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 treat all the ballots from the first precinct to rank every explicitly ranked candidate above the write-in: for each candidate in the first precinct, against the write-in in the second, add the number of voters in the first precinct who explicitly ranked that non-write-in candidate. [3][4]
  • The negative vote-counting approach automatically handles write-ins, and requires less markings than the above-mentioned approach when explicit equal-rankings are counted as a vote for both candidates in a matchup. However, it requires a post-processing stage to convert the Condorcet matrix into the more familiar form before usage by Condorcet methods.

Count complexity[edit | edit source]

Sequentially examining each rank on a voter's ballot[edit | edit source]

A GIF for pairwise counting with a ranked ballot, which shows how to sequentially count it one rank at a time. Click on the image and then the thumbnail of the image to see the animation.
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. In other words, a ballot can be more quickly counted by examining candidates in each of its ranks sequentially from the highest rank on downward. The pairwise 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.

A special case of this speedup is to separately record the first preferences of each ballot, as in a First_past_the_post count. A voter who ranks a candidate X uniquely first must rank X above every other candidate and no other candidate above X, so there's no need to look at Y>X preferences at all.

Uses for first choice information[edit | edit source]

(This actually collects more information than the usual pairwise approach; specifically, if no voters equally rank candidates 1st, then it is possible to determine who the FPTP winner is, and further, if it can be determined that there is only one candidate in the Dominant mutual third set, then that candidate is the IRV winner.)

Techniques for when one is collecting both rated and pairwise information[edit | edit source]

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[edit | edit source]

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.

Negative vote-counting approach[edit | edit source]

See Negative vote-counting approach for pairwise counting for an alternative way to do pairwise counting. The negative counting approach can be faster than the approach outlined in this article in some cases; for example, a voter who votes A>B when there are 10 candidates requires 9+8=17 markings to be made to count their ballot under the usual approach, but only 3 in the negative counting approach.

Defunct sections[edit | edit source]

These sections were at one time part of this particle, but have been shifted to the Pairwise preference article. They are kept here only to avoid breaking any links pointing to them.

Election examples[edit | edit source]

See Pairwise preference#Election examples

Terminology[edit | edit source]

See Pairwise preference#Definitions.

Condorcet[edit | edit source]

See Pairwise preference#Condorcet.

Cardinal methods[edit | edit source]

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

Notes[edit | edit source]

Image to right shows interpretation of ranked ballot.

References[edit | edit source]

  1. Mackie, Gerry. (2003). Democracy defended. Cambridge, UK: Cambridge University Press. p. 6. ISBN 0511062648. OCLC 252507400.
  2. 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/978-3-642-20441-8_10. ISBN 978-3-642-20440-1. Retrieved 2020-01-16.
  3. "Condorcet method". Electowiki. 2020-05-14. Retrieved 2020-05-14.
  4. "r/EndFPTP - Comment by u/ASetOfCondors on "Possible solution to the Condorcet write-in problem"". reddit. Retrieved 2020-05-14.

Notes[edit | edit source]