Andy Jennings wrote:
Have you looked into Monroe's method? (The American Political Science
Review, Vol. 89, No. 4 (Dec., 1995), pp. 925-940)
Every voter submits a grade for every candidate. Say there are N
voters, M candidates and S seats to be filled. A valid election outcome
consists of choosing the S winners out of the M candidates as well as
assigning the voters, evenly, to the winning candidates. That is, every
winning candidate must be assigned either floor(N/S) or ceil(N/S)
constituents. We define the quality of the election outcome to be the
sum of each voter's grade for his assigned candidate. Ideally, we would
find the election outcome that maximizes quality, but that problem is
non-polynomial in the size of M and S. Here is Warren Smith's
complexity analysis: http://rangevoting.org/MonroeMW.html
In my opinion, Monroe's method works most naturally with score voting
inputs. It could also be used with approval voting inputs.
That sounds like it's part of or similar to a class I've called CFC, for
"continuous fractional clustering". I've implemented CFC-Range and
CFC-Kemeny.
CFC-Range works like this: Each ballot scores every candidate. We also
have an assignment between ballots and candidates. Say that the first
ballot is assigned to the first candidate. Then the first candidate
gains as many points as the ballot gives to that candidate.
The objective is then to find the assignment of all voters to k
candidates so that the sum of the scores of those candidates is maximized.
There are two proportionality constraints. First, each candidate can
only assign a total of 1x his ballot to a number of candidates. This
seems to be where CFC-Range differs from Monroe's method: a voter can
assign his ballot to any combination of the candidates, as long as he
assigns his entire ballot once in full. That is, he might assign half
the ballot to the first candidate and half to the second, in which case
the first candidate gets half the first candidate's score on the ballot,
and the second candidate gets half the second candidate's score on that
ballot. Since half and half adds up to a whole, that's allowed.
Second, each voter must be assigned equally many ballots. When the
number of seats does not cleanly divide the number of voters, that means
the "continuous" aspect will be forced into play.
CFC-Range uses fractional assignment because one would want to be
consistent with a situation where the number of voters are multiplied by
some high number. The result should be the same whether we have
2000: A > B > C
2000: B > C > A
or
2: A > B > C
2: B > C > A
but if we don't permit fractional assignment, the former may divide the
ballots more evenly than the latter simply because there are more
ballots to go around.
Since it seems to be NP-hard, my simulator tries all possible assemblies
and picks the one with the best score.
It could even be used with ranked ballots, using a positional vector to
translate each candidate's ranking position into a grade.
That's sort of what I did with CFC-Kemeny. It uses Kemeny instead of
Range by deciding on not just a candidate council, but a set of
candidate orderings. As a result, it has a truly horrible runtime:
there's an exponential number of orderings per possible assembly, and
there's an exponential number of possible assemblies.
It's completely impractical - a proof of concept. By my simulator's
measure, it's quite proportional (moreso than STV), but each individual
member of the assembly is less liked by the electorate as a whole. See
http://munsterhjelm.no/km/elections/multiwinner_tradeoffs/ for a graph
of that, although it's old and so doesn't include CFC-Range.
Ignoring the algorithmic difficulty, what criteria does this method satisfy?
Monotonicity?
Proportionality?
Quota?
It's hard to define quota in the context of score/range ballots. I
suppose the best one can do is to say something similar to "if all
voters vote Approval-style, then if more than x Droop quotas approve
only of a set of k particular candidates, then min(x,k) of these should
appear in the outcome".
Even with such a definition, I don't know. Much of the behavior of the
methods above arise emergently because they're not programmed into them.
If I were to guess, however, I'd say that they all satisfy quota and
thus one form of proportionality - CFC-Kemeny in the Droop
proportionality sense, Monroe's and CFC-Range in the Approval DPC sense.
I am not sure about this - I need to keep improving my simulation
program so it'll be easier to find out things like that.
----
Election-Methods mailing list - see http://electorama.com/em for list info
