[EM] "Minimum squared envy" (MSE) voting: proportional, monotonic, cloneproof, ...

[Jameson Quinn]

This is a proportional method which takes approval ballots as inputs. (If
you want to use score ballots, you can convert them into approval ballots
first)

Say you have V voters and S seats to allot. One Hare quota Q is thus V/S.
Let's use W to denote a potential set of S winners. This method, as the
name suggests, elects the set W which minimizes a "squared envy" measure.

To calculate "squared envy" for W, we do the following:

For each candidate w in W, we find the number a(w) of ballots which approve
w. From this w, we give each of those ballots a "representation score" of
1/(a(w)+Q). We add up the representation for each ballot across all w. (In
other words, we create Q "ghost voters" who approve everything, then divide
up one point for each winner among those ballots approving that winner)

We find the "ideal average representation" IAR. Take the candidate m with
the maximum approval a(m), and imagine electing a parliament consisting of
S clones of m. The average representation across all voters will then be
the product of S/(a(m)+Q) (the representation score for the a(m) voters who
would like this) times a(m)/V (the fraction of voters who would like it).

For each ballot, the "squared envy" is just the square of the difference
between the representation they get from W, and the IAR. Any
"supersatisfied" ballot which has more representation than the IAR is
counted as having zero squared envy. The method elects the set W which
minimizes the sum of squared envy.

The case of "supersatisfied" ballots should be rare. In a partisan election
of different-colored factions, the only ballots like that would be a
minority which vote for the winning candidates from each party. (If you
wanted to absolutely ensure no "supersatisfied" ballots, you could use the
ideal maximum representation IMR in place of the IAR as the baseline for
representation. This would make the method more "majoritarian"; though it
would still be proportional with purely disjoint partisan voting, it would
be less IUAC, independent of universally approved candidates. There could
be numbers in between the IMR and the IAR which would avoid any
supersatisfied voters, but since the IMR is the worst case for that, any
other formula which avoided supersatisfaction would lose cloneproofness.)

If there are no "supersatisfied" ballots, this method is minimizing the
mean squared error of the ballots from the IAR. As any statistician knows,
mean squared error (acronym MSE, just like this system) is mathematically
equal to the square of bias (that is, how far the average representation is
below the IAR; the higher the average representation, the happier all
voters are, the better) plus the variance (the square of the standard
deviation of the representations; the lower it is, the more
equally-represented all voters are, the better).

Note that the "bias" is governed by the average representation. This is a
monotonic function of the number of approvals for each winning candidate,
independent of which voters those approvals come from. The "variance" is
where it matters who approves who, so as to keep all voters approximately
equal. Once you zero out the excess contributions to variance from
"supersatisfied" voters, it's easy to see that this system is monotonic.

It's also easy to verify that it gives (D'Hondt-like) proportional results
in cases of pure partisan voters, and that it tends towards (though does
not actually perfectly achieve) independence of universally approved
candidates.

In order to find the global minimum of squared envy, it is possible to take
advantage of the fact that, if you allow any real-valued fraction or
negative amount of each candidate, but still keep the sum of the total
number of candidates constant at S, the quality becomes a nice simple
quadratic surface in each dimension. The global minimum is easy to
calculate, and there are polynomial-time algorithms to find which of the
nearby points with only 0 or 1 copy of each candidate is optimum. So this
is not an NP-complete system, unlike many globally-maximizing systems.
(This may break if there are a lot of supersatisfied voters of various
types; in that case, I guess, you could still find the IMR-based MSE, and
try perturbing from there, and also find lower bounds on the MSE so that
you could probably tell when you'd achieved the minimum.)

Jameson

ps. Thanks to Toby, Warren, and the others in the various threads that have
led up to this proposal. There is no way I would have been thinking along
these lines without the rich discussion of Phragmen, Ebert, etc.

pps. I realized that you can't add new pages on electowiki anymore. I've
written Rob Lanphier to see if he will fix that.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20151204/90d88cba/attachment.htm>