[EM] Semiproportional Bucklin method

[Kristofer Munsterhjelm]

First, I have been trying to construct proofs that various methods pass 
mutual majority. So far, I've managed to make proofs for elimination 
methods where the base method passes Majority (I've mentioned that proof 
before), for methods that are Smith (really just showing that Smith is a 
subset of the mutual majority set), and for Bucklin.

This suffices to cover almost all the methods condorcet.org mentions as 
passing mutual majority: Bucklin, Coombs (elimination with majority), 
IRV (ditto), pairwise elimination (ditto), Kemeny-Young (elects from the 
Smith set), Ranked Pairs, Schulze, and Smith//Minmax (all elect from the 
Smith set).

That leaves Borda-elimination (Baldwin) and Nanson, both of which are 
elimination methods based on Borda. Borda doesn't meet majority, and so 
one can't use that proof. However, if there is a Condorcet winner, he'll 
always have above-average Borda score. This secures the Smith set from 
being completely eliminated, therefore the Borda elimination methods 
meet Smith (and hence mutual majority).

This would suggest that, as I've mentioned before, for loser elimination 
methods where the base method that elect candidates with property X, the 
loser eliminatino method passes the criterion for all sets that reduce 
to the candidate with property X when there's only one left. If X is 
majority, the set property is mutual majority. If X is Condorcet, then 
the set property is Smith.

-

 From investigating the various methods, I've found a semiproportional 
method based on Bucklin. It seems to often elect according to the 
constraints of the Droop Proportionality criterion. My question is, does 
it always do that?

The definition of the method is:

Start as Bucklin. Call each step a "round". A set of q candidates has a 
support equal to the support of that candidate in the set that has the 
least support. So, for instance, the set {A, B, C} has support 20 if the 
individual support of each candidate is A: 20, B: 30, C: 98.
At round p, a candidate has support equal to the number of voters who 
placed that candidate in rank 1..p inclusive, where rank 1 is first 
preference, rank 2 second preference, etc.

At round p, if there's some set of cardinality p that's supported by a 
Droop quota more than the number of members we've already elected from 
it, pick a candidate from that set (use any method you want to decide 
which). Otherwise, go on to round p+1.

It's that simple.

Let's try it, using the PSC-CLE example:

33 A>D1>D2>D3>B>C
33 B>D1>D2>D3>A>C
32 C>D1>D2>D3>A>B
  2 D1>D2>D3>A>B>C

100 voters, 2 to be elected, so the Droop quota is 100/3 = 33.333^. For 
simplicity, I'll use the "method of first difference" to determine who 
gets picked within a set. The method of first difference is simply this: 
if two or more candidates are tied as far as support goes, pick the one 
who first scored above the others.

Round 1: support is: A: 33, B: 33, C: 32, D1: 2. No set of card 1 has 
reached the quota.

Round 2: support is: A: 33, B: 33, C: 32, D1: 100. No set of card 2 has 
reached the quota. Although D1 has reached the quota, it can't be paired 
with any other candidate to make a set that reached the quota, and 
therefore it can't be used yet.

Round 3: support is: A: 33, B: 33, C: 32, D1: 100, D2: 100. D1 and D2 
are above quota, but can't make a set of cardinality 3.

Round 4: support is: A: 35, B: 33, C: 32, D1: 100, D2: 100, D3: 98
          Now we have the set {D1 D2 D3 A} which is supported by 35, 
since the weakest candidate in the set, A, is supported by 35. 35 > 
33.333, so we can elect a single candidate from the set. The method of 
first difference says to elect A, because the first round where A had a 
different score than any others was the first round, where A had the 
most support.

Round 5: support is: A: 100, B: 68 C: 32, D1: 100, D2: 100, D3: 100.
          We have the set {A B D1 D2 D3} which is supported by 68. 
That's two Droop quotas (68 > 2/3), but we've already elected one from 
that set, so we can only elect one more. That candidate is B, since it 
had a greater score than the others in the first round.

All done, and the winners are A and B. The method of first difference 
may not be very good, but it shows the point.

Does this method (or group of methods) pass the DPC? If not, when does 
it not? If it does, that's quite interesting, because the method is 
summable.


If it does not pass the DPC, I think the reason would be something like 
what I'd call "shadowing". Consider the following situation for 
single-winner Bucklin, where the set in question is the mutual majority set:

2: A > B > ...
2: B > A > ...
2: A > ... > B
1: B > ... > A
1: C > B > ...
1: D > C > ...

9 voters

At round 2, we have
7: A, 6: B, 2: C

This suggests that {A, B} is a mutual majority set, but it is in fact 
not so. Shadowing is not a problem in single-winner Bucklin, since it 
implies that there is no mutual majority set, in which case Bucklin is 
free to pick whatever it wants. However, in the multiwinner version, one 
might have a shadowing candidate (that is, one that's picked due to 
shadowing) occupy the place that the DPC demands should be given to 
another candidate -- that is, unless shadowing requires enough voters 
that you couldn't make this work *and* set up other Droop sets at the 
same time.