[EM] Multiwinner Bucklin - proportional, summable (n^3), monotonic (if fully-enough ranked)

[Jameson Quinn]

The "Condorcet How?" discussion got me to thinking (again) about how it's
good to have similar proposals for single-winner and proportional systems.
So I'd like to argue that MCV is an excellent single-winner system, then
suggest a multiwinner generalization which is also attractive.

Right now, I think MCV - that is, two-rank, equality-allowed Bucklin, with
top-two runoffs if no candidate receives a majority of approvals in those
two ranks - is my favorite proposal for practical implementation. While it's
not the theoretical best method, it does the best on the following practical
criteria, in order of importance to me:

1. Attainable (simple to explain, simple to vote, close to systems which
have already been used in government, runs easily on existing equipment)
2. Strategy resistant (Unlike Range, Approval, or even 3-rank Bucklin, when
there's a known CW, voting doesn't "feel" strategic[0]; and unlike all
Condorcet systems and many others, all optimal strategies are semi-honest,
which avoids pathologies.) [1]
3. Good honest results (by Bayesian Regret [2], or by Condorcet Criterion
[3], or by Monotonicity, or other measures.
4. Summable (thus easily recountable, sampleable, etc. - this is important
for confidence and legitimacy.)

So, what would be a multiwinner "variant" of MCV which preserves these
advantages as much as possible?[4] First, I'll describe a multiwinner system
based on multiround Bucklin, then I'll explain how to "patch" it for two
rounds (as the possible runoff "patches" MCV). The system I have come up
with is STV-like - that is, candidates are elected one-by-one with droop
quotas, which "uses up" a droop quota of votes. As long as there's a
candidate with more than a Droop quota of approvals, elect that candidate.
All ballots which approve that candidate are "used up" proportionally
(multiplied by a factor of (a-D)/a, where a is the number of approvals that
the candidate has, and D is the Droop quota). This fully defines the result.
When no more candidates have a droop quota of approvals, proceed to the next
round: re-weight each ballot to 1, add the next-lower category of candidates
to the "approved" set for all ballots, and go through the list of
already-elected candidates in order, re-discounting as if they'd just been
elected.

How can you ensure electing a full slate? Let A be the minimum number of
approvals per ballot in a round, C be the number of candidates, and S be the
number of seats. If there is a situation which elects only N candidates,
then there's a situation where the same candidates are elected and no voter
approves more than A-N candidates outside that set (that is, all voters
approve the winners; these votes are "free" in terms of not electing more
candidates). You want to be sure that S candidates are elected; so to prove
it, assume the contrary, that only S-1 or fewer candidates are elected. So
if A-S+1 approvals per vote, over C-S+1 candidates, with (S-1)/(S+1) of the
votes used up - that is, 2/(S+1) of them remaining - is enough to ensure
another Droop quota, then that's the contradiction that D's the QED. That
is, 2(A-S+1)/(C-S+1)(S+1)>1/(S+1). Solve for A: A>(C+S-1)/2. Thus, if you
require at least that many approvals (not counting write-ins) - "one for
each seat, and half of the rest" - from each voter in the last round, you
are guaranteed to elect a full slate. (I'll discuss ways to avoid this
burden and thus finish in 2 rounds, below).

In order to count this election without keeping an exponentially large
number of piles of (possibly fractional) ballots, you can keep aggregate
information about the remaining votes for in a summable C^2 half-matrix per
round: M(x,y) says how many remaining votes approve both X and Y. Of course,
this matrix is symmetrical around the x=y diagonal, which gives the
one-candidate approval.

This matrix does not have the same information as all ballots for the round;
that would be exponential. However, it does keep enough information to give
results. When you "eliminate" a droop quota (D votes) for candidate x, you
find the "used up votes" factor u=(D/M(x,x)). All cells involving that
candidate are multiplied by the "remainder factor" r=1-u, and, for y != x,
M(y,y) is replaced by M(y,y) - u*M(x,y).

This system is proportional: a group of N droop quotas who approve only the
same M>N candidates in round 1 will, obviously, elect N of them - their
ballots will go to no one else, and the round will not end until N droop
quotas have been deducted from the approval of the candidate set.

It's monotonic, in the sense that "raising" a winning candidate to a higher
approval (earlier round) cannot cause that candidate to lose. It affects
only the round where you added their approval, and if it does not cause
their election that round, it does not affect the results of that round,
because all ballots are treated proportionally, and only a different
candidate being elected can affect later results.

Note that that does not mean that it obeys the participation criterion. By
participating you can cause one of your preferred candidates to be elected
in an earlier round than otherwise, and this could cause another of your
preferred candidates not to be elected. Still, one should remember that in a
proportional system, you do not have any right to determine who wins once
"your" representative is elected. I believe that it does obey a weaker
"proportional participation" criterion: your participation cannot cause a
given candidate X to lose instead of win, unless there is some candidate Y,
whom you rank equal or higher, who wins when you participate (whether or not
they won without you). Personally, I find it implausible that anyone could
find a practical, safe strategy involving this flaw; especially since one
would have to be strategizing against "allies" who share relatively strong
support (or, support that is at least as strong as your motivation to
strategize) for at least one candidate.

Let's work out an example. Say you have the following approvals in the first
round of a 5-seat election:

A
AB
AC
ACD
BDFG
CE
DE
DEFG
F
G

The approval matrix is: (Only the lower-left half; the upper-right is just
symmetrical)
* *  A  B  C  D  E  F  G
A  4
B  1  2
C  2     3
D  1  1  1  4
E        1  2  3
F     1     2  1  3
G     1     2  1  2  3

A and D have the most approvals: 4 each. That's more than the Droop quota of
2, so we'll elect one. We'll break the tie towards the candidate with a
lower average number of approvals on the ballots that approve them (this
uses the "scarcer per ballot, more valuable" approvals first, and leaves the
"more flexible" ones for later). In this case, that's A. So we have to take
half (Droop quota/total approvals - 2/4) of each A vote away.
* *  A  B  C  D  E  F  G
A  2
B  .5 1.5
C  1     2
D  .5 1  1 3.5
E        1  2  3
F     1     2  1  3
G     1     2  1  2  3

Next comes D, using 4/7 of the votes
* *  A    B    C    D    E    F    G
A  1.79
B  .5   1.5
C  1         1.57
D  .29       .57  1.5
E            1    1.14 2.14
F       1         1.14 1    2.14
G       1         1.14 1    2    2.14

Next, either E, F, or G, using 14/15 of their total. E wins the tiebreaker.
* *  A    B    C    D    E    F    G
A  1.79
B  .5   1.5
C  1         .64
D  .29       .57  .46
E            .07  .1   .14
F       1         1.14 .07  .21
G       1         1.14 .07  2    .21

We've elected A, D, and E; and there is no Droop quota left, so we'd proceed
to the next round.

There's a couple of things that would make this system more user-friendly.

This system reduces to Bucklin in the one-candidate case. However, to get it
to reduce to MCV - remember, my motivation is that classing into
"preferred", "approved", and "disapproved" is easier and involves less
strategic thinking for the voter than more rounds; and voters don't really
want to be forced to approve, even minimally, something over half of the
candidates for a large assembly - you need some way to "round out" the
legislature after there are no Droop quotas left. There are 3 ways to do
this: with some kind of a runoff (as in MCV); approval-style, where the
lowest-approval candidates are forced to share their votes which aren't
already shared; or simply continuing to pick the highest diagonal elements,
and deducting a full Droop quota (leaving negative numbers). (This last
option can be used with Hare quotas from the beginning to yield a more
Saint-Lague-style method).

Finally, to reduce the burden of individually marking candidates, there
could be (overlapping) party slates which could be marked in either
preference category wholesale.

I believe that this system's advantages speak for itself. I am not aware of
another system which is easy, monotonic, preferential, summable, and almost
strategy-free.[5]

This email is long enough for now, but I'd be happy to answer questions if
I've left something(s) unclear.

[0] MCV asks voters only to class candidates into "preferred", "approved",
and "disapproved". To me, this is always a natural division. If there's a
known CW, that candidate will almost certainly be salient to most voters,
and thus anchoring effects will tend to naturally put the
approved/disapproved breakpoint next to that candidate (perhaps with an
empty set of approved); that's why MCV will tend to elect the CW. In
Approval, one is forced to choose whether to put one's cutoff between
"preferred" and "approved", or between "approved" and "disapproved"; this is
fundamentally a strategic, not a natural, choice. In Range, a [nearly]
rational voter is forced to do the same, and then to exaggerate to a
[nearly] approval-style vote; this feels even more strategic. And for me,
MCV feels less strategic than Bucklin versions with more ranks. For
instance, in 3-rank, equality allowed Bucklin, it could often be rational to
"hold out to the last minute" by leaving the middle rank blank (or voting
Mickey Mouse there); yet that's purely due to strategic considerations, and
not at all about the inherent relative qualities of the given candidates.
[1] OK, if there are only a few 100% rational voters and all of them have
exact knowledge of each others' preferences, you can construct scenarios
where the game-theoretic optimum for one voter would not be semi-honest. It
happens because their preferences are only orthogonal, maximizing the
differences between candidates that all other voters regard as near-clones.
Warren Smith showed this for Approval in a paper somewhere (I suspect he can
provide the reference if someone's curious) and MCV is alike enough to
Approval for the result to apply. But it's a contrived and fragile case,
inhuman even when it happens and improbable exponentially in the number of
voters - that is, vastly less probable than exact ties.
[2] In WDS's simulations, it's the second-best system, after Range, if I'm
not mistaken.
[3] The method does not strictly satisfy the Condorcet Criterion, but in
practice, violations are rare for monte-carlo voters, and I think that human
nature would tend to make them rarer. If there's a known CW, they will win
in a cabal equilibrium.
[4] I've also explored the idea of a system like asset voting, with your
preferred candidate(s) transferring your vote to make Droop quotas, but with
guarantees to make sure your vote is never transferred to a disapproved
candidate. However, you have to go through crazy contortions to make a
system like that summable, and even with those contortions, I can't find a
"natural" way to make it a well-determined function of the votes and the
candidate's preference orders - that is, strategy would matter too much at
the "candidate's convention".
[5] Actually, this system is related to RRV. Perhaps a similar trick, using
a "correlation matrix", would make RRV summable. But RRV would still call
for an exaggeration strategy - one that's significantly more complex than
simple Range, by the way.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20100326/f15bfc5a/attachment-0003.htm>