*To*: debian-vote@lists.debian.org*Subject*: Re: RFD: Reviving Constitutional amendment: Smith/Condorcet vote tallying*From*: Markus Schulze <markus.schulze@alumni.tu-berlin.de>*Date*: Thu, 17 Oct 2002 21:19:06 +0200*Message-id*: <3DAF0D2A.4192D8DC@alumni.tu-berlin.de>

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

- Prev by Date:
**Re: General Resolution draft against spam.** - Next by Date:
**Re: General Resolution draft against spam.** - Previous by thread:
**Re: RFD: Reviving Constitutional amendment: Smith/Condorcet vote tallying** - Next by thread:
**Why the default option is special** - Index(es):