[EM] Proportional Representation from Ratings Ballots

[Raph Frank]

Stealing the Meek's method proof :).

This is the existance proof:

A weighting vector is defined as "feasible" if all elected candidates
have a score >= the quota (Q)

A candidate receives from each ballot (B) a score (S) equal to
 S(B) = r(c)*w(c)/(sum_over_x(r(x)*w(x))

r(x) is the rating for the candidate on that ballot
w(x) is the global weighting of that candidate

The candidate's total T(c) is the sum of the vote received from each ballot

Theorom: Replacing an elected candidate's weight by w(c)*k will not
convert a feasible vector into an non-feasible one, if k>=Q/T(c)

Proof:  The candidate will receive from each ballot

 S_new(B) = r(c)*w_new(c)/(sum_over_x(r(x)*w_new(x))

Only 1 term has changed in the sum

Since w_old(x) >= w_new(c) and r(c) >= 0, then the sum cannot increase, i.e.

sum_over_x(r(x)*w_new(x)) <= sum_over_x(r(x)*w_old(x))

Thus,

S_new(B) >= r(c)*w_new(c)/(sum_over_x(r(x)*w_old(x))

replacing w_new(c) with w_old(c)*k as required, gives

S_new(B) >= r(c)*w_old(c)*k/(sum_over_x(r(x)*w_old(x))

Re-arranging:

S_new(B) >= k*[r(c)*w_old(c)/(sum_over_x(r(x)*w_old(x))

S_new(B) >= k*S_old(B)

Thus, the candidate will receive form each ballot a score that is at
least k times as large as before the change.

Thus,

T_new(c) >= T_old(c)*k

Assuming, k>=Q/T_old(c)

T_new(c) >= T_old(c)*[Q/T_old(c)]

T_new(c) >= Q

Thus, the candidate in question who had his weighting decreased will
still have at least a quota.  All other candidates will at worst have
their vote totals
remain static, and will likely increase.  (The same proof, except
their weight doesn't actually decrease).

This means that if the vector was feasible initially, then it will
still be feasible after updating the weight of candidate c.

This means that the process can be applied over and over.  In each
step, the weighting of one of the elected candidates will be
decreased, but never increase.  This means that the total vote held by
the elected candidates will decrease.

This also gives an algorithm.  You can apply that rule to each elected
candidate in turn.

In fact, you can update them all in 1 go (set a weights w(c) = Q/T(c)
for elected candidates).  If you update them in order, then all the
other candidate's who haven't being reduced yet will have totals that
will have increased slightly (or stayed the same).  Thus, k = Q/T(c)
for all the other candidates will drop (or stay the same).

If you use the k from before the update, it will still be greater or
equal to the k that would have been used if they were done in order,
which is all that is required.