[EM] Multiwinner Method Yardstick (Gregory Nisbet)

[Kristofer Munsterhjelm]

Greg Nisbet wrote:
> Proportional Approval Voting
> http://www.nationmaster.com/encyclopedia/Proportional-approval-voting
> Brief summary of this method:
> there are O(c!) (candidates factorial) many "pseudocandidates" 
> consisting of all the possible combinations of candidates.
> Let's say we have a voter named Alice and a three person pseudocandidate 
> composed of real candidates X,Y, and Z.
> If Alice approves of one of them, the score for XYZ += 1
> "                            two         " ,                           
> += (1 + 1/2)
> "                            three/all  " 
> ,                            += (1 + 1/2 + 1/3)
>  
> This way Alice approving of X and Bob approving of X is worth 2 pts 
> whereas Alice approving of X and Y and Bob approving of neither is only 
> worth 1.5 pts. The procedure isn't iterative hence the failure of RRV
> http://rangevoting.org/RRV.html
> to satisfy the multimember equivalent of the participation criterion is 
> sidestepped. In other words, voting for a candidate cannot hurt you 
> because PAV does not use an elect-candidate-then-punish-supporters 
> iteration to achieve its result.
>  
> However great PAV may be its O(c!cv) (candidates factorial * candidates 
> * voters) time complexity is enough to make me think twice before 
> seriously considering it.

Perhaps one could use branch-and-bound methods to wrangle this down to 
something more managable (with high probability or in the case of 
"realistic" ballots). One option, if that's impossible, is to reduce the 
ballots to a tree (to thwart fingerprint attacks), make the tree public, 
and then have anybody who wants to submit their proposed council. The 
council with the best score then wins. If there's a PTAS for this 
problem, that might serve as a default.

One could also have a Sainte-Laguë variant of this. In it, the score for 
"got one candidate" would be 1, "got two candidates" 1 + 1/3, "got three 
candidates" 1 + 1/3 + 1/5, and so on.

> Multiwinner Method Yardstick
>  
> PAV is the basis of the multiwinner analogue of Bayesian regret. Think 
> of it this way.
> PAV gives us a nice formula for dealing with range values.
> Let's use the previous example of Alice and XYZ
> Let's pretend Alice votes X = 99, Y = 12, Z = 35
>  
> with PAV, the formula is (1+1/2+1/3...1/n) for the nth thing
> think of it as sorting the list for that candidate and THEN applying 
> (1,1/2,1/3..1/n) to it.
> in the previous example if Alice approved X and Z (1,0,1)
> we sort the list
> (1,1,0)
> then multiply by the coefficients
> (1*1,1*1/2,0*1/3)
> and add
> 1.5
>  
> apply the same thing to the current example
>  
> 99,12,35 ==> 99,35,12
>  
> and multiply...
>  
> 99*1,35*1/2,12*1/3
>  
> and add...
>  
> 120.5
>  
> there, the score for XYZ from Alice is 120.5
>  
> Thus the procedure for evaluating various multiwinner methods is simple:
>  
> create some fake voters (make their preferences between 0 and n, 
> distributed however you like) 
> I'd recommend NOT using negative numbers because I have no idea how they 
> will interact with the sorting and tabulating procedure.

This works *if* PAV is the ultimate solution. That is, if what PAV 
produces is the best of the best, then your scores will give you an idea 
of how good a multiwinner method is, because you can calculate the PAV 
score given any proposed council.

But is that the case? It doesn't seem to readily follow. One may ask, 
even if we have a single universal standard independent of external 
information (as candidates' opinions), is PAV the best possible 
standard? Why not, for instance, Sainte-Laguë PAV? Or, for that matter, 
Warren's Logarithmic Penalty Voting defined in his paper #91? As long as 
it's true that approving an additional candidate can only improve your 
satisfication, they should all pass your multiwinner equivalent of 
participation.

> I'm in the process of programming something to actually test this. If 
> anyone has a program for STV, CPO-STV, or some other multiwinner 
> something or rather, I would really appreciate it.
>  
> Even if it's just a description of a method; it's better than nothing. 
> (no party-based or asset voting related methods please.)

I made a program to test multiwinner methods based on a metric one may 
call "opinion fidelity". The simulation consists of many rounds, and for 
each round there are a certain number of binary opinions, voters, and 
candidates. Each voter (a candidate is also a voter) is assigned a 
random boolean vector of length equal to the number of opinions. Then 
the simulation counts how many have true (aye) for each opinion, and 
constructs rank ballots for each voter, where the voter ranks those who 
agree with him (lower Hamming distance on the opinion vector) ahead of 
those who don't. Then it sums the ayes for each opinion on the council 
produced by a multiwinner method, and the closer these are (by RMSE, 
Webster measure, Gini .. any measure), the better the multiwinner system 
in question.

This program has multiwinner method objects which may be of interest for 
your tests. It implements STV (Meek or ordinary), D'Hondt without lists, 
QPQ, my simple multiwinner version of Bucklin, and "naive multiwinner" 
versions of some single-winner methods. Through a quick and dirty 
"shunt", it can also do Schulze STV, but that uses Schulze's 
implementation which requires superpolynomial space. There's also a 
class for PSC-CLE, but the solid coalition structure can grow very 
large, and so it's disabled by default.

If you know STL C++, it should be fairly simple to adapt the classes to 
your own program. The multiwinner classes returns a list of candidates 
elected, given council size, number of candidates, and a list of ballots.

The source is here: http://munsterhjelm.no/km/raw/quadelect.tar.gz . It 
compiles in Linux - just use "g++ multiwin.cc".

If you want descriptions, there's a paper on QPQ here: 
http://www.votingmatters.org.uk/ISSUE17/I17P1.PDF
I describe my simple STV-like multiwinner version of Bucklin in a post 
that can be found here: 
http://listas.apesol.org/pipermail/election-methods-electorama.com/2008-August/022305.html
PSC-CLE is described here: 
http://listas.apesol.org/pipermail/election-methods-electorama.com/2005-July/016419.html 
  , though the variant with rounding off instead of up does better.