[EM] More about the Websterish method, and implementation
Kristofer Munsterhjelm
kmelmet at broadpark.no
Fri May 22 00:58:19 PDT 2009
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 halfsolid, 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 tieamongsets (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 populationpair 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 singlewinner 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 singlewinner 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 monoraise.)

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 nontext attachment was scrubbed...
Name: set_webster.cc
Type: text/xc++src
Size: 18315 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/electionmethodselectorama.com/attachments/20090522/f9853ca8/attachment0003.cc>
More information about the ElectionMethods
mailing list