electowiki

Copeland's method: Difference between revisions

Page Discussion

Copeland's method (view source)

Revision as of 08:45, 7 November 2023

485 bytes removed ,  6 months ago
Removed merge request
VisualWikitext
No edit summary
(Removed merge request)
 
(15 intermediate revisions by 4 users not shown)
Line 1:
{{Wikipedia}}
 
'''Copeland's method''' is a [[Smith criterion|Smith-efficient]]<ref>http://dss.in.tum.de/files/brandt-research/choicesets.pdf "The Copeland set C is given
by [...] i.e., the set of alternatives with maximal Copeland score." "Theorem 1. The Copeland set [...] [is] contained
Line 16 ⟶ 15:
}}</ref>
 
(Some alternative versions of Copeland don't count pairwise defeats, and others give each candidate in a pairwise tie half a point each.)
 
Proponents argue that this method is more understandable to the general populace, which is generally familiar with the sporting equivalent. In many team sports, the teams with the greatest number of victories in regular season matchups make it to the playoffs.
Line 24 ⟶ 23:
Example:
 
{{ballots|
25 A>B>C
40 B>C>A
35 C>A>B
}}
 
A beats B beats C beats A, so there is a [[Condorcet cycle]] between all candidates. Each candidate has one [[pairwise beat|pairwise victory]] and one defeat, so their Copeland scores are all 0, thus there is a tie. This example demonstrates why Copeland is almost never used for actual elections; it can guarantee someone in the [[Smith set]] will win, but says much less about who.
 
==Criterion compliances==
== Criteria ==
 
The reasoning for why Copeland's method is Smith-efficient is as follows: every candidate in the [[Smith set]] has a pairwise victory over every candidate not in the Smith set by definition, and at most has a pairwise defeat against all but one candidate other than themselves in the Smith set, which is reduced to no pairwise defeats when the Smith set has fewer than 3 candidates (since, they can't be pairwise defeated by themselves, and if they had a pairwise defeat against all candidates other than themselves in the Smith set, then they themselves would not be in the Smith set by definition, and when there are fewer than 3 Smith candidates, either there is only one Smith candidate, who thus can't be beaten by anyone, or 2 Smith candidates, who must pairwise tie each other), so all candidates in the Smith set have a Copeland score of at least (NS - S + 1), fully written out as ((number of candidates not in the Smith set) - ((number of candidates in the Smith set) - 1). Every candidate not in the Smith set has a pairwise defeat against every candidate in the Smith set by definition, and can at most have pairwise victories against every candidate other than themselves not in the Smith set, thus their Copeland score can at most be (NS - S - 1), which is ((number of candidates not in the Smith set) - 1) - (number of candidates in Smith set). Thus, the members of the Smith set will always have a Copeland score at least 2 points higher than the candidates not in the Smith set.
===Smith===
Copeland's method passes the [[Smith criterion]] because any candidate in the Smith set by definition beats everybody outside of the Smith set, but no candidate outside of it does so. For any candidate X in the Smith set and Y outside of it, Y is defeated by at least as many candidates as X, and X defeats at least one candidate that Y doesn't. Thus, every candidate in the Smith set must have a greater Copeland score than any candidate outside of it. Furthermore, the Copeland ranking of candidates (the ordering of candidates based on Copeland score) is a [[Smith set ranking]], since the above statement also holds with X being in the nth Smith set and Y in the (n+1)-th Smith set.
 
(Example showing Smith members having only 2 points more than non-Smith members: Suppose there are two candidates, one of whom is the Condorcet winner, and thus the only candidate in the Smith set. The CW has one victory and no defeats for a Copeland score of 1, while the other candidate has no victories and one defeat for a score of -1.) ▼
 
===Independence of Smith-dominated alternatives===
 
Copeland's method also passes [[ISDA]]: since every candidate in the Smith set beats everybody outside it, eliminating a candidate outside of the Smith set will subtract one win from the score of every candidate in that Smith set. Thus eliminating a Smith-dominated candidate can never change the relative Copeland scores of candidates in the Smith set, and thus not change the winner either.
 
===Uncovered set===
 
Further, Copeland always elects from the [[Uncovered set|uncovered set]], and the Copeland ranking is an uncovered set ranking. This is because when one candidate covers another, the former candidate pairwise beats all candidates pairwise beaten by the latter candidate, and also either pairwise beats the latter candidate or beats someone who beats the latter candidate. Because of this, the covering candidate will have a minimum Copeland score of ((number of candidates beaten by latter candidate) + 1) - (number of candidates beating former candidate)), and the covered candidate will have a maximal Copeland score of ((number of candidates beaten by latter candidate) - ((number of candidates beating former candidate) + 1), resulting in the covering candidate having at least 2 more points than the covered candidate. This type of logic can be used to simplify the above Smith set-related proofs too. ▼
 
==Criterion failures==
 
=== Schwartz ===
 
In the election
 
{{ballots|
1: A > B3 > B1 > B2 > C
1: B3 > B1 > B2 > C > A
2: C > A > B2 > B1 > B3
}}
 
the Schwartz winner is C, but Copeland elects A.
 
=== Independence of clones ===
 
Copeland's method is vulnerable to crowding. This example is [[w:Independence_of_clones_criterion#Copeland|due to Wikipedia]].
 
First consider the election
 
{{ballots|
1: A>B>C
1: B>C>A
2: C>A>B}}
 
C is the Condorcet winner and thus also the Copeland winner. Now clone B into B1, B2, and B3:
 
{{ballots|
1: A > B3 > B1 > B2 > C
1: B3 > B1 > B2 > C > A
2: C > A > B2 > B1 > B3
}}
 
The Copeland winner changes to A.
 
Since the Copeland winner is unique in both cases, every method that elects from the Copeland set must also fail clone independence.
 
=== Independence of covered alternatives ===
 
Unlike the Smith set, the Copeland set is not independent of alternatives not in it. It's possible for an election to contain a candidate X that is not in the Copeland set, but when removed, changes what candidates are in that set. An election set by Forest Simmons<ref>{{cite web|url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2010-July/091997.html|title=independence form covered alternatives is incompatible with monotonicity|website=Election-methods mailing list archives|date=2010-07-16|last=Simmons|first=F.}}</ref> can be used to show that Copeland is not independent of covered alternatives. First, consider the election
 
{{ballots|
40: D>B>C>A
30: A>B>C>D
30: C>A>D>B
}}
 
In this election, the Copeland set consists of A and C. The uncovered set is {A, B, C}. Now eliminate D, who is a covered candidate, and the election becomes
 
{{ballots|
40: B>C>A
30: A>B>C
30: C>A>B
}}
 
where every candidate is in the Copeland set. Thus eliminating a covered alternative changed the Copeland set.
 
=== Dominant mutual third burial resistance ===
 
Copeland fails dominant mutual third burial resistance.<ref>{{cite web|url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2022-June/003987.html|title=Copeland DMTBR (DMTCBR) failure|website=Election-methods mailing list archives|date=2022-06-26|last=Munsterhjelm|first=K.}}</ref>
Copeland's method also passes [[ISDA]]; the previous paragraph proves that all candidates in the Smith set must have higher Copeland scores than all candidates not in the Smith set, and since by definition candidates in the Smith set have a pairwise victory (and thus no pairwise defeat) against every candidate not in the Smith set, adding or removing any number of candidates not in the Smith set will only result in every candidate in the Smith set having that number of pairwise victories added or subtracted from their total (with no change to their number of pairwise defeats); since the original Copeland winner must have had a higher Copeland score than all other Smith set candidates in order to win, they will still have a higher Copeland score and thus still win.
 
==Generalizations==
The Copeland ranking of candidates (the ordering of candidates based on Copeland score) is a [[Smith set ranking]]. This is because in general, a candidate in the n-th Smith set (if n is 1, this is the Smith set. If n is 2, this is the secondary Smith set, which is the set of candidates that would be in the Smith set if all the candidates in the Smith set were eliminated from the election. If n is 3, this is the tertiary Smith set, the set of candidates that would be in the Smith set ignoring all candidates in the Smith set and secondary Smith set, etc.) will have pairwise victories against at least all candidates in k-th Smith sets (for any value of k which is greater than n), and have pairwise defeats against at most all candidates in j-th Smith sets (for any non-negative value of j which is smaller than n) and all but two candidates in the n-th Smith set, which reduces to no defeats against any candidates in the n-th Smith set when the n-th Smith set is smaller than 3 candidates (since they can't be beaten by themselves, and must not be beaten by everyone else in their Smith set in order to be in it, and there are guaranteed to be no pairwise defeats for candidates in a given Smith set against other candidates in that same Smith set when that Smith set is either one or two candidates large), while a candidate in any k-th Smith set will have pairwise victories against at most all candidates other than themselves in k-th Smith sets, and will have pairwise defeats against at least all candidates in n-th or j-th Smith sets. Mathematically, this can be represented as minimal/maximal Copeland scores of (K-J-N+1) and (K-J-N-1) respectively, with K being the number of candidates in all Smith sets "after" the n-th Smith set, J for all Smith sets "before" the n-th Smith set, and N for the candidates in the n-th Smith set. Therefore, the Copeland score of a candidate in the n-th Smith set is guaranteed to be at least 2 points higher than a candidate in any of the k-th (after or below n) Smith sets. Similar reasoning shows that a candidate in any of the j-th (before or above n) Smith sets is at least 2 points higher than any candidate in the n-th Smith set.
 
Zoghi et al have developed a multi-armed bandit variant of Copeland's method. It can be used to determine a winner in a multi-armed bandit setting, even if a Condorcet winner does not necessarily exist.<ref>{{Cite journal|last=Zoghi|first=Masrour|last2=Karnin|first2=Zohar|last3=Whiteson|first3=Shimon|last4=de Rijke|first4=Maarten|date=2015-05-31|title=Copeland Dueling Bandits|url=http://arxiv.org/abs/1506.00312|journal=arXiv:1506.00312 [cs]}}</ref>
▲(Example showing Smith members having only 2 points more than non-Smith members: Suppose there are two candidates, one of whom is the Condorcet winner, and thus the only candidate in the Smith set. The CW has one victory and no defeats for a Copeland score of 1, while the other candidate has no victories and one defeat for a score of -1.)
 
== See also ==▼
▲Further, Copeland always elects from the [[Uncovered set|uncovered set]], and the Copeland ranking is an uncovered set ranking. This is because when one candidate covers another, the former candidate pairwise beats all candidates pairwise beaten by the latter candidate, and also either pairwise beats the latter candidate or beats someone who beats the latter candidate. Because of this, the covering candidate will have a minimum Copeland score of ((number of candidates beaten by latter candidate) + 1) - (number of candidates beating former candidate)), and the covered candidate will have a maximal Copeland score of ((number of candidates beaten by latter candidate) - ((number of candidates beating former candidate) + 1), resulting in the covering candidate having at least 2 more points than the covered candidate. This type of logic can be used to simplify the above Smith set-related proofs too.
 
▲== See also ==
# E Stensholt, "[http://www.electoral-reform.org.uk/publications/votingmatters/P2.HTM Nonmonotonicity in AV]"; Electoral Reform Society ''Voting matters'' - Issue 15, June 2002 (online).
# A.H. Copeland, A 'reasonable' social welfare function, Seminar on Mathematics in Social Sciences, University of Michigan, 1951.
# V.R. Merlin, and D.G. Saari, "Copeland Method. II. Manipulation, Monotonicity, and Paradoxes"; Journal of Economic Theory; Vol. 72, No. 1; January, 1997; 148-172.
# D.G. Saari. and V.R. Merlin, 'The Copeland Method. I. Relationships and the Dictionary'; Economic Theory; Vol. 8, No. l; June, 1996; 51-76.
 
== References ==
<references />
 
[[Category:Smith-efficient Condorcet methods]]
[[Category:Condorcet-related concepts]]
[[Category:Ranked voting methods]]
[[Category:Condorcet methods]]
[[Category:Monotonic electoral systems]]
 
{{fromwikipedia}}
Retrieved from "https://electowiki.org/wiki/Special:MobileDiff/9489...17771"