[EM] Minmax approval party list

[Kristofer Munsterhjelm]

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?