User:BetterVotingAdvocacy/Negative vote-counting approach for pairwise counting: Difference between revisions
User:BetterVotingAdvocacy/Negative vote-counting approach for pairwise counting (view source)
Revision as of 20:14, 12 October 2020
, 3 years agono edit summary
No edit summary |
|||
Line 1:
[[File:Adding ballot matrices in negative pairwise counting approach.png|thumb|1088x1088px|Note in "Step 1: Combination" that the two ballots' negative pairwise matrices are added up.[[File:Pairwise counting negative counting with ranked ballot GIF.gif|thumb|454x454px|GIF for negative counting. Click on the image and then the thumbnail of the image to see the animation.]]]]
The negative counting approach is an alternative method of doing [[pairwise counting]]. It is faster (i.e. requires less marks and tallying), depending on implementation, when voters
Semi-negative pairwise counting, which is theoretically even faster, is based on using both of the regular and negative pairwise counting techniques. There are also vote-counting techniques based on similar principles that can be used in non-pairwise contexts, such as for [[Score voting]] and various [[PR]] methods.
== Description ==
Line 19 ⟶ 21:
The number of ballots marking each candidate can be placed in the blank cell comparing themselves to themselves in the pairwise matrix i.e. for candidate A, the cell A>A would contain the number of voters ranking A.<ref>{{Cite web|url=https://www.reddit.com/r/EndFPTP/comments/fsa4np/possible_solution_to_the_condorcet_writein_problem/|title=Possible solution to the Condorcet write-in problem|last=|first=|date=|website=|url-status=live|archive-url=|archive-date=|access-date=}}</ref>
'''<big>Note</big>''': When using this approach, there is an important caveat to consider when dealing with voters who explicitly rank two candidates equally which can alter the vote totals; see the [[#Dealing with equal-ranking]] section below.
* Negative vote-counting can be used to yield accurate vote totals for pairwise matchups involving regular candidates versus write-in candidates, but this comes at the cost of greater complexity in terms of how last-ranked candidates are counted; see [[#Dealing with last-ranked candidates]].
=== Example ===
Line 50 ⟶ 52:
|-
|A
|''-10
|0 votes
|-
|B
| -10 votes
|''-15
|}
becoming:
Line 75 ⟶ 77:
=== Dealing with equal-ranking ===
The negative counting approach, depending on implementation, can require even more markings when equal-ranking is allowed and it is desired to have traditional pairwise vote totals. Any implementation of negative counting will give accurate information about who won, tied, or lost each matchup (i.e. the pairwise [[margins]]), however. This is because if there are 2 candidates A and B, with the (explicit) votes being:
▲The negative counting approach, depending on implementation, can require even more markings when equal-ranking is allowed and it is desired to have traditional pairwise vote totals. Any implementation of negative counting will give accurate information about who won, tied, or lost each matchup (i.e. the pairwise [[margins]]), however. This is because if there are 2 candidates A and B, with the (explicit) votes being: <blockquote>2 A>B
1 B>A
Line 90:
* Neither of them (similar to [[FPTP|choose-one FPTP voting]]; this is the traditional pairwise counting approach).
* Both of them (similar to [[Approval voting]]).
**To get this value, one must consider a voter to "prefer A and B simultaneously" in the matchup between the two. It may be easier to think of this as the voter "supporting" or "liking" both, rather than preferring them; this is the type of support measured by Score voting and the [[rated pairwise preference ballot]] in 2-candidate elections (with no write-ins), real or simulated.
This is related to how, in [[Approval voting]], if A has 30 approvals and B 20, and no other information is supplied, then it is impossible to know whether any of the 20 voters who approved B also approved A or not.
Line 112 ⟶ 113:
* 2 markings can be made (1 negative vote for A>B and 1 for B>A).
**Note: In essence, this approach involves counting the number of voters who explicitly ranked a given candidate '''below''' '''<big>or equal</big>''' to the other candidate, rather than only '''below'''.
* 1 negative marking can be made for the A vs B matchup in general, which is later interpreted as a negative vote for both candidates. (Note that this may require more values to be recorded, since not only are values recorded for the number of votes on both sides of a matchup, but also for each individual matchup)
</blockquote>In this example, there are 0.5*(9*8)=0.5*72='''36''' matchups to count between equally-ranked candidates. Accordingly, at least either 36*2='''72''' or '''36''' markings must be made.
=== Dealing with last-place candidates ===▼
It is not necessary to make any markings for a candidate a voter ranked as their last choice, because this means they wouldn't vote for that candidate in any matchups. One way of thinking about this is that if the voter hadn't ranked that candidate, then no marks would've been made to count them, and in effect the voter would still be treated as ranking them last. ▼
This can save a great deal of work in some cases; if a voter ranks all of 10 candidates, and ranks 5 of them last (i.e. they are all ranked 6th), then 5*(5+1)=30 fewer marks need be made if not counting them (explanation for the math: there are 5 such candidates, and they are each ranked under 5 candidates, with 1 additional mark made to record that they were ranked by the voter). In fact, if not using this trick, negative counting can actually require more marks than regular counting in some cases. ▼
==== Write-in candidates ====▼
This advice is less relevant when write-ins are allowed, however, because even if a voter ranks a candidate last among the candidates named on their ballot, they are still implicitly ranking that candidate above all of the write-in candidates they didn't rank on their ballot. So if last-ranked candidates aren't counted, then it may be necessary to modify how the calculation is done, or otherwise mention caveats in the final result, to avoid giving the impression that the vote totals are accurate for the matchups involving write-in candidates (however, the totals will only be off by the number of voters that rank a non-write-in candidate last and don't rank the write-in candidate for a given matchup between such candidates). ▼
It is possible to make a special marking for a last-choice candidate that indicates they are not preferred over any of the on-ballot (regular) candidates, but that they are preferred over all write-in candidates. It would then only be necessary to record negative votes for matchups involving write-in candidates who are ranked above the last-choice candidate on some ballots. This would mean making at most two additional marks for every last-ranked candidate on a ballot, because in practice, in most elections, voters are only allowed to write in at most one candidate.<ref>{{Cite web|url=https://forum.electionscience.org/t/negative-vote-counting-approach-for-pairwise-counting/644|title=Negative vote-counting approach for pairwise counting|date=2020-04-27|website=The Center for Election Science|language=en-US|access-date=2020-09-15}}</ref> This can be compared to the regular approach to dealing with write-ins at [[Pairwise counting#Dealing with write-in candidates]]. ▼
== Semi-negative counting procedure ==
Line 129 ⟶ 120:
{| class="wikitable"
|+Negative counting values ''italicized'', regular pairwise counting values normal, and semi-negative counting values bolded and <big>big</big>
!Number of marks made
(smaller number = better)
!Voter's ranking
!
Line 137 ⟶ 130:
!E
|-
|'''1''' vs 4
|1st (choice)
|A
Line 145 ⟶ 139:
|<small>1</small>
|-
|'''2''' vs 3
|2nd
|B
Line 153 ⟶ 148:
|<small>1</small>
|-
|3 vs '''2'''
|3rd
|C
Line 161 ⟶ 157:
|'''<big>1</big>'''
|-
|4 vs '''1'''
|4th
|D
Line 169 ⟶ 166:
|'''<big>1</big>'''
|-
|5 vs '''0'''
|5th
|E
Line 181 ⟶ 179:
* With regular counting, this ballot would require at least '''10''' marks to count.
** The same applies to negative counting when last-ranked candidates aren't counted.
* With semi-negative counting, it only required '''6''' marks to count.
With semi-negative counting, it is possible to reduce the number of marks required to count a ballot by roughly half or greater, depending on which of the other two approaches it is compared to, and how many of the candidates are ranked by the voter. The positive and negative marks can either be stored as separate values, or they can be combined during the counting (i.e. 5 positive votes for A>B and 3 negative votes for A>B can be stored as 2 votes for A>B. This means incrementing and decrementing the same number during the count, so it could be confusing).
▲=== Dealing with last-place candidates ===
▲
▲This can save a great deal of work in some cases; if a voter ranks all of 10 candidates, and ranks 5 of them last (i.e. they are all ranked 6th), then 5*(5+1)=30 fewer marks need be made if not counting them (explanation for the math: there are 5 such candidates, and they are each ranked under 5 candidates, with 1 additional mark made to record that they were ranked by the voter). In fact, if not using this trick, negative counting can actually require more marks than regular counting in some cases.
▲==== Write-in candidates ====
▲This advice is less relevant when write-ins are allowed, however, because even if a voter ranks a candidate last among the candidates named on their ballot, they are still implicitly ranking that candidate above all of the write-in candidates they didn't rank on their ballot. So if last-ranked candidates aren't counted, then it may be necessary to modify how the calculation is done, or otherwise mention caveats in the final result, to avoid giving the impression that the vote totals are accurate for the matchups involving write-in candidates (however, the totals will only be off by the number of voters that rank a non-write-in candidate last and don't rank the write-in candidate for a given matchup between such candidates).
▲It is possible to make a special marking for a last-choice candidate that indicates they are not preferred over any of the on-ballot (regular) candidates, but that they are preferred over all write-in candidates. It would then only be necessary to record negative votes for matchups involving write-in candidates who are ranked above the last-choice candidate on some ballots. This would mean making at most two additional marks for every last-ranked candidate on a ballot, because in practice, in most elections, voters are only allowed to write in at most one candidate.<ref>{{Cite web|url=https://forum.electionscience.org/t/negative-vote-counting-approach-for-pairwise-counting/644|title=Negative vote-counting approach for pairwise counting|date=2020-04-27|website=The Center for Election Science|language=en-US|access-date=2020-09-15}}</ref> This can be compared to the regular approach to dealing with write-ins at [[Pairwise counting#Dealing with write-in candidates]].
=== Regular pairwise counting but done by counting first choices separately ===▼
Note that regular pairwise counting can have its required number of marks reduced, without using any negative numbers, by counting 1st choices separately from all other ranks; see the section above [[Pairwise counting#Uses for first choice information]]. This is essentially equivalent to doing semi-negative pairwise counting with negative counting only applied to 1st choices and regular pairwise counting applied to all other candidates. The regular approach requires [(number of candidates)-2] less marks if using this modification i.e. a voter who ranks 2 candidates sequentially when there are 10 candidates only requires ''1''+8=9 marks rather than ''9''+8=17 marks to have their ballot counted, a [(10)-2=] 8-mark difference.▼
* The 1st choice information allows one to determine the [[FPTP]] winner (so long as no voters equally ranked any candidates 1st), and the [[IRV]] winner in cases where some candidate is the [[Condorcet winner]] and has over 1/3rd of 1st choices (see [[Dominant mutual third]]).▼
* However, when voters equally rank multiple candidates 1st, then whether or not the modification is still applied can make a significant difference in overall number of marks i.e. a voter ranking 2 candidates 1st can either be counted using 1 mark for each candidate, or using [number of candidates - 2] marks for each, as in the regular approach.▼
** If 1 mark is used per 1st choice candidate, then the matchups involving two 1st choice candidates will have each of them get 1 vote against the other. This is the same dilemma as mentioned in this article for [[#Dealing with equal-ranking]] in negative pairwise counting.▼
== Comparison to other vote-counting procedures ==
Line 195 ⟶ 210:
** It isn't possible to know for certain how voters would score the candidates when provided only ranked data. However, it is possible to guess; for example, if there were certain candidates known to be frontrunners, then strategic voters would likely do [[min-max voting]] among those frontrunners, and adjust their scores for candidates they preferred more or less than their preferred frontrunner(s) accordingly. In addition, it can be assumed some voters would do [[normalization]].
* With [[RCV]], there is some additional work involved in transporting the ballots to a centralized location, and in doing multiple rounds of counting, rather than one; ignoring that, however, at least one mark must be made per ballot (to indicate 1st choices), and then in each sequential round where votes are transferred, the number of transferred votes is the number of additional marks that must be made in that round.
▲=== Regular pairwise counting but done by counting first choices separately ===
▲Note that regular pairwise counting can have its required number of marks reduced, without using any negative numbers, by counting 1st choices separately from all other ranks; see the section above [[Pairwise counting#Uses for first choice information]]. The regular approach requires [(number of candidates)-2] less marks if using this modification i.e. a voter who ranks 2 candidates sequentially when there are 10 candidates only requires ''1''+8=9 marks rather than ''9''+8=17 marks to have their ballot counted, a [(10)-2=] 8-mark difference.
▲* The 1st choice information allows one to determine the [[FPTP]] winner (so long as no voters equally ranked any candidates 1st), and the [[IRV]] winner in cases where some candidate is the [[Condorcet winner]] and has over 1/3rd of 1st choices (see [[Dominant mutual third]]).
▲* However, when voters equally rank multiple candidates 1st, then whether or not the modification is still applied can make a significant difference in overall number of marks i.e. a voter ranking 2 candidates 1st can either be counted using 1 mark for each candidate, or using [number of candidates - 2] marks for each, as in the regular approach.
▲** If 1 mark is used per 1st choice candidate, then the matchups involving two 1st choice candidates will have each of them get 1 vote against the other. This is the same dilemma as mentioned in this article for [[#Dealing with equal-ranking]] in negative pairwise counting.
===Comparison to the regular pairwise counting approach ===
All pairwise counting approaches are based on counting the preferences of the voters for the candidates they ranked. Verbal comparison between the regular approach and negative counting:
*'''The regular approach''': The precinct vote-counters manually count all of the voter's preferences in each head-to-head matchup; in other words, a candidate is assumed to be preferred only in the matchups where the vote-counters mark them as being so.
Line 278 ⟶ 285:
==== Formula for counting the required number of marks to be made ====
(Note: See table below for definition of N and R) The formula is a series (though it is only accurate when equal-ranking isn't allowed; when it is allowed, then depending on implementation, this series may provide an upper bound on the number of marks that are to be made):
*
*In ''negative counting'', the series starts at 0 when 0 candidates are ranked, and then the formula is that the number of marks that must be made for a given number of candidates that were ranked on a ballot is the value in the series for a ballot that had ranked one less candidate than that given number, plus the number of candidates ranked on the ballot.
**This is because for each additional candidate added (ranked below all candidates already on a ballot), one mark is made to indicate that they were ranked, and [number of candidates already on ballot] marks are made to indicate the voter's preference for all of those already-ranked candidates over the newly ranked candidate.
*In the ''regular approach'', take whatever number of marks would be produced in negative counting for a given number of ranked candidates on a ballot (see above bullet point), and then subtract it from the number of candidates that are ranked on a ballot multiplied by the number of non-write-in candidates in the election.
**This is because, if the negative counting approach is thought of as "count the number of times a ranked candidate is "not preferred
***For example, with 10 candidates, for a ballot with one 1st choice that doesn't rank any of the other candidates, the negative counting approach only requires counting the fact that the 1st choice is "not preferred
**** If this ballot also ranked a 2nd choice, the negative approach requires indicating that the 2nd choice is also "not preferred to themselves", and
**The formulas for regular counting w/ 1st choices counted separately, are derived by subtracting N-2 from the corresponding formula for the regular approach.
**Note that regular pairwise counting's formula can be derived as follows: when only 1 candidate is ranked, the formula is N-1. When 2 candidates are ranked, it is the formula for when only 1 candidate is ranked plus another formula i.e. (N-1)+(N-2), which becomes 2N-3. For 3 candidates ranked, it is (2N-3)+(N-3), which is 3N-6, etc.▼
*''Semi-negative counting''<nowiki/>'s numbers can be derived as such: the voter's N/2 (rounded down to nearest integer) highest-ranked candidates are counted with negative counting's worst-case, and the remaining candidates are counted with regular pairwise counting separately.
**
**Semi-negative counting's performance is always better than or equal to negative counting's performance for the same N and R. As an example for R=2: ▼
***When N also equals 2, then in both approaches, at least '''1''' mark needs to be made (to count the 1st choice; the 2nd choice can be skipped because they are ranked last).▼
*** If 3 candidates run, then in negative counting, the 2nd choice is counted with 2 additional marks, so at least ''3'' marks are made; but in semi-negative counting, only 1 additional mark needs to be made (because 2nd choice is ranked above only 1 candidate), so at least '''2''' marks are made.▼
*** If 4 candidates run, then in both approaches, '''3''' marks are made (2nd choice is ranked above 2 candidates and below 1 candidate).▼
Here are some examples for the first numbers in each series (with the upper bound bolded):
Line 331 ⟶ 348:
Notes:
*For both regular counting approaches, a lower bound has been provided (when N=R), and since there is no upper bound, instead the number of marks required when N is one higher than R is provided.
*For both negative and semi-negative counting, the numbers provided are a series that include both lower and upper bounds on the number of marks that have to be made, depending on N (which starts at R, and sequentially increases by one, up to twice that i.e. 2R), and how last-ranked candidates are counted.
▲**Note that regular pairwise counting's formula can be derived as follows: when only 1 candidate is ranked, the formula is N-1. When 2 candidates are ranked, it is the formula for when only 1 candidate is ranked plus another formula i.e. (N-1)+(N-2), which becomes 2N-3. For 3 candidates ranked, it is (2N-3)+(N-3), which is 3N-6, etc.
▲*For both negative and semi-negative counting, the numbers provided are a series that include both lower and upper bounds on the number of marks that have to be made, depending on N (which starts at R, and sequentially increases by one, up to twice that i.e. 2R), and how last-ranked candidates are counted.
▲**Semi-negative counting's numbers can be derived as such: the voter's N/2 (rounded down to nearest integer) highest-ranked candidates are counted with negative counting's worst-case, and the remaining candidates are counted with regular pairwise counting separately. So if a voter ranks 5 out of 7 candidates, half of the candidates (3.5) rounded down (=3) are counted with negative counting (negative counting for 3 candidates requires at most 6 marks), and the remaining 2 ranked candidates are counted with regular pairwise counting (that means having to do regular pairwise counting for R=2 and N=4, because out of the 7 candidates, you ignore the 3 candidates already counted by negative counting; so plugging that into 2N-3 yields: 2(4)-3= 5 marks). So that is 6+5=11 marks for R=5 and N=7 with semi-negative counting.
▲***The reasoning for this can be derived as follows: separate the voter's ranked candidates into their N/2 most-preferred candidates (their "top-ranked half") and their N/2 least-preferred candidates (the "bottom-ranked half"); if there are an odd number of candidates, consider the median candidate to be in the bottom-ranked half. Any candidate in the top-ranked half will be ranked above more candidates than they are ranked below, so it will be easier or equally easy to use negative counting to count them. Any candidate in the bottom-ranked half will be in the opposite situation, so regular counting is easier for them.
▲***This explains why semi-negative counting has the same worst-case as negative counting for N>=2R, since they become equivalent in that case.
▲**Semi-negative counting's performance is always better than or equal to negative counting's performance for the same N and R. As an example for R=2:
▲***When N also equals 2, then in both approaches, at least '''1''' mark needs to be made (to count the 1st choice; the 2nd choice can be skipped because they are ranked last).
▲*** If 3 candidates run, then in negative counting, the 2nd choice is counted with 2 additional marks, so at least ''3'' marks are made; but in semi-negative counting, only 1 additional mark needs to be made (because 2nd choice is ranked above only 1 candidate), so at least '''2''' marks are made.
▲*** If 4 candidates run, then in both approaches, '''3''' marks are made (2nd choice is ranked above 2 candidates and below 1 candidate).
Note that negative counting is faster when voters rank only a few of all candidates, and potentially slower otherwise.
Line 512 ⟶ 520:
===Using with strength of preference ===
Negative vote-counting can be used to count weak pairwise preferences (i.e. if a voter only wants to give 0.4 votes in a matchup, rather than 1 vote; see [[Rated pairwise preference ballot#Implementations]]) by counting only a "partial ballot" marking a candidate, and partial (i.e. weighted or fractional) negative votes in certain matchups. In other words, it is treated as if only a partial voter or ballot supported a candidate (see [[KP transform]]). Note that this is equivalent to using Score voting in a matchup, if using a scale of 0 to 1 rather than the more familiar 0 to 5 or 0 to 10 scales.
Negative numbers can be used to count Approval voting, and can also be used in the context of most PR methods.▼
*For Approval, when a voter approves more than half of the candidates, they can be considered to disapprove fewer than half the candidates. That is, a ballot approving (A, B, and C), but not D, can be counted as a ballot that approves everyone except D (i.e. gives everyone a positive vote and additionally gives D a negative vote). This means using only 2 marks rather than 3. ▼
**Note that the same trick works for Score, but doesn't always speed the counting up there. For example, a voter who scores a candidate a 3 out of 5 can be thought of as giving them 5 positive points and -2 negative points as well.▼
*For sequential PR methods, some selection algorithm generally picks the a winner in a given round, then reweighting is applied to the votes, and this repeats. Because reweighting generally only alters some votes, it's often possible to treat the votes in one round as being the votes from a previous round, except some candidates have lost some support. [[SPAV]] is one such example. <ref>{{Cite web|url=https://forum.electionscience.org/t/possible-trick-for-counting-spav-and-cardinal-pr-faster/657|title=Possible trick for counting SPAV (and cardinal PR) faster|date=2020-05-26|website=The Center for Election Science|language=en-US|access-date=2020-07-21}}</ref>▼
== Notes==
[[File:Negative vote-counting approach to pairwise counting.png|thumb|1114x1114px|Negative vote-counting approach for pairwise counting (Note: Regular approach may be better in some use cases; see cited discussions in text to the left).Here is a discussion clarifying some confusion that may arise from seeing the above picture: <ref>{{Cite web|url=https://www.reddit.com/r/EndFPTP/comments/gh7fix/new_pairwise_counting_approach_based_on_approval/|title=r/EndFPTP - New pairwise counting approach based on Approval voting|website=reddit|language=en-US|access-date=2020-09-15}}</ref>]]
In practice, to make pairwise counting easier, voters could be provided with two or fewer ranks than the number of candidates, with equal-ranking being allowed so that voters could do [[preference compression]]. This way, a voter who would usually indicate a preference that would have to be counted between two candidates would have to indicate no preference between them instead.
Negative pairwise counting requires slightly more values (= N^2) to be recorded than regular pairwise counting. Regular pairwise counting records N fewer values, because it doesn't record values for the "matchups" between each candidate and themselves.
===Alternative ways to frame negative pairwise counting===
Line 762 ⟶ 784:
Note: In the B vs C matchup, B has 1 vote and C has 2 votes; yet in reality, 1 of the 2 voters equally ranked B and C (giving 0 votes to either of them), and the other ranked C over B (giving 1 vote to C and 0 to B); this discrepancy can be explained as being because the equal-ranking voter was treated as voting for both B and C, rather than neither of them.
▲=== Negative counting used for non-pairwise methods===
▲Negative numbers can be used to count Approval voting, and can also be used in the context of most PR methods.
▲==== Negative vote-counting approach for Score voting ====
▲*For Approval, when a voter approves more than half of the candidates, they can be considered to disapprove fewer than half the candidates. That is, a ballot approving (A, B, and C), but not D, can be counted as a ballot that approves everyone except D (i.e. gives everyone a positive vote and additionally gives D a negative vote). This means using only 2 marks rather than 3.
▲**Note that the same trick works for Score, but doesn't always speed the counting up there. For example, a voter who scores a candidate a 3 out of 5 can be thought of as giving them 5 positive points and -2 negative points as well.
▲==== Negative vote-counting approach for sequential PR methods ====
▲*For sequential PR methods, some selection algorithm generally picks the a winner in a given round, then reweighting is applied to the votes, and this repeats. Because reweighting generally only alters some votes, it's often possible to treat the votes in one round as being the votes from a previous round, except some candidates have lost some support. [[SPAV]] is one such example. <ref>{{Cite web|url=https://forum.electionscience.org/t/possible-trick-for-counting-spav-and-cardinal-pr-faster/657|title=Possible trick for counting SPAV (and cardinal PR) faster|date=2020-05-26|website=The Center for Election Science|language=en-US|access-date=2020-07-21}}</ref>
===Dealing with truncation===
Line 784 ⟶ 794:
=== Independence of unranked candidates===
The negative approach doesn't require additional marks to be made for a given ballot when candidates are added to the election that that ballot doesn't vote for. For example, at most 3 marks need be made for a voter whose ballot is A>B, regardless of whether there are 2 candidates in the election or 100.
== See also ==
* [[Rated pairwise preference ballot]]
==References==
| |||