[EM] calculating the N matrix in Schulze STV
Kristofer Munsterhjelm
km_elmet at lavabit.com
Sat Jun 29 02:20:04 PDT 2013
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 rank prefer these of {A,B,C} to D
60 A>B>C>D>E A B C
45 A>C>E>B>D A B C
30 A>D>B>E>C A
15 A>E>D>C>B A
12 B>A>E>D>C A B
48 B>C>D>E>A B C
39 B>D>A>C>E B
21 B>E>C>A>D A B C
27 C>A>D>B>E A C
9 C>B>A>E>D A B C
51 C>D>E>A>B A C
33 C>E>B>D>A B C
42 D>A>C>E>B <none>
18 D>B>E>C>A <none>
6 D>C>B>A>E <none>
54 D>E>A>B>C <none>
57 E>A>B>C>D A B C
36 E>B>D>A>C B
24 E>C>A>D>B A C
3 E>D>C>B>A <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 45 0 0 45
2 45 75 0 75
3 57 75 0 12
4 79.5 75 79.5 102
5 79.5 117.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.
More information about the Election-Methods
mailing list