[EM] Thresholded weighted multiwinner elections
Kristofer Munsterhjelm
km_elmet at t-online.de
Wed Jul 1 13:14:11 PDT 2015
I think I see why the cloning attack is possible in two-stage weighted
voting. If I'm right, then it is possible to make voting methods that
produce results that fit weighted voting better -- at least when the
voters are honest. However, I'm not sure if it is possible at all if
enough voters are strategic. It might turn out that the only way of
making weighted voting work is through either varying the number of
winners (like in party list) or by an unconventional (nondeterministic)
voting system or the Asset version of this.
First, why the cloning attack is possible: when we use (call them semi-
majoritarian[1]) methods like IRV or Plurality, if candidates represent
parties who can clone as many as they want, then I think the strategic
equilibrium gives each party a number of seats equal to their number of
Droop quotas. If we instead use an unweighted multiwinner method (STV,
Schulze STV, etc), then the Droop proportionality criterion gives each
party at least their Droop quotas' worth in seats without strategy.
Simply, when the number of winners is fixed, the semi-majoritarian
methods have an implicit threshold of a Droop quota, and the unweighted
multiwinner methods have an explicit threshold of the same.
In that light, the cloning strategy in three-seat
26: A1 > A2 > B > C > D
26: A2 > A1 > C > B > D
25: B > C > A1 > A2 > D
10: C > B > A2 > A1 > D
5: D > A1 > A2 > B > C
works because the A-group has more than two Droop quotas (a Droop quota
being 23 here).
Perhaps we'd want to have no threshold at all, something like minimax
Approval where we want to find the outcome that satisfies the voter who
likes it the least the most. But it'd seem unreasonable to elect {A1, B,
C} in this extreme variant of the above:
1000: A1 > A2 > B > C > D
1000: A2 > A1 > C > B > D
500: B > C > A1 > A2 > D
2: C > B > A2 > A1 > D
1: D > A1 > A2 > B > C
and hence, that implies there should be some kind of threshold, but that
it should be lower than a Droop quota[2]. A lower threshold would mean
that the assembly would be more broad than deep: it would choose a
compromise among popular candidates to make room for more specialized
candidates.
For instance, in a two-seat election with an augmented LCR example like
50: L > C > R > S
40: R > C > L > S
10: C > R > L > S
20: S
the method could elect {LR} with a high threshold, but instead elect
{CS} if the threshold were lower. In return, the candidate C would have
a much greater weight in the latter case than either L or R would have
in the former.
The next thing to do would be to find a proof of concept method that
would have a tunable threshold just to show that it'x possible (at least
under honesty). Here's one that reduces to Bucklin (if one picks a 50%
threshold):
==
Let X be a set of winners and t a threshold (in number of voters). Then
evaluate(X, t) is a function that works on the ballots and returns a
list of numbers in sorted order from least to most. evaluate(Y, t) is
"better" than evaluate(X, t) if the first number where the output from
evaluate(Y, t) differs from evaluate(X, t) is one where evaluate(Y, t)'s
number is greater than evaluate(X, t)'s. The best set is the one that is
better than every other, and that set wins.
Evaluate itself just counts the ranks of the ballots (of the candidates
in the set X), where first place is n, second place is n-1, all the way
to nth place is 1 (and unranked is 0). It then sorts these and removes
the t worst.
==
Here's the two-seat LCR example above with a Droop quota (40) and with a
threshold of 10. {LR} wins with a Droop quota and {CS} with the
threshold of 10. To skip, just search for #. I have omitted other sets
like CL, CR, LS, etc.
evaluate({LR}, 40):
rank number: 4 3 2 1
50: *L C R S
40: *R C L S
10: C *R L S
20: S
So we have 50 4s, 40 4s, 10 3s and 20 0s, or
20 0s, 10 3s, 90 4s
Threshold of 40 removes the 40 least, so the output is
80 4s.
evaluate({CS}, 40):
rank number: 4 3 2 1
50: L *C R S
40: R *C L S
10: *C R L S
20: *S
So we have 50 3s, 40 3s, 10 4s, 20 4s, or
90 3s, 30 4s
Threshold of 40 removes the 40 least, giving 50 3s and
30 4s.
So here {LR} with 80 4s wins over {CS} with 50 3s and 30 4s.
With a threshold of 10:
evaluate({LR}, 10):
As above, before truncating, we have 20 0s, 10 3s, 90 4s
But now we can only remove 10 worst. So the final
output is 10 0s, 10 3s, 90 4s
evaluate({CS}, 10):
90 3s, 30 4s.
Removing 10 worst gives
80 3s, 30 4s.
So now {CS} with 80 3s and 30 4s wins over {LR} with 10 0s
first, because 3 is clearly greater than 0.
#
Hence it's possible to make something that has a tunable threshold under
honesty.
But here's a problem. In the single-seat case, this behaves like Borda:
it may violate the majority criterion to elect a candidate that has more
second-place votes. That is, in something like
55: A>B>C
35: B>C>A
10: C>B>A
Borda will elect B, and with a threshold of say, 10, so will the method
above:
evaluate({B}, 10) gives (truncated) 55 2s, 35 3s
evaluate({A}, 10) gives (truncated) 35 1s, 55 3s
evaluate({C}, 10) gives (truncated) 45 1s, 35 2s, 10 3s
All well and good. But for Borda, a strategic majority can force a
winner by acting like an unreasonable group or an aggregate of different
smaller groups so that the method considers the majority winner to be
the broad-support candidate. The problem with this is that if that's a
general property, then it might turn out that a Droop quota can force
the election of a particular candidate in a weighted voting method with
a lower threshold just by pretending to be very unreasonable or to be
many different smaller groups.
It certainly is possible for the proof of concept method. For instance,
the L-first voters can truncate after L, after which the outcome changes
from {CS} to {LS}. Part of this, however, is due to that the method
above passes LNHelp but not LNHarm (because it's Bucklinesque and
because voters are assigned completely to their first preferences). If
the strategy is particular to certain weighted voting/tunable threshold
methods, then there's no problem. But if it's general (and it might
intuitively be), that's another matter.
If it is general, I can think of three ways to keep weighted voting:
1. Let the number of seats/winners be adjustable.
2. Accept the Droop quota.
3. Use a (randomized) consensus method.
Some combination of 1 and 3 might also be possible.
The first option is to let the number of winners be adjustable. The
general idea would be to have the same threshold and if a party clones
itself, it does get another winner - but the number of winners also
increases so that there's no benefit. Or, conversely (if one accepts the
Droop quota), a candidate who gets more than a Droop quota's worth
removes as many seats as he has Droop quotas. E.g. in the clone example
above, without cloning, the outcome would then be {A, B}, and with
cloning, it would be {A1, A2, B}. Again, there's no benefit. Both of
these make weighted voting more like party list PR.
The second option is to just accept the Droop quota and use a
multiwinner method as basis. The cloning is still possible, but at least
one gets more varied winners without cloning and there's no need to
engage in strategic nomination. With IRV, a party could split itself too
thin by overestimating its support, but that won't happen with say, STV.
A party just has to field enough candidates (say enough to fill the
council) and doesn't have to worry about fielding too many.
The third option is to use consensus. If it's an Asset variant, we could
just "stick the candidates in a room and have them negotiate until they
agree" with a supermajority, but there's an incentive for the status quo
to block the consensus. That can be fixed with randomized consensus -
some kind of variant of the methods Jobst and Forest Simmons have
proposed[3]. Randomized consensus can be done either before the election
(as a general method) or after (as a variant of Asset), but the former
is much less likely to work.
Basically, these methods consist of every voter (candidates in case of
Asset) voting for a consensus outcome as well as for a favorite outcome.
If fewer voters than the threshold disagree about the consensus outcome,
then it is picked, otherwise a random favorite outcome is picked. As
random ballot is suboptimal but gives nobody an advantage, so everybody
would want to find a consensus outcome to the extent they can work
together to do so. The equivalent of a cloning attack would be for a
majority candidate to stick to his guns and only propose a council
consisting of his own party. But if he tries to block the consensus,
then it falls through to random ballot which favors nobody and only
degrades the quality of the solution.
Generalizing this to multiwinner might be trickier because we want
something that with high probability returns a low-threshold assignment
and that is strategically unbiased. The consensus ballot can simply be a
set of winners. If fewer voters than the threshold disagree about the
consensus, then it is picked. But the fallback is hard. If we just do
"pick a winner from voters' first preferences at random, eliminate,
repeat", then that favors Droop quota cloning because only one of the
clones get eliminated at once. "Pick a proposed winner set at random"
favors extreme outcomes. It would be fair, but have very high variance:
one could end up with a council controlled completely by a single party,
it's just which party would control it that would be random in a
low-threshold unbiased manner.
---
[1] These are methods that never elect candidates with zero first
preference votes and where giving someone more first preferences always
helps. I think the observation above holds for all of these; it does at
least seem to hold for Plurality and IRV.
[2] We could also argue that there should be a threshold less than a
Droop quota by saying that if the threshold is a Droop quota, then
(under strategy) the outcome for weighted voting and unweighted voting
is the same, so why bother with weights? Thus the point of having a
weight should be to make weighted voting be more representative with
fewer seats than ordinary unweighted voting can be. If, on the other
hand, a Droop quota is good enough (and we just want weighting to handle
excess beyond the Droop quota), then we shouldn't use semi-majoritarian
methods but instead unweighted multiwinner methods to decide upon the
winners in the first stage.
[3]
https://www.pik-potsdam.de/members/heitzig/presentation-slides/some-chance-for-consensus
More information about the Election-Methods
mailing list