http://wiki.electorama.com/w/api.php?action=feedcontributions&user=68.122.4.103&feedformat=atom
Electowiki - User contributions [en]
2020-10-23T05:22:18Z
User contributions
MediaWiki 1.27.3
http://wiki.electorama.com/w/index.php?title=Schulze_method&diff=432
Schulze method
2005-04-04T05:21:26Z
<p>68.122.4.103: /* External Resources */</p>
<hr />
<div>'''Cloneproof Schwartz Sequential Dropping''' ('''CSSD''') is a [[voting system]] developed by Markus Schulze that selects a single winner using votes that express preferences. CSSD can also be used to create a sorted list of winners. CSSD is also known as "Schwartz Sequential Dropping", "Beatpath Method", "Beatpath Winner", "Path Voting", "Path Winner", and "Schulze Method".<br />
<br />
If there is a candidate who is preferred over the other candidates,<br />
when compared in turn with each of the others, CSSD guarantees that that candidate will win.<br />
Because of this property, CSSD is (by definition) a '''[[Condorcet method]]'''.<br />
Note that this is different from some other preference voting systems such as [[Borda count|Borda]] and<br />
[[Instant-runoff voting]], which do not make this guarantee.<br />
<br />
== The Schwartz Set ==<br />
<br />
The definition of a [[Schwartz set]], as used in CSSD, is as follows:<br />
<br />
# An unbeaten set is a set of candidates of whom none is beaten by anyone outside that set. <br />
# An innermost unbeaten set is an unbeaten set that doesn't contain a smaller unbeaten set. <br />
# The Schwartz set is the set of candidates who are in innermost unbeaten sets.<br />
<br />
== Procedure ==<br />
<br />
The voters cast their ballots by ranking the candidates according to their preferences, just like for any other Condorcet election.<br />
<br />
CSSD uses [[Condorcet method|Condorcet]] pairwise matchups between the candidates and a winner is chosen in each of the matchups.<br />
<br />
From there, CSSD operates as follows to select a winner (or create a ranked list):<br />
<br />
# Calculate the Schwartz set based only on undropped defeats. <br />
# If there are no defeats among the members of that set then they (plural in the case of a tie) win and the count ends. <br />
# Otherwise, drop the weakest defeat among the candidates of that set. Go to 1.<br />
<br />
== An Example ==<br />
<br />
=== The Situation ===<br />
<br />
Imagine an election for the capital of [[Tennessee]], a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south. Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga). Here's the population breakdown by metro area (surrounding county): <br />
<div style="float:right; padding:2px; text-align:center"><br />
[[Image:CondorcetTennesee.png]]</div><br />
<br />
* Memphis (Shelby County): 826,330<br />
* Nashville (Davidson County): 510,784<br />
* Chattanooga (Hamilton County): 285,536<br />
* Knoxville (Knox County): 335,749<br />
<br />
Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:<br />
<br />
<table border=1><br />
<tr><br />
<td><br />
'''42% of voters (close to Memphis)'''<br><br />
1. Memphis<br><br />
2. Nashville<br><br />
3. Chattanooga<br><br />
4. Knoxville<br />
</td><br />
<td valign="top"><br />
'''26% of voters (close to Nashville)'''<br><br />
1. Nashville<br><br />
2. Chattanooga<br><br />
3. Knoxville<br><br />
4. Memphis<br />
</td><br />
<td><br />
'''15% of voters (close to Chattanooga)'''<br><br />
1. Chattanooga<br><br />
2. Knoxville<br><br />
3. Nashville<br><br />
4. Memphis<br />
</td><br />
<td><br />
'''17% of voters (close to Knoxville)'''<br><br />
1. Knoxville<br><br />
2. Chattanooga<br><br />
3. Nashville<br><br />
4. Memphis<br />
</td><br />
</tr><br />
</table><br />
<br />
The results would be tabulated as follows:<br />
<table BORDER><caption>Pairwise Election Results</caption><br />
<tr><th colspan=2><th colspan=4 bgcolor="#c0c0ff">A</tr><br />
<br />
<tr><br />
<th colspan=2><th bgcolor="#c0c0ff">Memphis<br />
<th bgcolor="#c0c0ff">Nashville<br />
<th bgcolor="#c0c0ff">Chattanooga<br />
<th bgcolor="#c0c0ff">Knoxville<br />
</tr><br />
<tr><th bgcolor="#ffc0c0" rowspan=4>B<th bgcolor="#ffc0c0">Memphis<td><td nowrap bgcolor="#e0e0ff">[A] 58% <br>[B] 42% <br><td nowrap bgcolor="#e0e0ff">[A] 58% <br>[B] 42% <br><td nowrap bgcolor="#e0e0ff">[A] 58% <br>[B] 42% <br></tr><br />
<tr><th bgcolor="#ffc0c0">Nashville<td nowrap bgcolor="#ffe0e0">[A] 42% <br>[B] 58% <br><td><td nowrap bgcolor="#ffe0e0">[A] 32% <br>[B] 68% <br><td nowrap bgcolor="#ffe0e0">[A] 32% <br>[B] 68% <br></tr><br />
<br />
<tr><th bgcolor="#ffc0c0">Chattanooga<td nowrap bgcolor="#ffe0e0">[A] 42% <br>[B] 58% <br><td nowrap bgcolor="#e0e0ff">[A] 68% <br>[B] 32% <br><td><td nowrap bgcolor="#ffe0e0">[A] 17% <br>[B] 83% <br></tr><br />
<tr><th bgcolor="#ffc0c0">Knoxville<td nowrap bgcolor="#ffe0e0">[A] 42% <br>[B] 58% <br><td nowrap bgcolor="#e0e0ff">[A] 68% <br>[B] 32% <br><td nowrap bgcolor="#e0e0ff">[A] 83% <br>[B] 17% <br><td></tr><br />
<tr><th colspan=2 bgcolor="#c0c0ff">Pairwise election results (won-lost-tied):<br />
<br />
<td bgcolor="#ffffff">0-3-0<br />
<td bgcolor="#ffffff">3-0-0<br />
<td bgcolor="#ffffff">2-1-0<br />
<td bgcolor="#ffffff">1-2-0<br />
<tr><th colspan=2 bgcolor="#c0c0ff">Votes against in worst pairwise defeat:<br />
<td bgcolor="#ffffff">58%<td bgcolor="#ffffff">N/A<td bgcolor="#ffffff">68%<td bgcolor="#ffffff">83%</table><br />
<br />
* [A] indicates voters who preferred the candidate listed in the column caption to the candidate listed in the row caption<br />
* [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption<br />
* [NP] indicates voters who expressed no preference between either candidate<br />
<br />
=== Pairwise Winners ===<br />
<br />
First, list every pair, and determine the winner:<br />
{| border="1"<br />
!Pair!!Winner<br />
|-<br />
| Memphis (42%) vs. Nashville (58%)|| Nashville 58%<br />
|-<br />
| Memphis (42%) vs. Chattanooga (58%)|| Chattanooga 58%<br />
|-<br />
| Memphis (42%) vs. Knoxville (58%)|| Knoxville 58%<br />
|-<br />
| Nashville (68%) vs. Chattanooga (32%)|| Nashville 68%<br />
|-<br />
| Nashville (68%) vs. Knoxville (32%)||Nashville 68%<br />
|-<br />
| Chattanooga (83%) vs. Knoxville (17%)|| Chattanooga: 83%<br />
|}<br />
<br />
Note that absolute counts of votes can be used, or<br />
percentages of the total number of votes; it makes no difference.<br />
<br />
=== Dropping ===<br />
<br />
Next we start with our list of cities and their matchup wins/defeats<br />
<br />
* Nashville 3-0<br />
* Chattanooga 2-1<br />
* Knoxville 1-2<br />
* Memphis 0-3<br />
<br />
Technically, the Schwartz set is simply Nashville as it beat all others 3 to 0.<br />
<br />
Therefore, Nashville is the winner.<br />
<br />
=== Ambiguity Resolution Example ===<br />
<br />
Let's say there was an ambiguity. For a simple situation involving candidates A, B, and C.<br />
<br />
* A > B 72%<br />
* B > C 68%<br />
* C > A 52%<br />
<br />
In this situation the Schwartz set is A, B, and C as they all beat someone.<br />
<br />
CSSD then says to drop the weakest defeat, so we drop C > A and are left with<br />
<br />
* A > B 72% (as C has been removed)<br />
<br />
Therefore, A is the winner.<br />
<br />
<br />
(It may be more accessible to phrase that as "drop the weakest win", though purists may complain.)<br />
<br />
=== Summary ===<br />
<br />
In the (first) example election, the winner is Nashville.<br />
This would be true for any [[Condorcet method]].<br />
Using the [[first-past-the-post]] system and some other systems, Memphis would have won the election by having the most people, even though Nashville won every simulated pairwise election outright. Using [[Instant-runoff voting]] in this example would result in Knoxville winning, even though more people preferred Nashville over Knoxville.<br />
<br />
== Satisfied Criteria ==<br />
<br />
CSSD satisfies the following criteria:<br />
<br />
# [[Monotonicity criterion]]<br />
# [[Pareto criterion]]<br />
# [[Condorcet Criterion|Condorcet criterion]]<br />
# [[Smith set|Smith criterion]] ([[Aka_(initialism)|aka]] [[Generalized Condorcet criterion]])<br />
# [[Independence of irrelevant alternatives|local independence from irrelevant alternatives]]<br />
# [[Schwartz set|Schwartz criterion]]<br />
# [[Strategy-Free criterion]]<br />
# [[Generalized Strategy-Free criterion]]<br />
# [[Strong Defensive Strategy criterion]]<br />
# [[Weak Defensive Strategy criterion]]<br />
# [[Summability criterion]]<br />
# [[Strategic nomination|Independence of clones]]<br />
<br />
CSSD violates the following criteria:<br />
<br />
# [[Participation criterion]]<br />
# [[Consistency|Consistency criterion]]<br />
# [[Tactical voting|invulnerability to compromising]]<br />
# [[Tactical voting|invulnerability to burying]]<br />
<br />
It isn't known whether CSSD satisfies the following criteria:<br />
<br />
# [[Favorite Betrayal criterion]]<br />
<br />
== Use of CSSD ==<br />
<br />
CSSD is not currently used in government elections. However, it is starting to receive support in some public organizations. Organizations which currently use CSSD are:<br />
<br />
# the [[Debian]] project<br />
# the [[Software in the Public Interest]] project<br />
# the [[UserLinux]] project<br />
# the [http://www.leaderofthefreeworld.com/ Leader of the Free World] project<br />
# the [http://www.demexp.org/ L'ExpÃƒÂ©rience DÃƒÂ©mocratique] project<br />
# the [http://glasnost.entrouvert.org/ Glasnost] project<br />
<br />
== External Resources ==<br />
* [http://groups.yahoo.com/group/election-methods-list/ A mailing list containing technical discussions about election methods]<br />
* [http://electionmethods.org/ electionmethods.org] where CSSD is also called "Schwartz Sequential Dropping" and "Beatpath Winner"<br />
* [http://www.condorcet.org/emr/index.shtml Election Methods Resource] where CSSD is called "Schulze"<br />
* [http://accuratedemocracy.com/voting_rules.htm Accurate Democracy] where CSSD is called "Schulze", "Schwartz Sequential Dropping", and "Beatpath"<br />
* [http://www.alumni.caltech.edu/~seppley The Maximize Affirmed Majorities voting procedure (MAM)] where CSSD is called "Path Winner"<br />
* [http://www.mcs.vuw.ac.nz/~ncj/comp303/schulze.pdf A New Monotonic and Clone-Independent Single-Winner Election Method] ('''[[Portable Document Format|PDF]]''') by Markus Schulze ([http://www.citizensassembly.bc.ca/resources/submissions/csharman-10_0409201706-143.pdf mirror1], [http://lists.gnu.org/archive/html/demexp-dev/2003-09/pdflQW7IlpAfC.pdf mirror2])<br />
* [http://cec.wustl.edu/~rhl1/rbvote/desc.html Descriptions of ranked-ballot voting methods] where CSSD is called "Schulze"<br />
* [http://fc.antioch.edu/~james_green-armytage/voting.htm Voting methods resource page] where CSSD is also called "Schwartz Sequential Dropping" and "Beatpath"<br />
<br />
<br />
<br />
{{fromwikipedia}}<br />
<br />
[[Category:Condorcet method]]</div>
68.122.4.103
http://wiki.electorama.com/w/index.php?title=Ranked_Pairs&diff=5165
Ranked Pairs
2005-04-04T05:20:42Z
<p>68.122.4.103: /* External Resources */</p>
<hr />
<div>'''Ranked Pairs''' (RP) or '''Tideman''' (named after [[Nicolaus Tideman]]) is a [[voting system]] that selects a single winner using votes that express preferences. RP can also be used to create a sorted list of winners. RP passes the [[Condorcet Criterion]], and is by definition a '''[[Condorcet method]]'''. RP has many variations such as the [[Maximize Affirmed Majorities]] (MAM) and [[Maximum Majority Voting]] (MMV) voting methods.<br />
<br />
== Procedure ==<br />
<br />
The RP procedure is as follows:<br />
# Tally the vote count comparing each pair of candidates, and determine the winner of each pair (provided there is not a tie)<br />
# Sort (rank) each pair, by the largest margin of victory first to smallest last.<br />
# "Lock in" each pair, starting with the one with the largest number of winning votes, and add one in turn to a graph as long as they do not create a cycle (which would create an ambiguity). The completed graph shows the winner.<br />
<br />
RP can also be used to create a sorted list of preferred candidates.<br />
To create a sorted list, repeatedly use RP to select a winner,<br />
remove that winner from the list of candidates,<br />
and repeat (to find the next runner up, and so forth).<br />
<br />
=== Tally ===<br />
<br />
To tally the votes, consider each voters' preferences.<br />
For example, if a voter states "A &gt; B &gt; C"<br />
(A is better than B, and B is better than C), the tally<br />
should add one for A in A vs. B, one for A in A vs. C, and<br />
one for B in B vs. C.<br />
Voters may also express indifference (e.g., A = B), and unstated<br />
candidates are assumed to be equally worse than the stated candidates.<br />
<br />
Once, tallied the majorities can be determined.<br />
If "Vxy" is the number of Votes that rank x over y, then<br />
"x" wins if Vxy &gt; Vyx, and "y" wins if Vyx &gt; Vxy.<br />
<br />
=== Sort ===<br />
<br />
The pairs of winners, called the "majorities", are then sorted from<br />
the largest majority to the smallest majority.<br />
A majority for x over y precedes a majority for z over w <br />
if and only if at least one of the following conditions holds:<br />
<br />
#Vxy &gt; Vzw. In other words, the majority having more support for its alternative is ranked first.<br />
#Vxy = Vzw and Vwz &gt; Vyx. Where the majorities are equal, the majority with the smaller minority opposition is ranked first.<br />
<br />
=== Lock ===<br />
<br />
The next step is to examine each pair in turn to determine<br />
which pairs to "lock in".<br />
Using the sorted list above, lock in each pair in turn ''unless''<br />
the pair will create a circularity in a graph<br />
(e.g., where A is more than B, B is more than C, but C is more than A).<br />
<br />
== An Example ==<br />
<br />
=== The Situation ===<br />
<br />
Imagine an election for the capital of [[Tennessee]], a state in the United States that is over 500 miles east-to-west, and only 110 miles north-to-south. Let's say the candidates for the capital are Memphis (on the far west end), Nashville (in the center), Chattanooga (129 miles southeast of Nashville), and Knoxville (on the far east side, 114 northeast of Chattanooga). Here's the population breakdown by metro area (surrounding county): <br />
<div style="float:right; padding:2px; text-align:center"><br />
[[Image:CondorcetTennesee.png]]</div><br />
<br />
* Memphis (Shelby County): 826,330<br />
* Nashville (Davidson County): 510,784<br />
* Chattanooga (Hamilton County): 285,536<br />
* Knoxville (Knox County): 335,749<br />
<br />
Let's say that in the vote, the voters vote based on geographic proximity. Assuming that the population distribution of the rest of Tennessee follows from those population centers, one could easily envision an election where the percentages of votes would be as follows:<br />
<br />
<table border=1><br />
<tr><br />
<td><br />
'''42% of voters (close to Memphis)'''<br><br />
1. Memphis<br><br />
2. Nashville<br><br />
3. Chattanooga<br><br />
4. Knoxville<br />
</td><br />
<td valign="top"><br />
'''26% of voters (close to Nashville)'''<br><br />
1. Nashville<br><br />
2. Chattanooga<br><br />
3. Knoxville<br><br />
4. Memphis<br />
</td><br />
<td><br />
'''15% of voters (close to Chattanooga)'''<br><br />
1. Chattanooga<br><br />
2. Knoxville<br><br />
3. Nashville<br><br />
4. Memphis<br />
</td><br />
<td><br />
'''17% of voters (close to Knoxville)'''<br><br />
1. Knoxville<br><br />
2. Chattanooga<br><br />
3. Nashville<br><br />
4. Memphis<br />
</td><br />
</tr><br />
</table><br />
<br />
The results would be tabulated as follows:<br />
<table BORDER><caption>Pairwise Election Results</caption><br />
<tr><th colspan=2><th colspan=4 bgcolor="#c0c0ff">A</tr><br />
<br />
<tr><br />
<th colspan=2><th bgcolor="#c0c0ff">Memphis<br />
<th bgcolor="#c0c0ff">Nashville<br />
<th bgcolor="#c0c0ff">Chattanooga<br />
<th bgcolor="#c0c0ff">Knoxville<br />
</tr><br />
<tr><th bgcolor="#ffc0c0" rowspan=4>B<th bgcolor="#ffc0c0">Memphis<td><td nowrap bgcolor="#e0e0ff">[A] 58% <br>[B] 42% <br><td nowrap bgcolor="#e0e0ff">[A] 58% <br>[B] 42% <br><td nowrap bgcolor="#e0e0ff">[A] 58% <br>[B] 42% <br></tr><br />
<tr><th bgcolor="#ffc0c0">Nashville<td nowrap bgcolor="#ffe0e0">[A] 42% <br>[B] 58% <br><td><td nowrap bgcolor="#ffe0e0">[A] 32% <br>[B] 68% <br><td nowrap bgcolor="#ffe0e0">[A] 32% <br>[B] 68% <br></tr><br />
<br />
<tr><th bgcolor="#ffc0c0">Chattanooga<td nowrap bgcolor="#ffe0e0">[A] 42% <br>[B] 58% <br><td nowrap bgcolor="#e0e0ff">[A] 68% <br>[B] 32% <br><td><td nowrap bgcolor="#ffe0e0">[A] 17% <br>[B] 83% <br></tr><br />
<tr><th bgcolor="#ffc0c0">Knoxville<td nowrap bgcolor="#ffe0e0">[A] 42% <br>[B] 58% <br><td nowrap bgcolor="#e0e0ff">[A] 68% <br>[B] 32% <br><td nowrap bgcolor="#e0e0ff">[A] 83% <br>[B] 17% <br><td></tr><br />
<tr><th colspan=2 bgcolor="#c0c0ff">Pairwise election results (won-lost-tied):<br />
<br />
<td bgcolor="#ffffff">0-3-0<br />
<td bgcolor="#ffffff">3-0-0<br />
<td bgcolor="#ffffff">2-1-0<br />
<td bgcolor="#ffffff">1-2-0<br />
<tr><th colspan=2 bgcolor="#c0c0ff">Votes against in worst pairwise defeat:<br />
<td bgcolor="#ffffff">58%<td bgcolor="#ffffff">N/A<td bgcolor="#ffffff">68%<td bgcolor="#ffffff">83%</table><br />
<br />
* [A] indicates voters who preferred the candidate listed in the column caption to the candidate listed in the row caption<br />
* [B] indicates voters who preferred the candidate listed in the row caption to the candidate listed in the column caption<br />
* [NP] indicates voters who expressed no preference between either candidate<br />
<br />
=== Tally ===<br />
<br />
First, list every pair, and determine the winner:<br />
{| border="1"<br />
!Pair!!Winner<br />
|-<br />
| Memphis (42%) vs. Nashville (58%)|| Nashville 58%<br />
|-<br />
| Memphis (42%) vs. Chattanooga (58%)|| Chattanooga 58%<br />
|-<br />
| Memphis (42%) vs. Knoxville (58%)|| Knoxville 58%<br />
|-<br />
| Nashville (68%) vs. Chattanooga (32%)|| Nashville 68%<br />
|-<br />
| Nashville (68%) vs. Knoxville (32%)||Nashville 68%<br />
|-<br />
| Chattanooga (83%) vs. Knoxville (17%)|| Chattanooga: 83%<br />
|}<br />
<br />
Note that absolute counts of votes can be used, or<br />
percentages of the total number of votes; it makes no difference.<br />
<br />
<br />
=== Sort ===<br />
<br />
The votes are then sorted.<br />
The largest majority is "Chattanooga over Knoxville"; 83% of the<br />
voters prefer Chattanooga.<br />
Nashville (68%) beats both Chattanooga and Knoxville by a score<br />
of 68% over 32% (an exact tie, which is unlikely in real life<br />
for this many voters).<br />
Since Chattanooga &gt; Knoxville, and they're the losers,<br />
Nashville vs. Knoxville will be added first, followed by<br />
Nashville vs. Chattanooga.<br />
<br />
Thus, the pairs from above would be sorted this way:<br />
<br />
{| border="1"<br />
!Pair!!Winner<br />
|-<br />
| Chattanooga (83%) vs. Knoxville (17%)|| Chattanooga 83%<br />
|-<br />
| Nashville (68%) vs. Knoxville (32%)||Nashville 68%<br />
|-<br />
| Nashville (68%) vs. Chattanooga (32%)|| Nashville 68%<br />
|-<br />
| Memphis (42%) vs. Nashville (58%)|| Nashville 58%<br />
|-<br />
| Memphis (42%) vs. Chattanooga (58%)|| Chattanooga 58%<br />
|-<br />
| Memphis (42%) vs. Knoxville (58%)|| Knoxville 58%<br />
|}<br />
<br />
=== Lock ===<br />
<br />
<br />
The pairs are then locked in order, skipping any pairs<br />
that would create a cycle:<br />
<br />
* Lock Chattanooga over Knoxville.<br />
* Lock Nashville over Knoxville.<br />
* Lock Nashville over Chattanooga.<br />
* Lock Nashville over Memphis.<br />
* Lock Chattanooga over Memphis.<br />
* Lock Knoxville over Memphis.<br />
<br />
In this case, no cycles are created by any of the<br />
pairs, so every single one is locked in.<br />
<br />
Every "lock in" would add another arrow to the<br />
graph showing the relationship between the candidates.<br />
Here is the final graph (where arrows point from<br />
the winner).<br />
<br />
[[Image:Tennessee-vote.png]]<br />
<br />
In this example, Nashville is the winner using RP.<br />
<br />
=== Ambiguity Resolution Example ===<br />
<br />
Let's say there was an ambiguity. For a simple situation involving canidates A, B, and C.<br />
<br />
* A > B 68%<br />
* B > C 72%<br />
* C > A 52%<br />
<br />
In this situation we "lock in" the majorities starting with the greatest one first.<br />
<br />
* Lock B > C<br />
* Lock A > B<br />
* We don't lock in the final C > A as it creates an ambiguity or cycle.<br />
<br />
Therefore, A is the winner.<br />
<br />
== External Resources ==<br />
* [http://condorcet.org/rp Ranked Pairs]<br />
* [http://www.alumni.caltech.edu/~seppley The Maximize Affirmed Majorities voting procedure (MAM)]<br />
* [http://radicalcentrism.org/majority_voting.html Maximum Majority Voting]<br />
* [http://cec.wustl.edu/~rhl1/rbvote/desc.html Descriptions of ranked-ballot voting methods]<br />
* [http://fc.antioch.edu/~james_green-armytage/voting.htm Voting methods resource page]<br />
<br />
[[Category:Condorcet method]]<br />
<br />
{{fromwikipedia}}</div>
68.122.4.103
http://wiki.electorama.com/w/index.php?title=Techniques_of_method_design&diff=4061
Techniques of method design
2005-04-02T21:02:51Z
<p>68.122.4.103: /* Special sets */</p>
<hr />
<div>This is a list of techniques and concepts which are more or less useful when designing a single winner election method, with some comments.<br />
<br />
== Scores ==<br />
Scores can be interpreted as measures of "goodness" of a candidate. Their usage can thus improve the "efficiency" of a method.<br />
* '''Direct support''' = ''no. of voters ranking the candidate first.'' Retains clone-proofness when used appropriately, requires ranked ballots, is not well defined when more than one candidate is ranked top.<br />
* (Total) '''approval score''' = ''no. of voters approving of the candidate.'' Retains clone-proofness when used appropriately, requires approval information.<br />
* '''Borda score''' = ''sum of ranks the candidate gets on all ballots.'' Destroys clone-proofness and most "independency"-properties, requires ranked ballots.<br />
* '''Copeland score''' = ''no. of alternatives the candidate beats pairwise.'' Destroys clone-proofness.<br />
* Laslier's '''minimal gain score''' = ''probability that an alternative beaten by the candidate wins divided by the probability that an alternative beating the candidate wins, when choosing from the bipartisan distribution on the set of all other candidates.'' Improves the monotonicity of the bipartisan distribution, but destroys clone-proofness and is complicated to compute.<br />
<br />
== Defeats and defeat strength ==<br />
Looking at pairwise defeats and their strength can help assessing the "immunity" of a candidate against certain types of complaints. Care has to be taken so that the definition of strength doesn't destroy monotonicity.<br />
* (Pairwise) '''defeat''' <=> ''more voters expressed to prefer A over B than expressed to prefer B over A'' <br />
* '''Winning votes''' (wv) = ''no. of voters preferring the winner of the defeat to the loser''<br />
* '''Margin(s)''' = ''winning votes minus no. of voters preferring the loser.'' Gives more strategic incentives and seems more arbitrary (why not take the quotient instead?) than wv<br />
* '''Pairwise opposition''' or '''Votes against''' = Certain methods behave differently when defeats are not considered; instead the number of votes for each side of a pairwise contest against the other are counted as "opposition."<br />
* Other similar definitions of strength are possible, especially when voters can distinguish between equivalence and undecidedness<br />
* '''Majority-strength defeat''' = ''pairwise defeat which has a wv-strength of more than half the no. of voters.'' Using only such defeats can reduce incentive to truncate by reducing the likelihood that additional preferences will harm earlier ones. Voters adding a preference can create a majority-strength win, but they can't reverse the direction of one.<br />
* '''Approval-consistent defeat''' (definitive defeat) = ''pairwise defeat in which the winner is more approved than the loser.'' These are acyclic and can thus all be respected without a contradiction<br />
* '''Winning approval''' = ''approval score of the winner of the defeat.'' Using this as defeat strength leaves only one immune candidate: the least approved of those who beat all more approved ones. Similar for other scores. <br />
* '''Approval-based support''' = ''no. of voters approving of the winner but not of the loser of the defeat.'' Gives special influence to preferences which cross the aproval cutoff and thus helps diminishing certain strategies. Useful when one assumes that only these voters will support the correspondig "majority complaint".<br />
* '''Cardinal rated''' strength = ''sum of difference in the candidates' cardinal ratings on all ballots which rate the winner over the loser of the defeat.'' Helps diminishing certain strategies even better, but requires interpersonally comparable cardinal ratings.<br />
<br />
== Steps ==<br />
Many methods work in more than one, perhaps similar, perhaps different steps.<br />
* '''Iteration''': Similar steps are performed until some break criterion applies.<br />
* '''Reduction to a subset''': All members outside some special set are removed.<br />
* '''Runoff''': Special case of reduction to a subset, for example by removing worst candidate according to some score. Can be iterated.<br />
* '''Ordering''': Many methods involve the construction of an ordering of the candidates or the defeats, not to be interpreted as a social order, but only as an intermediate tool.<br />
* '''Randomization''': Using a certain amount of randomness can help avoiding some strategies, especially when it leads to each candidate being beaten by a possible winner.<br />
<br />
== Special sets ==<br />
* '''Smith set''' (top cycle, top tier, minimal dominant set) = ''smallest non-empty set of candidates each of which beats all candidates outside the set.''<br />
* '''Schwartz set''' (GOChA set, union of minimal undominated sets) = ''smallest non-empty set of candidates so that each candidate beating a member of the set is also in the set.''<br />
* Woodall's '''[[CDTT]]''' ("Condorcet doubly-augmented top tier") = ''union of all minimal non-empty sets such that no candidate in each set has a majority-strength loss to any candidate outside the set''. Alternatively, ''the set containing every candidate ''A'' where, for each other candidate ''B'' who has a majority-strength beatpath to ''A'', ''A'' also has a majority-strength beatpath to ''B.<br />
* '''Uncovered set''' = ''set of candidates which have defeats or beatpaths of length two to all other candidates''. Not monotonic as a set.<br />
* '''Banks set''' = ''set of candidates which are top on some maximal sub-chain of the defeat graph.'' Not monotonic as a set.<br />
* Dutta's '''Minimal covering set''' = ''smallest non-empty set such that when any other candidate is added, that candidate is covered in the resulting set.<br />
* '''Bipartisan set''' = ''set of candidates getting non-zero probability in the bipartisan distribution.'' <br />
* Forest Simmons' set '''P''' = ''set of candidates which are not approval-consistently defeated.'' This set is totally ordered by the defeats and contains the most approved candidate and a possible Condorcet winner.<br />
<br />
== Orderings == <br />
* Ordering by some score<br />
* (Uniformly) '''random order''': ''Pick some order uniformly at random.'' Destroys clone-proofness.<br />
* '''Random ballot order''': ''A is above B when A is above B on the first ballot distinguishing between them, in a random sequence of ballots.'' This is an often used tie breaking rank order (TBRO). Retains clone-proofness when used appropriately.<br />
* '''Random ballot approval order''': ''A is above B when A is above B on the first ballot on which the approval cutoff is between them, in a random sequence of ballots.'' Retains clone-proofness when used appropriately.<br />
<br />
== Randomization ==<br />
* '''Randomized start''': Pick an initial candidate by some random process, then proceed with other steps.<br />
* '''Randomized order''': Use a random process to determine the order in which the candidates are processes in some way.<br />
* '''Final randomization''': Restrict to some subset, then use a random process to choose from that set.</div>
68.122.4.103
http://wiki.electorama.com/w/index.php?title=Definite_Majority_Choice&diff=389
Definite Majority Choice
2005-04-02T20:45:09Z
<p>68.122.4.103: </p>
<hr />
<div>'''Definite Majority Choice''' (DMC) is a [[voting method]] proposed by several (name suggested by [http://lists.electorama.com/pipermail/election-methods-electorama.com/2005-March/015164.html Forest Simmons]) to select a single winner using ballots that express both ranked preferences and approval.<br />
<br />
If there is a candidate who is preferred over the other candidates,<br />
when compared in turn with each of the others, DMC guarantees that that candidate will win.<br />
Because of this property, DMC is (by definition) a '''[[Condorcet method]]'''.<br />
Note that this is different from some other preference voting systems such as [[Borda count|Borda]] and<br />
[[Instant-runoff voting]], which do not make this guarantee.<br />
<br />
The main difference between DMC and Condorcet methods such as [[Ranked Pairs]] (RP), [[Cloneproof Schwartz Sequential Dropping]] (Beatpath or Schulze) and [[River]] is the use of the additional Approval score to break ties. If defeat strength is measured by the Total Approval score of the pairwise winner, all three other methods become equivalent to DMC (For proof, see [http://lists.electorama.com/pipermail/election-methods-electorama.com/2005-March/015405.html this]).<br />
<br />
DMC chooses the same winner as (and could be considered equivalent in most respects to) [[Ranked Approval Voting]] (RAV) (also known as Approval Ranked Concorcet), and [[Pairwise Sorted Approval]] (PSA).<br />
<br />
The philosophical basis of DMC (also due to [http://lists.electorama.com/pipermail/election-methods-electorama.com/2005-March/015144.html Forest Simmons]) is to first eliminate candidates that the voters strongly agree should not win, using two different measures, and choose the winner from among those that remain.<br />
<br />
Some people believe that DMC is currently the best candidate for a Condorcet Method that meets the [[Public Acceptability Criterion|Public Acceptability "Criterion"]].<br />
<br />
== Procedure ==<br />
The DMC differs from the [[Condorcet Criterion|Condorcet Winner]] in one crucial respect:<br />
:The Definite Majority Choice winner is the ''least approved'' candidate who, when compared in turn with each of the other ''higher-approved'' candidates, is preferred over the other candidate.<br />
<br />
We'll illustrate how the method works with a deliberately crude ballot and then explore other ballot formats.<br />
<br />
=== Simple ballot example ===<br />
A voter ranks candidates in order of preference, additionally giving approval points to some or all of those ranked, using a ballot like the following:<br />
<pre><br />
+-----------------------+---------------+<br />
|<-- Favorite Least Preferred -->|<br />
+-----------------------+---------------+<br />
|<-- Approved -->| Not Approved |<br />
+-------+-------+-------+-------+-------+<br />
| 1 | 2 | 3 | 4 | 5 |<br />
-------+-------+-------+-------+-------+-------+<br />
X1 | ( ) | ( ) | ( ) | ( ) | ( ) |<br />
| | | | | |<br />
X2 | ( ) | ( ) | ( ) | ( ) | ( ) |<br />
| | | | | |<br />
X3 | ( ) | ( ) | ( ) | ( ) | ( ) |<br />
| | | | | |<br />
X4 | ( ) | ( ) | ( ) | ( ) | ( ) |<br />
-------+-------+-------+-------+-------+-------+<br />
</pre><br />
<br />
On this ballot,<br />
# Candidates ranked at 1st through 3rd choice get 1 approval point each.<br />
# Candidates ranked fourth, fifth and unranked receive no approval points.<br />
# A higher-ranked candidate is given one vote in each of its head-to-head contests with lower-ranked candidates. In particular, all explicitly ranked candidates are given 1 vote in each of their contests with unranked candidates.<br />
<br />
As an example, say a voter ranked candidates as follows:<br />
<pre><br />
+-----------------------+---------------+<br />
|<-- Favorite Least Preferred -->|<br />
+-----------------------+---------------+<br />
|<-- Approved -->| Not Approved |<br />
+-------+-------+-------+-------+-------+<br />
| 1 | 2 | 3 | 4 | 5 |<br />
-------+-------+-------+-------+-------+-------+<br />
X1 | ( ) | ( ) | ( ) | (X) | ( ) |<br />
| | | | | |<br />
X2 | (X) | ( ) | ( ) | ( ) | ( ) |<br />
| | | | | |<br />
X3 | ( ) | ( ) | ( ) | ( ) | (X) |<br />
| | | | | |<br />
X4 | ( ) | (X) | ( ) | ( ) | ( ) |<br />
-------+-------+-------+-------+-------+-------+<br />
</pre><br />
<br />
This ballot could be summarized briefly using the notation<br />
X2 > X4 >> X1 > X3<br />
where the ">>" indicates the approval cutoff --- candidates to the right of that sign receive no approval votes. This ballot is counted as<br />
X2 > X4<br />
X2 > X1<br />
X2 > X3<br />
X2 > X2 (approval point)<br />
X4 > X1<br />
X4 > X3<br />
X4 > X4 (approval point)<br />
X1 > X3<br />
<br />
=== Tallying Votes ===<br />
As in other [[Condorcet method]]s, the rankings on a single ballot are added into a round-robin table using the standard [[Condorcet_method#Counting_with_matrices|Condorcet pairwise matrix]]: when a ballot ranks / grades one candidate higher than another, it means the higher-ranked candidate receives one vote in the head-to-head contest against the other.<br />
<br />
Since the diagonal cells in the Condorcet pairwise matrix are usually left blank, those locations can be used to store each candidate's Approval point score.<br />
<br />
For example, the single example ballot above,<br />
X2 > X4 >> X1 > X3<br />
, the following votes would be added into the pairwise array:<br />
{| border="1"<br />
! !! X1 !! X2 !! X3 !! X4<br />
|-<br />
! X1 || 0 || 0 || 1 || 0<br />
|-<br />
! X2 || 1 || 1 || 1 || 1<br />
|-<br />
! X3 || 0 || 0 || 0 || 0<br />
|-<br />
! X4 || 1 || 0 || 1 || 1<br />
|}<br />
<br />
We call a candidate [[Techniques_of_method_design#Defeats_and_defeat_strength|definitively defeated]] when that candidate is defeated in a head-to-head contest against any other candidate with higher Approval score. This kind of defeat is also called an ''Approval-consistent defeat''.<br />
<br />
To determine the winner,<br />
# Eliminate all definitively defeated candidates. We call the remaining candidates the '''definite majority set'''.<br />
# The winner is the single candidate who pairwise defeats (wins head-to-head contests with) all other candidates in the definite majority set.<br />
<br />
DMC always selects the [[Condorcet Criterion|Condorcet Winner]], if one exists, and otherwise selects a member of the [[Smith set]]. Step 1 has the effect of successively eliminating the least approved candidate in the Smith set and then recalculating the new Smith set until a single winner exists. But the definite majority set may also contain higher-approved candidates outside the Smith set. For example, the Approval Winner will always be a member of the definite majority set.<br />
<br />
DMC has some interesting properties:<br />
* The DMC winner has the lowest total approval score of any candidate in the Definite Majority set.<br />
* When defeat strength is measured by the approval of the defeating candidate, there is only one possible immune method, namely DMC.<br />
* DMC is a strong majority rule method.<br />
<br />
==== A more intuitive ballot --- Ranking Candidates using Grades ====<br />
<br />
One barrier to public acceptance of DMC is the ballot design. So how could the process be more intuitive, without sacrificing flexibility and expression?<br />
<br />
Many people are familiar with the standard method of giving grades A-plus through F-minus. Most are also familiar with the Pass/Fail form of grading. A student receives grades from many instructors and on finishing school has a total grade point average or pass/fail total.<br />
<br />
A similar idea could be used to rank candidates -- a voter could grade candidates as if the voter were the instructor and the candidates were the students. Determining the winner of the election would be similar to finding the student with the best set of grades.<br />
<pre><br />
A B C D F + / -<br />
<br />
X1 ( ) ( ) ( ) ( ) ( ) ( ) ( )<br />
<br />
X2 ( ) ( ) ( ) ( ) ( ) ( ) ( )<br />
<br />
X3 ( ) ( ) ( ) ( ) ( ) ( ) ( )<br />
<br />
X3 ( ) ( ) ( ) ( ) ( ) ( ) ( )<br />
</pre><br />
Like an instructor grading students, a voter may give the same grade (rank) to more than one candidate. But here, there is one additional grade -- no grade at all. Ungraded candidates are ranked lower than all graded candidates. By giving one candidate a higher grade than another, the voter gives the higher-graded candidate one vote in its head-to-head contest with the lower-graded candidate.<br />
<br />
C is the "Lowest Passing Grade" (LPG): any candidate with a grade of C or higher gets one Approval point. No Approval points are given to candidates graded at C-minus or below (that includes ungraded candidates).<br />
<br />
A candidate's total approval score will be used like the 'seed' rating in sports tournaments, to decide which head-to-head victories are worth more than others.<br />
<br />
Grades assigned to non-passing (disapproved) candidates help determine which of them will win if the voter's approved candidates do not win.<br />
<br />
In small elections it should be adequate for a voter to grade only 2 or 3 candidates, but in crowded races, the voter could also fill in the plus or minus option to fine-tune the grade. Plus/minus options allow a voter to distinguish up to 16 different rank levels: 8 approved (A-plus to C) and 8 unapproved (C-minus to unranked).<br />
<br />
Because we have fixed the Approval Cutoff / Lowest Passing Grade at C instead of C-minus, an indecisive voter has the opportunity to be hesitant about granting approval by initially filling in a grade of C. If after reconsideration the voter decides to withold approval, the minus can then be checked.<br />
<br />
To avoid spoiled ballots, we count a grade with both plus and minus cells filled as no plus or minus at all. So a truly indecisive voter could change a C grade to C-minus and back to C.<br />
<br />
==== An even simpler ballot --- Voting by slate ====<br />
In our modern world, there are sometimes too many choices available. A voter who is confused by too many choices or hasn't had time to study issues carefully might benefit by using a published preference slate, as has been suggested by the [[Imagine Democratic Fair Choice|Democratic Fair Choice]] method:<br />
<pre><br />
I | I also<br />
support | approve<br />
directly: | of:<br />
--------------------------+----------<br />
Anna (X) | ( )<br />
Bob ( ) | ( )<br />
Cecil ( ) | (X)<br />
Deirdre ( ) | (X)<br />
Ellen ( ) | ( )<br />
--------------------------+----------<br />
Democrat ( ) | ---<br />
Republican ( ) | ---<br />
Libertarian ( ) | ---<br />
Green ( ) | ---<br />
Labor ( ) | ---<br />
Progressive ( ) | ---<br />
<local newspaper> ( ) | ---<br />
--------------------------+----------<br />
(vote | (vote for as<br />
for | many candidates<br />
exactly | as you want)<br />
one) |<br />
</pre><br />
Each candidate, political organization or local newspaper could publish a preference and approval ranking, its "slate" for that particular race.<br />
<br />
By selecting a slate, the voter is saying that they want to simply copy the ranking, but if they also approve other candidates, they have the opportunity to move those candidates up in the ranking in the order they appear in the slate.<br />
<br />
Say the Libertarian slate for this race is<br />
<pre><br />
Deirdre (Lib.) >> Cecil (Reb.) > Ellen (Dem.) > Bob (Ind.) > Anna (Green)<br />
</pre><br />
where we denote the approval cutoff using ">>". Say the voter selects the libertarian slate but also approves Bob and Anna. Then the ballot would be counted as<br />
<pre><br />
Deirdre (Lib.) > Bob (Ind.) > Anna (Green) >> Cecil (Reb.) > Ellen (Dem.)<br />
</pre><br />
<br />
==== Discussion ====<br />
What is a voter saying by giving a candidate a non-approved grade or rank?<br />
<br />
One could consider the Approval Cutoff / Lowest Passing Grade (LPG) to be like Gerald Ford. Anybody better would make a good president, and anybody worse would be bad.<br />
<br />
Grading candidate X below the LPG gives the voter a chance to say "I don't want X to win, but of all the alternatives, X would make fewest changes in the wrong direction. I also won't give X a passing grade because I want X to have as small a mandate as possible." This allows the losing minority to have some say in the outcome of the election, instead of leaving the choice to the strongest core support within the majority faction.<br />
<br />
=== Handling Ties and Near Ties ===<br />
<br />
==== Approval Ties ====<br />
<br />
During the initial ranking of candidates, two candidates may have the same approval score.<br />
<br />
If equal Approval scores affect the outcome, there are several alternatives for Approval-tie-breaking. The procedure that would be most in keeping with the spirit of DMC, however would be to initially rank candidates<br />
# In descending order of Approval<br />
# If equal, in descending order of "Grade Point Average" (i.e., total Cardinal Rating)<br />
# If equal, in descending order of total first- and second-place votes<br />
# If equal, in descending order of total first-, second- and third-place votes.<br />
<br />
==== Pairwise Ties ====<br />
When there are no ties, the winner is the candidate in Forest Simmon's '''[http://wiki.electorama.com/wiki/Techniques_of_method_design#Special_sets P]''' set, the ''set of candidates which are not definitively defeated''.<br />
<br />
In the event of a pairwise tie or near tie (say, margin within 0.01%), it is sometimes possible to proceed anyway, since another member of P may defeat the tied pair. But if there is no clear winner, ties should be handled using the same [http://wiki.electorama.com/wiki/Maximize_Affirmed_Majorities#Compute_Tiebreak Random Ballot] procedure as in [[Maximize Affirmed Majorities]].<br />
<br />
== See Also ==<br />
<br />
* [[Imagine Democratic Fair Choice]]: a method that picks its winner from the same P set as DMC. It currently uses a 'slate' ballot similar to the one suggested above.<br />
* [[Pairwise Sorted Methods]]<br />
<br />
[[Category:Condorcet method]]</div>
68.122.4.103