Condorect sub-cycle rule
Markus Schulze
schulze at sol.physik.tu-berlin.de
Fri Oct 3 11:57:37 PDT 1997
Dear David,
you wrote (29 Sep 1997):
> Thank you for your responses. You inspired me to look through
> the archives more thoroughly. I still don't understand the sub-cycle
> rule, though. First, do you have a reference to Tideman, MIIAC and
> GITC?
************************************************************
Definition ("Majority Criterion"):
A method meets the "Majority Criterion" if & only if:
If a majority of the voters prefers candidate A to
every other candidate, then candidate A must be the
unique winner.
Remark:
Another word for "Majority Criterion" is "Majority
Winner Criterion."
Definition ("Condorcet Criterion"):
A method meets the "Condorcet Criterion" if & only if:
If there is a candidate A, such that this candidate
wins all of the head-to-head pairings between it and
each other candidate, then this candidate must be the
unique winner.
Remarks:
Another word for "Condorcet Criterion" is "Condorcet
Winner Criterion."
Every method, that meets the Condorcet Criterion, also
meets the Majority Criterion, because, if a majority of
the voters prefers candidate A to every other candidate,
then candidate A wins every head-to-head pairing and
thus A is a Condorcet winner.
Definition ("Majority Loser Criterion"):
A method meets the "Majority Loser Criterion" if &
only if: If a majority of the voters prefers every other
candidate to candidate A, then candidate A must not be
elected.
Definition ("Condorcet Loser Criterion"):
A method meets the "Condorcet Loser Criterion" if &
only if: If there is a candidate A, such that this candidate
loses all of the head-to-head pairings between it and
each other candidate, then this candidate must not be
elected.
Remark:
Every method, that meets the Condorcet Loser Criterion,
also meets the Majority Loser Criterion, because, if a
majority of the voters prefers every other candidate to
candidate A, then candidate A loses every head-to-head
pairing.
Definition ("Smith set"):
The Smith set is the smallest set of candidates, such that
every candidate in this set wins every head-to-head pairing
between it and a candidate outside this set.
Definition ("Smith Criterion"):
A method meets the "Smith Criterion" if & only if:
A candidate, who is not in the Smith set, must not be
elected.
Remarks:
Another word for "Smith Criterion" is "Generalized Condorcet
Criterion."
Every method, that meets the Smith Criterion, also meets
the Condorcet Criterion (and thus it meets the Majority
Criterion), because, if there is a candidate, who
wins all of the head-to-head pairings between it and
each other candidate, then the Smith set consists only
of this candidate.
Every method, that meets the Smith Criterion, also meets
the Condorcet Loser Criterion (and thus it meets the
Majority Loser Criterion), because, if there is a candidate,
who loses all of the head-to-head pairings between it and
each other candidate, then this candidate cannot be in the
Smith set.
Definition ("Modified Independence from Irrelevant Alternatives
Criterion"):
A method meets the "Modified Independence from Irrelevant
Alternatives Criterion" (MIIAC) if & only if:
An additional candidate, who is not in the Smith set, must not
change the result of the elections.
Remarks:
A method meets MIIAC, if it doesn't violate that principle
unnecessarily, that an un-elected candidate must not change
the result of the elections.
Every method, that meets MIIAC, also meets the Smith
Criterion, the Majority Criterion, the Condorcet Criterion,
the Majority Loser Criterion, and the Condorcet Loser
Criterion.
Other words for "Modified Independence from Irrelevant
Alternatives Criterion" are "Local Independence from
Irrelevant Alternatives Criterion" and "Local Stability."
************************************************************
Definition ("twins"):
A[1],...,A[m] are a set of m twins if & only if
for each pair (A[i],A[j]) of two candidates
of the set of m twins,
for each voter V, and
for each candidate C outside the set of m twins
the following statements are valid:
V prefers A[i] to C, if & only if V prefers A[j] to C.
V prefers C to A[i], if & only if V prefers C to A[j].
Definition ("Generalized Independence from Twins Criterion"):
A voting method meets the "Generalized Independence
from Twins Criterion" (GITC) if & only if additional
twins cannot change the result of the elections.
[If one twin is elected instead of another twin,
then this is not regarded as a change of the result.]
Remark:
GITC means that a party must not get any advantage or
disadvantage by presenting additional candidates
with the same or similar opinions.
Mike Ossipoff calls this criterion "Co-Partisan Independence
Criterion."
Mike Ossipoff wrote (23 Jun 1996):
> A co-partisan set is
> a set of alternatives such that everyone who ranks 1 member
> of that set over some alternative X ranks every member of
> that set over X. And everyone who doesn't rank X over some
> particular member of the set doesn't rank X over any member
> of the set. And everone who ranks some alternative Y over 1
> member of the set ranks Y over every member of the set. And
> everyone who doesn't rank Y over some particular member of
> the set doesn't rank Y over any member of the set.
>
> A method meets the Co-Partisan Independence Criterion #1
> (CPI-1) if:
>
> Given any configuration of candidates & votes, there's always
> a way of adding or subtracting members to or from any co-partisan
> set without changing the election by giving or denying victory
> to an alternative outside that co-partisan set, regardless of
> how many are added or subtracted.
>
> [For this criterion I couldn't say "adding or subtracting members
> to or from a co-partisan set can't change the election result
> by giving or denying victory to somethign outside the set", because
> it would usually or always be possible, with any or almost any
> method, to add to a co-partisan set an alternative that can
> deny victory to a member of that set, without itself being able
> to win].
>
> Of course, for any initial configuration of candidates & voters,
> adding a new candidate, for whom the voters vote, with respect
> to the other candidates, however you choose to specify, is
> permissible, and doesn't amount to changing that _initial_
> configuration. And of course no other change is permissible
> other than the removal of a candidate (in the co-partisan set)
> from the election.
>
> The point of this is to determine whether a method's
> result can depend on the size of a co-partisan set.
>
> In Copeland it's easy to have a situation where the co-partisan
> set initially (say it just has 1 member) is in a tie with
> the candidate that it beats. Adding another member to the
> co-partisan set gives an additional defeat to that other
> candidate, the one that the set beats, and is in a Copeland
> tie with. This lowers that non-co-partisan candidate's
> Copeland score by 1, and gives the election to the initial
> member of the co-partisan set, if the new member is beaten
> by him, or to the new member if he beats the initial member
> of the co-partisan set.
>
> Of course any 1 candidate is a co-partisan set.
>
> ***
>
> I've written several other versions of CPI, which do say
> that adding or subtracting an alternative from a co-partisan
> set can't change the election by giving or denying victory to
> anything outside the set, _under specified conditions_, such
> as:
>
> A method meets CPI-2 iff adding a new member to a co-partisan set
> can never change the election result by denying victory to anyone
> outside that co-partisan set unless that new addition to the
> set is the winner by that method's rules.
>
> [Obviously one could always deny victory to the previous winner
> by adding a new candidate who's the winner by the method's rules.
> We're trying to test for whether the mere addition of a member
> to a co-partisan set can deny victory to someone outside the
> set, merely because we've added a member & enlarged the set,
> not because we've added a new candidate to the election who
> is the winner by the method's rules].
Mike Ossipoff wrote (23 Jun 1996):
> A set, S, is a co-partisan set iff:
>
> Everyone who ranks some member of S over some alternative, X,
> outside S, ranks everything in S over X. And everyone who
> doesn't rank some alternative in S over some alternative X,
> outside S, doesn't rank any alternative in S over X. And
> everyone who ranks some alternative, Y, outside S, over some
> alterntive in S ranks Y over everything in S. And everyone who
> doesn't rank some alternative Y, outside S, over some alterenative
> in S doesn't rank Y over anything in S.
Mike Saari calls this criterion "Twins" Litmus Test.
Mike Saari wrote (31 Mar 1996):
> OK, here's a situation where Condorset voting fails the "Twins"
> Litmus Test. It's a variation on the Apple-Chocolate ambiguous
> example in my paper. This example works because there "just happened"
> to be a "voting cycle" between the 3 versions of Apple.
>
> The example is a bit hairy, but I trust that other motivated people
> will check my math/logic and let us know if I screwed up.
>
> Basically, with this example Condorcet voting yields winner=Apple
> when the ballot contains (Apple, Chocolate), but yields
> winner=Chocolate when the ballot contains (Apple-1, Apple-2, Apple-3,
> Chocolate). Ready? Here goes!
>
> Assume the following ratings (opinions):
>
> Apple-1 Apple-2 Apple-3 Chocolate (Ranking)
> 20% Exc(99) Exc(98) Exc(97) Exc(95) A1>A2>A3>Ch
> 20% Exc(97) Exc(99) Exc(98) Exc(95) A2>A3>A1>Ch
> 15% Exc(98) Exc(97) Exc(99) Exc(95) A3>A1>A2>Ch
>
> 15% Bad(-30) Bad(-40) Bad(-50) Exc(95) Ch>A1>A2>A3
> 15% Bad(-50) Bad(-30) Bad(-40) Exc(95) Ch>A2>A3>A1
> 15% Bad(-40) Bad(-50) Bad(-30) Exc(95) Ch>A3>A1>A2
>
> If the ballot contains only (Apple-x vs.Chocolate) then the
> Condorset winner is Apple:
> A > Ch 55%-45%
> Apple wins easily.
>
> But if the ballot contains (Apple-1, Apple-2, Apple-3, Chocolate)
> then the Condorset winner is Chocolate:
> A1 > A2 65-35
> A2 > A3 70-30
> A3 > A1 65-35
> A1 > Ch 55-45
> A2 > Ch 55-45
> A3 > Ch 55-45
> (Chocolate is the candidate whose worse pairing defeat is smallest.)
>
> Because a situation can be created where adding "Twins" to the
> ballot alters the outcome, I conclude that Condorset voting fails the
> "Twins" Litmus Test and therefore is not worthy.
I want to emphasize, that even Smith//Condorcet[EM] fails to
meet this "Twins" Litmus Test.
Example:
(1)120 voters vote Clinton > Dole > Perot.
105 voters vote Dole > Perot > Clinton.
75 voters vote Perot > Clinton > Dole.
Clinton:Dole = 195:105.
Clinton:Perot = 120:180.
Dole:Perot = 225:75.
Clinton has the lowest number of votes against and
easily wins the elections.
(2)Now, Clinton is cloned and Clinton1, Clinton2, and Clinton3
are his twins.
40 voters vote Clinton1 > Clinton2 > Clinton3 > Dole > Perot.
40 voters vote Clinton2 > Clinton3 > Clinton1 > Dole > Perot.
40 voters vote Clinton3 > Clinton1 > Clinton2 > Dole > Perot.
35 voters vote Dole > Perot > Clinton1 > Clinton2 > Clinton3.
35 voters vote Dole > Perot > Clinton2 > Clinton3 > Clinton1.
35 voters vote Dole > Perot > Clinton3 > Clinton1 > Clinton2.
25 voters vote Perot > Clinton1 > Clinton2 > Clinton3 > Dole.
25 voters vote Perot > Clinton2 > Clinton3 > Clinton1 > Dole.
25 voters vote Perot > Clinton3 > Clinton1 > Clinton2 > Dole.
Clinton1:Dole = 195:105.
Clinton2:Dole = 195:105.
Clinton3:Dole = 195:105.
Clinton1:Perot = 120:180.
Clinton2:Perot = 120:180.
Clinton3:Perot = 120:180.
Dole:Perot = 225:75.
Clinton1:Clinton2 = 200:100.
Clinton2:Clinton3 = 200:100.
Clinton1:Clinton3 = 100:200.
Now, Dole has the lowest number of votes against
and wins the elections.
Thus, Clinton's twins change the result of the elections
without being elected.
GITC is important because of many reasons:
First reason: STV, Approval voting, and ranking voting meet
GITC. The supporters of these methods will say, that
Condorcet Criterion methods are inferior for not meeting GITC.
Second reason: In many states, the parliament can suggest
additional proposals to a referendum. If a Condorcet Criterion
method is used for referendums, it would be very desirable,
that the method meets GITC. Otherwise the parliament would
present many similar proposals to increase the probability
of the parliament's most prefered proposal to win.
Third reason: Very often, it is said, that, if a Condorcet
Criterion method is used, there will be no need for primaries
anymore. But Smith//Condorcet[EM] has the property, that it
will never reward -but sometimes punish- a party for presenting
additional candidates with similar opinions. The consequence
would be, that each party would still have primaries and
would present only one candidate at the final ballot.
Remarks:
The above mentioned definition of twins is identical
to Mike Saari's definition of twins and to Mike
Ossipoff's definition of co-partisan sets.
The above mentioned definition of twins is _not_
identical to Steve Eppley's definition of twins.
Steve Eppley uses a weaker definition, which is _not_
transitive. A definition of twins is transitive if & only
if: If A2 is a twin of A1 and if A3 is a twin of A2,
then A3 is a twin of A1. Steve Eppley's definition
doesn't meet this condition.
Every method, that meets GITC, also meets Steve Eppley's
"Independence from Twins Criterion" (ITC) and Mike
Ossipoff's "The Candidate-Numbers-Are-Everything
Criterion" (CNAE).
Another word for "twins" is "clones".
************************************************************
Definition ("Generalized Majority Criterion"):
"X >> Y" means, that a majority of the voters prefers
X to Y.
"There is a majority beat-path from X to Y," means,
that X >> Y or there is a set of candidates
C[1], ..., C[n] with X >> C[1] >> ... >> C[n] >> Y.
A method meets the "Generalized Majority
Criterion" (GMC) if and only if:
If there is a majority beat-path from A to B, but
no majority beat-path from B to A, then B must not
be elected.
Remark:
A method meets GMC if & only if it doesn't unnecessarily
violate the principle, that, if a majority of the voters
prefer A to B, then B must not be elected.
Attention: There are other formulations of GMC. But these
formulations are not compatible to MIIAC or GITC.
*****
The following formulation of GMC is _not_ compatible to MIIAC:
A method meets GMC-1 if & only if that method will never elect
an alternative that has a majority against it unless every
alternative has a majority against it.
Example:
33 voters vote ABCD.
31 voters vote BCAD.
2 voters vote DABC.
2 voters vote DBAC.
32 voters vote DCAB.
33 voters vote A.
31 voters vote BC.
2 voters vote DA.
2 voters vote DB.
32 voters vote DC.
A:B=102:66
A:C=72:126
A:D=97:72
B:C=101:64
B:D=95:72
C:D=95:72
The Smith Criterion says, that D must not be elected.
GMC-1 says, that D has to be elected.
The following formulation of GMC is _not_ compatible to GITC:
A method meets GMC-2 if & only if that method will never
elect an alternative that has a majority against it unless
every alternative in the Smith set has a majority against
it.
This formulation is not compatible to GITC, because it
could happen, that twins beat eachother so badly that they
disqualify eachother by GMC-2.
*****
Every method, that meets GMC, also meets LO2E-2, truncation
resistancy, and Invulnerability to Mis-Estimate.
************************************************************
Thus: Every method, that meets MIIAC, GITC, GMC, and Pareto,
meets every important criterion mentioned in EM.
************************************************************
Tideman looks as follows:
Step1: Calculate the Smith set and eliminate all those
candidates, who are not in the Smith set.
Step2: Calculate the beat-path-defeats of the remaining
candidates. The winner is that candidate, who defeats every
other candidate via a beat path.
If there is no unique candidate, who defeats every other
candidate via a beat path, then the Schwartz set of
the beat-path-defeats is calculated, those candidates,
who are not in this Schwartz set, are eliminated and
the algorithm is re-started with the remaining candidates.
*****
What are beat-path-defeats?
A defeats B M:N via a beat-path means:
M is the highest number with
X >> Y means, that the number of voters, who prefer
X to Y, is larger than or equal to the number of voters,
who prefer Y to X, and that X gets at least M votes in
the pairwise comparison of X versus Y.
The following statement is valid:
A >> B or there is a set of candidates C[1],...,C[s]
with A >> C[1] >> ... >> C[s] >> B.
N is the highest number with
X >> Y means, that the number of voters, who prefer
X to Y, is larger than or equal to the number of voters,
who prefer Y to X, and that X gets at least N votes
the pairwise comparison of X versus Y.
The following statement is valid:
B >> A or there is a set of candidates D[1],...,D[t]
with B >> D[1] >> ... >> D[t] >> A.
And M > N.
*****
Example:
25 voters vote BCDFEA.
24 voters vote CDFEAB.
20 voters vote ABFECD.
15 voters vote EABCDF.
8 voters vote EBCADF.
4 voters vote ECADBF.
4 voters vote ECABDF.
The direct defeats look as follows:
A:B=67:33
A:C=35:65
A:D=51:49
A:E=20:80
A:F=51:49
B:C=68:32
B:D=72:28
B:E=45:55
B:F=76:24
C:D=100:0
C:E=49:51
C:F=80:20
D:E=49:51
D:F=80:20
E:F=31:69
A has 67 votes against B via the beat path A > B.
A has 67 votes against C via the beat path A > B > C.
A has 67 votes against D via the beat path A > B > D.
A has 67 votes against E via the beat path A > B > F > E.
A has 67 votes against F via the beat path A > B > F.
B has 69 votes against A via the beat path B > F > E > A.
B has 68 votes against C via the beat path B > C.
B has 72 votes against D via the beat path B > D.
B has 69 votes against E via the beat path B > F > E.
B has 76 votes against F via the beat path B > F.
C has 69 votes against A via the beat path C > F > E > A.
C has 67 votes against B via the beat path C > F > E > A > B.
C has 100 votes against D via the beat path C > D.
C has 69 votes against E via the beat path C > F > E.
C has 80 votes against F via the beat path C > F.
D has 69 votes against A via the beat path D > F > E > A.
D has 67 votes against B via the beat path D > F > E > A > B.
D has 67 votes against C via the beat path D > F > E > A > B > C.
D has 69 votes against E via the beat path D > F > E.
D has 80 votes against F via the beat path D > F.
E has 80 votes against A via the beat path E > A.
E has 67 votes against B via the beat path E > A > B.
E has 67 votes against C via the beat path E > A > B > C.
E has 67 votes against D via the beat path E > A > B > D.
E has 67 votes against F via the beat path E > A > B > F.
F has 69 votes against A via the beat path F > E > A.
F has 67 votes against B via the beat path F > E > A > B.
F has 67 votes against C via the beat path F > E > A > B > C.
F has 67 votes against D via the beat path F > E > A > B > D.
F has 69 votes against E via the beat path F > E.
Thus: The beat-path-defeats look as follows:
A:B=67:69
A:C=67:69
A:D=67:69
A:E=67:80
A:F=67:69
B:C=68:67
B:D=72:67
B:E=69:67
B:F=76:67
C:D=100:67
C:E=69:67
C:F=80:67
D:E=69:67
D:F=80:67
E:F=67:69
Thus: B wins each pairwise comparison and wins the election.
B is the winner of Tideman.
************************************************************
As far as I know, Tideman's method hasn't been published yet.
If you should search the journals for Tideman's voting methods,
you will only find his PR STV methods. This is very sad,
because Tideman's Condorcet Criterion method is very much more
interesting than his PR STV methods. [Nevertheless, I want to
emphasize, that his publications about his PR STV methods are
very excellent.]
But, I found a publication that offers a very simple explanation
of Tideman's method. In "An Introduction to Vote-Counting Schemes"
by Jonathan Levin and Barry Nalebuff ("Journal of Economic
Perspectives," vol. 9, no. 1, p. 3), it is said:
> Condorcet's (1785) seminal paper expresses the idea that a candidate
> who would defeat each of the others head-to-head should win the
> election. If no such candidate exists, then large majorities should
> take precedence over small majorities in breaking cycles. In his
> own words, the general rule was "to take successively all the
> propositions that have a majority, beginning with those possessing
> the largest. As soon as these first decisions produce a result, it
> should be taken as a decision, without regard for the less probable
> decisions that follow." How is this idea implemented? Consider all
> the possible lists that order the candidates from top to bottom.
> Find the largest margin of victory in any pairwise match - and then
> eliminate all potential rankings that contradict this preference.
> For example, if the largest victory is for candidate A over
> candidate B, eliminate all potential rankings which place B above A.
> Next, consider the second largest margin of victory, and eliminate
> all potential rankings that disagree. Continue this process until
> one ranking remains.
> With only three candidates, this method is well defined and is
> equivalent to ignoring the election with the smallest margin of
> victory. The problem is that in elections with four or more
> candidates, considering the largest unconsidered margin of victory
> may, at some point, force us to eliminate all remaining potential
> rankings (by locking in a cycle). Condorcet does not discuss this
> possibility, an omission which has led to criticism and some
> confusion.
> T.N. Tideman suggests one solution to this dilemma of cycles:
> simply skip over a head-to-head result that will lock in a cycle.
> Tideman further notes that if ties exist, there may be more than
> one potential ranking left even after we have considered all
> victories. In this case, we declare a tie among the candidates
> who have first-place ranks in the remaining potential rankings.
> Tideman calls this scheme "ranked pairs."
> In the pairwise-comparisons matrix below, we first lock in A > B,
> then B > C. This implies A > C. The next largest victory is C > A,
> but this locks in a cycle, so we ignore that head-to-head result.
> We then lock in A > D, B > D, C > D, which leaves us which a final
> ranking A > B > C > D.
>
> A:B=61:39
> A:C=41:59
> A:D=51:49
> B:C=60:40
> B:D=51:49
> C:D=51:49
Of course, "margin of victory" has to be changed to
"absolute number of votes."
*****
Suppose, there are not two (or more) pairwise comparisons,
where the winner of the one pairwise comparison gets exactly
as many votes as the winner of the other pairwise comparison.
And suppose, that there are no pairwise ties. Then, Tideman
can be explained very simply:
Step1:
In the pairwise-comparisons matrix, look for the highest
number in a pairwise comparison, that hasn't been locked
or skipped yet! If this pairwise comparison would create a
tie, skip it! If this pairwise comparison would not create
a tie, lock it!
Step2:
Repeat Step1, until every pairwise comparison is either
locked or skipped! Then: The winner is that candidate, who
is not "dominated" (i.e. who wins every locked pairwise
comparison).
Example:
46 voters vote A.
10 voters vote BAC.
10 voters vote BCA.
34 voters vote CBA.
The pairwise-comparison matrix looks as follows:
A:B=46:54
A:C=56:44
B:C=20:34
The highest number in the pairwise-comparisons matrix is 56.
Thus: A > C is locked.
Now, the highest number of a pairwise comparison, that hasn't
been locked or skipped yet, is 54. Thus: B > A is locked.
Now, the highest number of a pairwise comparison, that hasn't
been locked or skipped yet, is 34. But C > B would create a
tie (A > C > B > A). Thus: C > B is skipped.
Thus: We have A > C and B > A. B is the only candidate, who
is not dominated.
Thus: B wins. Or -to use Steve Eppley's wordings- Tideman
meets "Truncation Resistance #2".
*****
Tideman meets Pareto, because, as consensuses cannot
form a cycle, Tideman locks every consensus, before it
locks another defeat.
Tideman meets GITC, because is it not possible that twins
beat eachother so badly that they disqualify eachother,
because those defeats between twins, which would create a cycle,
are skipped, so that at least one twin in every set of twins
cannot be dominated by the other twins of his set of twins.
Tideman meets MIIAC, because a defeat of a candidate B outside
the Smith set by a candidate A of the Smith set cannot change
the order, in which the defeats between candidates of the Smith
set are locked resp. skipped, because a defeat of a candidate
outside the Smith set by a candidate of the Smith set cannot
create a cycle.
Tideman meets GMC, because, if there is a majority beat-path
from A to B, but no majority beat-path from B to A, then the
beat-path from A to B will be locked, before a beat-path from
B to A could create a cycle.
************************************************************
Another reason, why I prefer Tideman to Smith//Condorcet[EM]
is the fact, that Smith//Condorcet[EM] is *strange*, while
Tideman is not *strange*.
Definition:
A method is *strange* if & only if it is possible, that
a unique *best* candidate is a unique *worst* candidate.
Remarks:
If a unique *best* candidate is a unique *worst* candidate,
then this candidate is called *strange winner*.
*Strangeness* is a generalization of the "Majority Loser
Criterion" and the "Condorcet Loser Criterion."
Example:
18 voters prefer A to B to C to D to E.
17 voters prefer E to D to A to B to C.
17 voters prefer B to C to A to D to E.
15 voters prefer D to E to C to A to B.
14 voters prefer E to D to B to C to A.
11 voters prefer E to C to A to B to D.
2 voters prefer C to A to B to D to E.
1 voter prefers A to C to B to D to E.
1 voter prefers C to B to E to A to D.
1 voter prefers C to E to B to A to D.
1 voter prefers E to B to C to D to A.
1 voter prefers E to C to D to A to B.
1 voter prefers D to E to B to C to A.
Case 1: Suppose, the voters were asked, who the *best*
candidate is. [Example: There is only one seat to be filled.]
18 voters would say ABCDE.
17 voters would say EDABC.
17 voters would say BCADE.
15 voters would say DECAB.
14 voters would say EDBCA.
11 voters would say ECABD.
2 voters would say CABDE.
1 voter would say ACBDE.
1 voter would say CBEAD.
1 voter would say CEBAD.
1 voter would say EBCDA.
1 voter would say ECDAB.
1 voter would say DEBCA.
A:B=65:35
A:C=36:64
A:D=51:49
A:E=38:62
B:C=68:32
B:D=52:48
B:E=39:61
C:D=53:47
C:E=40:60
D:E=54:46
Suppose, Smith//Condorcet[EM] was used to determine the *best*
candidate. Then, the unique *best* candidate would be D.
Case 2: Suppose, the voters were asked, who the *worst*
candidate is. [Example: There are 4 seats to be filled and
5 candidates. The voters are asked to eliminate one
candidate.]
18 voters would say EDCBA.
17 voters would say CBADE.
17 voters would say EDACB.
15 voters would say BACED.
14 voters would say ACBDE.
11 voters would say DBACE.
2 voters would say EDBAC.
1 voter would say EDBCA.
1 voter would say DAEBC.
1 voter would say DABEC.
1 voter would say ADCBE.
1 voter would say BADCE.
1 voter would say ACBED.
A:B=35:65
A:C=64:36
A:D=49:51
A:E=62:38
B:C=32:68
B:D=48:52
B:E=61:39
C:D=47:53
C:E=60:40
D:E=46:54
Suppose, Smith//Condorcet[EM] was used to determine the *worst*
candidate. Then, the unique *worst* candidate would be D.
Thus: The unique *best* candidate is the unique *worst* candidate!
Tideman is not *strange*, because the order in which pairwise comparisons
are locked resp. skipped does not depend on whether the voters vote for
or against candidates.
Case 1:
Lock B > C.
Lock A > B.
Skip C > A.
Lock E > A.
Lock E > B.
Lock E > C.
Lock D > E.
Skip C > D.
Skip B > D.
Skip A > D.
D is the only candidate, who is not *dominated*. Thus: D is the unique
*best* candidate.
Case 2:
Lock B < C.
Lock A < B.
Skip C < A.
Lock E < A.
Lock E < B.
Lock E < C.
Lock D < E.
Skip C < D.
Skip B < D.
Skip A < D.
C is the only candidate, who is not *dominated*. Thus: C is the unique
*worst* candidate.
The fact, that Tideman is not *strange*, has some consequences.
I have already criticized, that, when Smith//Condorcet[EM] is used to elect
a candidate, then the voters are urged to differ less between the favorite
candidates and more and more between the less favoured candidates,
because otherwise it could happen, that a favorite candidate is not
elected, because he has his worst defeat against another of the
favorite candidates.
I wrote (6 May 1997):
> (1)Upward truncation [i.e., the voter gives his best preference
> to more than one candidate] becomes a usefull strategy,
> especially if there is the danger that more than one of the
> most favoured candidates comes into the Smith set and one of
> the most favoured candidates in the Smith set would have his
> highest defeat against another of the most favoured candidates
> in the Smith set.
>
> (2)Distributing the worst preferences random among the least
> favoured candidates becomes a usefull strategy. That means:
> If the voter doesn't care, who of his least favoured
> candidates wins [if one of them should win], then it is
> nevertheless the best strategy to give them different
> preferences to maximize the chances of a favoured
> candidate to win.
Rob Lanphier wrote (10 May 1997):
> This does bring up an interesting point, though, which is that
> Smith//Condorcet[EM] seems to encourage voters to be less differentiating
> of their favorite candidates, and then get more and more particular of
> candidates as one moves down the list. At the bottom of the list, one is
> encouraged to find the most minute differences and rank otherwise
> identical candidates differently.
When Smith//Condorcet[EM] is used to eliminate a candidate, then the voters
are urged to differ less between the less favoured candidates and more and
more between the more favoured candidates, because otherwise it could happen,
that a less favoured candidate is not eliminated, because he has his worst
defeat against another of the less favoured candidates.
On the other side: Tideman is not *strange*. That means, that the optimal
strategy for the voters is independent from whether the voters vote for
or against candidates. That means, that the voters are neither urged to
differ more and more between the less favoured candidates nor to differ
more and more between the most favoured candidates. [This can be explained
as follows: For Tideman, the absolute *strength* of defeats is not important.
The order in which defeats are locked resp. skipped depends only on the
relative *strength* of the defeats.]
Of course, it is possible to create examples, where voters are punished
for differing too much between the most favoured candidates or for
differing too much between the less favoured candidates or for differing
too few between the most favoured candidates or for differing too few
between the less favoured candidates. But Tideman has not the tendency
to punish those voters.
************************************************************
You wrote (26 Sep 1997):
> Does anyone have an authoritative English reference for the sub-cycle
> rule?
Mike Ossipoff wrote (10 Jul 1996):
> The subcycle rule:
>
> Definitions:
>
> A "cycle" is a set of alternatives that beat eachother in circular
> fashion: A beats B beats C beats A, for example.
>
> Cycle A is a "subcycle" of cycle B if every alternative in cycle
> A beats everything in cycle B that is beaten by something in cycle
> A, and if every alternative in cycle A is beaten by everything that
> beats something in cycle A.
>
> What it amounts to is that cycle A is an element of cycle B. A
> cycle that's an element of another cycle.
>
> 1. Before choosing a winner, solve any cycles that exist.
>
> 2. Before solving a cycle, first solve any subcycle of that cycle.
>
> 3. To solve a cycle, apply Condorcet's choice rule to the alternatives
> in that cycle, choosing a winner among those alternatives according
> to the Condorcet choice rule. Eliminate from the election every
> member of that cycle except for the winner. If that cycle, A, is a
> subcycle of another cycle, B, then the winner in A replaces cycle
> A in cycle B, occupying the same position in cycle B that cycle
> A occupied. This last sentence isn't strictly necessary as part
> of the rule, since it follows from the definition of a subcycle
> that the winner in A beats what the other members of a beat
> and is beaten by what beats them.
Mike Ossipoff wrote (18 Aug 97):
> 1. Cycle B is a subcycle of cycle A if, for any 2 elements of B,
> anything in A, but not in B, beats one of those 2 B elements
> only if it beats the other, and is beaten by one only if it
> is beaten by the other.
>
> 2. Before solving any cycle, solve every subcycle of it.
>
> 3. To solve a cycle, apply the Condorcet(EM) choice rule
> within that cycle, determine the winner, and eliminate from
> the election every member of that cycle except for the winner.
Although, it doesn't make any sense to ask a German for an
authoritative English reference, I will try to explain the
subcycle rule again:
A subcycle is a sub-set of a cycle with the following properties:
1) The smallest sub-sub-set of this sub-set, such that every
candidate in this sub-sub-set beats every candidate, who is
in this sub-set but not in this sub-sub-set, in the
head-to-head pairing is the sub-set itself. [In short:
The Smith set of this sub-set is the sub-set itself.]
2) If candidate A of this sub-set wins against candidate B
outside this sub-set in the head-to-head pairing, then every
candidate of this sub-set wins against B in the head-to-head
pairing.
3) If candidate A of this sub-set loses against candidate B
outside this sub-set in the head-to-head pairing, then every
candidate of this sub-set loses against B in the head-to-head
pairing.
Step1: Before solving a cycle, first solve any subcycle of that
cycle. To solve a cycle, use Condorcet[EM]. Eliminate from the
cycle every member of that cycle except for the winner.
Step2: Repeat Step1, until there is no cycle anymore.
Example:
25 voters vote BCDFEA.
24 voters vote CDFEAB.
20 voters vote ABFECD.
15 voters vote EABCDF.
8 voters vote EBCADF.
4 voters vote ECADBF.
4 voters vote ECABDF.
A:B=67:33
A:C=35:65
A:D=51:49
A:E=20:80
A:F=51:49
B:C=68:32
B:D=72:28
B:E=45:55
B:F=76:24
C:D=100:0
C:E=49:51
C:F=80:20
D:E=49:51
D:F=80:20
E:F=31:69
The Smith set consists of A, B, C, D, E, and F,
because A > B > C > D > F > E > A.
A > B > C > A is the only subcycle of the Smith set.
A > B > D > F > E > A, for example, is _not_ a
subcycle of the Smith set, because E wins against C
in the head-to-head pairing, while F loses against C
in the head-to-head pairing.
The Condorcet[EM] tie breaker is used to
solve the subcycle:
A:B=67:33
A:C=35:65
B:C=68:32
The winner of the Condorcet[EM] tie breaker
of the subcycle is A, because the worst defeat of
candidate A against another candidate of the subcycle
is the lowest.
Now, we eliminate all of the candidates of the subcycle,
except for the winner of the Condorcet[EM] tie breaker
of the subcycle.
A:D=51:49
A:E=20:80
A:F=51:49
D:E=49:51
D:F=80:20
E:F=31:69
The winner of the Condorcet[EM] tie breaker is D,
because the worst defeat of D against another of
the remaining candidates is the lowest.
************************************************************
You wrote (29 Sep 1997):
> I understand from a DEMOREP1 posting of 26 July 1996 that Young
> cites Condorcet as considering all cycles together. This gives B.
As far as I have understood Young correctly, then he interprets
Condorcet's wordings as follows:
Ignore lowest defeats, until there is no cycle anymore!
Then the winner is that unique candidate, who wins every
not-ignored head-to-head pairing.
Young saw the following problem ("Young Paradox"):
19 voters vote ADBC.
17 voters vote BCAD.
16 voters vote CADB.
16 voters vote DABC.
16 voters vote CDAB.
10 voters vote DBCA.
6 voters vote BCDA.
A:B=67:33
A:C=35:65
A:D=52:48
B:C=68:32
B:D=23:77
C:D=53:47
There are still cycles (e.g. A > B > C > A,
D > B > C > D, A > D > B > C > A).
A:D=52:48 is the lowest defeat in a cycle,
thus A > D is ignored.
Now, we have:
A:B=67:33
A:C=35:65
B:C=68:32
B:D=23:77
C:D=53:47
There are still cycles (e.g. A > B > C > A,
D > B > C > D).
C:D=53:47 is the lowest defeat in a cycle,
thus C > D is ignored.
Now, we have:
A:B=67:33
A:C=35:65
B:C=68:32
B:D=23:77
There is still a cycle (A > B > C > A).
A:C=35:65 is the lowest defeat in a cycle,
thus A < C is ignored.
Now, we have:
A:B=67:33
B:C=68:32
B:D=23:77
Now, we have no cycles anymore.
But there are two candidates (A and D), who
each wins every not-ignored head-to-head pairing.
Who should win? Of course, you can use
Smith//Condorcet[EM] to answer this question,
but this won't be Young's interpretation of
Condorcet's wordings anymore.
************************************************************
You wrote (3 Oct 1997):
> 100 voters, 6 options (I don't want to know about examples with more
> options!)
>
> BCDFEA 25
> CDFEAB 24
> ABFECD 20
> EABCDF 15
> EBCADF 8
> ECADBF 4
> ECABDF 4
>
> I tally pair-wise majorities
>
> AB 67-33=44
> AC 35-65=-30 BC 68-32=36
> AD 51-49=2 BD 72-28=44 CD 100
> AE 20-80=-60 BE 45-55=-10 CE 49-51=-2
> AF 51-49=2 BF 76-24=52 CF 80-20=60
> DE 49-51=-2 DF 80-20=60 EF 31-69=-38
>
> I hope that that is right.
>
> I assume that there are lots of cycles, so I start 'at the top'.
> T=100:CD
> T=60:CDF,EA
> T=44:CDF,EABDF
> T=38:gives FE, which creates a
> cycle. Thus FE must be ignored.
> T=36:gives BC, leading to
> EABCDF, which I claim is the 'obvious' solution. It would be
> reasonable to declare a tie between CE, on the basis that the
> evidence is unclear, but if pushed E must be chosen, particularly as
> it has a pair-wise majority of 2 over C.
>
> Note that one has a non-uniform threshold, with some evidence being
> accepted even though it has less support that some other evidence in
> the same 'base cycle' that is discounted.
>
> I f I had started at the bottom, for T<36 I would have the above
> solution as remaining, eliminating only contrary evidence. At T=36 I
> would have a cycle (EABCDFE), and so might be tempted to reject BC as
> having the least evidence. However, deleting it does not resolve the
> 'impossible opinion'. For this T=38. What next? Rejecting all
> evidence below the threshold for each cycle is simple, but some of it
> may be salvaged. In essence, one can carry on with the top-down
> approach to break ties.
>
> Thus, I suggest:
> 1) guess a threshold (e.g., 0)
> 2) check and increase where necessary to remove cycles
> 3) reduce where necessary to resolve ambiguities.
>
> It is simpler to describe a pure top-down approach, but the above
> mixed approach may be quicker. With computerisation, it hardly
> matters, I guess.
>
> I don't see how one can have one form of
> words that is both appealing to voters and complete and unambiguous.
> Starting with a low threshold seems intuitive and follows Condorcet,
> but introduces complications.
>
> Here's an attempt, following Condorcet:
>
> "Ballots that express a preference for X over Y are tallied, for each
> X and Y. A threshold, T, is found such that the preferences that
> tally T or more form a consistent set. This will typically be about
> half the number of voters. There may be some ties, in which case
> these are broken using any remaining consistent evidence, with
> precedence being given to that evidence with the highest tallies.
> Typically, though, this stage is not necessary"
>
> If abstentions are allowed then the method needs to be modified.
>
> "In rare cases it can happen that there is a non-chosen option that
> has a slight pair-wise majority over the chosen option. This is due
> to there being no clear overall view held by the electorate. If the
> existence of such an option is considered to grounds for rejecting
> the selected option, then similar or stronger grounds could be held
> against any of the options. Thus, although the method cannot always
> select a clear winner, its results will stand up to scrutiny."
It seems to me, that your proposal is identical to Tideman.
************************************************************
Summary:
Smith//Condorcet[EM] meets MIIAC, GMC, and Pareto. But it
fails to meet GITC.
Tideman meets MIIAC, GITC, GMC, and Pareto. Thus it meets
every important criterion.
Unlike Smith//Condorcet[EM], Tideman is not *strange*.
Unlike Smith//Condorcet[EM], Tideman doesn't urge the voters
to differ more and more between the less favoured candidates.
Nor does Tideman urge the voters to differ less between the less
favoured candidates.
Markus Schulze
More information about the Election-Methods
mailing list