Warren D. Smith. Nov 2015. UNDER MODIFICATION.
Abstract. We show how some proportional representation (PR) election ideas dating to Lars Edvald Phragmen 1895, and Bjarke Dahl Ebert in October 2003 can be written as solving a mixed linear/integer program (MILP) to optimality to find the "optimal" PR parliament.
Let C=#candidates, V=#voters, W=#winners, 0<W<C<V. Let Sv,c be the real-valued score given by voter v to candidate c on her ballot. Consider the bipartite grqph with V red vertices corrsponding to the V voters and C blue vertices corresponding to the C candidates. The edge from voter v to candidate c shall be associated with a real variable xvc. There will also be one additional real variable p. There also will be an integer variable ec associated with each candidate c. Here is a mixed linear/integer program involving those variables.
Linear constraints:
Optimization: minimize p by choice of all the variables. The W election winners then are the c such that ec=1. The C-W losers are the c with ec=0.
The total number of real variables is VC+1, and of integer variables is C. The total number of 01-interval-containment linear inequality constraints is 2VC+2C. The total number of other linear inequality constraints is V. The total number of linear equality constraints is C+1.
This has formalized a score-using version of Ebert's description of a Phragmen-like system that is an optimization problem. (Phragmen's original system was not optimizing anything.) Ebert has his own PR voting system – or at least, it is hoped to be PR, I have not seen any proof that it is, only incompletely convincing heuristic arguments – which cannot be formalized in this manner because it would require a nonlinear objective function. There are many possible nonlinear objective functions. To explain them, replace the single variable p with V variables pv, replace the first constraint by
and replace the optimization goal by "minimize ∑1≤v≤VF(pv)" where F is some nonlinear function – for example Ebert suggested F(x)=x² for no particularly convincing reason. If we use F(x)=xμ in the limit μ→∞ then we get a more-unique version of the "Phragmen" method I began with. By "more unique" I mean that the method I described could produce ties and this limit-method presumably would experience ties less often.
I'd guess this program can usually be solved to optimality in a number of steps of order 2C+(V+C)3. This is not a theorem, but merely a heuristic runtime estimate, and not a very convincing one; and perhaps the first + sign should be changed to "multiply" which would make a rather large difference.
In this 4-candidate 20-voter 2-winner election
10 voters: A=1 B=1 C=1 D=0 10 voters: A=1 B=1 C=0 D=1
both Ebert's L2-norm proposal, and the MILP at top, both would give pv=1/10 to every voter if the winner-set was AB, but also if the winner set were CD. I.e. both AB and CD are regarded by these voting systems as "equally good" winner-duos. That is foolish since obviously AB is superior.
This same simple election example embarrasses Monroe's election method for the same reason.