[EM] calculating the N matrix in Schulze STV
Hi
I'm trying to implement the Schulze STV method and are currently working
through the paper schulze2.pdf.
On page 38 there is an example (section 6.3) where this result was arrived
at:
N[{a,b,c},d] = 169;
and Ñ[{a,b,c}, {a,b,d}] = 169;
And i can't seem to figure out how to arrive at the number 169.
It's not a sum of any of the voting groups (as those are all divisible by
three, and 169 is not), and since all voters cast linear order preferences
of candidates the weight p of the votes should all be 1 (as far as i
understood it).
Could someone here maybe help me by explaining what step I'm not
understanding correctly, I'm guessing it has something to do with
Proportional Completion but I'm not really seeing that.
best regards
Alexander Kjäll
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] calculating the N matrix in Schulze STV
On 06/29/2013 09:38 AM, Alexander Kjäll wrote:
Hi
I'm trying to implement the Schulze STV method and are currently working
through the paper schulze2.pdf.
On page 38 there is an example (section 6.3) where this result was
arrived at:
N[{a,b,c},d] = 169;
and Ñ[{a,b,c}, {a,b,d}] = 169;
And i can't seem to figure out how to arrive at the number 169.
It's not a sum of any of the voting groups (as those are all divisible
by three, and 169 is not), and since all voters cast linear order
preferences of candidates the weight p of the votes should all be 1 (as
far as i understood it).
Could someone here maybe help me by explaining what step I'm not
understanding correctly, I'm guessing it has something to do with
Proportional Completion but I'm not really seeing that.
It hasn't to do with proportional completion. Instead, let's define the
process for calculating N[{x,y,z}, w] as follows:
Let each candidate in the set (here {x, y, z}) have an assigned vote
count.
If a given set of ballots ranks a subset of {x, y, z} before w, it can
contribute to the vote count of that subset, in any proportion. Say the
given ballot set is 100: x y z w. Then it can contribute any
combination of positive reals to the vote count of x, y, and z, as long
as the sum of the combination is 100.
The ballots' values are distributed to the vote counts so that the vote
count with the minimal value is the highest. The value of this (minimal)
count is then the value of N[{x,y,z},w].
And to give an example of this, consider the example on page 38, where
we're trying to determine N[{a,b,c},d]. After processing, we find out that:
value rankprefer these of {A,B,C} to D
60 ABCDE A B C
45 ACEBD A B C
30 ADBEC A
15 AEDCB A
12 BAEDC A B
48 BCDEA B C
39 BDACE B
21 BECAD A B C
27 CADBE A C
9 CBAED A B C
51 CDEAB A C
33 CEBDA B C
42 DACEB none
18 DBECA none
6 DCBAE none
54 DEABC none
57 EABCD A B C
36 EBDAC B
24 ECADB A C
3 EDCBA none
or
value can be distributed among
60 A B C
45 A B C
30 A
15 A
12 A B
48 B C
39 B
21 A B C
27 A C
9 A B C
51 A C
33 B C
57 A B C
36 B
24 A C
So now to distribute. There's probably an algorithm that ensures that
the minimal value is maximal, but I don't know it. I know it's possible
to do with linear programming, but that's probably overkill. For this
particular example, it suffices to first add in all one-candidate
combinations, then all two-candidate combinations in such a way as to
maximize the minimum at each step, then all three-candidate combinations
in a similar manner. That gives a reordered list of
30 A
15 A
39 B
36 B
12 A B
24 A C
27 A C
51 A C
33 B C
48 B C
9 A B C
60 A B C
45 A B C
21 A B C
57 A B C
or
45 A
75 B
12 A B
102 A C
81 B C
192 A B C
and adding them in, we get
after step allocation to sum of values added
A B C this step
--- - --
1 450 0 45
2 45 75 0 75
3 57 75 0 12
4 79.5 75 79.5 102
5 79.5117.75 117.75 81
6 169 169 169 192,
giving us a maximum minimal value of 169, which was what was wanted.
I am not at all sure that algorithm will work in the general case,
though, so I suggest you look at Schulze's source code to find out how
it is done there. But this example should show how you get at
N[{x,y,z},w]: by distributing votes between the candidates ranked before
the comparison candidate on each ballot so that the candidate that
ends up with least votes has the most.
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] calculating the N matrix in Schulze STV
Hallo,
N[{a,b,c},d] = 169 or Ñ[{a,b,c}, {a,b,d}] = 169 means
that W=169 is the largest value such that the electorate
can be divided into 4 disjoint parts T1,T2,T3,T4 such that
(1) Every voter in T1 prefers candidate a to candidate d;
and T1 consists of at least W voters.
(2) Every voter in T2 prefers candidate b to candidate d;
and T2 consists of at least W voters.
(3) Every voter in T3 prefers candidate c to candidate d;
and T3 consists of at least W voters.
Here is the example of page 38:
Group 1: 60 voters a b c d e
Group 2: 45 voters a c e b d
Group 3: 30 voters a d b e c
Group 4: 15 voters a e d c b
Group 5: 12 voters b a e d c
Group 6: 48 voters b c d e a
Group 7: 39 voters b d a c e
Group 8: 21 voters b e c a d
Group 9: 27 voters c a d b e
Group 10: 9 voters c b a e d
Group 11: 51 voters c d e a b
Group 12: 33 voters c e b d a
Group 13: 42 voters d a c e b
Group 14: 18 voters d b e c a
Group 15: 6 voters d c b a e
Group 16: 54 voters d e a b c
Group 17: 57 voters e a b c d
Group 18: 36 voters e b d a c
Group 19: 24 voters e c a d b
Group 20: 3 voters e d c b a
T1, T2, and T3 can be chosen as follows:
T1
Group 1: 60 voters a b c d e
Group 2: 1 voter a c e b d (one of the 45 voters of group 2)
Group 3: 30 voters a d b e c
Group 4: 15 voters a e d c b
Group 5: 12 voters b a e d c
Group 9: 27 voters c a d b e
Group 19: 24 voters e c a d b
T2
Group 2: 44 voters a c e b d (44 of the 45 voters of group 2)
Group 7: 39 voters b d a c e
Group 8: 17 voters b e c a d (17 of the 21 voters of group 8)
Group 12: 33 voters c e b d a
Group 18: 36 voters e b d a c
T3
Group 6: 48 voters b c d e a
Group 8: 4 voters b e c a d (4 of the 21 voters of group 8)
Group 10: 9 voters c b a e d
Group 11: 51 voters c d e a b
Group 17: 57 voters e a b c d
Markus Schulze
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] calculating the N matrix in Schulze STV
On 06/29/2013 11:32 AM, Markus Schulze wrote:
Hallo,
N[{a,b,c},d] = 169 or Ñ[{a,b,c}, {a,b,d}] = 169 means
that W=169 is the largest value such that the electorate
can be divided into 4 disjoint parts T1,T2,T3,T4 such that
(1) Every voter in T1 prefers candidate a to candidate d;
and T1 consists of at least W voters.
(2) Every voter in T2 prefers candidate b to candidate d;
and T2 consists of at least W voters.
(3) Every voter in T3 prefers candidate c to candidate d;
and T3 consists of at least W voters.
What algorithm do you use to distribute the voters in this manner? The
same voter may increase any of the subset of candidates he prefers to d,
so it doesn't seem straightforward to determine which candidate's group
a given voter should be placed into.
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] calculating the N matrix in Schulze STV
Hallo, the precise algorithm is described in the file calcul02.pdf of this zip file: http://m-schulze.webhop.net/schulze3.zip Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
[EM] A candidate winning multiple seats.
Vidar Wahlberg, One very simple rule that transcends the dichotomy between a party-list and a candidate-based PR election rule is 3-seat LR Hare. Each party has one candidate and each voter one vote. Typically the top 3 vote-getters would get one seat each, but if the top vote-getter beats the 3rd place candidate by more than one-third of the total vote then (s)he'd win two seats and get to pick a vice-candidate(who could've been pre-selected and already announced prior to the election). And, theoretically, if the first place candidate beat the second place candidate by more than 2/3rds of the total vote then (s)he'd win three seats and get to pick two vice-candidates. So if the vote totals were: 40, 30, 20, 10 then the top three would win one seat each, But if the vote totals were: 50, 35, 10, 5 then the top candidate would win two seats and get to pick a vice-candidate. And if the vote totals were 80-10-7-3 then the top candidate would win three seats. This uses the Hare quota and so it's best to couple it with the use of at least one at-large single-winner seat to help with the formation of a working gov't. It tends to increase equality by virtue of how a third party candidate can win a seat with as little as 10% of the vote if the top candidate gets less than 43.3% of the vote and no other third party candidate does better. This makes the third seat very likely to be competitive. The top two candidates have more secure elections, but if their parties are competing in the single-winner seats then they'd need to help their party's candidates in that other election. There is scope for the creative combination of 3-seat LR Hare with rules that tend to reinforce hierarchy so that 3-seat LR Hare can: 1) elevate interest in local elections with its high probability of a competitive seat, 2) handicap rivalry between larger parties, 3) make larger parties more attentive to minority rights/views and 4) Allow for more direct constituent-legislator relationships than with larger party-list proportional representation. It also might retain the tendency of party-list PR to elect a higher percentage of women legislators than with a ranked-choice form of PR. My theory is that this is because two of the three seats will tend to be safe. This goes off of a theory of mine that since women tend to have a larger deep limbic systemhttps://www.google.com/webhp?sourceid=chrome-instantion=1ie=UTF-8#sclient=psy-abq=%22deep+limbic+system%22oq=%22deep+limbic+system%22gs_l=serp.3..0l4.39236.41736.2.42084.2.2.0.0.0.0.209.329.0j1j1.2.0.epsugrpqhmsignedin%2Chtma%3D120%2Chtmb%3D120..0.0.0..1.1.17.psy-ab.W35os1Z9Fvcpbx=1bav=on.2,or.r_cp.r_qf.fp=e16824eab702e431ion=1biw=1366bih=659 portions of their brain, they are better at the connecting/relating that is critical for good leadership. Unfortunately, having a bigger deep limbic system also creates a larger vulnerability to its becoming over-active or perturbed, which can affect the quality of decision-making in important moments like during elections. When (all of the) election seats are competitive, there is more scope for competitors machiavellianly to try and take advantage of this tendency during the election, which tragically would then discriminate in favor of male leaders who are less good at connecting in their leadership after the election. But when there's both competitive and not-so-competitive seats then there's a variety of conditions that would help elect a better balance of male and female leaders. dlw Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Preferential voting system where a candidate may win multiple seats
On 06/29/2013 01:27 AM, Vidar Wahlberg wrote: On Fri, Jun 28, 2013 at 03:04:13PM +0200, Vidar Wahlberg wrote: This gave me an idea. We seem to agree that it's notably the exclusion part that may end up excluding a party that is preferred by many, but just isn't their first preference. I'm sticking to quota election because I don't fully grasp how to apply other methods (Sainte-Laguë, for instance) to determine when to start excluding parties. 1. Give seats to parties exceeding the quota (seats = votes / quota) 2. Create an ordered list using Ranked Pairs/Beatpath, exclude the least preferred party and redistribute its votes. Repeat. Chris, Kristofer. Spending the rest of the day on this, I think I finally understood what you meant with best formula for apportioning seats in List PR. Or at least I eventually came up with a very simple method, even though it does not meet my concerns about excluding a second preference party that is far more popular than a party that have some more first preference voters. For larger parties who are very likely to get a seat there's neither any reason to create an ordered list, as those parties who do receive one or more seats will never have any votes transfered. Basically, this is what I do: 1. Distribute seats using Sainte-Laguë. 2. If any parties received no seats, exclude the party with least votes and redistribute votes to 2nd preference. 3. Repeat 1-2 until all non-excluded parties got at least 1 seat. Although as noted a party that is a popular as second preference (but less popular as first preference) will easily be excluded, even though more voters would prefer this party over another party. I think that when the number of seats is large enough, you could combine the two methods. That is, by combining them, you handle the problem arising from voters not having an influence, but the problem arising from the method not becoming Condorcet-like when there are few seats remains. The combined method would go like this: 1. Run the ballots through RP (or Schulze, etc). Reverse the outcome ordering (or the ballots; these systems are reversal symmetric so it doesn't matter). Call the result the elimination order. 2. Distribute seats using Sainte-Laguë. 3. Call parties that receive no seats unrepresented. If there are unrepresented parties, remove the unrepresented party that is listed first in the elimination order. 4. Go to 2 until no party is unrepresented. This should help preserve parties that are popular as second preferences but not as first preferences, because the elimination order will remove parties that hide the second preferences before it removes the party that is being hidden, thus letting the second-preference party grow in support before it is at risk of being eliminated. Note that this doesn't solve the small-council problem. If we have: 46: L C R 44: R C L 10: C R L 1 seat, then the first seat goes to L just like in Plurality. The elimination order never enters the picture. For a similar reason, it is not perfect: if the second preference party has widespread support but is hidden behind many parties that get one seat each, then the council will fill up with the smaller parties and the second preference party never gets a shot. But in a sense, that is proportional: every voter is represented. The question is how much second preferences should override first preferences. I think that an answer to that, and implementation thereof, would also fix the L-C-R problem, because they're two aspects of the same thing. (And good luck explaining the purpose of the elimination order, and why it should be determined by Condorcet, to the average voter!) Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] MAV on electowiki
At 10:19 AM 6/28/2013, Chris Benham wrote: Jameson, ...But I don't think it's realistic... I don't think any of the multiple majorities scenarios are very realistic. Irrespective of how they are resolved, all voters who regard one or more of the viable candidates as unacceptable will have a strong incentive to top-rate all the candidates they regard as acceptable, out of fear that an unacceptable candidate gets a majority before their vote can help all the acceptable ones. This is probably the opposite of what would happen. The pressure is *heavily* toward majority failure, not multiple majorities. Essentially, the comment assumes that a voter will think that another candidate will get a majority in the first round before one of those acceptable to them. This would indicate that those acceptable are not frontrunners. While we have proposed to *allow* voters to vote for more than one in the first round, that is mostly to avoid tossing ballots for overvoting and to cover the rare situation that a voter actuallyh does not know which of two candidates they prefer. Given Bucklin amalgamation, it is *extremely unlikely* that voters with a significant preference between A and B will vote for both in the first round. The pressure to sincerely distinguish a favorite is high. That largely vanishes after the first round completes without a majority. Remember, it's rare that there are three viable candidates. So, here, the voter only approves of one of them. Not two. If there is a multiple majority in the first round, it's unlikely to be outside of this set. What is being said is that the voter strongly disapproves of one viable candidate, so strongly that the voter wants to nail down, absolutely do the utmost to prevent the election of this one, so the voter approves of the other two, in the first round. I'd be amazed if 0.1% of voters actually voted that way, in a real election, outside of this rare situation: the voter only knows the strong dislike for one candidate, and is ignorant of all others, so votes antiplurality. In that case, it would be a fair representation of the voter's preferences. The problem is? I still say that your suggestion only increases that incentive (even though maybe more psychologically than likely to cause extra actual post-election regret). We cannot prevent voters from making up irrational reasons to do this or that. Forget about using the mechanism for resolving the (probably very rare) multiple-majorities scenario to try to gain some whiff of later-no-harm. I came to the conclusion that the problem with MAV is that it loses the Range winner, so it damages SU, and that could reasonably commonly occur. Multiple majorities *did* occur in real Bucklin elections, though only in second or third rank. I don't recall all the specifics. Voting for more than one was locked out in original Bucklin. If the problem described *did* occur, that would be a reason for demoting first rank votes that were overvoted, they would get pushed, for Bucklin amalgamation, into second rank. (Which would be much better than considering them spoiled. Or even to third rank, if it were decided to make the top two ranks vote-for-one. But I don't like this. I'd tolerate the first rank limitation, but would still leave a meaning for overvoted first rank, for ballot position assignment, it would be split, i.e., a half-vote each if it was two.) BTW, the Majority Choice Approval Bucklin-like method using ratings (or grading) ballots, simply elected the candidate whose majority tally was the biggest. I also prefer that to your suggestion. It and yours are simpler to count than the Mike Ossipoff idea I support. That is basically Bucklin-ER. It has the virtue of simplicity. Ranked Approval voting, preponderance of the votes at the majority-found rank, or as a plurality result if all ranks have been collapsed. EMAV is the same except that the ranks are interpreted as ratings and the multiple-majority or plurality standard is based on a range sum. That automatically deprecates lower-ranked votes, without eliminating them. Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Preferential voting system where a candidate may win multiple seats
Kristofer Munsterhjelm wrote (29 June 2013): The combined method would go like this: 1. Run the ballots through RP (or Schulze, etc). Reverse the outcome ordering (or the ballots; these systems are reversal symmetric so it doesn't matter). Call the result the elimination order. 2. Distribute seats using Sainte-Laguë. 3. Call parties that receive no seats unrepresented. If there are unrepresented parties, remove the unrepresented party that is listed first in the elimination order. 4. Go to 2 until no party is unrepresented. This should help preserve parties that are popular as second preferences but not as first preferences, because the elimination order will remove parties that hide the second preferences before it removes the party that is being hidden, thus letting the second-preference party grow in support before it is at risk of being eliminated. Note that this doesn't solve the small-council problem. If we have: 46: L C R 44: R C L 10: C R L 1 seat, then the first seat goes to L just like in Plurality. The elimination order never enters the picture. Kristopher, I don't see this. Your elimination order is obviously L, R,C. R and C are unrepresented so we eliminate R. Then we have 46: L 54: C Then we redistribute the seat to C and then eliminate L and confirm the final redistribution. But I'm not on board with the spirit of this method, because it seems to give a say to voters who are efficiently represented a say in which party/candidate will represent other voters. Chris Benham Election-Methods mailing list - see http://electorama.com/em for list info
