[EM] More about the Webster-ish method, and implementation

[Kristofer Munsterhjelm]

All this talk about IRV/STV being arbitrary and unfair inspired me to 
try to actually implement my Webster/DSC hybrid, wich I've named Set 
Webster. The general idea remains the same:

Sort solid (or acquiescing, or half-solid, depending on how you want) 
coalitions in order from most voters to least, breaking ties by sorting 
the coalitions of greatest cardinality first. Then, for a given divisor, 
each set is entitled to (exactly) the minimum of its cardinality and the 
number of voters supporting the coalition, divided by the divisor and 
rounded off. Go down the list, affirming constraints unless the 
constraint would leave no possible solution sets, in which case one says 
the number of voters supporting that coalition has been contradicted.

Then simply find the divisor that leaves the least number of voters 
contradicted. The constraints end up narrowing the set of possible 
assemblies down to either one or more; usually one, but if there are 
more, then that's a tie. I pick a random set from the result if that's 
the case, but there may be better tiebreakers.

There may also be ties between divisors. Say that both divisor x and y 
results in an assembly that contradict z voters, but the assembly is 
different. If x is a tie-among-sets (more than one winning set), and y 
is not, then break the tie in favor of y. Otherwise, it's not clear what 
to pick in order to maintain house monotonicity.

-

The changes I've made are that contradictions no longer count as one per 
solid coalition. It seems more sensible to make them count according to 
the support of the coalition, because otherwise, a group may benefit 
from changing its votes from something like:

90: A > B > C > D

to

30: A > B > C > D
30: A > C > B > D
30: A > D > C > B

in the hope of causing so many contradictions that the method will pick 
another choice, perhaps to include A whereas it would not otherwise do so.

One could make this even more sophisticated, by only counting part of a 
contradiction if it's not entirely contradicted. Say, for instance, that 
earlier constraints have limited your winning sets to
	A B C, A B D
and the next constraint is
	Winner set should have 3 from B C D
then both the winning sets include two out of three. However, I don't 
think that is needed, because if it *does* include two out of three, it 
will get an implicit bonus by not contradicting the "B" and "C" or "D" 
coalitions later on.

-

So, what properties does this method pass? From my limited experiments, 
it seems to be like Webster. That is, it is house monotone (proportional 
ordering, meaning that the result for four winners is equal to the 
result for three winners, plus one more) and population-pair monotone 
(ordinary "monotonicity" - you won't harm a candidate by voting him 
higher). It certainly reduces to Webster in a certain party situation: 
if everybody ranks only the members of the party they support, then each 
party will get a share of the assembly equal to what would be the case 
in Webster.

That means that it is not Droop proportional (doesn't meet quota). 
Again, like Webster, such failures may be rare, but they're present. 
Therefore, if you want to go by the strict word of Woodall, it's not a 
true proportional method.

The method also reduces to DAC/DSC/DHSC in the single-winner case 
(depending on how you calculate the coalitions). That method is more or 
less of the quality of IRV (at least by utilitarian measures - depends 
on how honest the voters are), but if you can't tolerate 
nonmonotonicity, well, it's monotone. It doesn't reweight any faction 
either, so if your complaint is that IRV or STV "counts some people's 
votes before it counts others'", this method solves that as well.

-

I think that, as a consequence of that it's house monotone, Set Webster 
must elect what IRV proponents call "winners with core support". The 
reason it has to do that is that, if it picked a centrist, it would be 
in an unfortunate situation when picking the next seat: however it 
picked the next candidate (unless it chose another centrist), that would 
cause an unfair bias to that side, since the centrist contributes 
equally to all sides. But it's this very property that makes it a 
relatively bad single-winner method: it doesn't pick the centrist.

However, IRV doesn't pick the centrist, either, and it's not house 
monotone, so one may say that that's at least an advantage of Set 
Webster with regards to STV. Of course, if passing the quota 100% of the 
time is more important, then it doesn't matter; STV will still be 
better. (On a side note, if the apportionment proofs port cleanly to 
ranked multiwinner methods, it's possible to make a method that's house 
monotone and passes quota, but that method will by necessity be 
nonmonotonic, i.e. fail mono-raise.)

-

Set Webster may or may not have a polynomial runtime; I'm not sure, 
really. The naive version I've coded in my implementation, which just 
constructs the set of all possible winner sets, then winnows them down 
according to constraints, is definitely not. The sophisticated version 
of my implementation may or may not be - since it makes use of house 
monotonicity, each winner set is recursively defined as one of (the 
winner set of last candidate, plus some other candidate), which means 
that at each round, or number of seats, there are only n sets to check. 
However, the number of solid coalitions may be larger, and so may the 
number of divisors to check. Whether these can be got around by using 
clever tricks, I don't know, so I'll just say, "mostly polytime". It is 
not summable.

As regards divisors, my implementation uses a few tricks to determine 
the significant divisors (where some set constraint changes) by 
determining "tipping points", which are divisors that are the least or 
most that doesn't alter the constraint number for a set. This isn't 
significant to Set Webster itself, but it does improve the runtime.

-

If I'm wrong about any of this - for instance, if it's nonmonotonic in 
some situation not possible in ordinary Webster, then tell me. For that 
matter, if you have questions, just ask!

My implementation was made in g++, and so should compile using GNU C++ 
compilers. I haven't tested it on other compilers.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: set_webster.cc
Type: text/x-c++src
Size: 18315 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20090522/f9853ca8/attachment-0003.cc>