[EM] Ranked Phragmen (QPQ) satisfies proportional completion

[Ross Hyman]

The formatting is so messed up.  I don't know why.  I'm sending as plain text.  Hope that helps.

Proof that the ranked Phragmen method (QPQ) satisfies proportional completion.  

The Phragmen Method

The Phragmen method is, in my opinion, a beautifully elegant way to elect multiple winners proportionally from Approval ballots.  It was introduced to this list by Olli Salmi in 2002.  

http://groups.yahoo.com/group/election-methods-list/message/10068I think it would be the simplest and most elegant way to modify the nomination procedure for the Hugo.

Salmi generalized Phragmen to ranked ballots and the method was developed further by Douglas Woodall in Voting Matters, where he christened it QPQ.  http://www.votingmatters.org.uk/ISSUE17/I17P1.PDF
The method is, in my opinion, a very beautiful and elegant STV-like method.  I have also written about it in Voting Matters.  http://www.votingmatters.org.uk/ISSUE28/I28P2.pdf

Proportional Completion

Proportional completion is a way to complete ballots that do not rank every candidate.  It was developed by Markus Schulze and used in his multiple winner proportional representation version of his beat path voting method, Schulze STV.  http://m-schulze.9mail.de/schulze2.pdf

Proportional completion completes incompletely ranked ballots so as to preserve the version of the Condorcet matrix that uses matrix elements of the form VA>B/(VA>B + VB>A), that is it preserves the proportion of voters amongst those who have expressed an opinion.  Proportional completion is achieved by dividing up incomplete ballots proportionally.  For example, if for all ballots that do have a ranking between A and B, 60% rank A>B and 40% rank B>A then each incomplete ballot that does not provide a ranking between A and B is divided up so that 60% of it ranks A>B and 40% ranks B>A.  

I define the Proportional Completion voting methods criterion to be satisfied when a voting method produces the same result if incomplete ballots are proportionally completed or not.

Terminology:
V_A is the total number of ballots that contribute to electing A.  Ballots are included in
which Candidate A is the highest ranked hopeful (not elected and not excluded)candidate.


S_A is the sum of the loads of all of the ballots that contribute to electing A. 

V_act is the total number of active ballots.  These are the ballots that rank at least one hopeful candidate. 

V_inact is the total number of inactive ballots.  These are the ballots that do not rank any hopeful candidates.  They only rank elected and excluded candidates. 

S_inact is the sum of the loads of all of the inactive ballots.

V_tot is the total number of ballots.  V_tot = V_act + V_inact.  Unlike all of the other variables listed above, it does not change throughout the procedure.
Proof that the ranked Phragmen method (QPQ)satisfies proportional completion.  
Without proportional completion, the load to elect candidate A is 
s_A= (S_A +1)/V_A
This is also the load that will now be on each ballot that contributed to electing A.  

With proportional completion, the same formula applies but V_A and S_A are modified to:
V^pc_A  = V_A + V_inact *( V_A/V_act)
and 
S^pc_A = S_A + S_inact*(V_A/V_act).

The proportionally completed load to elect A is therefore 
s^pc_a = (S_A + S_inact * (V_A/V_act)  +1) / ( V_A + V_inact*(V_A/V_act))
= (V_act/V_tot) * s_A + S_inact/V_tot


The load with proportional completion is just a scale and a shift of the load without completion.  It is the same scale and shift for each candidate.  A scale and shift does not change the relative order of the loads so the same candidates would be elected in the same order. The same scale and shift applies to the load to determine if
a candidate should be excluded.  So the ranked Phragmen (QPQ) satisfies proportional completion.- Ross Hyman