[EM] calculating the N matrix in Schulze STV

[Kristofer Munsterhjelm]

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.