Re: Debian's custom use of Condorcet and later-no-harm
Hallo, the Condorcet criterion and the later-no-harm criterion are incompatible. Therefore, the fact that Debian's Condorcet method violates the later-no-harm criterion doesn't come from the order of its checks. Markus Schulze -- To UNSUBSCRIBE, email to debian-vote-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/e1whipv-bk...@mailbox.alumni.tu-berlin.de
Re: Supermajority requirements and historical context [Was, Re: First call for votes for the Lenny release GR]
Hallo, actually, the discussion surrounding supermajorities in Condorcet goes back to 2000. See e.g.: http://lists.debian.org/debian-vote/2000/11/msg00156.html Between 2000 and 2002, this issue was discussed off-list resp. at the Debian-EM Joint Committee mailing list. See also section 7 of my paper: http://m-schulze.webhop.net/schulze1.pdf Markus Schulze -- To UNSUBSCRIBE, email to debian-vote-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Dear Anthony, I wrote (25 May 2003): >37 ACB >32 BAC >28 CBA >03 CAB >A:B=40:60 >A:C=69:31 >B:C=32:68 >Default option: A. >Quorum: 30. >B meets quorum. >C meets quorum. >Manoj's May 15 proposal would choose A. You wrote (25 May 2003): > C fails to reach its majority requirement and is dropped. > B and A are the only remaining options, and B defeats A. > B wins. That's strange! The majority requirement makes the default option lose. Doesn't that contradict the intention of the majority requirement? Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Dear Raul, you wrote (25 May 2003): > On the other hand, if you could show that the May 15 mechanism > violates monotonicity, then I'd be opposed to it. Situation 1: 40 ACB 32 BAC 28 CBA A:B=40:60 A:C=72:28 B:C=32:68 Default option: A. Quorum: 30. B meets quorum. C fails to meet quorum. Manoj's May 15 proposal would choose B. Situation 2: 3 ACB voters change their minds to CAB. 37 ACB 32 BAC 28 CBA 03 CAB A:B=40:60 A:C=69:31 B:C=32:68 Default option: A. Quorum: 30. B meets quorum. C meets quorum. Manoj's May 15 proposal would choose A. Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Dear Raul, here is a simpler example. 8 ABC 7 BCA 5 CAB A:B=13:07 A:C=08:12 B:C=15:05 Suppose, that the quorum is 10 and the default option is A. Then the winner according to Manoj's May 15 proposal is C. If there was a second election and the voters don't change their minds, then the winner (according to Manoj's May 15 proposal) of this second election would be B. If there was a third election and again the voters don't change their minds, then the winner (according to Manoj's May 15 proposal) of this third election would be A. In short: The winner according to Manoj's May 15 proposal can be cyclic even when the voters don't change their minds. This is caused by the fact that _direct defeats_ can be cyclic. On the other side, _beat path defeats_ cannot be cyclic. Therefore, the winner according to my proposal cannot be cyclic when the voters don't change their minds. Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Dear Raul, I wrote (25 May 2003): > There is only one election. You wrote (25 May 2003): > This seems to contradict what you said in your 5/24 message: > >Manoj's May 15 proposal would choose candidate E. In the next >elections, when candidate E is the default option, Manoj's >May 15 proposal would choose candidate D. There is only one election. In this election, 38 voters prefer E to C, 42 voters prefer D to E and 24 voters prefer D to C. Manoj's May 15 proposal would choose candidate E. My proposal would choose candidate D. But --and this is what I have to criticize-- _if there was a second election_ then (simply because of the fact that in the first election the default option has been changed from candidate C to candidate E) in this second election the winner according to Manoj's May 15 proposal would be changed from candidate E to candidate D _without having any voter to change his mind_. On the other side, the winner according to my proposal would still be candidate D. In my opinion, this is a disadvantage of Manoj's May 15 proposal because this means that Manoj's May 15 proposal leads to unnecessarily frequent changes of the status quo. Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Dear Raul, you wrote (25 May 2003): > Quorum of 10, ballot A, default (D), votes: > > 31 A D > 28 D A > > Here, A does not defeat D by 10, but still satisfies > the quorum requirement. As far as I have understood Manoj's May 15 proposal correctly, A defeats D by 31 in your example. ** I wrote (25 May 2003): > As far as I have understood Manoj's May 15 proposal correctly, > an option is dropped unless it _directly_ defeats the default > option with the required quorum. I suggest that it should be > sufficient that this option _transitively_ defeats the default > option with the required quorum. You wrote (25 May 2003): > As stated, this changes the quorum requirement from a concept > of "minimum level of approval required to conduct business" to > a concept of "required margin of victory required against the > default option". > > In earlier discussions, it was felt that the "margin of victory" > concept was too heavily biased in the direction of the status quo. > > That said, I'll note that your explanation, further down, actually > indicates you had a different idea in mind. What makes you believe that I prefer margins? Actually, I don't even mentioned the "margins vs. positive votes" issue in my last mails. ** I wrote (25 May 2003): > Situation 1: > >04 ABCDEF >02 ABFDEC >04 AEBFCD >02 AEFBCD >02 BFACDE >02 CDBEFA >04 CDBFEA >12 DECABF >08 ECDBFA >10 FABCDE >06 FABDEC >04 FEDBCA > >A:B=40:20 >A:C=30:30 >A:D=30:30 >A:E=30:30 >A:F=24:36 >B:C=34:26 >B:D=30:30 >B:E=30:30 >B:F=38:22 >C:D=36:24 >C:E=22:38 >C:F=30:30 >D:E=42:18 >D:F=30:30 >E:F=32:28 > >The beat paths have the following strengths: > >A:B=40:36 >A:C=34:32 >A:D=34:32 >A:E=34:32 >A:F=38:36 >B:C=34:32 >B:D=34:32 >B:E=34:32 >B:F=38:36 >C:D=36:38 >C:E=36:38 >C:F=32:34 >D:E=42:36 >D:F=32:34 >E:F=32:34 > >Therefore, the ranking according to the beat path >method is ABFDEC. > >Suppose that, for example, the default option is C >and the quorum is 38. Then the winner is candidate D. I wrote (25 May 2003): > Manoj's May 15 proposal would choose candidate E. In the next > elections, when candidate E is the default option, Manoj's > May 15 proposal would choose candidate D. My proposal would > choose candidate D immediately. In my opinion, the advantage > of my proposal is that it doesn't lead to unnecessarily > frequent changes of the status quo. You wrote (25 May 2003): > It's true that in your example, E was ranked second last (with C, > the default, ranked last). But, given that not many voters elected to > participate, and given that those who did vote couldn't muster enough > agreement that any of the other options were better than doing nothing, > I think this is a worthwhile outcome. > > More fundamentally, however: you've assumed that while only 24 people > thought D was a good idea in the first election, that 42 would think it's > a good idea in the second election. In other words, your starting point > is thinking of the default option as an outcome, rather than a refusal > to choose an option. At the same time, you've assumed that the large > majority of voters who didn't participate in the first election would > continue to ignore the second. > > The way I see it, either these options just aren't all that important > (in which case there's no reason for 18 people to suddenly decide to > change their minds about whether or not D is a good idea), or they are > important (in which case there should be many more people participating > in that second election). There is only one election. In this election, 38 voters prefer E to C, 42 voters prefer D to E and 24 voters prefer D to C. When the default option is changed from C to E, then the number of voters who prefer D to the default option is raised from 24 to 42 without having any voter to change his mind. You wrote (25 May 2003): > In neither circumstance does the extra "decisiveness" gained by your > approach yield a positive result: > > For the case that these options aren't that important, it's harder to > explain to people what the default option means. [It no longer means > postponing agreeing on some decisions, except for cases where people > can come to some sort of agreement on the overall ranking of options.] > > For the case where these options are important, we're achieving a decision > before people have realized that they care. My proposal isn't "extra decisive." When Manoj's May 15 proposal disqualifies all options (other than the default option) because of the quorum requirement then so does my proposal. Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Dear Nathanael, Raul Miller wrote (25 May 2003): > Correct me if I'm wrong, but: what Manoj's May 15 proposal > implements logically equivalent to your suggestion? I wrote (25 May 2003): > As far as I have understood Manoj's May 15 proposal correctly, > an option is dropped unless it _directly_ defeats the default > option with the required quorum. I suggest that it should be > sufficient that this option _transitively_ defeats the default > option with the required quorum. You wrote (25 May 2003): > Let me apply this to my evil testcase. :-) > > 19x A=DB > 19x ABD > 1x BA=D > > A defeats B by 38 to 1 > A defeats D by 19 to 0 > B defeats D by 20 to 19. > > On the A->B->D defeat path, A defeats D with 20 positive > votes at the weakest link, which makes quorum, and A wins. > > Yep, this fixes the perverse result I was talking about in > another thread (where Manoj's proposal causes B to win). > Am I correct, Markus? Yes. You are absolutely correct. Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Dear Raul, you wrote (25 May 2003): > Markus Schulze wrote (25 May 2003): > > I suggest that one should at first calculate the ranking of > > the candidates according to the beat path method and then, > > of those candidates whose beat path to the default option > > meets the quorum, that candidate should be elected who is > > ranked highest in the ranking of the beat path method. > > That's the maximum that you can get without undermining > > the intention of super-majority requirements. > > Correct me if I'm wrong, but: what Manoj's May 15 proposal > implements logically equivalent to your suggestion? As far as I have understood Manoj's May 15 proposal correctly, an option is dropped unless it _directly_ defeats the default option with the required quorum. I suggest that it should be sufficient that this option _transitively_ defeats the default option with the required quorum. In Situation 1 in my last mail, the quorum is 38. According to Manoj's May 15 proposal, candidate D is disqualified since only 24 voters strictly prefer candidate D to candidate C. According to my proposal, candidate D is not disqualified since 38 voters strictly prefer candidate E to candidate C and 42 voters strictly prefer candidate D to candidate E. Manoj's May 15 proposal would choose candidate E. In the next elections, when candidate E is the default option, Manoj's May 15 proposal would choose candidate D. My proposal would choose candidate D immediately. In my opinion, the advantage of my proposal is that it doesn't lead to unnecessarily frequent changes of the status quo. Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Hallo, Situation 1: 04 ABCDEF 02 ABFDEC 04 AEBFCD 02 AEFBCD 02 BFACDE 02 CDBEFA 04 CDBFEA 12 DECABF 08 ECDBFA 10 FABCDE 06 FABDEC 04 FEDBCA A:B=40:20 A:C=30:30 A:D=30:30 A:E=30:30 A:F=24:36 B:C=34:26 B:D=30:30 B:E=30:30 B:F=38:22 C:D=36:24 C:E=22:38 C:F=30:30 D:E=42:18 D:F=30:30 E:F=32:28 The winner is candidate A. Situation 2: 3 AEFCBD voters are added. A:B=43:20 A:C=33:30 A:D=33:30 A:E=33:30 A:F=27:36 B:C=34:29 B:D=33:30 B:E=30:33 B:F=38:25 C:D=39:24 C:E=22:41 C:F=30:33 D:E=42:21 D:F=30:33 E:F=35:28 Now, the winner is candidate D. Thus the 3 AEFCBD voters change the winner from candidate A to candidate D. ** John wrote (23 May 2003): > instead, the per-option quorum will throw out the IDW in > favour of a less-favoured option due to quorum requirements. > > R=15 > 10 ABD > 5 BDA I suggest that one should at first calculate the ranking of the candidates according to the beat path method and then, of those candidates whose beat path to the default option meets the quorum, that candidate should be elected who is ranked highest in the ranking of the beat path method. That's the maximum that you can get without undermining the intention of super-majority requirements. In Situation 1, for example, the beat paths have the following strengths: A:B=40:36 A:C=34:32 A:D=34:32 A:E=34:32 A:F=38:36 B:C=34:32 B:D=34:32 B:E=34:32 B:F=38:36 C:D=36:38 C:E=36:38 C:F=32:34 D:E=42:36 D:F=32:34 E:F=32:34 Therefore, the ranking according to the beat path method is ABFDEC. Suppose that, for example, the default option is C and the quorum is 38. Then the winner is candidate D. Markus Schulze (not Martin Schulze)
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Hallo, John wrote (23 May 2003): > instead, the per-option quorum will throw out the IDW in > favour of a less-favoured option due to quorum requirements. > > R=15 > 10 ABD > 5 BDA I suggest that one should at first calculate the ranking of the candidates according to the beat path method and then, of those candidates whose beat path to the default option meets the quorum, that candidate should be elected who is ranked highest in the ranking of the beat path method. That's the maximum that you can get without undermining the intention of super-majority requirements. Example: A:B=206:94 A:C=160:140 A:D=161:139 A:E=162:138 A:F=96:204 B:C=202:98 B:D=163:137 B:E=164:136 B:F=205:95 C:D=203:97 C:E=93:207 C:F=165:135 D:E=228:72 D:F=166:134 E:F=201:99 Via beat paths, the pairwise defeats are: A:B=206:204 A:C=202:201 A:D=202:201 A:E=202:201 A:F=205:204 B:C=202:201 B:D=202:201 B:E=202:201 B:F=205:204 C:D=203:207 C:E=203:207 C:F=201:202 D:E=228:203 D:F=201:202 E:F=201:202 Therefore, the ranking according to the beat path method is ABFDEC. Suppose that, for example, the default option is C and the quorum is 207. Then the winner is candidate D. Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Hallo, here is an extreme violation of the participation criterion. Situation 1: A:B=206:94 A:C=160:140 A:D=161:139 A:E=162:138 A:F=96:204 B:C=202:98 B:D=163:137 B:E=164:136 B:F=205:95 C:D=203:97 C:E=93:207 C:F=165:135 D:E=228:72 D:F=166:134 E:F=201:99 Candidate A is the unique beat path winner. Situation 2: 10 AEFCBD voters are added. A:B=216:94 A:C=170:140 A:D=171:139 A:E=172:138 A:F=106:204 B:C=202:108 B:D=173:137 B:E=164:146 B:F=205:105 C:D=213:97 C:E=93:217 C:F=165:145 D:E=228:82 D:F=166:144 E:F=211:99 Candidate D is the unique beat path winner. This example demonstrates that the extreme violation of the participation criterion has nothing to do with quorum requirements. Markus Schulze
Re: Constitutional amendment: Condorcet/Clone Proof SSD vote tallying
Hallo, it is necessary to distinguish between the participation criterion and the monotonicity criterion. The participation criterion says that a set of additional voters who strictly prefer candidate A to candidate B must not change the winner from candidate A to candidate B. The Condorcet criterion and the participation criterion are incompatible (Herve Moulin, "Condorcet's Principle Implies the No Show Paradox," Journal of Economic Theory, vol. 45, pp. 53-64, 1988). Therefore, this criterion is _of no concern_ when we want to discuss which Condorcet method should be adopted. The monotonicity criterion says that (1) when some voters rank a given candidate A higher without changing the orders in which they prefer the other candidates then candidate A must not be changed from a winner to a loser and (2) when some voters rank a given candidate A lower without changing the orders in which they prefer the other candidates then candidate A must not be changed from a loser to a winner. It is _not_ true that the monotonicity criterion implies the participation criterion. It is also _not_ true that the monotonicity criterion implies that when candidate A is the original winner then adding voters who strictly prefer candidate A to every other candidate must not change candidate A into a loser. Suppose that candidate A is the original winner. Suppose that an ABC voter is added. Then on the one side this voter is changed from a voter who ranks all three candidates equally to a voter who strictly prefers candidate A to every other candidate; therefore, one could expect that the monotonicity criterion implies that candidate A stays the winner. However, this voter is also changed from a voter who ranks candidate B and candidate C equally to a voter who strictly prefers candidate B to candidate C. Therefore, the requirement that the orders in which the other candidates are prefered aren't changed isn't met. However, it is true that the monotonicity criterion implies that when candidate A is the original winner then adding voters who strictly prefer candidate A to every other candidate and who rank all the other candidates equally must not change candidate A into a loser. Markus Schulze
Re: Dec 15 voting amendment draft
Dear Clinton, you wrote (14 Feb 2003): > Participation Monotonicity. > > If > (i) There is an election X in which option A wins. > (ii) There is a vote V ranks option A over option B. > (iii) There is an election Y identical to election X except that it has > an additional vote V. > then > Option B must not win election Y. > > What Participation Monotonicity says is, that participation will never > cause a less prefered option to win than non-participation. That is, it > is never advantagous to not participate. The participation criterion and the Condorcet criterion are incompatible. (Proof: Herve Moulin, "Condorcet's Principle Implies the No Show Paradox," Journal of Economic Theory, vol. 45, pp. 53-64, 1988.) As far as I know, only point methods (e.g. plurality, Approval Voting, Borda) meet the participation criterion. Markus Schulze
Re: Dec 15 voting amendment draft
Dear Clinton, you wrote (14 Feb 2003): > Participation Monotonicity. > > If > (i) There is an election X in which option A wins. > (ii) There is a vote V ranks option A over option B. > (iii) There is an election Y identical to election X except that it has > an additional vote V. > then > Option B must not win election Y. > > What Participation Monotonicity says is, that participation will never > cause a less prefered option to win than non-participation. That is, it > is never advantagous to not participate. The participation criterion and the Condorcet criterion are incompatible. (Proof: Herve Moulin, "Condorcet's Principle Implies the No Show Paradox," Journal of Economic Theory, vol. 45, pp. 53-64, 1988.) As far as I know, only point methods (e.g. plurality, Approval Voting, Borda) meet the participation criterion. Markus Schulze -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: Another draft of A.6
Dear Raul, you wrote (14 Nov 2002): > Definition: An option C is in the Schultz set if there is no > other option D such that C transitively defeats D AND D does > not transitively defeat C. I guess you mean: > Definition: An option C is in the Schultz set if there is no > other option D such that D transitively defeats C AND C does > not transitively defeat D. Markus Schulze
Re: Another draft of A.6
Dear Raul, you wrote (14 Nov 2002): > Definition: An option C is in the Schultz set if there is no > other option D such that C transitively defeats D AND D does > not transitively defeat C. I guess you mean: > Definition: An option C is in the Schultz set if there is no > other option D such that D transitively defeats C AND C does > not transitively defeat D. Markus Schulze -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: [mike ossipoff ] Cloneproof SSD program, with balloting
Dear Manoj,
the Floyd algorithm to calculate the beat paths from
each candidate to each other candidate looks as follows
(Markus Schulze; 17 Oct 2002):
> for (i : = 1; i <= NumberOfCandidates; i++)
> for (j : = 1; j <= NumberOfCandidates; j++)
> for (k : = 1; k <= NumberOfCandidates; k++)
> {
> s : = min(P(j,i),P(i,k));
> if (s > P1(j,k)) then
> P1(j,k) : = s;
> }
However, Mike Ossipoff wrote (31 Oct 2002):
>for i in range(N)
> for j in range(N)
> for k in range(N)
> low=min(B[A(i,j)],B[A(j,k)]
> if low>B[A(i,k)]
>B[A(i,k)]=low
>change=1
The order of the indices is NOT irrelevant! Only when
one uses the same order that I use in my implementation,
it is guaranteed that one has to apply the triple loop
only once! The Floyd algorithm can be found in every
book on graph theory.
Markus Schulze
Re: [mike ossipoff ] Cloneproof SSD program, with balloting
Dear Manoj,
the Floyd algorithm to calculate the beat paths from
each candidate to each other candidate looks as follows
(Markus Schulze; 17 Oct 2002):
> for (i : = 1; i <= NumberOfCandidates; i++)
> for (j : = 1; j <= NumberOfCandidates; j++)
> for (k : = 1; k <= NumberOfCandidates; k++)
> {
> s : = min(P(j,i),P(i,k));
> if (s > P1(j,k)) then
> P1(j,k) : = s;
> }
However, Mike Ossipoff wrote (31 Oct 2002):
>for i in range(N)
> for j in range(N)
> for k in range(N)
> low=min(B[A(i,j)],B[A(j,k)]
> if low>B[A(i,k)]
>B[A(i,k)]=low
>change=1
The order of the indices is NOT irrelevant! Only when
one uses the same order that I use in my implementation,
it is guaranteed that one has to apply the triple loop
only once! The Floyd algorithm can be found in every
book on graph theory.
Markus Schulze
--
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: RFD: Reviving Constitutional amendment: Smith/Condorcet vote tallying
Dear Manoj, dear Raul, dear Anthony,
I have added the original description (1997) of this method.
I hope that it will make the idea behind this method clearer.
***
Axiomatic Definition:
Suppose, that d(Ci,Cj) is the number of voters who strictly prefer
candidate Ci to candidate Cj. A "beat path from candidate A to
candidate B" is an ordered set of candidates C1,...,Cn such that
candidate A is identical to candidate C1, such that candidate B
is identical to candidate Cn, and such that
d(Ci,C(i+1)) - d(C(i+1),Ci) >= 0 for all i = 1,...,(n-1).
S1(C1,...,Cn) : = min{ d(Ci,C(i+1))| i = 1,...,(n-1)}.
S2(C1,...,Cn) : = min{ d(Ci,C(i+1)) - d(C(i+1),Ci) | i = 1,...,(n-1)}.
P1(A,B) : = max { S1(C1,...,Cn) | C1,...,Cn is a beat path from A to B}.
P2(A,B) : = max { S2(C1,...,Cn) | C1,...,Cn is a beat path from A to B;
S1(C1,...,Cn) = P1(A,B)}.
When there is no beat path from candidate A to candidate B, then
P1(A,B) := -1. [P2(A,B) can be defined arbitrarily when there is
no beat path from candidate A to candidate B.]
When C1,...,Cn is a beat path, then S1(C1,...,Cn) is called the
"absolute strength of the beat path C1,...,Cn" and S2(C1,...,Cn)
is called the "margin of the beat path C1,...,Cn".
A "Schulze winner" is a candidate A such that
(P1(A,B) > P1(B,A)) or ((P1(A,B) = P1(B,A)) and (P2(A,B) >= P2(B,A)))
for every other candidate B.
The "Schulze set" is the set of all Schulze winners. [It can be proven
that there is always at least one Schulze winner.] If there is more
than one Schulze winner, the elector with the casting vote picks the
winner from the Schulze set.
***
Algorithmic Definition with the Floyd Algorithm:
Input: d(i,j) is the number of voters who strictly
prefer candidate i to candidate j
for (i : = 1; i <= NumberOfCandidates; i++)
for (j : = 1; j <= NumberOfCandidates; j++)
if (i <> j) then
{
if (d(i,j) >= d(j,i)) then
P1(i,j) : = d(i,j);
else
P1(i,j) : = -1;
P2(i,j) : = d(i,j) - d(j,i);
}
for (i : = 1; i <= NumberOfCandidates; i++)
for (j : = 1; j <= NumberOfCandidates; j++)
if (i <> j) then
for (k : = 1; k <= NumberOfCandidates; k++)
if ((i <> k) and (j <> k)) then
{
s : = min(P1(j,i),P1(i,k));
t : = min(P2(j,i),P2(i,k));
if ((P1(j,k) < s) or
((P1(j,k) = s) and (P2(j,k) < t))) then
{
P1(j,k) : = s;
P2(j,k) : = t;
}
}
for (i : = 1; i <= NumberOfCandidates; i++)
{
winner(i) : = true;
for (j : = 1; j <= NumberOfCandidates; j++)
if (i <> j) then
if ((P1(i,j) < P1(j,i)) or
((P1(i,j) = P1(j,i)) and (P2(i,j) < P2(j,i then
winner(i) : = false;
}
If there is more than one candidate with "winner(i) = true",
the elector with the casting vote picks the winner from all
the candidates with "winner(i) = true".
Markus Schulze
Re: RFD: Reviving Constitutional amendment: Smith/Condorcet vote tallying
Dear Manoj, dear Raul, dear Anthony,
I have added the original description (1997) of this method.
I hope that it will make the idea behind this method clearer.
***
Axiomatic Definition:
Suppose, that d(Ci,Cj) is the number of voters who strictly prefer
candidate Ci to candidate Cj. A "beat path from candidate A to
candidate B" is an ordered set of candidates C1,...,Cn such that
candidate A is identical to candidate C1, such that candidate B
is identical to candidate Cn, and such that
d(Ci,C(i+1)) - d(C(i+1),Ci) >= 0 for all i = 1,...,(n-1).
S1(C1,...,Cn) : = min{ d(Ci,C(i+1))| i = 1,...,(n-1)}.
S2(C1,...,Cn) : = min{ d(Ci,C(i+1)) - d(C(i+1),Ci) | i = 1,...,(n-1)}.
P1(A,B) : = max { S1(C1,...,Cn) | C1,...,Cn is a beat path from A to B}.
P2(A,B) : = max { S2(C1,...,Cn) | C1,...,Cn is a beat path from A to B;
S1(C1,...,Cn) = P1(A,B)}.
When there is no beat path from candidate A to candidate B, then
P1(A,B) := -1. [P2(A,B) can be defined arbitrarily when there is
no beat path from candidate A to candidate B.]
When C1,...,Cn is a beat path, then S1(C1,...,Cn) is called the
"absolute strength of the beat path C1,...,Cn" and S2(C1,...,Cn)
is called the "margin of the beat path C1,...,Cn".
A "Schulze winner" is a candidate A such that
(P1(A,B) > P1(B,A)) or ((P1(A,B) = P1(B,A)) and (P2(A,B) >= P2(B,A)))
for every other candidate B.
The "Schulze set" is the set of all Schulze winners. [It can be proven
that there is always at least one Schulze winner.] If there is more
than one Schulze winner, the elector with the casting vote picks the
winner from the Schulze set.
***
Algorithmic Definition with the Floyd Algorithm:
Input: d(i,j) is the number of voters who strictly
prefer candidate i to candidate j
for (i : = 1; i <= NumberOfCandidates; i++)
for (j : = 1; j <= NumberOfCandidates; j++)
if (i <> j) then
{
if (d(i,j) >= d(j,i)) then
P1(i,j) : = d(i,j);
else
P1(i,j) : = -1;
P2(i,j) : = d(i,j) - d(j,i);
}
for (i : = 1; i <= NumberOfCandidates; i++)
for (j : = 1; j <= NumberOfCandidates; j++)
if (i <> j) then
for (k : = 1; k <= NumberOfCandidates; k++)
if ((i <> k) and (j <> k)) then
{
s : = min(P1(j,i),P1(i,k));
t : = min(P2(j,i),P2(i,k));
if ((P1(j,k) < s) or
((P1(j,k) = s) and (P2(j,k) < t))) then
{
P1(j,k) : = s;
P2(j,k) : = t;
}
}
for (i : = 1; i <= NumberOfCandidates; i++)
{
winner(i) : = true;
for (j : = 1; j <= NumberOfCandidates; j++)
if (i <> j) then
if ((P1(i,j) < P1(j,i)) or
((P1(i,j) = P1(j,i)) and (P2(i,j) < P2(j,i then
winner(i) : = false;
}
If there is more than one candidate with "winner(i) = true",
the elector with the casting vote picks the winner from all
the candidates with "winner(i) = true".
Markus Schulze
--
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: Condorcet Voting and Supermajorities (Re: [CONSTITUTIONAL AMENDMENT] Disambiguation of 4.1.5)
Dear Buddha,
you wrote (14 Nov 2000):
> Could someone explain to me, in simple terms, how
> Condorcet-based voting schemes work in the face of
> a supermajority requirement?
>
> My understanding of Condorcet is that a ballot like
> Anthony Towns used as an example ("Remove non-free
> // We Love non-free! // Status-quo // Further
> discussion") would be, during the first analysis,
> treated as if it were 6 separate 1-on-1 votes, with
> each of the four choices paired against each of the
> remaining 3. If any of the four wins all three of
> the 1-on-1 votes it's part of, it wins the full
> balloting. Otherwise, we use a fall-back resolution
> method (of which there are several varieties in the
> literature to choose in advance from).
>
> This works fine if all the options required a plurality
> to win (note: I'm not even sure if "majority" or
> "plurality" are appropriate descriptions of the victory
> condition in Condorcet-based schemes). The system is
> balanced.
>
> But if one of the choices explicitly requires a 3:1
> supermajority to work, I don't see how it works quite
> so well.
To my opinion, one should at first check which proposals
are "available" (i.e. which proposals can be passed without
violating the supermajority requirement) and then one
should use a Condorcet method amongst these "available"
proposals.
Definition ("available"):
"X >> Y" means that a supermajority of the voters
strictly prefers proposal X to proposal Y.
"There is a qualified beat path from proposal A to
proposal B" means that
(1) A >> B or
(2) there is a set of candidates C[1],...,C[n] with
A >> C[1] >> ... >> C[n] >> B.
"Proposal D is available" means that there is a
qualified beat path from proposal D to the status quo.
Explanation:
If and only if there is a qualified beat path
D >> C[1] >> ... >> C[n] >> StatusQuo from proposal D
to the Status Quo, then proposal D can be passed
without violating the supermajority requirement.
Those voters who prefer proposal D to the Status Quo
will at first propose proposal C[n] to the Status Quo
so that proposal C[n] becomes the new Status Quo.
Then these voters will propose the proposals
C[n-1],...,C[1] successively so that C[n-1],...,C[1]
successively become the new Status Quo wihout
violating the supermajority requirement. Then
they will propose proposal D so that proposal D
becomes the new Status Quo wihout violating the
supermajority requirement. Therefore the above
mentioned definition of "available" proposals
makes sense.
The above mentioned definition of an "available" proposal
is very weak. Even proposals that are Pareto-inferior to
the Status Quo (**) can be "available" due to the above
mentioned definition. But this is not a problem at least
as long as the used Condorcet method guarantees that such
a proposal cannot be chosen.
Markus Schulze
(**) "Proposal Z is Pareto-inferior to the Status Quo"
means that every voter strictly prefers the Status Quo
to proposal Z.
Re: Condorcet Voting and Supermajorities (Re: [CONSTITUTIONAL AMENDMENT] Disambiguation of 4.1.5)
Dear Buddha,
you wrote (14 Nov 2000):
> Could someone explain to me, in simple terms, how
> Condorcet-based voting schemes work in the face of
> a supermajority requirement?
>
> My understanding of Condorcet is that a ballot like
> Anthony Towns used as an example ("Remove non-free
> // We Love non-free! // Status-quo // Further
> discussion") would be, during the first analysis,
> treated as if it were 6 separate 1-on-1 votes, with
> each of the four choices paired against each of the
> remaining 3. If any of the four wins all three of
> the 1-on-1 votes it's part of, it wins the full
> balloting. Otherwise, we use a fall-back resolution
> method (of which there are several varieties in the
> literature to choose in advance from).
>
> This works fine if all the options required a plurality
> to win (note: I'm not even sure if "majority" or
> "plurality" are appropriate descriptions of the victory
> condition in Condorcet-based schemes). The system is
> balanced.
>
> But if one of the choices explicitly requires a 3:1
> supermajority to work, I don't see how it works quite
> so well.
To my opinion, one should at first check which proposals
are "available" (i.e. which proposals can be passed without
violating the supermajority requirement) and then one
should use a Condorcet method amongst these "available"
proposals.
Definition ("available"):
"X >> Y" means that a supermajority of the voters
strictly prefers proposal X to proposal Y.
"There is a qualified beat path from proposal A to
proposal B" means that
(1) A >> B or
(2) there is a set of candidates C[1],...,C[n] with
A >> C[1] >> ... >> C[n] >> B.
"Proposal D is available" means that there is a
qualified beat path from proposal D to the status quo.
Explanation:
If and only if there is a qualified beat path
D >> C[1] >> ... >> C[n] >> StatusQuo from proposal D
to the Status Quo, then proposal D can be passed
without violating the supermajority requirement.
Those voters who prefer proposal D to the Status Quo
will at first propose proposal C[n] to the Status Quo
so that proposal C[n] becomes the new Status Quo.
Then these voters will propose the proposals
C[n-1],...,C[1] successively so that C[n-1],...,C[1]
successively become the new Status Quo wihout
violating the supermajority requirement. Then
they will propose proposal D so that proposal D
becomes the new Status Quo wihout violating the
supermajority requirement. Therefore the above
mentioned definition of "available" proposals
makes sense.
The above mentioned definition of an "available" proposal
is very weak. Even proposals that are Pareto-inferior to
the Status Quo (**) can be "available" due to the above
mentioned definition. But this is not a problem at least
as long as the used Condorcet method guarantees that such
a proposal cannot be chosen.
Markus Schulze
(**) "Proposal Z is Pareto-inferior to the Status Quo"
means that every voter strictly prefers the Status Quo
to proposal Z.
--
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
