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