Proportionality: the small bias effect seems to be real for Harmonic
I implemented some different measures of proportionality for my
simulator, and they all favor small values of delta for the cardinal
methods.
Since the result seemed so persistent, I decided to take a more
mathematical approach with a 1D standard normal to see if I could
reproduce it there. Infinite voters and candidates along the Gaussian,
and treating it like an integration problem.
That Harmonic voting only cares about the ratings of the winners makes
it easier, as I don't have to sum up infinite non-winning candidate
terms per voter.
My simple proportionality idea for this model is: suppose the winners
are x_1 and x_2, identified by their x coordinate on the standard normal
and that WLOG x_1 is to the left of x_2. Then we want x_1's right wing
to contain just as many voters (area under the curve) as x_1's left
wing, and ditto for x_2's wings.
This means that x_1 should be at the 25th percentile and x_2 at the
75th. Then x_1 covers/represents everybody from the minimum to the
median, and x_2 covers everybody from the median to the maximum, with
equal area on both sides.
We can then integrate over all the voters for some choices of x_1, x_2,
and delta; and get the Harmonic's quality score for those choices. Since
the normal is symmetric, we can also let x_1 = -x_2 and x_2 >= 0. We
would then want to determine the delta where the maximum quality
function value is attained at x ~= -0.6745. For that delta, Harmonic
would pick winners who have equally strong left and right wings.
Doing the integral is pretty hairy but the general idea is that there
are four types of voter:
1. voters to the left of x_1
2. voters between x_1 and x_2, but closer to x_1
3. voters between x_1 and x_2, but closer to x_2
4. voters to the right of x_2,
and they all rate x_1 and x_2 according to some constant (I set 20)
minus the distance to the winner in question.
The first two voter types rate x_1 higher than x_2, and the second two
rate x_2 higher than x_1, so we know whose rating will get divided by
delta and whose will be divided by (1 + delta).
After a particularly long procedure (made possible by WolframAlpha), the
integral is found to evaluate to:
2 * (20 - sqrt(2/pi) + x_1)/(2 + 2 * delta) + 2 * ((2 * x_1 *
erfc(x_1/sqrt(2)) - 2 * sqrt(2/pi) * exp(-(x_1*x_1)/2) - 3 * x_1 +
sqrt(2/pi) + 20) / (2 * delta)).
Some numerical testing later, and the optimum for delta=0.5
(Sainte-Laguë) is x_1 ~= -0.43, which WolframAlpha states as x_1 =
-sqrt(2) * erfc^-1(2/3) = -0.43073... x_1 is at the 33% percentile in
this case.
For delta = 1, it is approximately -0.31864; -sqrt(2) erfc^-1(3/4): the
37.5th percentile.
Further numerical testing suggests that the correct position, x ~=
-0.6745, is only obtained in the limit of delta->0. E.g. delta=1e-6
gives y ~= -0.67449.
Some fiddling and setting derivatives to zero appear to indicate that
the optimum for a given delta is at sqrt(2) * erf^-1(-1/(2delta+2)),
and that this corresponds to the (2delta+1)/(4*delta+4) quantile. Which
gives the desired point exactly at delta=0 (and at-large Range at
delta->infty).
So at least in this respect, the effect seems to be real. You can either
have optimal proportionality for party list (at delta = 0.5) or for the
1D gaussian (at delta -> 0), but not both at the same time.
One may argue that the "wings are balanced" definition of
proportionality is kind of sketchy. I wouldn't entirely disagree; it
would be better to have three candidates (one at zero, one at -x, and
one at +x), and then set the requirement so that the number of voters
closest to each is the same. But I wouldn't want to do those
integrals; two winners was hard enough!
One could also argue that this kind of proportionality idea is too
Monrovian in that it only takes into account the voter's favorite.
Perhaps a better notion of proportionality would take the other winners
into account. But how?
(In the limit of delta approaching zero, Harmonic reduces to simply:
each voter contributes to the quality function the rating of the voter's
favorite winner. Which shows the similarity to Monroe, although Monroe
imposes an explicit limit on the fraction of voters assigned to each
winner.)
-km
Interesting as always, Kristofer. A couple of things:
My intuition is that the most balanced result for 2 candidates is at 33 and 67 rather than 25 and 75. 25 and 75 seems to suggest you're just splitting the electorate into two and finding the best candidate for each half, rather than finding the best 2 candidates for the entire electorate. Given that harmonic voting works on the scores voters give to all elected candidates rather than simply their best candidate, I would suggest that the Sainte-Laguë delta giving the 33/67 result is what I would consider to be the correct behaviour. I would expect methods that assign voters to a single candidate to be 75/25.
Also, I think using a the normal distribution rather than a uniform one complicates matters, even if it is more realistic. The normal and uniform will have the mean and median the same, but the percentiles won't be the same as what I call the "permeantiles" (percentile equivalents when using the mean). So while I would expect the Sainte-Laguë delta to give 33/67 for a uniform distribution, I'm not sure I'd necessarily expect this result for the normal distribution, although your results suggest it does give this anyway. This is because harmonic voting works on scores rather than ranks, so I wouldn't expect it to particularly follow the percentile data. So your results are a bit of a surprise in that respect.
There's probably more to get from your post so I will go through it again and see if I have anything to add or change my mind about.
Toby
On Monday 23 September 2024 at 13:07:31 BST, Kristofer Munsterhjelm <km-elmet@munsterhjelm.no> wrote:
I implemented some different measures of proportionality for my
simulator, and they all favor small values of delta for the cardinal
methods.
Since the result seemed so persistent, I decided to take a more
mathematical approach with a 1D standard normal to see if I could
reproduce it there. Infinite voters and candidates along the Gaussian,
and treating it like an integration problem.
That Harmonic voting only cares about the ratings of the winners makes
it easier, as I don't have to sum up infinite non-winning candidate
terms per voter.
My simple proportionality idea for this model is: suppose the winners
are x_1 and x_2, identified by their x coordinate on the standard normal
and that WLOG x_1 is to the left of x_2. Then we want x_1's right wing
to contain just as many voters (area under the curve) as x_1's left
wing, and ditto for x_2's wings.
This means that x_1 should be at the 25th percentile and x_2 at the
75th. Then x_1 covers/represents everybody from the minimum to the
median, and x_2 covers everybody from the median to the maximum, with
equal area on both sides.
We can then integrate over all the voters for some choices of x_1, x_2,
and delta; and get the Harmonic's quality score for those choices. Since
the normal is symmetric, we can also let x_1 = -x_2 and x_2 >= 0. We
would then want to determine the delta where the maximum quality
function value is attained at x ~= -0.6745. For that delta, Harmonic
would pick winners who have equally strong left and right wings.
Doing the integral is pretty hairy but the general idea is that there
are four types of voter:
1. voters to the left of x_1
2. voters between x_1 and x_2, but closer to x_1
3. voters between x_1 and x_2, but closer to x_2
4. voters to the right of x_2,
and they all rate x_1 and x_2 according to some constant (I set 20)
minus the distance to the winner in question.
The first two voter types rate x_1 higher than x_2, and the second two
rate x_2 higher than x_1, so we know whose rating will get divided by
delta and whose will be divided by (1 + delta).
After a particularly long procedure (made possible by WolframAlpha), the
integral is found to evaluate to:
2 * (20 - sqrt(2/pi) + x_1)/(2 + 2 * delta) + 2 * ((2 * x_1 *
erfc(x_1/sqrt(2)) - 2 * sqrt(2/pi) * exp(-(x_1*x_1)/2) - 3 * x_1 +
sqrt(2/pi) + 20) / (2 * delta)).
Some numerical testing later, and the optimum for delta=0.5
(Sainte-Laguë) is x_1 ~= -0.43, which WolframAlpha states as x_1 =
-sqrt(2) * erfc^-1(2/3) = -0.43073... x_1 is at the 33% percentile in
this case.
For delta = 1, it is approximately -0.31864; -sqrt(2) erfc^-1(3/4): the
37.5th percentile.
Further numerical testing suggests that the correct position, x ~=
-0.6745, is only obtained in the limit of delta->0. E.g. delta=1e-6
gives y ~= -0.67449.
Some fiddling and setting derivatives to zero appear to indicate that
the optimum for a given delta is at sqrt(2) * erf^-1(-1/(2delta+2)),
and that this corresponds to the (2delta+1)/(4*delta+4) quantile. Which
gives the desired point exactly at delta=0 (and at-large Range at
delta->infty).
So at least in this respect, the effect seems to be real. You can either
have optimal proportionality for party list (at delta = 0.5) or for the
1D gaussian (at delta -> 0), but not both at the same time.
One may argue that the "wings are balanced" definition of
proportionality is kind of sketchy. I wouldn't entirely disagree; it
would be better to have three candidates (one at zero, one at -x, and
one at +x), and then set the requirement so that the number of voters
closest to each is the same. But I wouldn't want to do those
integrals; two winners was hard enough!
One could also argue that this kind of proportionality idea is too
Monrovian in that it only takes into account the voter's favorite.
Perhaps a better notion of proportionality would take the other winners
into account. But how?
(In the limit of delta approaching zero, Harmonic reduces to simply:
each voter contributes to the quality function the rating of the voter's
favorite winner. Which shows the similarity to Monroe, although Monroe
imposes an explicit limit on the fraction of voters assigned to each
winner.)
-km
Election-Methods mailing list - see https://electorama.com/em for list info
Just to add to this:
While the percentiles and "permeantiles"* would clearly match for a uniform distribution, I was assuming that they definitely wouldn't match for a non-uniform distribution. That might be true anyway but I'm not entirely sure. It might be that for a normal distribution they would also match, which would remove the tension I was discussing in my last post. In any case, it would be interesting to see results for a uniform distribution.
Also, in the case where delta approaches zero, resulting in only each voter's favourite winner counting towards the quality function, the results in general wouldn't look at all proportional, but I'm not sure it really matters because the 25/75 result that you wanted was likely an intuition that you could be persuaded out of!
*I'm not sure if anything like a "permeantile" is a recognised concept, but I do think it's useful for things like this. My working definition of the permeantile would involve finding the relevant weighted mean. If you wanted to find e.g. the 25th permeantile, you would find the point in the data that becomes the mean if you weight everything to the left of it by 75^2 and everything to right right of it by 25^2 (or just 3^2 to 1, or 9 to 1). To find the pth permeantile, you find the point that becomes the mean if you weight everything below it by (100-p)^2 and weight everything above it by p^2. The reason you square it is that you essentially have to weight twice - once for the weight of data and once for the distance.
Toby
On Monday 23 September 2024 at 18:56:05 BST, Toby Pereira tdp201b@yahoo.co.uk wrote:
Interesting as always, Kristofer. A couple of things:
My intuition is that the most balanced result for 2 candidates is at 33 and 67 rather than 25 and 75. 25 and 75 seems to suggest you're just splitting the electorate into two and finding the best candidate for each half, rather than finding the best 2 candidates for the entire electorate. Given that harmonic voting works on the scores voters give to all elected candidates rather than simply their best candidate, I would suggest that the Sainte-Laguë delta giving the 33/67 result is what I would consider to be the correct behaviour. I would expect methods that assign voters to a single candidate to be 75/25.
Also, I think using a the normal distribution rather than a uniform one complicates matters, even if it is more realistic. The normal and uniform will have the mean and median the same, but the percentiles won't be the same as what I call the "permeantiles" (percentile equivalents when using the mean). So while I would expect the Sainte-Laguë delta to give 33/67 for a uniform distribution, I'm not sure I'd necessarily expect this result for the normal distribution, although your results suggest it does give this anyway. This is because harmonic voting works on scores rather than ranks, so I wouldn't expect it to particularly follow the percentile data. So your results are a bit of a surprise in that respect.
There's probably more to get from your post so I will go through it again and see if I have anything to add or change my mind about.
Toby
On Monday 23 September 2024 at 13:07:31 BST, Kristofer Munsterhjelm <km-elmet@munsterhjelm.no> wrote:
I implemented some different measures of proportionality for my
simulator, and they all favor small values of delta for the cardinal
methods.
Since the result seemed so persistent, I decided to take a more
mathematical approach with a 1D standard normal to see if I could
reproduce it there. Infinite voters and candidates along the Gaussian,
and treating it like an integration problem.
That Harmonic voting only cares about the ratings of the winners makes
it easier, as I don't have to sum up infinite non-winning candidate
terms per voter.
My simple proportionality idea for this model is: suppose the winners
are x_1 and x_2, identified by their x coordinate on the standard normal
and that WLOG x_1 is to the left of x_2. Then we want x_1's right wing
to contain just as many voters (area under the curve) as x_1's left
wing, and ditto for x_2's wings.
This means that x_1 should be at the 25th percentile and x_2 at the
75th. Then x_1 covers/represents everybody from the minimum to the
median, and x_2 covers everybody from the median to the maximum, with
equal area on both sides.
We can then integrate over all the voters for some choices of x_1, x_2,
and delta; and get the Harmonic's quality score for those choices. Since
the normal is symmetric, we can also let x_1 = -x_2 and x_2 >= 0. We
would then want to determine the delta where the maximum quality
function value is attained at x ~= -0.6745. For that delta, Harmonic
would pick winners who have equally strong left and right wings.
Doing the integral is pretty hairy but the general idea is that there
are four types of voter:
1. voters to the left of x_1
2. voters between x_1 and x_2, but closer to x_1
3. voters between x_1 and x_2, but closer to x_2
4. voters to the right of x_2,
and they all rate x_1 and x_2 according to some constant (I set 20)
minus the distance to the winner in question.
The first two voter types rate x_1 higher than x_2, and the second two
rate x_2 higher than x_1, so we know whose rating will get divided by
delta and whose will be divided by (1 + delta).
After a particularly long procedure (made possible by WolframAlpha), the
integral is found to evaluate to:
2 * (20 - sqrt(2/pi) + x_1)/(2 + 2 * delta) + 2 * ((2 * x_1 *
erfc(x_1/sqrt(2)) - 2 * sqrt(2/pi) * exp(-(x_1*x_1)/2) - 3 * x_1 +
sqrt(2/pi) + 20) / (2 * delta)).
Some numerical testing later, and the optimum for delta=0.5
(Sainte-Laguë) is x_1 ~= -0.43, which WolframAlpha states as x_1 =
-sqrt(2) * erfc^-1(2/3) = -0.43073... x_1 is at the 33% percentile in
this case.
For delta = 1, it is approximately -0.31864; -sqrt(2) erfc^-1(3/4): the
37.5th percentile.
Further numerical testing suggests that the correct position, x ~=
-0.6745, is only obtained in the limit of delta->0. E.g. delta=1e-6
gives y ~= -0.67449.
Some fiddling and setting derivatives to zero appear to indicate that
the optimum for a given delta is at sqrt(2) * erf^-1(-1/(2delta+2)),
and that this corresponds to the (2delta+1)/(4*delta+4) quantile. Which
gives the desired point exactly at delta=0 (and at-large Range at
delta->infty).
So at least in this respect, the effect seems to be real. You can either
have optimal proportionality for party list (at delta = 0.5) or for the
1D gaussian (at delta -> 0), but not both at the same time.
One may argue that the "wings are balanced" definition of
proportionality is kind of sketchy. I wouldn't entirely disagree; it
would be better to have three candidates (one at zero, one at -x, and
one at +x), and then set the requirement so that the number of voters
closest to each is the same. But I wouldn't want to do those
integrals; two winners was hard enough!
One could also argue that this kind of proportionality idea is too
Monrovian in that it only takes into account the voter's favorite.
Perhaps a better notion of proportionality would take the other winners
into account. But how?
(In the limit of delta approaching zero, Harmonic reduces to simply:
each voter contributes to the quality function the rating of the voter's
favorite winner. Which shows the similarity to Monroe, although Monroe
imposes an explicit limit on the fraction of voters assigned to each
winner.)
-km
Election-Methods mailing list - see https://electorama.com/em for list info
On 2024-09-23 19:56, Toby Pereira wrote:
Interesting as always, Kristofer. A couple of things:
My intuition is that the most balanced result for 2 candidates is at 33
and 67 rather than 25 and 75. 25 and 75 seems to suggest you're just
splitting the electorate into two and finding the best candidate for
each half, rather than finding the best 2 candidates for the entire
electorate. Given that harmonic voting works on the scores voters give
to all elected candidates rather than simply their best candidate, I
would suggest that the Sainte-Laguë delta giving the 33/67 result is
what I would consider to be the correct behaviour. I would expect
methods that assign voters to a single candidate to be 75/25.
I can see that argument. The question is really what proportionality means.
We have to determine if 33/67 being more desirable than 25/75 is because
33/67 is more proportional as such, or if we're deliberately giving up
some raw proportionality to get an assembly that's better adjusted as a
whole (more able to work as a unified body, related to the "utility"
measure).
If it's the former, then we'd need to find a better definition of what
we mean by proportional. Whatever it is should use hidden information
(something depending on opinion space) so that the 1D normal reaches
optimal proportionality by 33/67 instead of 25/75. Just saying "what
harmonic/psi/Phragmen says is good is good" blinds us to the possibility
that there may exist (yet undiscovered) methods that do what the
yardstick does, but better.
If it's the latter, then that means that what we're balancing is the
ability of the method to evenly cover opinion space with its winners,
and the ability of the winning assembly to work in a way similar to a
high-quality single winner.
That this balance isn't "all proportionality at all costs" makes sense.
Party list PR methods with Plurality ballots can't do that balance well,
even when they're proportionally unbiased, and thus exhibits other
problems: an assembly elected by Sainte-Laguë may still have kingmaker
problems, something that would be improved by having a "centrist center
of gravity" to break the ties instead. But D'Hondt can't do that because
it doesn't know who the centrists are, since all it's got are first
preference votes.
As you point out, it's not that strange for Harmonic to deviate from the
Monrovian proportionality concept, since it does, after all, take
ratings of all winners by all voters into account. What I'm saying is
that we should try to find out what the ideal of proportionality ought
to be. Or find some of the different aspects of the elephant, if we
can't characterize it exactly.
Also, I think using a the normal distribution rather than a uniform one
complicates matters, even if it is more realistic. The normal and
uniform will have the mean and median the same, but the percentiles
won't be the same as what I call the "permeantiles" (percentile
equivalents when using the mean). So while I would expect the
Sainte-Laguë delta to give 33/67 for a uniform distribution, I'm not
sure I'd necessarily expect this result for the normal distribution,
although your results suggest it does give this anyway. This is because
harmonic voting works on scores rather than ranks, so I wouldn't expect
it to particularly follow the percentile data. So your results are a bit
of a surprise in that respect.
I'm not quite sure I get what you're saying. By permeantile, do you mean
something related to the expected value of a truncated distribution, the
way the mean is the expected value of the full distribution?
I agree that Harmonic doesn't try to place itself at a given percentile
for the normal, since it hasn't been designed to do so. It is
surprising, though, that my first proportionality measure (opinion space
proportionality) seems to prefer deltas that lead to 25-75 to ones that
lead to 33-67.
If there is a Monroe component to this measure, then I would expect
Monroe itself to show up as being very proportional by that measure. I
should check that - only problem is that implementing the assignment
algorithm is kind of a hassle.
While the percentiles and "permeantiles"* would clearly match for a
uniform distribution, I was assuming that they definitely wouldn't match
for a non-uniform distribution. That might be true anyway but I'm not
entirely sure. It might be that for a normal distribution they would
also match, which would remove the tension I was discussing in my last
post. In any case, it would be interesting to see results for a uniform
distribution.
I did some quick integral evaluations, so take this with a bit of salt,
but it seems like the uniform distribution percentiles are the same as
the normal.[1]
Suppose we have a uniform between -1 and 1. the pdf is 1/2. Each voter
rates a candidate equal to the negative of their distance (I'm skipping
the constant of 20 this time as it shouldn't matter.) As before, the
winners' positions are at x_1 and -x_1. Then, if my calculations are
correct, the Harmonic score for given delta and x_1 is:
(-2 * x_1^2 * delta - 2 * x_1^2 - 2 * x_1 - 2 * delta - 1)/(2 * delta *
(delta + 1))
The optimum is achieved when x_1 = -1/(2(delta+1)), which might look a
bit familiar.
The quantile is (2 * delta + 1) / (4 * delta + 4), which definitely
looks familiar.
For different values of delta:
delta = 0 x_1 = -1/2 25th percentile
delta = 0.5 x_1 = -1/3 33rd percentile
delta = 1 x_1 = -1/4 37.5th percentile.
Also, in the case where delta approaches zero, resulting in only each
voter's favourite winner counting towards the quality function, the
results in general wouldn't look at all proportional, but I'm not
sure it really matters because the 25/75 result that you wanted was
likely an intuition that you could be persuaded out of!
Oh, delta=0 definitely isn't proportional in every case. Monroe proper
has a constraint that each candidate can only be assigned to a certain
number of voters, so that each candidate represents the same number of
voters. On symmetric distributions like the normal and uniform with
symmetrically positioned candidates, you get that anyway, but I would
imagine that Harmonic with delta=0 would be disproportional if the
distribution is skewed: some winners would be backed by more voters than
others. Meanwhile, Monroe's constraint would keep that from happening,
even for a Monroe-type idea of proportionality.
To put it differently, Harmonic delta=0's results would be more like
Chamberlin-Courant but with the weights discarded after election. E.g.
for something like
100: A (10) > B (9) > C (0)
1: C (10) > B (1) > A (0)
the intuitively proportional result for two winners is {A, B}, but
Harmonic with delta=0 would choose {A, C}. Monroe would pick {A, B} but
Chamberlin-Courant would do something like: A (weight 100/101), C
(weight 1/101).
In this sense delta=0 is akin to at-large IRV and LPV0+.
This also shows that methods that are on-average proportional (for some
model) may still fail quite badly outside that model, or even some of
the time in-model. That's a weakness of VSE-type analysis. We could
possibly get some information about how often that happens (still
in-model) by reporting something that is to the standard deviation what
the VSE is to the mean.
-km
[1] A better mathematician might be able to determine if this is true of
every symmetric distribution. Such a strategy would probably use that
the pdfs of distributions that are symmetric about 0 are odd, and then
something with voters on the far right canceling out voters on the far
left. But turning that into an actual proof would still be quite a lot
of work.
Thanks for the response and added information. On proportionality, it can be difficult to pin down a definition precisely, but obviously I would see it in terms of balance in some sense. But given that my existing intuition was that 33/67 was the better result and the Sainte-Laguë delta gave this result anyway, rather than me having to rationalise the result, I'm not too concerned at the moment.
In any case, I don't see the more polarised version of proportionality where it's all about your best candidate as the best definition. E.g.
50: A=10, B=0, C=9, D=950: A=0, B=10, C=9, D=9
I see CD as a "better" result than AB, and so a definition that prefers this would be more appealing to me. This is likely to lead to 33/67 rather than 25/75 in the other example.
For approval voting, my working definition of proportionality is achieving perfect representation in the limit as the number of candidates increases, as long as the ballots make this possible (voters approve enough candidates). Converting this definition to score voting might involve making some arbitrary decisions about what scores should mean. E.g. if one simply assumes that the KP-transformation is what you are supposed to do, then just using an approval method that passes perfect representation in the limit with the KP-transformation will do the job.
https://electowiki.org/wiki/Perfect_representation
On permeantiles, I was really just thinking of something that corresponds to the mean the same way as percentiles correspond to the median. Given what you say about the uniform and normal distributions behaving in the same way under Harmonic voting, it probably doesn't matter at this point anyway.
Toby
On Wednesday 25 September 2024 at 14:51:27 BST, Kristofer Munsterhjelm km-elmet@munsterhjelm.no wrote:
On 2024-09-23 19:56, Toby Pereira wrote:
Interesting as always, Kristofer. A couple of things:
My intuition is that the most balanced result for 2 candidates is at 33
and 67 rather than 25 and 75. 25 and 75 seems to suggest you're just
splitting the electorate into two and finding the best candidate for
each half, rather than finding the best 2 candidates for the entire
electorate. Given that harmonic voting works on the scores voters give
to all elected candidates rather than simply their best candidate, I
would suggest that the Sainte-Laguë delta giving the 33/67 result is
what I would consider to be the correct behaviour. I would expect
methods that assign voters to a single candidate to be 75/25.
I can see that argument. The question is really what proportionality means.
We have to determine if 33/67 being more desirable than 25/75 is because
33/67 is more proportional as such, or if we're deliberately giving up
some raw proportionality to get an assembly that's better adjusted as a
whole (more able to work as a unified body, related to the "utility"
measure).
If it's the former, then we'd need to find a better definition of what
we mean by proportional. Whatever it is should use hidden information
(something depending on opinion space) so that the 1D normal reaches
optimal proportionality by 33/67 instead of 25/75. Just saying "what
harmonic/psi/Phragmen says is good is good" blinds us to the possibility
that there may exist (yet undiscovered) methods that do what the
yardstick does, but better.
If it's the latter, then that means that what we're balancing is the
ability of the method to evenly cover opinion space with its winners,
and the ability of the winning assembly to work in a way similar to a
high-quality single winner.
That this balance isn't "all proportionality at all costs" makes sense.
Party list PR methods with Plurality ballots can't do that balance well,
even when they're proportionally unbiased, and thus exhibits other
problems: an assembly elected by Sainte-Laguë may still have kingmaker
problems, something that would be improved by having a "centrist center
of gravity" to break the ties instead. But D'Hondt can't do that because
it doesn't know who the centrists are, since all it's got are first
preference votes.
As you point out, it's not that strange for Harmonic to deviate from the
Monrovian proportionality concept, since it does, after all, take
ratings of all winners by all voters into account. What I'm saying is
that we should try to find out what the ideal of proportionality ought
to be. Or find some of the different aspects of the elephant, if we
can't characterize it exactly.
Also, I think using a the normal distribution rather than a uniform one
complicates matters, even if it is more realistic. The normal and
uniform will have the mean and median the same, but the percentiles
won't be the same as what I call the "permeantiles" (percentile
equivalents when using the mean). So while I would expect the
Sainte-Laguë delta to give 33/67 for a uniform distribution, I'm not
sure I'd necessarily expect this result for the normal distribution,
although your results suggest it does give this anyway. This is because
harmonic voting works on scores rather than ranks, so I wouldn't expect
it to particularly follow the percentile data. So your results are a bit
of a surprise in that respect.
I'm not quite sure I get what you're saying. By permeantile, do you mean
something related to the expected value of a truncated distribution, the
way the mean is the expected value of the full distribution?
I agree that Harmonic doesn't try to place itself at a given percentile
for the normal, since it hasn't been designed to do so. It is
surprising, though, that my first proportionality measure (opinion space
proportionality) seems to prefer deltas that lead to 25-75 to ones that
lead to 33-67.
If there is a Monroe component to this measure, then I would expect
Monroe itself to show up as being very proportional by that measure. I
should check that - only problem is that implementing the assignment
algorithm is kind of a hassle.
While the percentiles and "permeantiles"* would clearly match for a
uniform distribution, I was assuming that they definitely wouldn't match
for a non-uniform distribution. That might be true anyway but I'm not
entirely sure. It might be that for a normal distribution they would
also match, which would remove the tension I was discussing in my last
post. In any case, it would be interesting to see results for a uniform
distribution.
I did some quick integral evaluations, so take this with a bit of salt,
but it seems like the uniform distribution percentiles are the same as
the normal.[1]
Suppose we have a uniform between -1 and 1. the pdf is 1/2. Each voter
rates a candidate equal to the negative of their distance (I'm skipping
the constant of 20 this time as it shouldn't matter.) As before, the
winners' positions are at x_1 and -x_1. Then, if my calculations are
correct, the Harmonic score for given delta and x_1 is:
(-2 * x_1^2 * delta - 2 * x_1^2 - 2 * x_1 - 2 * delta - 1)/(2 * delta *
(delta + 1))
The optimum is achieved when x_1 = -1/(2(delta+1)), which might look a
bit familiar.
The quantile is (2 * delta + 1) / (4 * delta + 4), which definitely
looks familiar.
For different values of delta:
delta = 0 x_1 = -1/2 25th percentile
delta = 0.5 x_1 = -1/3 33rd percentile
delta = 1 x_1 = -1/4 37.5th percentile.
Also, in the case where delta approaches zero, resulting in only each
voter's favourite winner counting towards the quality function, the
results in general wouldn't look at all proportional, but I'm not
sure it really matters because the 25/75 result that you wanted was
likely an intuition that you could be persuaded out of!
Oh, delta=0 definitely isn't proportional in every case. Monroe proper
has a constraint that each candidate can only be assigned to a certain
number of voters, so that each candidate represents the same number of
voters. On symmetric distributions like the normal and uniform with
symmetrically positioned candidates, you get that anyway, but I would
imagine that Harmonic with delta=0 would be disproportional if the
distribution is skewed: some winners would be backed by more voters than
others. Meanwhile, Monroe's constraint would keep that from happening,
even for a Monroe-type idea of proportionality.
To put it differently, Harmonic delta=0's results would be more like
Chamberlin-Courant but with the weights discarded after election. E.g.
for something like
100: A (10) > B (9) > C (0)
1: C (10) > B (1) > A (0)
the intuitively proportional result for two winners is {A, B}, but
Harmonic with delta=0 would choose {A, C}. Monroe would pick {A, B} but
Chamberlin-Courant would do something like: A (weight 100/101), C
(weight 1/101).
In this sense delta=0 is akin to at-large IRV and LPV0+.
This also shows that methods that are on-average proportional (for some
model) may still fail quite badly outside that model, or even some of
the time in-model. That's a weakness of VSE-type analysis. We could
possibly get some information about how often that happens (still
in-model) by reporting something that is to the standard deviation what
the VSE is to the mean.
-km
[1] A better mathematician might be able to determine if this is true of
every symmetric distribution. Such a strategy would probably use that
the pdfs of distributions that are symmetric about 0 are odd, and then
something with voters on the far right canceling out voters on the far
left. But turning that into an actual proof would still be quite a lot
of work.
The other thing with this is that looking solely at proportionality is not necessarily the best thing to do. It needs to be combined with some reasonable degree of monotonicity as well. Take the following approval ballots:
99: ABC99: ABD1: C1: D
With two to elect, arguably CD is the most proportional result (and this is what Phragmen philosophy prefers). However, C and D each have just 50% of the support, whereas A and B each have 99%. The 99s in the ballots could be increased arbitrarily and you'd get the same thing. This is why Phragmen-based methods tend to be only weakly monotonic.
I've written about optimal proportionality before, but if you are allowed to elect any number of candidates with any amount of weight (rather than having a fixed number with equal weight), then optimal PAV and COWPEA both have some very nice properties, including a strong degree of monotonicity and passing independence of irrelevant ballots. They differ slightly in their "philosophy" so can produce different results, but I see them as possibly the only two contenders for the "ultimate" in optimal PR.
Unfortunately, they do not carry all of their nice properties over to elections to elect a fixed number of candidates with equal weight. Well, there isn't a definitive version of COWPEA for deterministic elections of this sort. PAV (and by extension Harmonic Voting) can give disproportional results, although this goes away if candidates all have infinite clones. While this is unrealistic, it means that PAV is proportional in the case where it is an approval-based party-list election where all parties field enough candidates.
PAV and COWPEA do retain their nice properties if you allow non-deterministic elections. For this you would use the candidate weights instead as probabilities in a lottery and elect sequentially. The PAV version of this is likely to be computationally intractable, but the COWPEA version is very simple.
But the bottom line is that there is no known method that keeps all the nice properties you'd want for all deterministic elections where a fixed number of candidates are to be elected with equal weight. Some compromise is likely to always be needed. It's not that surprising since proportionality and monotonicity are essentially orthogonal things, and it's not a priori obvious that they could be perfectly combined in a non-arbitrary and clean way. It seems they can be anyway for optimal PR (with two nice methods - an embarrassment of riches) but not for fixed candidates with equal weight.
So I do largely trust Harmonic Voting with the Sainte-Laguë delta to give good results in cases where a lack of clones is not an issue.
Toby
On Wednesday 25 September 2024 at 18:28:16 BST, Toby Pereira tdp201b@yahoo.co.uk wrote:
Thanks for the response and added information. On proportionality, it can be difficult to pin down a definition precisely, but obviously I would see it in terms of balance in some sense. But given that my existing intuition was that 33/67 was the better result and the Sainte-Laguë delta gave this result anyway, rather than me having to rationalise the result, I'm not too concerned at the moment.
In any case, I don't see the more polarised version of proportionality where it's all about your best candidate as the best definition. E.g.
50: A=10, B=0, C=9, D=950: A=0, B=10, C=9, D=9
I see CD as a "better" result than AB, and so a definition that prefers this would be more appealing to me. This is likely to lead to 33/67 rather than 25/75 in the other example.
For approval voting, my working definition of proportionality is achieving perfect representation in the limit as the number of candidates increases, as long as the ballots make this possible (voters approve enough candidates). Converting this definition to score voting might involve making some arbitrary decisions about what scores should mean. E.g. if one simply assumes that the KP-transformation is what you are supposed to do, then just using an approval method that passes perfect representation in the limit with the KP-transformation will do the job.
https://electowiki.org/wiki/Perfect_representation
On permeantiles, I was really just thinking of something that corresponds to the mean the same way as percentiles correspond to the median. Given what you say about the uniform and normal distributions behaving in the same way under Harmonic voting, it probably doesn't matter at this point anyway.
Toby
On Wednesday 25 September 2024 at 14:51:27 BST, Kristofer Munsterhjelm km-elmet@munsterhjelm.no wrote:
On 2024-09-23 19:56, Toby Pereira wrote:
Interesting as always, Kristofer. A couple of things:
My intuition is that the most balanced result for 2 candidates is at 33
and 67 rather than 25 and 75. 25 and 75 seems to suggest you're just
splitting the electorate into two and finding the best candidate for
each half, rather than finding the best 2 candidates for the entire
electorate. Given that harmonic voting works on the scores voters give
to all elected candidates rather than simply their best candidate, I
would suggest that the Sainte-Laguë delta giving the 33/67 result is
what I would consider to be the correct behaviour. I would expect
methods that assign voters to a single candidate to be 75/25.
I can see that argument. The question is really what proportionality means.
We have to determine if 33/67 being more desirable than 25/75 is because
33/67 is more proportional as such, or if we're deliberately giving up
some raw proportionality to get an assembly that's better adjusted as a
whole (more able to work as a unified body, related to the "utility"
measure).
If it's the former, then we'd need to find a better definition of what
we mean by proportional. Whatever it is should use hidden information
(something depending on opinion space) so that the 1D normal reaches
optimal proportionality by 33/67 instead of 25/75. Just saying "what
harmonic/psi/Phragmen says is good is good" blinds us to the possibility
that there may exist (yet undiscovered) methods that do what the
yardstick does, but better.
If it's the latter, then that means that what we're balancing is the
ability of the method to evenly cover opinion space with its winners,
and the ability of the winning assembly to work in a way similar to a
high-quality single winner.
That this balance isn't "all proportionality at all costs" makes sense.
Party list PR methods with Plurality ballots can't do that balance well,
even when they're proportionally unbiased, and thus exhibits other
problems: an assembly elected by Sainte-Laguë may still have kingmaker
problems, something that would be improved by having a "centrist center
of gravity" to break the ties instead. But D'Hondt can't do that because
it doesn't know who the centrists are, since all it's got are first
preference votes.
As you point out, it's not that strange for Harmonic to deviate from the
Monrovian proportionality concept, since it does, after all, take
ratings of all winners by all voters into account. What I'm saying is
that we should try to find out what the ideal of proportionality ought
to be. Or find some of the different aspects of the elephant, if we
can't characterize it exactly.
Also, I think using a the normal distribution rather than a uniform one
complicates matters, even if it is more realistic. The normal and
uniform will have the mean and median the same, but the percentiles
won't be the same as what I call the "permeantiles" (percentile
equivalents when using the mean). So while I would expect the
Sainte-Laguë delta to give 33/67 for a uniform distribution, I'm not
sure I'd necessarily expect this result for the normal distribution,
although your results suggest it does give this anyway. This is because
harmonic voting works on scores rather than ranks, so I wouldn't expect
it to particularly follow the percentile data. So your results are a bit
of a surprise in that respect.
I'm not quite sure I get what you're saying. By permeantile, do you mean
something related to the expected value of a truncated distribution, the
way the mean is the expected value of the full distribution?
I agree that Harmonic doesn't try to place itself at a given percentile
for the normal, since it hasn't been designed to do so. It is
surprising, though, that my first proportionality measure (opinion space
proportionality) seems to prefer deltas that lead to 25-75 to ones that
lead to 33-67.
If there is a Monroe component to this measure, then I would expect
Monroe itself to show up as being very proportional by that measure. I
should check that - only problem is that implementing the assignment
algorithm is kind of a hassle.
While the percentiles and "permeantiles"* would clearly match for a
uniform distribution, I was assuming that they definitely wouldn't match
for a non-uniform distribution. That might be true anyway but I'm not
entirely sure. It might be that for a normal distribution they would
also match, which would remove the tension I was discussing in my last
post. In any case, it would be interesting to see results for a uniform
distribution.
I did some quick integral evaluations, so take this with a bit of salt,
but it seems like the uniform distribution percentiles are the same as
the normal.[1]
Suppose we have a uniform between -1 and 1. the pdf is 1/2. Each voter
rates a candidate equal to the negative of their distance (I'm skipping
the constant of 20 this time as it shouldn't matter.) As before, the
winners' positions are at x_1 and -x_1. Then, if my calculations are
correct, the Harmonic score for given delta and x_1 is:
(-2 * x_1^2 * delta - 2 * x_1^2 - 2 * x_1 - 2 * delta - 1)/(2 * delta *
(delta + 1))
The optimum is achieved when x_1 = -1/(2(delta+1)), which might look a
bit familiar.
The quantile is (2 * delta + 1) / (4 * delta + 4), which definitely
looks familiar.
For different values of delta:
delta = 0 x_1 = -1/2 25th percentile
delta = 0.5 x_1 = -1/3 33rd percentile
delta = 1 x_1 = -1/4 37.5th percentile.
Also, in the case where delta approaches zero, resulting in only each
voter's favourite winner counting towards the quality function, the
results in general wouldn't look at all proportional, but I'm not
sure it really matters because the 25/75 result that you wanted was
likely an intuition that you could be persuaded out of!
Oh, delta=0 definitely isn't proportional in every case. Monroe proper
has a constraint that each candidate can only be assigned to a certain
number of voters, so that each candidate represents the same number of
voters. On symmetric distributions like the normal and uniform with
symmetrically positioned candidates, you get that anyway, but I would
imagine that Harmonic with delta=0 would be disproportional if the
distribution is skewed: some winners would be backed by more voters than
others. Meanwhile, Monroe's constraint would keep that from happening,
even for a Monroe-type idea of proportionality.
To put it differently, Harmonic delta=0's results would be more like
Chamberlin-Courant but with the weights discarded after election. E.g.
for something like
100: A (10) > B (9) > C (0)
1: C (10) > B (1) > A (0)
the intuitively proportional result for two winners is {A, B}, but
Harmonic with delta=0 would choose {A, C}. Monroe would pick {A, B} but
Chamberlin-Courant would do something like: A (weight 100/101), C
(weight 1/101).
In this sense delta=0 is akin to at-large IRV and LPV0+.
This also shows that methods that are on-average proportional (for some
model) may still fail quite badly outside that model, or even some of
the time in-model. That's a weakness of VSE-type analysis. We could
possibly get some information about how often that happens (still
in-model) by reporting something that is to the standard deviation what
the VSE is to the mean.
-km
[1] A better mathematician might be able to determine if this is true of
every symmetric distribution. Such a strategy would probably use that
the pdfs of distributions that are symmetric about 0 are odd, and then
something with voters on the far right canceling out voters on the far
left. But turning that into an actual proof would still be quite a lot
of work.
On 2024-09-26 23:49, Toby Pereira wrote:
The other thing with this is that looking solely at proportionality is
not necessarily the best thing to do. It needs to be combined with some
reasonable degree of monotonicity as well.
I agree that criteria matter too. As an analogy: even if Borda has a
better VSE than Schulze, I much prefer to have the majority criterion of
the latter.
Take the following approval ballots:
99: ABC
99: ABD
1: C
1: D
With two to elect, arguably CD is the most proportional result (and this
is what Phragmen philosophy prefers). However, C and D each have just
50% of the support, whereas A and B each have 99%. The 99s in the
ballots could be increased arbitrarily and you'd get the same thing.
This is why Phragmen-based methods tend to be only weakly monotonic.
What kind of monotonicity does the example show the limits of? It
doesn't seem to be mono-raise or mono-add-top.
I've written about optimal proportionality before, but if you are
allowed to elect any number of candidates with any amount of weight
(rather than having a fixed number with equal weight), then optimal PAV
and COWPEA both have some very nice properties, including a strong
degree of monotonicity and passing independence of irrelevant ballots.
They differ slightly in their "philosophy" so can produce different
results, but I see them as possibly the only two contenders for the
"ultimate" in optimal PR.
In a ranked setting, if you're allowed to elect any number of candidates
with any weight, then electing everybody's first preference can be
strategy-proof (by Duggan-Schwartz). It would also be optimal by
Chamberlin-Courant - every candidate would be assigned every voter
voting that candidate first, with weight equal to their proportion. So I
would imagine "elect any number with any weight" to be a setting where
it's relatively easy to do well.
But the bottom line is that there is no known method that keeps all the
nice properties you'd want for all deterministic elections where a fixed
number of candidates are to be elected with equal weight. Some
compromise is likely to always be needed. It's not that surprising since
proportionality and monotonicity are essentially orthogonal things, and
it's not a priori obvious that they could be perfectly combined in a
non-arbitrary and clean way. It seems they can be anyway for optimal PR
(with two nice methods - an embarrassment of riches) but not for fixed
candidates with equal weight.
How is proportionality and monotonicity incompatible in the fixed
candidates setting? It would seem to me that if A is on the winning
council and someone ranks or rates A higher, then it's possible to
ensure that A still wins without having to compromise proportionality.
-km
On weak monotonicity, take the following ballots:
99: AC99: BD1: C1:D
And then these ballots:
99: ABC99: ABD1: C1:D
In the first ballot set, CD would win (2 to elect), but the Phragmen score of AB (under e.g. var-Phragmen) would still be close. In the second set, CD would still win. Despite all those extra approvals for A and B, there would be no improvement in the score for AB. I would say that in a strongly monotonic method, each extra approval should count for the candidate being approved, rather than merely not against. These is why Phragmen-based methods are weakly monotonic. All these approvals count for nothing. I think mono-raise and mono-add-top are defined for ranked methods. Under approval voting, approving an extra candidate is in a sense raising them but also adding them to (potentially joint) top. But I don't think those exact definitions matter in this case. But it would also be the same for raising a score of a candidate or adding them to the top score in Harmonic Voting.
When talking about the "ultimate" in PR, I was largely talking about cardinal voting at that point, and something that could even be used on voters' raw utilities. Also it would have to take into count cases where a voter might be indifferent between two candidates while still passing independence of irrelevant ballots (IIB). If a voter has A and B top, then merely adding an equal weight for each in the overall parliament would not pass IIB.
My point wasn't that proportionality and monotonicity were incompatible in the fixed candidates setting, but that getting a clean method that passes all the criteria you want doesn't seem possible. E.g. I don't think there is a deterministic cardinal method that passes the same desirable criteria as COWPEA Lottery or Optimal PAV Lottery.
Toby
On Thursday 3 October 2024 at 15:43:08 BST, Kristofer Munsterhjelm km-elmet@munsterhjelm.no wrote:
On 2024-09-26 23:49, Toby Pereira wrote:
The other thing with this is that looking solely at proportionality is
not necessarily the best thing to do. It needs to be combined with some
reasonable degree of monotonicity as well.
I agree that criteria matter too. As an analogy: even if Borda has a
better VSE than Schulze, I much prefer to have the majority criterion of
the latter.
Take the following approval ballots:
99: ABC
99: ABD
1: C
1: D
With two to elect, arguably CD is the most proportional result (and this
is what Phragmen philosophy prefers). However, C and D each have just
50% of the support, whereas A and B each have 99%. The 99s in the
ballots could be increased arbitrarily and you'd get the same thing.
This is why Phragmen-based methods tend to be only weakly monotonic.
What kind of monotonicity does the example show the limits of? It
doesn't seem to be mono-raise or mono-add-top.
I've written about optimal proportionality before, but if you are
allowed to elect any number of candidates with any amount of weight
(rather than having a fixed number with equal weight), then optimal PAV
and COWPEA both have some very nice properties, including a strong
degree of monotonicity and passing independence of irrelevant ballots.
They differ slightly in their "philosophy" so can produce different
results, but I see them as possibly the only two contenders for the
"ultimate" in optimal PR.
In a ranked setting, if you're allowed to elect any number of candidates
with any weight, then electing everybody's first preference can be
strategy-proof (by Duggan-Schwartz). It would also be optimal by
Chamberlin-Courant - every candidate would be assigned every voter
voting that candidate first, with weight equal to their proportion. So I
would imagine "elect any number with any weight" to be a setting where
it's relatively easy to do well.
But the bottom line is that there is no known method that keeps all the
nice properties you'd want for all deterministic elections where a fixed
number of candidates are to be elected with equal weight. Some
compromise is likely to always be needed. It's not that surprising since
proportionality and monotonicity are essentially orthogonal things, and
it's not a priori obvious that they could be perfectly combined in a
non-arbitrary and clean way. It seems they can be anyway for optimal PR
(with two nice methods - an embarrassment of riches) but not for fixed
candidates with equal weight.
How is proportionality and monotonicity incompatible in the fixed
candidates setting? It would seem to me that if A is on the winning
council and someone ranks or rates A higher, then it's possible to
ensure that A still wins without having to compromise proportionality.
-km