[EM] Fair and Democratic versus Majority Rules

[Kristofer Munsterhjelm]

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.