Pairwise counting: Difference between revisions
no edit summary
No edit summary |
|||
Line 4:
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 ===
Line 209:
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 ===
==== Non-comprehensive approaches ====
A comprehensive approach is to, 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, the number of votes each non-write-in candidate gets against the write-in candidate is the number of ballots they were so far ranked on. The ballot is then counted, and the write-in candidate is treated as a non-write-in candidate from that point onwards (from the perspective of this algorithm). When the pairwise vote totals are summed up 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 the number of votes each candidate in the first precinct is treated as getting against the write-in candidate are the number of ballots that ranked them in the first precinct. <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> ▼
* Write-in candidates can be banned. This is the usual approach.
The below-discussed negative counting approach automatically handles write-ins, and requires less markings than the above-mentioned approach when equal-rankings are counted as a vote for both candidates in a matchup. ▼
** 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.
==== 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.
▲* A comprehensive approach is to, 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, the number of votes each non-write-in candidate gets against the write-in candidate is the number of ballots they were so far ranked on. The ballot is then counted, and the write-in candidate is treated as a non-write-in candidate from that point onwards (from the perspective of this algorithm). When the pairwise vote totals are summed up 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 the number of votes each candidate in the first precinct is treated as getting against the write-in candidate are the number of ballots that ranked them in the first precinct. <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
==Notes==
Line 219 ⟶ 227:
=== Quicker ways to do pairwise counting ===
Also see the
==== Sequentially examining each rank on a voter's ballot ====
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.
==== Counting first choices separately ====
For every voter who ranks a candidate as their only 1st choice, because it is known they prefer this candidate over all others, it is possible to speed up the usual pairwise counting procedure by modifying it in the following way:
* Information collected by vote-counters:
*# Count the '''['''number of voters who rank a candidate as their only 1st choice''']'''
*# For those voters' ballots, don't count any preferences in head-to-head matchups involving their unique 1st choice candidate
* Math: Each candidate has as many votes added in favor of them as the '''['''number of ballots that ranked them uniquely 1st''']'''
This can be further generalized to handle ballots that equally rank multiple candidates 1st, but with a caveat; see [[Negative vote-counting approach for pairwise counting#Dealing with equal-ranking]].
===== 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 ===
Line 253 ⟶ 281:
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==▼
=== Defunct sections ===▼
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.▼
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.
See [[Pairwise preference#Election examples]]
See [[Pairwise preference#Definitions]].
See [[Pairwise preference#Condorcet]].
See [[Pairwise preference#Strength of preference]] and [[rated pairwise preference ballot]].
▲==Negative vote-counting approach==
▲See [[Negative vote-counting approach for 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.
==References==
| |||