Baldwin's method: Difference between revisions

From electowiki
Content added Content deleted
No edit summary
 
(9 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Wikipedia}}
{{Wikipedia}}


Candidates are voted for on [[Ranked voting]] as in the [[Borda count]]. Then, the points are tallied in a series of rounds. In each round, the candidate with the fewest points is eliminated, and the points are re-tallied as if that candidate were never on the ballot.
Under '''Baldwin's method''', candidates are voted for on [[Ranked voting]] as in the [[Borda count]]. Then, the points are tallied in a series of rounds. In each round, the candidate with the fewest points is eliminated, and the points are re-tallied as if that candidate were never on the ballot.


It was systematized by Joseph M. Baldwin<ref>{{Cite journal|last=Baldwin|first=J. M.|date=1926|title=The technique of the Nanson preferential majority system of election|url=https://archive.org/details/proceedingsroyaxxxvroyaa/page/42|journal=Proceedings of the Royal Society of Victoria|volume=39|pages=42–52|via=}}</ref> in 1926, who incorporated [[Condorcet method|a more efficient matrix tabulation]],<ref>{{Cite journal|last=Hogben|first=G.|date=1913|title=Preferential Voting in Single-member Constituencies, with Special Reference to the Counting of Votes|url=http://rsnz.natlib.govt.nz/volume/rsnz_46/rsnz_46_00_005780.html|journal=Transactions and Proceedings of the Royal Society of New Zealand|series=|volume=46|issue=|pages=304–308|via=}}</ref> extending it to support incomplete ballots and equal rankings.
It was systematized by Joseph M. Baldwin<ref>{{Cite journal|last=Baldwin|first=J. M.|date=1926|title=The technique of the Nanson preferential majority system of election|url=https://archive.org/details/proceedingsroyaxxxvroyaa/page/42|journal=Proceedings of the Royal Society of Victoria|volume=39|pages=42–52|via=}}</ref> in 1926, who incorporated [[Condorcet method|a more efficient matrix tabulation]],<ref>{{Cite journal|last=Hogben|first=G.|date=1913|title=Preferential Voting in Single-member Constituencies, with Special Reference to the Counting of Votes|url=http://rsnz.natlib.govt.nz/volume/rsnz_46/rsnz_46_00_005780.html|journal=Transactions and Proceedings of the Royal Society of New Zealand|series=|volume=46|issue=|pages=304–308|via=}}</ref> extending it to support incomplete ballots and equal rankings. Baldwin's method has been confused with [[Nanson's method]] in some literature.<ref name=":1">{{Cite journal|last=Niou|first=Emerson M. S.|date=1987|title=A Note on Nanson's Rule|journal=Public Choice|volume=54|issue=2|pages=191–193|issn=0048-5829|citeseerx=10.1.1.460.8191|doi=10.1007/BF00123006}}</ref> This method predates but is related to [[Nanson's method]]. Nanson noted Baldwin's method was already in use by the Trinity College at the University of Melbourne Dialectic Society when he invented his method.<ref name=":0">{{Cite journal|last=Nanson|first=E. J.|date=1882|title=Methods of election|url=https://archive.org/details/transactionsproc1719roya/page/197|journal=Transactions and Proceedings of the Royal Society of Victoria|volume=19|pages=197–240|via=}}</ref>{{Rp|217}}

[[Baldwin's method]] has been confused with [[Nanson's method]] in some literature.<ref name=":1">{{Cite journal|last=Niou|first=Emerson M. S.|date=1987|title=A Note on Nanson's Rule|journal=Public Choice|volume=54|issue=2|pages=191–193|issn=0048-5829|citeseerx=10.1.1.460.8191|doi=10.1007/BF00123006}}</ref> This method predates but is related to [[Nanson's method]]. Nanson noted [[Baldwin's method]] was already in use by the Trinity College at the University of Melbourne Dialectic Society when he invented his method.<ref name=":0">{{Cite journal|last=Nanson|first=E. J.|date=1882|title=Methods of election|url=https://archive.org/details/transactionsproc1719roya/page/197|journal=Transactions and Proceedings of the Royal Society of Victoria|volume=19|pages=197–240|via=}}</ref>{{Rp|217}}
This system was rechristened as '''Total Vote Runoff''' by Nobel Memorial Prize laureate economists [https://en.wikipedia.org/wiki/Edward_B._Foley Edward B. Foley] and [https://en.wikipedia.org/wiki/Eric_Maskin Eric Maskin], who proposed it as a way to fix problems in the [https://en.wikipedia.org/wiki/Instant-runoff_voting instant-runoff method]. Maskin and Foley note that unlike instant-runoff, TVR ensures majority support for the winner and typically elects more broadly-acceptable candidates.<ref>{{Cite news|last=Foley|first=Edward B.|url=https://www.washingtonpost.com/opinions/2022/11/01/alaska-final-four-primary-begich-palin-peltola/|title=Alaska’s ranked-choice voting is flawed. But there’s an easy fix.|date=November 1, 2022|work=Washington Post|access-date=2022-11-09|last2=Maskin|first2=Eric S.|language=en-US|issn=0190-8286|quote=the way Alaska uses ranked-choice voting also caused the defeat of Begich, whom most Alaska voters preferred to Democrat Mary Peltola … A candidate popular only with the party’s base would be eliminated early in a Total Vote Runoff, leaving a more broadly popular Republican to compete against a Democrat.|author-link=Edward B. Foley|author-link2=Eric Maskin}}</ref><ref>{{Cite journal|last=Foley|first=Edward B.|date=2023-01-18|title=Total Vote Runoff: A Majority-Maximizing Form of Ranked Choice Voting|url=https://papers.ssrn.com/abstract=4328946|language=en|location=Rochester, NY}}</ref><ref>{{Cite web|url=https://electionlawblog.org/?p=132792|title=“Total Vote Runoff” tweak to Ranked Choice Voting|last=Foley|first=Ned|author-link=Edward B. Foley|date=November 1, 2022|website=Election Law Blog|language=en-US|access-date=2022-11-09|quote=a small but significant adjustment to the “instant runoff” method … equivalent to a candidate’s Borda score, and eliminating sequentially the candidate with the lowest total votes}}</ref><ref>{{Cite web|url=https://electionlawblog.org/?p=132963|title=An Additional Detail about “Total Vote Runoff”|last=Foley|first=Ned|author-link=Edward B. Foley|date=November 8, 2022|website=Election Law Blog|language=en-US|access-date=2022-11-09|quote=Begich and Peltola each get half a vote by being tied for second place on this ballot}}</ref>


== Satisfied and failed criteria ==
== Satisfied and failed criteria ==


[[Baldwin's method]] satisfies the [[Condorcet criterion]].<ref name=":1" /> because Borda always gives any existing Condorcet winner more than the average Borda points, the Condorcet winner will never be eliminated. Furthermore it satisfies the [[majority criterion]], the [[mutual majority criterion]], the [[Condorcet loser criterion]] and the [[Smith set|Smith criterion]].
[[Baldwin's method]] satisfies the [[Condorcet criterion]].<ref name=":1" /> Because Borda always gives any existing Condorcet winner more than the average Borda points, the Condorcet winner will never be eliminated. Furthermore it satisfies the [[majority criterion]], the [[mutual majority criterion]], the [[Condorcet loser criterion]] and the [[Smith set|Smith criterion]].


[[Baldwin's method]] does not satisfy the [[independence of irrelevant alternatives]] criterion, the [[monotonicity criterion]], the [[participation criterion]], the [[consistency criterion]] and the [[independence of clones criterion]]. [[Baldwin's method]] also violates [[reversal symmetry]].<ref>{{Cite web|url=https://www.mail-archive.com/election-methods@lists.electorama.com/msg00625.html|title=Re: [Election-Methods] Borda-elimination, a Condorcet method for public elections?|website=www.mail-archive.com|access-date=2019-06-19}}</ref>
[[Baldwin's method]] does not satisfy the [[independence of irrelevant alternatives]] criterion, the [[monotonicity criterion]], the [[participation criterion]], the [[consistency criterion]] and the [[independence of clones criterion]]. [[Baldwin's method]] violates [[reversal symmetry]] (unlike [[Nanson's method]]).<ref>{{Cite web|url=https://www.mail-archive.com/election-methods@lists.electorama.com/msg00625.html|title=Re: [Election-Methods] Borda-elimination, a Condorcet method for public elections?|website=www.mail-archive.com|access-date=2019-06-19}}</ref>


[[Baldwin's method]] can be run in polynomial time to obtain a single winner, however, at each stage, there might be several candidates with lowest Borda score. In fact, it is NP-complete to decide whether a given candidate is a Baldwin winner, i.e., whether there exists an elimination sequence that leaves a given candidate uneliminated.<ref>{{Cite journal|last=Mattei|first=Nicholas|last2=Narodytska|first2=Nina|last3=Walsh|first3=Toby|date=2014-01-01|title=How Hard is It to Control an Election by Breaking Ties?|journal=Proceedings of the Twenty-first European Conference on Artificial Intelligence|volume=263|issue=ECAI 2014|series=ECAI'14|location=Amsterdam, The Netherlands, The Netherlands|publisher=IOS Press|pages=1067–1068|doi=10.3233/978-1-61499-419-0-1067|isbn=9781614994183}}</ref>. This implies that this method is computationally more difficult to compute than Borda's method.<ref>{{Cite journal|last=Davies|first=Jessica|last2=Katsirelos|first2=George|last3=Narodytska|first3=Nina|last4=Walsh|first4=Toby|last5=Xia|first5=Lirong|date=2014-12-01|title=Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules|journal=Artificial Intelligence|volume=217|pages=20–42|doi=10.1016/j.artint.2014.07.005|issn=0004-3702}}</ref>
[[Baldwin's method]] can be run in polynomial time to obtain a single winner, but at each stage, there may be several candidates with the lowest Borda score. In fact, it is NP-complete to decide whether a given candidate is a potential Baldwin winner, i.e. whether there exists an elimination sequence that leaves a given candidate uneliminated.<ref>{{Cite journal|last=Mattei|first=Nicholas|last2=Narodytska|first2=Nina|last3=Walsh|first3=Toby|date=2014-01-01|title=How Hard is It to Control an Election by Breaking Ties?|journal=Proceedings of the Twenty-first European Conference on Artificial Intelligence|volume=263|issue=ECAI 2014|series=ECAI'14|location=Amsterdam, The Netherlands, The Netherlands|publisher=IOS Press|pages=1067–1068|doi=10.3233/978-1-61499-419-0-1067|isbn=9781614994183}}</ref> This implies that this method is computationally more difficult to compute than Borda's method.<ref>{{Cite journal|last=Davies|first=Jessica|last2=Katsirelos|first2=George|last3=Narodytska|first3=Nina|last4=Walsh|first4=Toby|last5=Xia|first5=Lirong|date=2014-12-01|title=Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules|journal=Artificial Intelligence|volume=217|pages=20–42|doi=10.1016/j.artint.2014.07.005|issn=0004-3702}}</ref>


In practice, the computational bottleneck can be resolved easily enough by adopting some tiebreaking method (like eliminating all tied candidates simultaneously). However, the high frequency of near-ties leaves these methods open to lawsuits (similarly to [[Instant-runoff voting|plurality-with-elimination]]) and can lead to chaotic results.
==Cardianal Variant==


==Cardinal variant==
A [[Cardinal Voting]] variant of this system can be made by simply taking the scores initially rather than taking ranks and converting them with [[Borda count]]. In this context the motivation for the normalization at each round is derived by considering an affine transformation. When the lowest scored candidate is removed such a rescaling would then rescale so that each voter has some candidate at the MAX and some at the MIN score. This will always maximize effective vote power which is the issue attempted to be equalized by this method.


Using [[Score voting|scores]] instead of [[Borda count|Borda counts]] gives the '''Cardinal Baldwin''' method; the lowest-scored candidate is eliminated and the ballots are rescaled (normalized) in each round. When the lowest scored candidate is removed such a rescaling would then rescale so that each voter has some candidate at the MAX and some at the MIN score. This maximizes each voter's effective power at each step; eliminating minor candidates in this way prevents them from substantially affecting the results.
More explicitly. Let MAX and MIN be the extreme available grades. Let <math>u_c</math> be a voters score for candidate c, let <math>u_{min}</math> and <math>u_{max}</math> be their score for her worst and best candidates in the considered election round. The rescaled utility is:


Assuming the scores are all scaled to fall in the range [0, 1], ballots are rescaled as follows:
<math>\begin{equation}
v_c(u_c) = MIN + (MAX– MIN) \frac{(u_c u_{min})}{(u_{max} u_{min})}
\end{equation}</math>


For example, in a [0,10] system the translation is

<math>\begin{equation}
v_c(u_c) = 10 \frac{(u_c – u_{min})}{(u_{max} – u_{min})}
\end{equation}</math>

It would transform [1,3,5] to [0,5,10]


<math>v_c(u_c) = \frac{u_c - u_{\min}}{u_\max - u_\min}</math>


For example, we would transform [.1, .3, .5] to [0, .5, 1.0].
===Related systems===
===Related systems===


[[STAR voting]] is a simplified version of this where instead of eliminating each candidate one by one all but the last two candidates are removed at once. This alteration recovers the [[monotonicity criterion]].
[[STAR voting]] is a simplified version of this where instead of eliminating each candidate one by one all but the last two candidates are removed at once. This alteration recovers the [[monotonicity criterion]].


[[Distributed Voting]] is a [[Cumulative voting]] variant.
[[Distributed Voting]] is a [[cumulative voting]] variant.


==Notes==
==Notes==
Line 51: Line 43:


Borda scores are A 185, B 205, C 210. A beats B beats C beats A, so there is no Condorcet winner, and so A, the Borda loser, is eliminated. Since B beats C, B wins. Note that this is a different result than [[Black's method]], which would elect C. They are both related to [[Nanson's method]].
Borda scores are A 185, B 205, C 210. A beats B beats C beats A, so there is no Condorcet winner, and so A, the Borda loser, is eliminated. Since B beats C, B wins. Note that this is a different result than [[Black's method]], which would elect C. They are both related to [[Nanson's method]].

== Example ==
{{Tenn voting example}}This gives the following points table:
{| class="wikitable" style="border:none"
! {{diagonal split header|Candidate|Voters}}
!Memphis
!Nashville
!Knoxville
!Chattanooga
| rowspan="5" style="border: none; background: white;" |
!Score
|-
!Memphis
|42×3=126
|0
|0
|0
|126
|-
!Nashville
|42×2 = 84
|26×3 = 78
|17×1 = 17
|15×1 = 15
|194
|-
!Knoxville
|0
|26×1 = 26
|17×3 = 51
|15×2 = 30
|107
|-
!Chattanooga
|42×1 = 42
|26×2 = 52
|17×2 = 34
|15×3 = 45
|173
|}
Knoxville has the least amount of points, so it is eliminated.

We now have this table:
{| class="wikitable" style="border:none"
! {{diagonal split header|Candidate|Voters}}
!Memphis
!Nashville
!Knoxville
!Chattanooga
| rowspan="4" style="border: none; background: white;" |
!Score
|-
!Memphis
|42×2 = 84
|0
|0
|0
|84
|-
!Nashville
|42×1 = 42
|26×2 = 52
|17×1 = 17
|15×1 = 15
|126
|-
!Chattanooga
|0
|26×1 = 26
|17×2 = 34
|15×2 = 30
|90
|}
Now Memphis is eliminated.

This leaves us with Nashville and Chattanooga. Nashville has 42+26 points, giving it 68 points, while Chattanooga has 17+15 points giving it 32. This makes Nashville the winner.


== See also ==
== See also ==

Latest revision as of 14:57, 10 April 2024

Wikipedia has an article on:

Under Baldwin's method, candidates are voted for on Ranked voting as in the Borda count. Then, the points are tallied in a series of rounds. In each round, the candidate with the fewest points is eliminated, and the points are re-tallied as if that candidate were never on the ballot.

It was systematized by Joseph M. Baldwin[1] in 1926, who incorporated a more efficient matrix tabulation,[2] extending it to support incomplete ballots and equal rankings. Baldwin's method has been confused with Nanson's method in some literature.[3] This method predates but is related to Nanson's method. Nanson noted Baldwin's method was already in use by the Trinity College at the University of Melbourne Dialectic Society when he invented his method.[4]:217

This system was rechristened as Total Vote Runoff by Nobel Memorial Prize laureate economists Edward B. Foley and Eric Maskin, who proposed it as a way to fix problems in the instant-runoff method. Maskin and Foley note that unlike instant-runoff, TVR ensures majority support for the winner and typically elects more broadly-acceptable candidates.[5][6][7][8]

Satisfied and failed criteria

Baldwin's method satisfies the Condorcet criterion.[3] Because Borda always gives any existing Condorcet winner more than the average Borda points, the Condorcet winner will never be eliminated. Furthermore it satisfies the majority criterion, the mutual majority criterion, the Condorcet loser criterion and the Smith criterion.

Baldwin's method does not satisfy the independence of irrelevant alternatives criterion, the monotonicity criterion, the participation criterion, the consistency criterion and the independence of clones criterion. Baldwin's method violates reversal symmetry (unlike Nanson's method).[9]

Baldwin's method can be run in polynomial time to obtain a single winner, but at each stage, there may be several candidates with the lowest Borda score. In fact, it is NP-complete to decide whether a given candidate is a potential Baldwin winner, i.e. whether there exists an elimination sequence that leaves a given candidate uneliminated.[10] This implies that this method is computationally more difficult to compute than Borda's method.[11]

In practice, the computational bottleneck can be resolved easily enough by adopting some tiebreaking method (like eliminating all tied candidates simultaneously). However, the high frequency of near-ties leaves these methods open to lawsuits (similarly to plurality-with-elimination) and can lead to chaotic results.

Cardinal variant

Using scores instead of Borda counts gives the Cardinal Baldwin method; the lowest-scored candidate is eliminated and the ballots are rescaled (normalized) in each round. When the lowest scored candidate is removed such a rescaling would then rescale so that each voter has some candidate at the MAX and some at the MIN score. This maximizes each voter's effective power at each step; eliminating minor candidates in this way prevents them from substantially affecting the results.

Assuming the scores are all scaled to fall in the range [0, 1], ballots are rescaled as follows:

For example, we would transform [.1, .3, .5] to [0, .5, 1.0].

Related systems

STAR voting is a simplified version of this where instead of eliminating each candidate one by one all but the last two candidates are removed at once. This alteration recovers the monotonicity criterion.

Distributed Voting is a cumulative voting variant.

Notes

Note that Baldwin's method is Smith-efficient; this is because Borda can never rank a Condorcet winner last, and a Condorcet winner will always stay a Condorcet winner when losing candidates are removed/eliminated from an election. When all but one member of the Smith set is eliminated, the remaining member of the Smith set will pairwise beat all other candidates by definition, and thus will "become" a Condorcet winner at that point that can no longer be eliminated, and thus is guaranteed to be the final remaining candidate and win.

Example:

 25 A>B>C
 40 B>C>A
 35 C>A>B

Borda scores are A 185, B 205, C 210. A beats B beats C beats A, so there is no Condorcet winner, and so A, the Borda loser, is eliminated. Since B beats C, B wins. Note that this is a different result than Black's method, which would elect C. They are both related to Nanson's method.

Example

Tennessee's four cities are spread throughout the state
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

This gives the following points table:

Voters
Candidate
Memphis Nashville Knoxville Chattanooga Score
Memphis 42×3=126 0 0 0 126
Nashville 42×2 = 84 26×3 = 78 17×1 = 17 15×1 = 15 194
Knoxville 0 26×1 = 26 17×3 = 51 15×2 = 30 107
Chattanooga 42×1 = 42 26×2 = 52 17×2 = 34 15×3 = 45 173

Knoxville has the least amount of points, so it is eliminated.

We now have this table:

Voters
Candidate
Memphis Nashville Knoxville Chattanooga Score
Memphis 42×2 = 84 0 0 0 84
Nashville 42×1 = 42 26×2 = 52 17×1 = 17 15×1 = 15 126
Chattanooga 0 26×1 = 26 17×2 = 34 15×2 = 30 90

Now Memphis is eliminated.

This leaves us with Nashville and Chattanooga. Nashville has 42+26 points, giving it 68 points, while Chattanooga has 17+15 points giving it 32. This makes Nashville the winner.

See also

References

  1. Baldwin, J. M. (1926). "The technique of the Nanson preferential majority system of election". Proceedings of the Royal Society of Victoria. 39: 42–52.
  2. Hogben, G. (1913). "Preferential Voting in Single-member Constituencies, with Special Reference to the Counting of Votes". Transactions and Proceedings of the Royal Society of New Zealand. 46: 304–308.
  3. a b Niou, Emerson M. S. (1987). "A Note on Nanson's Rule". Public Choice. 54 (2): 191–193. CiteSeerX 10.1.1.460.8191. doi:10.1007/BF00123006. ISSN 0048-5829.
  4. Nanson, E. J. (1882). "Methods of election". Transactions and Proceedings of the Royal Society of Victoria. 19: 197–240.
  5. Foley, Edward B.; Maskin, Eric S. (November 1, 2022). "Alaska's ranked-choice voting is flawed. But there's an easy fix". Washington Post. ISSN 0190-8286. Retrieved 2022-11-09. the way Alaska uses ranked-choice voting also caused the defeat of Begich, whom most Alaska voters preferred to Democrat Mary Peltola … A candidate popular only with the party’s base would be eliminated early in a Total Vote Runoff, leaving a more broadly popular Republican to compete against a Democrat.
  6. Foley, Edward B. (2023-01-18). "Total Vote Runoff: A Majority-Maximizing Form of Ranked Choice Voting". Rochester, NY. Cite journal requires |journal= (help)
  7. Foley, Ned (November 1, 2022). ""Total Vote Runoff" tweak to Ranked Choice Voting". Election Law Blog. Retrieved 2022-11-09. a small but significant adjustment to the “instant runoff” method … equivalent to a candidate’s Borda score, and eliminating sequentially the candidate with the lowest total votes
  8. Foley, Ned (November 8, 2022). "An Additional Detail about "Total Vote Runoff"". Election Law Blog. Retrieved 2022-11-09. Begich and Peltola each get half a vote by being tied for second place on this ballot
  9. "Re: [Election-Methods] Borda-elimination, a Condorcet method for public elections?". www.mail-archive.com. Retrieved 2019-06-19.
  10. Mattei, Nicholas; Narodytska, Nina; Walsh, Toby (2014-01-01). "How Hard is It to Control an Election by Breaking Ties?". Proceedings of the Twenty-first European Conference on Artificial Intelligence. ECAI'14. Amsterdam, The Netherlands, The Netherlands: IOS Press. 263 (ECAI 2014): 1067–1068. doi:10.3233/978-1-61499-419-0-1067. ISBN 9781614994183.
  11. Davies, Jessica; Katsirelos, George; Narodytska, Nina; Walsh, Toby; Xia, Lirong (2014-12-01). "Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules". Artificial Intelligence. 217: 20–42. doi:10.1016/j.artint.2014.07.005. ISSN 0004-3702.