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 k (get a copy). 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
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
(In its typical minimalist manner, k’s prompt is an empty space.)
However, we also need to add (+) the shift of 1/2, which is the key
characteristic of Sainte-Laguë:
.5+!s
0.5 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 10.5 11.5 12.5 13.5 14.5
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
20800 6800 12400f
v % 1.5
6933.333 2266.667 4133.333
(v%)'.5+!s
20800 6800 12400
6933.333 2266.667 4133.333
4160 1360 2480
2971.429 971.4286 1771.429
2311.111 755.5556 1377.778
1890.909 618.1818 1127.273
1600 523.0769 953.8462
1386.667 453.3333 826.6667
1223.529 400 729.4118
...
This is the table already! Let’s store (:) it as r:
r:(v%)'.5+!s
We’ll then flatten the table into a list, by applying the concat
operator (,) over the table (/):
,/r
20800 6800 12400 6933.333 2266.667 4133.333 4160 1360 2480 2971.429 ...
Now we can sort this list, using the new ^ operator:
^,/r
234.4828 251.8519 272 295.6522 323.8095 357.8947 400 427.5862 453.3333 ...
But we actually want the biggest numbers, so let’s reverse this:
|^,/r
20800 12400 6933.333 6800 4160 4133.333 2971.429 2480 2311.111 2266.667 ...
Now we can take as many as we have seats:
s#|^,/r
20800 12400 6933.333 6800 4160 4133.333 2971.429 2480 2311.111 2266.667 1890.909 1771.429 1600 1386.667 1377.778
Great. Now, we have to find (?) these in the original table:
((s#|^,/r)?)'r
0 3 1
2 9 5
4 15 7
6 15 11
8 15 14
10 15 15
12 15 15
13 15 15
15 15 15
...
Find returns the index of the left side in the right side,
or an index out of bounds if it can’t find the element.
If we check this table for s, we can detect these elements:
s=((s#|^,/r)?)'r
000
000
010
010
010
011
011
011
111
...
But we actually want the negation (~) of this table:
~s=((s#|^,/r)?)'r
111
111
101
101
101
100
100
100
000
...
Now, we just have to sum (+) up (/) the columns again:
+/~s=((s#|^,/r)?)'r
8 2 5
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=((s#|^,/r)?)'r:(v%)'.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
+/~s=((s#|^,/r)?)'r:(v%)'.5+!s
7 7 7
Oops.
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:
r:(v%)'.5+!s
Instead of sorting, we now grade the flattened r up:
>,/r
0 2 3 1 6 5 9 8 12 4 15 11 18 21 14 7 24 17 27 30 10 20 33 36 23 39 13 26 42 29 16 32 35 19 38 41 22 44 25 28 31 34 37 40 43
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
0 3 1 2 9 5 4 15 7 6 20 11 8 26 14 10 30 17 12 33 21 13 36 24 16 38 27 18 39 29 19 40 31 22 41 32 23 42 34 25 43 35 28 44 37
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 new cut (^) operator that replaces the reshape operator.
As we have as many columns as votes, we get:
(#v)^<>,/r
0 3 1
2 9 5
4 15 7
6 20 11
8 26 14
10 30 17
...
But again, we are only interested in the seats less than s, so
s>(#v)^<>,/r
111
111
101
101
101
100
100
100
000
...
And we can sum up again:
+/s>(#v)^<>,/r
8 2 5
Since this solution doesn’t require r later, we can just inline it:
+/s>(#v)^<>,/(v%)'.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:
x:681
v%x
7.63583 2.496329 4.552129
To round these values, we use the idiom of adding 1/2 and taking the
integer part (a.k.a floor, _):
_.5+v%x
8 2 5
As we know, this sums up to s:
+/_.5+v%x
15
s=+/_.5+v%x
1b
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<+/_.5+v%x}(1+)/:1
681
Then, we can divide again for this divisor, and get the same result as with the previous method.
_.5+v%{s<+/_.5+v%x}(1+)/:1
8 2 5
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>(#v)^<>,/(v%)'.5+!s
20 23 2 3 18 3 3 3 1 1 0 0 1 0 1 1 0
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
20 23 2 3 18 3 3 3 1 1 0 0 1 0 1 1 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>(#v)^<>,/(v%)'1+!s
21 25 2 3 19 3 3 2 0 0 0 0 0 0 1 1 0
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