[EM] Minmax approval party list

Kristofer Munsterhjelm km_elmet at t-online.de
Thu Oct 17 02:14:08 PDT 2013

While tinkering with minmax approval for assignment review purposes, I
noticed the following:

Minmax approval can be stated in an integer programming form. (Recall
that minmax approval tries to find the council so that the person who
approves the fewest of them, approves most.) Without tiebreaks, the
integer program would look like this:

-----------------------------------------------------------------------

maximize min_approval

subject to

min_approval <= cand_1_selected + cand_2_selected ; first ballot: [1, 2]
min_approval <= cand_1_selected + cand_3_selected ; second: [1, 3]

; and so on for every ballot...

; constraint to keep the council size limited
cand_1_selected + cand_2_selected + ... + cand_n_selected = council_size

{cand_1_selected, ..., cand_n_selected} binary

-----------------------------------------------------------------------

Since it's an integer program, it's potentially NP-hard, and we know
from other sources that it is indeed NP-hard. But now let's consider
what would happen if we relax the integer constraint.

What we need to do is replace the last line:

{cand_1_selected, ..., cand_n_selected} binary

with the lines:
cand_1_selected >= 0
... ; same for ever candidate up to n
cand_n_selected >= 0

and then, because everything is now invariant under scaling, we can
replace the council constraint by

cand_1_selected + ... + cand_n_selected = 1

What would we get? Instead of a candidate assignment, we would get
positive real numbers for each "cand selected". Since we're now dealing
with a pure linear program rather than an integer program, it can be
solved in polytime (by interior point methods) or in "usually works good
enough, usually very quick" (simplex).

And here's the key observation. It seems we could use the real number
weights as party list proportions.

Suppose that instead of cand_1_selected ... cand_n_selected, we have
party_1_selected ... party_n_selected. We want to create a consensus
version of party list. Then we just run the linear program above, get
fractional party weights, and then put those into Sainte-Lague to
determine the council allocation. The potential "hijacked by extremists"
problem could be solved by instating a threshold, although that moves
the system somewhat away from the consensus idea.

I wonder what that kind of council would look like, but I don't have any
public Approval data to test it with.

I also have a hunch that this would resist party splitting. Say party 1
becomes parties 1 and 2, and everybody who approved of 1 now approves of
2. Then by dividing the weight that used to be on party 1 to parties 1
and 2, the outcome will be the same: either the constraint is placed
there by someone who votes only for 1 and 2 (in which case things don't
change), or it is not (in which case 1 was never a limiting factor in
the first place). But I'm not completely sure of that.

It could be used for other purposes as well. Say you have a show (of
some sort) and want to appeal to everybody. You have their approval
ballots as to what they'd like to see. Then the weights you get could
tell you how much time you should spend on each event.

-

So, minmax approval could be turned into a form of party list. But
minmax approval by itself is too consensus-like, I think, for general
public assemblies. If you have a vote pattern of the form:

51%: A1, A2
48%: B1, B2
1%: C1, C2

minmax Approval would pick {A1 A2 B1 B2 C1 C2} for the six-seat
instance. So it would be better to use PAV rather than minmax approval.
If we could phrase PAV as an integer program, then it might be possible
to relax it to a linear program and get party list out of it. But I
can't really see how to do it.

Any ideas?