Copeland's method

From electowiki
(Redirected from Llull's method)
Wikipedia has an article on:

Copeland's method is a Smith-efficient[1] Condorcet method in which the winner is determined by finding the candidate with the most (pairwise victories minus pairwise defeats), known as their Copeland score. It was invented by Ramon Llull in his 1299 treatise Ars Electionis, but his form only counted pairwise victories and not defeats (which could lead to a different result in the case of a pairwise tie).[2]

(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.

This method often leads to ties in cases when there are multiple members of the Smith set; specifically, there must be at least five or more candidates in the Smith set in order for Copeland to not produce a tie for winner unless there are pairwise ties. Critics argue that it also puts too much emphasis on the quantity of pairwise victories rather than the magnitude of those victories (or conversely, of the defeats).

Example:

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 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

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, 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

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 due to Wikipedia.

First consider the election

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:

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[3] can be used to show that Copeland is not independent of covered alternatives. First, consider the election

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

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.[4]

Generalizations

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.[5]

See also

  1. E Stensholt, "Nonmonotonicity in AV"; Electoral Reform Society Voting matters - Issue 15, June 2002 (online).
  2. A.H. Copeland, A 'reasonable' social welfare function, Seminar on Mathematics in Social Sciences, University of Michigan, 1951.
  3. 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.
  4. 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

  1. 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 in the Smith set."
  2. Colomer, Josep (2013). "Ramon Llull: From Ars Electionis to Social Choice Theory". Social Choice and Welfare. 40 (2): 317-328. doi:10.1007/s00355-011-0598-2.
  3. Simmons, F. (2010-07-16). "independence form covered alternatives is incompatible with monotonicity". Election-methods mailing list archives.
  4. Munsterhjelm, K. (2022-06-26). "Copeland DMTBR (DMTCBR) failure". Election-methods mailing list archives.
  5. Zoghi, Masrour; Karnin, Zohar; Whiteson, Shimon; de Rijke, Maarten (2015-05-31). "Copeland Dueling Bandits". arXiv:1506.00312 [cs].
This page uses Creative Commons Licensed content from Wikipedia (view authors).