In trying to generalize my 2-of-3 Bucklin method, I think I have found
one that very seldomly fails monotonicity, if at all. Since I am using
an experimental setup (basically trying what works and checking if the
program can find a monotonicity failure), I can not be certain that the
method is monotone, but my program has not found any failures so far (at
4 candidates or less for any number of seats; or at 6 candidates with
random number of seats).
If this truly is monotone, then it is, to my knowledge, the only Droop
proportional method that is. I even thought that it would be impossible
to have both monotonicity and Droop proportionality, but maybe I was
wrong. (Or maybe the failure in this method only shows up after lots and
lots of seats and candidates)
Because it's experimental, it's only really defined for the case where
there are no equal ranks and every voter ranks at least as many choices
as there are seats. Handling truncation before this point, or equal rank
is "left as an exercise to the reader" :-) But I think that if we make
use of symmetric completion, we don't need to show that the method is
monotone even with truncated or equal-rank votes, because these can be
simulated with an appropriate combination of ordinary votes.
So, here goes.
Say the election is to k seats and there are n candidates.
First, calculate the Bucklin result where the threshold is the Droop
quota rather than 50%. Ties are broken by the amount of votes the
candidate has got at the rank where it crosses the threshold. Further
ties are broken by the method of first differences: if both A and B have
10 more votes than the Droop quota at rank 2, but A had three more votes
than B at top rank, A is better than B. This can be modeled as having an
array of results: first the rank number where the threshold was exceeded
(or the total number of ranks minus this, if greater is better), then
the result at the rank where the threshold was exceeded, then results
for the first rank, second rank, etc. A comparison operator between two
candidates would compare the first element of each candidate's array,
then the second, then the third, etc, until one is greater than the other.
Call this the tiebreaker order. Candidates can be compared by comparing
their arrays. Subsets of candidates can be compared by comparing the sum
of their arrays (e.g. {AB} vs {CD} by comparing A's array + B's array to
C's array + D's array).
Then, the multiwinner Bucklin process:
This process consists of two steps, which I'll call the "increment" and
the "eligibility check" respectively. In an increment with parameter k,
you take every possible subset of k candidates, where at least one of
the candidates is at the current rank and all candidates in the subset
appear at or before the current rank in the ballot in question; and
increment a score number associated with the subset. This is done for
each ballot.
For instance, if you have ballot data like this:
10: A>B>C>D
5: C>D>A>B
and the parameter k is 2, and current rank is third, then you add 10 to:
AC (A is at first rank, i.e. before third, and C is at current rank,
thus satisfying that constraint),
BC (B is at first rank, and C is at current),
but not AB (none at current rank) or CD (D is at a lower rank).
You then add 5 to AC and AD.
In this respect, the increment is like Bucklin. An increment with a
parameter 1 is the same thing as one round of single-winner Bucklin.
If you have a parameter greater than the current rank, the function will
of course not increment anything.
-
The eligibility check is rather simple, though takes a lot of time in
practice. It may be optimized, but I haven't done so. Its logic is as
follows:
Each subset that has a score of p can give q candidates to the outcome,
where q is the minimum of the number of candidates in the subset, and
the number of Droop quotas for which the score of that subset is greater
than this number of Droop quotas.
Each set of candidates so that it is possible to assign the candidates
to the subsets without violating the q-constraint above is a possible
outcome. Of possible outcomes, pick the one with the best tiebreaker
order. Since these outcomes will involve multiple candidates, in
practice, you compare sums as mentioned above. If there are more than
one subset with the same tiebreaker order/sum, break randomly (or
according to a casting vote, etc).
To give an example of the eligibility check, consider an election with
50: A>B>C>D
50: D>E>F>G
two seats, and we're at second rank so the subsets are:
50: AB
50: DE
with the Droop quota being 100/3 = 33 + 1/3.
Then the AB set supports one candidate and the DE set supports another.
So the possible outcomes are {AD, BD, AE, BE} but not, say, {AB}
(because the AB subset can only support one candidate), nor {DE} (for
the same reason). The winner here would be {AD} because both reach the
Droop quota at first rank, and so they would have better tiebreaker
scores than any of the other candidates.
If there are no possible outcomes, the eligibility check returns nothing.
-
So now we just have to put all of this together. There are two variants
- one that is weakly summable and one that is not. Let's call the
former, "variant A", and the latter, "variant B".
In variant A, first calculate the tiebreaker. Then, for each rank from
top rank and down:
1. increment with parameter 1 and current rank.
2. increment with parameter equal to number of seats, and current rank.
3. run an eligibility check. If it returns something, that's the
outcome, otherwise loop to next rank.
In variant B, first calculate the tiebreaker. Then, for each rank from
top rank down:
1. for every integer r = 1...number of seats, inclusive:
1.1. increment with parameter r and current rank.
(end for)
2. run an eligibility check. If it returns something, that's the
outcome, otherwise loop to next rank.
-
I have been testing just variant A, and it seems to be monotone, but
there may be complex "revelation" scenarios where you could trick it to
be nonmonotone. On the other hand, if A is monotone all the time, then
it is preferable because it's weakly summable.
I put the "parameter 1" thing in A because of just such a "revelation"
scenario. The parameter 1 scenario goes something like:
C and D have more than a Droop quota each at first rank, but we don't
detect this because we don't have a parameter-1 subset.
So at rank 2, a set that includes C or D has more than a Droop quota.
Say it's {AD}, and {AC} is exactly at the Droop quota. However, these
are on different ballots so they don't increment {CD} enough. So {CD} is
never a possible outcome and, say, AD wins. The method can't pick from
{AC} either - {AC} needs to exceed the quota, not just be at it, for
that to be possible.
Now someone raises A on a ballot that used to go
C>B>A>D.
That increments the count for {AC}, so now one can pick one candidate
from {AD} and one from {AC}. The method then finds out that if it picks
D from the former and C from the latter, it gets something with a much
better tiebreaker result - so it does, so the method fails monotonicity.
The problem is that it can't know, by cardinality-two subsets alone,
whether A or C caused {AC} to go above the Droop quota. By using a
parameter 1 increment, if C and/or D go above the quota in the first
rank (and so would dominate every other subset in the tiebreaker), then
the method will include them in possible outcomes, thus averting the
situation.
It seems to me you could use the same reasoning as for why a 3-seat
method also needs to consider 2-seat subsets, but I haven't been able to
get the method to fail monotonicity even with variant A. So maybe I'm
missing something -- or maybe the monotonicity failure example would be
very hard to find, something on the order of Smith,Minmax examples of
mono-add-top failure.
-
Any suggestions? Comments? Failure examples? Ideas for a name?
(And now I'll be away for some time, dealing with real world things!)
----
Election-Methods mailing list - see http://electorama.com/em for list info
