Pairwise counting

From Electowiki
Revision as of 16:50, 15 March 2020 by VoteFair (talk | contribs) (Moved huge image to the section it relates to)
Jump to navigation Jump to search

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.

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

Note that in order to know the number of voters who have no preference between two candidates, the only values that need be known are the number of voters who prefer the first over the second, the number of voters that prefer the second over the first, and the number of total voters in the election. This is done by subtracting the first two categories (which together are the number of voters who have any preference between the two candidates) from the number of total voters.

In general, for N candidates, there are 0.5*N*(N-1) pairwise matchups to consider. So for 1 candidate, there are 0 matchups, 2 candidates, 1 matchup, 3 candidates, 3 matchups, 4 candidates, 6 matchups, 5 candidates, 10 matchups, 6 candidates, 15 matchups, 7 candidates, 21 matchups, etc.

Often these counts are arranged in a pairwise comparison matrix[1] or outranking matrix[2] 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 (i.e. candidate B can't be compared to candidate B, since there's only one candidate in the comparison), the cell that does so is always empty.

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

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
Prefer X over Y Equal preference Prefer Y over X
X = Memphis
Y = Nashville
42% 0 58%
X = Memphis
Y = Chattanooga
42% 0 58%
X = Memphis
Y = Knoxville
42% 0 58%
X = Nashville
Y = Chattanooga
68% 0 32%
X = Nashville
Y = Knoxville
68% 0 32%
X = Chattanooga
Y = Knoxville
83% 0 17%

Another example with numbers

If there are five candidates A, B, C, D and E, and two voters submit the ranked ballots A>B>C, this means that they prefer A over B, B over C, and A over C, with (if it is assumed unranked candidates are ranked equally last) all three of these ranked candidates being preferred over either D or E.

If, for the same example, those two voters instead submit rated ballots of A:5 B:4 C:3 (meaning A is given a score of 5, B a 4, and C a 3, with D and E left blank), pairwise preferences can be inferred from this as well; because A is scored higher than B, and B is scored higher than C, it is known that these ballots indicate that A is preferred to B, B to C, and A to C, and (if blank scores are assumed to mean the lowest score i.e. usually a 0) all 3 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.)

Partial pairwise comparisons can be done using Choose-one voting ballots and Approval voting ballots, 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.

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)


Terminology

The following terms are often used when discussing pairwise counting:

Pairwise win/beat and pairwise lose: 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."

Pairwise winner and pairwise loser: The candidate who pairwise wins is the pairwise winner of the matchup. The other candidate is the pairwise loser of the matchup.

Pairwise tie: Occurs when two candidates receive the same number of votes in their pairwise matchup.

Pairwise order/ranking: Also known as a Condorcet ranking, is the 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

The procedure for pairwise counting with various ballot formats and examples.
Pairwise matchups done using Score voting to indicate strength of preference in each matchup.

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

Cardinal methods can be counted using pairwise counting, by looking at the difference in scores (strength of preference) between each candidate. 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

References

  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. https://www.reddit.com/r/EndFPTP/comments/fcexg4/score_but_for_every_pairwise_matchup/