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. ---- Election-Methods mailing list - see http://electorama.com/em for list info
