Determining an election in k

This is a port of a blog post I made in March 2020 to ngn/k.

⁂

Last Sunday, we had local elections in Bavaria, and somehow I got nerd-sniped into looking at the proportional representation method that is being used now as of 2020, which is the Sainte-Laguë method.

As this algorithm turned out to be non-trivial yet pretty easy, I decided to implement it in ngn/k. The array-oriented style of k fits the algorithm quite well.

There are two styles of algorithm that compute this method, and I think the German Wikipedia page explains them best. If you can't read German you maybe still can look at the tables.

⁂

First, I'll explain the highest averages method (Höchstzahlverfahren): you write down the result of dividing the amount of votes for each party by 0.5, 1.5, 2.5, 3.5, 4.5 etc. From these quotients, you take the biggest numbers (depending on how many seats you need) and assign them to the corresponding party; each assignment is a seat.

So, let's do this in k. We set v to be the votes, and s to be the seats:

v: 10400 3400 6200

s: 15

First, we need the list of divisors. It does not make sense to make it longer than the amount of seats, so let's count up (!) to that:

 !s

However, we also need to add (+) the shift of 1/2, which is the key characteristic of Sainte-Laguë:

0.5+!s

As you can see, k evaluates the program from right to left.

Doing the division (%) is easy with k, but we need to use the each (') operator so say we want the whole list of votes to be divided by each divisor:

v % 0.5

v % 1.5

(v%)'0.5+!s

This is the table already! Let's store (:) it as r:

r:(v%)'0.5+!s

We'll then flatten the table into a list, by applying the concat operator (,) over the table (/):

,/r

Now we can sort this list, using a common k idiom: x@<x

x@<x:,/r

But we actually want the biggest numbers, so let's reverse this:

x@>x:,/r

Now we can take (#) as many as we have seats:

s#x@<x:,/r

Great. Now, we have to find (?) these in the original table:

((s#x@>x:,/r)?)'r

Find returns the index of the left side in the right side, or 0N if it can't find the element. Null (^) finds all the 0N elements:

^((s#x@>x:,/r)?)'r

But we actually want the negation (~) of this table:

~^((s#x@>x:,/r)?)'r

Now, we just have to sum (+) up (/) the columns again:

+/~^((s#x@>x:,/r)?)'r

This is the seat assignment per party now!

In good k manner, we fuse this program into a single line (assignment has the value that is being assigned):

+/~^((s#x@>x:,/r)?)'r:(v%)'0.5+!s

⁂

One issue with this implementation is that it doesn't work correctly when multiple parties get the same votes, for example:

v:7 7 7

s:20

+/~0>((s#x@>x:,/r)?)'r:(v%)'0.5+!s

Oops, we allocated 21 of 20 seats.

We can fix the solution, and actually even make it shorter (but a bit harder to explain), by using the grade-up operator (>).

Let's go back to our table r:

v: 10400 3400 6200

s: 15

r:(v%)'0.5+!s

Instead of sorting, we now grade the flattened r up:

>,/r

What does this mean? It says the biggest number is the 0th element, the second biggest number is the 2nd element, the third biggest number is the 3rd element, and so on.

This is not directly useful, but a well-known trick is to grade-down (<) this list now:

<>,/r

And this is actually the rank of each seat! (I recommend spending a few minutes to figure this out on your own.)

But now the column structure is lost. We can recreate it with the reshape operator (#). As we have as many columns as votes, we can use 0N as the second axis to compute the amount of rows automatically:

(0N,#v)#<>,/r

But again, we are only interested in the seats less than s, so

s>(0N,#v)#<>,/r

And we can sum up again:

+/s>(0N,#v)#<>,/r

Since this solution doesn't require r later, we can just inline it:

+/s>(0N,#v)#<>,/(v%)'0.5+!s

⁂

The other algorithm is the divisor method (Divisorverfahren), which says you find a number (it doesn't say how, so not really an algorithm...) such that the rounded sum of the votes divided by this divisor equals to the number of seats.

Given a divisor x, we can divide (%) the votes:

v: 10400 3400 6200

s: 15

x: 1361.0

v%x

To round these values, we use the idiom of adding 1/2 and taking the integer part (a.k.a floor, _):

_0.5+v%x

As we know, this sums up to s:

+/_0.5+v%x

s=+/_0.5+v%x

But how do we find the x? We'll use a while loop (/) for that, because we know that we'll find a divisor by counting up, and every solution that sums up to s is the same. So the first is good enough.

{s<+/_0.5+v%x}(1+)/1.0

Then, we can divide again for this divisor, and get the same result as with the previous method.

_0.5+v%{s<+/_0.5+v%x}(1+)/1.0

However, due to the linear search for the quotient, this method is slower.

⁂

Finally, we can insert the official results and check the election:

v: 9983378 11756412 1007445 1559070 8878524 1419438 1597499 1318396 395847 273557 86275 142051 339665 247453 528617 732056 120877

s: 80

+/s>(0N,#v)#<>,/(v%)'0.5+!s

This agrees with the official seat assignment.

For funsies (and because I'm pretty bored), we can contrast the new election algorithm with the previous ones. At the 2014 election, the Hare/Niemeyer method was used. Here's the code, perhaps you can figure it out:

_q+(s-+/_q)><>q-_q:s*v%+/v+0.0

This yields the same result as Sainte-Laguë for this election. There is still a significant difference between these methods: if we compute how many more votes mut would have needed to get a seat, it's 6220 additional votes with Sainte-Laguë, but 26105 with Hare/Niemeyer!

Until 2010, the d'Hondt method was used. Here, we just have to tweak the .5+ offset:

+/s>(0N,#v)#<>,/(v%)'1+!s

Using this method would have kicked out three small parties that are in this year! To no surprise, the big conservative parties want back to this system.

NP: Trembling Bells—This Is How The World Will End