# Pairwise preference

(Redirected from Dominating set)

Pairwise preferences are voters' preferences between pairs of candidates (their preferences in head-to-head matchups between candidates). Pairwise counting is used to extract this information from voters' ballots, and it is then used in all Category:Pairwise counting-based voting methods, which are mostly just the Condorcet methods, to help determine the winner of the election.

## Pairwise matchups

A pairwise matchup is when voters choose between two candidates, with there being a winner and loser, or a tie (the possibility of which will only intermittently be discussed throughout this article). The idea is that when there are only two options to choose from, it's always possible to get a majority in favor of one of them, because any votes that don't go to one must have gone to the other. A major argument in favor of analyzing pairwise preferences is that it minimizes the ability of strategic nomination to affect the race, that is, Independence of irrelevant alternatives is maximally satisfied (though not completely, if using majority rule) by ensuring candidates who enter or drop out of the race play less of a role in deciding which of the remaining candidates wins.

### Ways of collecting pairwise information

#### Manually doing each pairwise matchup

The most direct way to conduct a pairwise comparison is to ask voters "Who do you prefer between these two candidates" for every pair of candidates. However, this would be rather onerous when there are more candidates running, and could even result in violations of transitivity: a voter could say they prefer A>B (A over B in the A vs B matchup), B>C, and C>A, which means that if these were the only 3 candidates in the election, and the voter had total power to decide which of them won, then they'd be unable to make up their mind, since for whichever one they choose, they'd want to pick someone else (in fact, when voters express these cyclical preferences on their ballots, the common approaches to making their preferences "rational"/acyclical are to either ignore the last or lowest part of the cycle, such that A>B>C>A becomes A>B>C, or to treat all candidates as equally preferred, i.e. A=B=C, though the noncyclical preferences the voter expressed in regard to these candidates versus other candidates are still respected).

#### Collecting pairwise information from ranked ballots

Thus, in the context of voting, it's more common to ask voters to indicate their preference using a ballot type that automatically imposes transitivity, usually with a ranked ballot (though rated ballots are also sometimes used; theoretically, any ballot type that allows a voter to indicate at least one pairwise preference works for this purpose). The use of a transitive ballot type has the further advantage that, because it is usually assumed a voter prefers every candidate they mark a preference for over every unmarked candidate, voters don't have to explicitly mark all of their preferences.

### Identifying the winner of the matchup

To identify which candidate wins a specific pairwise matchup, such as between candidates A and B, subtract the value of B>A (the number of voters who prefer B to 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 margins.

## Definitions

The following terms are often used when discussing pairwise preferences:

• 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 (i.e. give more votes to) 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, though see the Strength of preference 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.
• 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 (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.) Note that some cycles can be symmetrical ties i.e. you can swap the candidates' names without changing the result. (See the Condorcet paradox article for an example, and the neutrality criterion and tie for more information).
• 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).
• Minimal pairwise dominant set: Also known as the Smith set, it is the smallest dominating set, which is any group of candidates who beat all candidates not in the group. The pairwise champion will always be the only member of this set when they exist.
• Note that the terms dominating/dominant are often used as shorter versions of pairwise-dominant.
• 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.

## Presenting pairwise preferences

This section covers how to demonstrate pairwise preferences.

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.

### Vertical versus horizontal

A pairwise table may be demonstrated either vertically or horizontally; that is, for the following horizontal table:

Horizontal table; Wins are bolded
A B C
A --- 35 40
B 27 --- 37
C 31 42 ---

it could also be written vertically as

Vertical table
A B C
A --- 27 31
B 35 --- 42
C 40 37 ---

### Percentages

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

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

### Election examples

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

 Andy Montroll Bob Kiss Kurt Wright 4 wins and no losses (4-0) 4 Wins ↓ 3 wins, 1 loss (3-1) 1 Loss → ↓ 3 Wins 4064 (Montroll) – 3476 (Kiss) 2 wins, 2 losses (2-2) 2 Losses → 2 Wins ↓ 4313 (Kiss) – 4061 (Wright) 4597 (Montroll) – 3664 (Wright) 1 win, 3 losses (1-3) 3 Losses → 1 Win ↓ 3971 (Wright) – 3793 (Smith) 3944 (Kiss) – 3576 (Smith) 4570 (Montroll) – 2997 (Smith) 0 wins, 4 losses (0-4) 4 Losses → 5570 (Smith) – 721 (Simpson) 5270 (Wright) – 1310 (Simpson) 5514 (Kiss) – 844 (Simpson) 6262 (Montroll) – 591 (Simpson)

In the top-right cell containing numbers (with "4064 (Montroll) - 3476 (Kiss)"), the "4064 (Montroll)" text means that 4067 voters preferred Andy Montroll over Bob Kiss, and "3477 (Kiss)" means that 3477 voters preferred Bob Kiss over Andy Montroll. Because more voters preferred Andy Montroll over Bob Kiss in that matchup (judging by their ballots), Montroll won that matchup.

## Condorcet

In a pairwise comparison matrix/table, often the color green is used to shade cells with pairwise victories (where more voters prefer the former candidate over the latter candidate than the other way around), the color red is used to shade cells with pairwise defeats (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 with pairwise ties (where as many voters prefer one candidate over the other as the other way around).

Pairwise comparison tables are often ordered to create a Smith ranking of candidates, such that whenever possible, the candidates can be divided into upper and lower groups such that every candidate in the upper group pairwise beats every candidate in the lower group. This is most easily accomplished by using the Copeland ranking.

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.

## Strength of preference

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 for a way to do this on a per-matchup basis.

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

### Margins and winning votes approaches

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 Rated pairwise preference ballot#Margins and winning votes approaches).

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)
• 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 these approaches assume a voter gives either:

• Maximal support/margin (1 vote) to their preferred candidate in the matchup, when they have one (which they can only achieve by giving maximal support to the preferred candidate and no support to the other candidate in the winning votes approach, so as to create maximal distance).
• No support (0 votes) to either candidate, when they equally prefer both candidates.

### Transitivity requirements

If every voter indicates the same rated preference for each pair of candidates, then the Smith set is 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.)[1]

## Uses

Pairwise preferences can be used to find the order of finish of any Condorcet method when there is a Condorcet ranking, and can always be used to calculate a complete result in Category:Defeat-dropping Condorcet methods. They can sometimes be used in Category:Runoff-based voting methods to avoid having to do additional rounds of counting (i.e. because no matter which candidates enter the runoff, the result is already known).

When combined with rated information, it is possible to surmise some additional information about how voters scored the candidates. For example, if 2/3rds of the voters prefer A>B, yet B has a higher points total than A, then the A>B voters must have received less than half the utility gain of going from their less-preferred candidate in the matchup to their more-preferred candidate as the B>A voters.

## Criticism

One major criticism of pairwise preferences is that they are harder to understand and think about because a candidate's quality can't be completely summed up into one number, like in cardinal methods.

Another criticism is that it can be harder to do pairwise counting than it is to count the vote in other methods, such as Approval voting. The Rated pairwise preference ballot#Rated or ranked preference implementation can potentially mitigate this criticism, because for every voter who indicates a rated preference, at most only one piece of information need be collected from their ballot for every candidate they marked (their score for the candidate), rather than several pairwise preferences.

### Incomparability of separate pairwise data sets

The nature of pairwise preferences prevents direct comparisons of candidates from two separate elections, unlike with rated methods or other methods. For example, it is possible to compare Reagan's approval rating in polls from the 1980s to Obama's in the 2010s without having to ask voters about both in the same election/poll, but their pairwise matchup against each other can't be evaluated like that.

## Notes

The rated pairwise preference ballot allows the voter to express the most nuanced pairwise information of all ballot types.

The interpretation of pairwise ties can conceptually link different concepts together sometimes. For example, the Smith set and Schwartz set are identical except that one treats a tie as counting against both tied candidates (i.e. it's as bad as a defeat) in terms of their deservingness to be in the set or not, while the other treats a tie as having no relevance to the quality of either of the tied candidates.

### Casual usage

One of the notable aspects of pairwise preferences is that a Condorcet winner or member of the Smith set can be found in a simple manner without needing to be done with written ballots; for each pair of candidates, the voters can be asked to raise their hands for the one they prefer, with the pairwise loser being eliminated, and this repeating until only one candidate remains. This rivals the simplicity of Approval voting for casual usage purposes, since a relatively similar amount of work is done both ways, though it can create failures of transitivity. See Category:Sequential comparison Condorcet methods for more information.

### Understanding non-pairwise methods using pairwise preferences

Pairwise preferences can be used to understand Weighted positional methods and their generalizations (such as Choose-one voting, Approval voting, and 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 in this way to some extent when observing its compliance with the dominant mutual third property.

### Required amount of information to collect

Pairwise preferences require (N^2 - N) pieces of information for N candidates. This is because each candidate can get a different number of votes in favor of then in each of their matchups against other candidate, resulting in 0.5*(N^2 - N) matchups. See also Precinct summability.

### Number of allowed transitive pairwise preferences

Most pairwise criteria (Condorcet criterion, Smith, etc.) assume a voter may indicate as many transitive pairwise preferences as desired i.e. they may place each candidate in a separate rank. Some Category:Pairwise counting-based voting methods actually violate this by limiting the number of slots voters have, such as common implementations of Smith//Score. This can be done for practical reasons (to keep the ballot smaller, potentially, or to limit the amount of vote-counting work necessary, since generally matchups between candidates at the same rank do not need to be counted), or for more philosophical reasons; some object to the idea that a voter should be able to put a full vote "between" every transitive pair of candidates (because it may be unlikely for voters to honestly feel such maximally strong preferences), and so wish to limit the number of available ranks. Indeed, when a voter can only indicate two ranks (or also give candidates partial support between these two ranks), then you get Score voting, because if you give 1 vote to help A beat B, then you must give 0 votes for B>C (or if you give 0.6 votes A>B, then you can't give 0.5 votes B>C). The Rated pairwise preference ballot can be implemented with fewer ranks than candidates in this manner, which then forces preference compression (or, more complexly, no, or a less strict, limitation on ranks might be imposed, but the voter might be required to indicate a weak preference between at least some of the ranks).

Because of preference compression, which can happen also for strategic voting purposes i.e. Min-max voting, it's not always possible to get accurate pairwise data from rated ballots. Thus, it is often useful to differentiate between a candidate who gets at least half of all voters to prefer them over their opponents in head-to-head matchups, rather than only at least half of all voters with preferences in the relevant matchups (i.e. they tie or Majority-beat their opponents), since no matter what preferences preference-compressing voters have in those matchups, the candidate in question will at least tie or win the matchup no matter what. Example:

25 A:5 B:4

26 B:5 A:5 (honest preference was A:4)

49 C:5 D:5

Here, the CW based on honest pairwise preferences is B, but because of min-max voting (potentially done to ensure at least one of A or B enter the runoff rather than both C and D), it looks like A is the CW.

### Multi-winner pairwise methods

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