[EM] Multiwinner Method Yardstick (Gregory Nisbet)

[Greg Nisbet]

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.

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.

In fact, it isn't even necessary to calculate the BEST result in order to
compare multiwinner voting methods.

Just calculate each winner according to the multiwinner methods you are
testing, and then add the score of the winning group of candidates that
method selected to the method's tally. In the end, each method will have a
score that is equal to the utility it generated each round summed up. This
gives you a great starting point for comparing the multiwinner methods.

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.)

If anyone notices a glaring error of some sort, please tell me; I'm just a
high school student.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20081010/29bdc031/attachment-0002.htm>