Hare clustering MAM-based PR, and a tie problem.
I was going through some old posts of mine and found this idea for a
MAM/Ranked Pairs-based PR method. It's based around the idea of making a
number of virtual constituencies (one for each seat), and then trying to
allocate voters to each so that the case for the winner (according to
the Ranked Pairs method run in that constituency) is as strong as
possible, i.e. the choice of winner or winning order is as justified as
it can be.
When I last had this thought, I stopped early because I couldn't make
sure that it would indeed choose the optimum in each constituency; but
recently, I realized that if it can't, then single-winner Ranked Pairs
can't, either.
But that doesn't make a lot of sense unless I describe just what
single-winner RP's score/metric is, and how it maximizes it, and then
how it (perhaps) doesn't. So I'll do that first, then get to the PR
method afterwards.
Suppose we have a social ordering, A>B>C. Then both Kemeny and RP assign
a score to this ordering, that is a function of the pairwise victories
consistent with this ordering (in this case A>B, B>C, and A>C). Kemeny's
score is the sum of the strength of victories, while RP's is the value
of the strongest victory, ties broken by the value of the next
strongest, ties broken by the value of the third strongest, and so on.
Then both Kemeny and RP, in the absence of ties, calls an election by
producing the social ordering that maximizes its respective score
function. That is, Kemeny chooses the one whose sum of consistent
pairwise victories is maximized, and RP the one whose largest pairwise
victory is maximized, and among these, the one whose next largest
pairwise victory is maximized, and so on.
But if there are ties, then we're in trouble. The Ranked Pairs algorithm
works by starting at the strongest pairwise victory, locking that in,
then proceeding to the next strongest. This is a greedy approach, and it
maximizes the RP score when there are no ties. But if there's a tie,
then it might be that earlier choices close off later choices in ways
that we can't determine from the start.
E.g. suppose the defeat strengths are as follows, in sorted order by
strength:
C>A: 100
D>A: 99
A>B: 80
B>C: 80
B>D: 75
(something else): 60
...
First we admit C>A and D>A. Then we have a choice of either admitting
A>B or B>C; we can't admit both.
So suppose we admit A>B. Then we have {C,D}>A>B; admitting B>C would
produce a cycle, and so would B>D. So we skip, go to the something else,
and the score vector is [100, 99, 80, 60, ...].
On the other hand, suppose we admit B>C. Then we have D>A and B>C>A. Now
we can admit B>D and get B>D>C>A with score vector [100, 99, 80, 75, 60,
...], which is better by the RP metric.
But the problem here is that when we were considering how to break the
strength-80 tie, we didn't know which would close off the ability to
admit B>D. So ordinary RP only maximizes the score vector in the absence
of ties.
So now, the MAM/RP-based method. The idea is this: through linear
programming we can find what's the greatest strength pairwise victory
supported by a Hare quota of the voters without having to determine who
the voters is.
To maximize the RP score in a constituency (subject to the caveats
above), we keep a list of pairwise victories that we've affirmed, just
like in ordinary Ranked Pairs. Then for each unaffirmed pairwise
victory, we use LP to determine which Hare quota consistent with what
we've already locked will maximize the strength of that victory; and
then we choose the one that doesn't produce a cycle, and that has
maximum strength.
For instance, suppose the Hare quota is 1000. When starting out, we find
that it's possible to choose a Hare quota of voters so that everybody
prefers A>B. So we lock A>B.
Then we try every other pairwise preference, and in essence for X>Y ask:
what's the largest support you can give X>Y by choosing a Hare quota of
voters all of whom rank A>B?
Suppose B>C has largest such support 850, while C>D has largest support
900. Okay, then we admit C>D.
Then we ask for all other pairwise preferences X>Y: what's the largest
support you can give X>Y by choosing a Hare quota of voters, all of whom
rank A>B, and 900 of whom rank C>D?
And so on. As we admit more and more pairwise preferences, the Hare
quota's worth of voters becomes increasingly more distinct until the
constituency is uniquely defined. At that point we assign the RP winner
to this constituency, remove these voters (and the winner) from the
election, and repeat with the next constituency.
But the tie problem shows up here, too. What should we do if the number
of seats is rather large so that (for the first step) it's easy to find
a Hare quota all of whom support X>Y, no matter who X and Y are? We have
to choose one of them, but we can't be sure we'll maximize the RP score
because of the path dependence problem I mentioned. So that's where I
got stuck.
But then I realized that single winner RP has this problem too! So it
shouldn't be a strike against the legitimacy of the RP procedure; we
just need to break the tie somehow. Choosing the pairwise preference
with most total support over the whole electorate is probably as good a
way as any.
So this multiwinner method should be implementable, although it would be
very slow: for each step, we'd have to go through every pairwise
preference to find the one with maximum attainable support; and worst
case, we have to go through n^2 steps. That makes for O(n^4) calls to
the LP solver, which, though it's polynomial in the number of voters,
may have a very high polynomial degree indeed.
Perhaps there is some dynamic programming trick that could be used
instead of linear programming, but I don't see it at the moment.
And perhaps there is a way to look ahead and actually maximize the RP
score, but I doubt it is. I suspect it's related to that determining if
candidate X can be made an RP winner by breaking ties in a particular
way -- is NP-complete.
-km
In the new "Hare clustering MAM-based PR, and a tie problem" thread,
Kristofer Munsterhjelm wrote:
.... It's based around the idea of making a
number of virtual constituencies (one for each seat), and
then trying to allocate voters to each so that the case for
the winner (according to the Ranked Pairs method run in
that constituency) is as strong as possible, i.e. the
choice of winner or winning order is as justified as
it can be.
...
Then both Kemeny and RP, in the absence of ties, calls an election by
producing the social ordering that maximizes its respective score
function. That is, Kemeny chooses the one whose sum of consistent
pairwise victories is maximized, and RP the one whose largest pairwise
victory is maximized, and among these, the one whose next largest
pairwise victory is maximized, and so on.
Kristofer, what you're describing sounds similar to the STV version of
VoteFair Representation ranking:
https://electowiki.org/wiki/VoteFair_representation_ranking#STV_version
I added this section to Electowiki recently because there is growing
interest in using STV to elect city councils, yet STV is overly
simplistic, and has flaws similar to IRV flaws (especially ignoring
valid ranking data that's very relevant).
This STV version of VoteFair Representation ranking extends the two-seat
version of it that I designed for partisan elections. The result is an
STV-like non-partisan method.
Of course it's based on the Kemeny method rather than Ranked Pairs.
That's my bias for the reason you mention, namely that locking in a
pairwise win can block additional info. This is similar to the way IRV
blocks lower-ranked preference info from being looked at.
Resolving ties is not a problem with this method. When the Kemeny
method declares a tie, it has already used all the available pairwise
count numbers, so it's an actual tie, not a
tip-of-the-iceberg-let's-look-deeper kind of tie. In a governmental
election just recounting the ballots usually resolves such ties. Or the
tie can be resolved by adding one ballot -- supplied by a judge or based
on a random selection process -- that ranks all the candidates at
different levels.
Whereas the simple version of STV reduces a ballot to zero influence
when it helps elect one candidate, this "VoteFair" STV method reduces
the influence of a ballot to a decimal amount after it helps one
candidate win, and then reduces the ballot to zero influence after it
fractionally helps a second candidate win.
Of course the Kemeny calculations are NP-hard, so it's more practical to
use an estimation method (which I suggest to be a variation of the
insertion-sort algorithm using the pairwise count matrix) to identify
the top 12 candidates. Then the full Kemeny calculations are done for
those top 12.
So, Kristofer, I agree that you are on to something worth pursuing.
For the benefit of those wanting to see the forest for the trees:
Of course the Ranked Pairs method could be inserted as a drop-in
replacement for the Kemeny method in my VoteFair STV method, but as
Kristofer says, resolving ties becomes an issue.
For comparison with the simplistic version of STV that the FairVote
organization promotes, that method's biggest flaw might be that it
tosses out a ballot when counting reaches a point where two candidates
are ranked at the same preference level. That's crazy. Even using
their simplistic approach, those ballots can be set aside and checked
again during each elimination round, and resume counting them when only
one of the same-ranked candidates remains in the race. Of course
neither Kristofer's method nor the "VoteFair" STV method has this
disadvantage.
Again, Kristofer, I appreciate that you take time to share your wisdom here.
Richard Fobes
The VoteFair guy
On 2/9/2022 7:57 AM, Kristofer Munsterhjelm wrote:
I was going through some old posts of mine and found this idea for a
MAM/Ranked Pairs-based PR method. It's based around the idea of making a
number of virtual constituencies (one for each seat), and then trying to
allocate voters to each so that the case for the winner (according to
the Ranked Pairs method run in that constituency) is as strong as
possible, i.e. the choice of winner or winning order is as justified as
it can be.
When I last had this thought, I stopped early because I couldn't make
sure that it would indeed choose the optimum in each constituency; but
recently, I realized that if it can't, then single-winner Ranked Pairs
can't, either.
But that doesn't make a lot of sense unless I describe just what
single-winner RP's score/metric is, and how it maximizes it, and then
how it (perhaps) doesn't. So I'll do that first, then get to the PR
method afterwards.
Suppose we have a social ordering, A>B>C. Then both Kemeny and RP assign
a score to this ordering, that is a function of the pairwise victories
consistent with this ordering (in this case A>B, B>C, and A>C). Kemeny's
score is the sum of the strength of victories, while RP's is the value
of the strongest victory, ties broken by the value of the next
strongest, ties broken by the value of the third strongest, and so on.
Then both Kemeny and RP, in the absence of ties, calls an election by
producing the social ordering that maximizes its respective score
function. That is, Kemeny chooses the one whose sum of consistent
pairwise victories is maximized, and RP the one whose largest pairwise
victory is maximized, and among these, the one whose next largest
pairwise victory is maximized, and so on.
But if there are ties, then we're in trouble. The Ranked Pairs algorithm
works by starting at the strongest pairwise victory, locking that in,
then proceeding to the next strongest. This is a greedy approach, and it
maximizes the RP score when there are no ties. But if there's a tie,
then it might be that earlier choices close off later choices in ways
that we can't determine from the start.
E.g. suppose the defeat strengths are as follows, in sorted order by
strength:
C>A: 100
D>A: 99
A>B: 80
B>C: 80
B>D: 75
(something else): 60
...
First we admit C>A and D>A. Then we have a choice of either admitting
A>B or B>C; we can't admit both.
So suppose we admit A>B. Then we have {C,D}>A>B; admitting B>C would
produce a cycle, and so would B>D. So we skip, go to the something else,
and the score vector is [100, 99, 80, 60, ...].
On the other hand, suppose we admit B>C. Then we have D>A and B>C>A. Now
we can admit B>D and get B>D>C>A with score vector [100, 99, 80, 75, 60,
...], which is better by the RP metric.
But the problem here is that when we were considering how to break the
strength-80 tie, we didn't know which would close off the ability to
admit B>D. So ordinary RP only maximizes the score vector in the absence
of ties.
So now, the MAM/RP-based method. The idea is this: through linear
programming we can find what's the greatest strength pairwise victory
supported by a Hare quota of the voters without having to determine who
the voters is.
To maximize the RP score in a constituency (subject to the caveats
above), we keep a list of pairwise victories that we've affirmed, just
like in ordinary Ranked Pairs. Then for each unaffirmed pairwise
victory, we use LP to determine which Hare quota consistent with what
we've already locked will maximize the strength of that victory; and
then we choose the one that doesn't produce a cycle, and that has
maximum strength.
For instance, suppose the Hare quota is 1000. When starting out, we find
that it's possible to choose a Hare quota of voters so that everybody
prefers A>B. So we lock A>B.
Then we try every other pairwise preference, and in essence for X>Y ask:
what's the largest support you can give X>Y by choosing a Hare quota of
voters all of whom rank A>B?
Suppose B>C has largest such support 850, while C>D has largest support
900. Okay, then we admit C>D.
Then we ask for all other pairwise preferences X>Y: what's the largest
support you can give X>Y by choosing a Hare quota of voters, all of whom
rank A>B, and 900 of whom rank C>D?
And so on. As we admit more and more pairwise preferences, the Hare
quota's worth of voters becomes increasingly more distinct until the
constituency is uniquely defined. At that point we assign the RP winner
to this constituency, remove these voters (and the winner) from the
election, and repeat with the next constituency.
But the tie problem shows up here, too. What should we do if the number
of seats is rather large so that (for the first step) it's easy to find
a Hare quota all of whom support X>Y, no matter who X and Y are? We have
to choose one of them, but we can't be sure we'll maximize the RP score
because of the path dependence problem I mentioned. So that's where I
got stuck.
But then I realized that single winner RP has this problem too! So it
shouldn't be a strike against the legitimacy of the RP procedure; we
just need to break the tie somehow. Choosing the pairwise preference
with most total support over the whole electorate is probably as good a
way as any.
So this multiwinner method should be implementable, although it would be
very slow: for each step, we'd have to go through every pairwise
preference to find the one with maximum attainable support; and worst
case, we have to go through n^2 steps. That makes for O(n^4) calls to
the LP solver, which, though it's polynomial in the number of voters,
may have a very high polynomial degree indeed.
Perhaps there is some dynamic programming trick that could be used
instead of linear programming, but I don't see it at the moment.
And perhaps there is a way to look ahead and actually maximize the RP
score, but I doubt it is. I suspect it's related to that determining if
candidate X can be made an RP winner by breaking ties in a particular
way -- is NP-complete.
-km
Election-Methods mailing list - see https://electorama.com/em for list info
Kristofer posted some thoughts about Hare-clustered multi-member PR
which I don't understand.
Would I be right in thinking that the aim of multi-member PR, under a
spatial model, is to elect a set of candidates for a constituency such
that the average distance from a voter to the nearest candidate is
minimised? In this case, does it not follow that two candidates who are
close to each other ("belong to the same party") will ideally never be
elected?
CJC
On 10.02.2022 10:23, Colin Champion wrote:
Kristofer posted some thoughts about Hare-clustered multi-member PR
which I don't understand.
Would I be right in thinking that the aim of multi-member PR, under a
spatial model, is to elect a set of candidates for a constituency such
that the average distance from a voter to the nearest candidate is
minimised? In this case, does it not follow that two candidates who are
close to each other ("belong to the same party") will ideally never be
elected?
The STV notion of proportionality is basically: if more than a Droop
quota all prefer a certain group of candidates (even if they do so in a
different order) to everybody else, then one candidate from that group
must be elected.
So this is different from your minimization concept, because suppose we
have this election:
150: A>B>C
149: B>A>C
1: C>A>B
with two to elect. The Droop quota is 100 voters. Then the ABC bloc gets
one candidate, and the BAC bloc also gets one, so A and B are elected,
even if the C voter is very far from both A and B. Just like ranked
voting has no concept of strength of preference, nor does the Droop
proportionality criterion.
The Hare notion is more explicitly about giving each group of 1/n voters
"its own candidate". There's a concept of the core that I was thinking
of writing a post about, but I haven't got around to it yet, that makes
this idea more concrete.
But for simplicity, suppose that you have an 1D spatial model with
voters uniformly distributed over the line [-1..1]. Then the Hare notion
is that the group of voters corresponding to the negative region of the
line get one candidate, and the group of voters corresponding to the
positive get the other one. Just which negative value candidate and
which positive value candidate will be elected is up to the election
method, but it will be one positive and one negative (if such candidates
exist).
With the Hare quota notion, each group of 1/n voters directly decide who
will be elected and get "their own" representative. With the Droop
quota, there are s+1 Droop quotas for s seats. s of these quotas get to
choose what faction will be elected (as in the example above); the final
Droop quota doesn't get its own representative but instead gets to
influence what candidate is chosen from each winner faction.
Droop quota methods are usually less partisan (more consensus-based)
than Hare quota ones. The comparison is similar to D'Hondt vs Sainte-Lague.
To answer your question: in a partisan, suppose there are enough seats
that the scenario I mention is possible, and 30% of the voters vote for
party X, then even if party X's candidates are all located at the exact
same spot, the fact that 30% of the voters vote for X first means
they're all closer to X than anywhere else. So 30% of the seats will be
filled with party X clones.
But if the candidate distribution is a bit more fuzzy, then say, a green
voter who usually likes party X might favor some candidate from party Y
because this candidate is particularly green even if Y isn't a green
party. Then X won't get 30% of the vote: candidates closer to the voters
may benefit from voters who would vote for other parties if they were to
vote party line.
So it doesn't necessarily follow that party clones will never be
elected. That depends on the composition of the electorate.
-km
Kristofer - thanks for your reply. Maybe I'm missing something - I'm
afraid I don't really understand PR. If you have a model of the
electoral process, you can ask what result it should ideally produce for
a given set of candidates, but you can also ask what will be the ideal
result if the candidates are such as allow the voters to express their
real attributes - their level of class selfishness or sense of social
justice or greenness or jingoism or whatever. When I read about PR, I
get the impression that a division into parties is assumed as
pre-existing, whereas when people talk about single-member voting they
discuss the effect of the electoral system on the party structure. I
feel that this latter factor needs to be taken into account.
Suppose that the voters are uniformly distributed over a circular disc
centred on the origin. Then if a single candidate is elected, he should
be at O. If there are two seats, the winning candidates can be at
(-0.4,0) and (+0.4,0). This corresponds to your own 1-D account if the
parties are left and right, but they could also be up and down.
If there are 3 seats, then the winners should be 120 degrees apart. A
feature which ties this to single-member elections is that when we
divide the circle into three 120-degree segments, the ideal candidate
for each segment is the one whose average distance to voters in the
segment is least - ie. the ideal single-member winner. I understood your
original post as partitioning voters into clusters based on their
rankings of candidates, and then electing one candidate per partition.
But I understood your partitioning as derived from a given set of
candidates rather than asking what set of candidates may lead to the
best result.
If there are 5 seats, perhaps the ideal set of winners is a candidate at
O and four other candidates 90 degrees apart. When the number of seats
is large, we pack them like oranges in a crate.
CJC
On 10.02.2022 12:33, Colin Champion wrote:
Kristofer - thanks for your reply. Maybe I'm missing something - I'm
afraid I don't really understand PR. If you have a model of the
electoral process, you can ask what result it should ideally produce for
a given set of candidates, but you can also ask what will be the ideal
result if the candidates are such as allow the voters to express their
real attributes - their level of class selfishness or sense of social
justice or greenness or jingoism or whatever. When I read about PR, I
get the impression that a division into parties is assumed as
pre-existing, whereas when people talk about single-member voting they
discuss the effect of the electoral system on the party structure. I
feel that this latter factor needs to be taken into account.
Party list methods assume there's a party structure. I don't think
candidate-based PR (like STV) does.
Suppose that the voters are uniformly distributed over a circular disc
centred on the origin. Then if a single candidate is elected, he should
be at O. If there are two seats, the winning candidates can be at
(-0.4,0) and (+0.4,0). This corresponds to your own 1-D account if the
parties are left and right, but they could also be up and down.
Right; all I was saying is that for the method to choose candidates at
the optimum positions, there must be candidates there. They don't have
to be members of a party, but that's usually how it goes.
So if the voters are uniformly distributed over a disc, then if there
exist two candidates that are at opposite sides of the disc, they should
be elected.
But Hare or Droop proportionality gives additional leeway. Suppose that
the voters are distributed uniformly on r=1. There are some candidates
who are properly placed (say at theta = 0 and theta = pi). But now
suppose there are three candidates at each angle: one at r=1.2, one at
r=1.0, and another at r=0.8. The proportionality criteria only say that
one candidate at theta=0 and one at theta=pi should be elected, for a
two-seat election. Depending on the voting method, it might be
"consensus based" (choose r=0.8), neutral (r=1) or polarized (r=1.2).
If there are 3 seats, then the winners should be 120 degrees apart. A
feature which ties this to single-member elections is that when we
divide the circle into three 120-degree segments, the ideal candidate
for each segment is the one whose average distance to voters in the
segment is least - ie. the ideal single-member winner. I understood your
original post as partitioning voters into clusters based on their
rankings of candidates, and then electing one candidate per partition.
But I understood your partitioning as derived from a given set of
candidates rather than asking what set of candidates may lead to the
best result.
In a way, yes. We're always restricted to what candidates are running.
Let's consider the circular model with two winners, and suppose RP
ranking captures the distance in this space reasonably well (for the
sake of the argument). Then my clustering method aims to slice the space
into two regions containing the same number of voters, and perform this
slice in such a way that for each slice, the voters' distance to their
closest candidate is minimized, under the constraint that no two slices
can have the same candidate as a winner.
Note here that the restriction that the slices must contain an equal
number of voters is vital. This is what leads to proportional
representation.[1]
If the viable candidates are at theta=0 and theta=pi, there's no
problem. We cut a vertical line separating the voters who are closer to
0 from those who are closer to pi, and then they get their preferred option.
But now suppose the two viable candidates are at theta=0.1 and
theta=-0.1 (add a bunch of other candidates at infinity so there are
more candidates than seats). We still have to choose two slices so that
the distances to the candidates are minimized, but now there are no good
options. The bisector pretty much has to go through theta=0, and then
one slice gets the theta=0.1 candidate and the other one gets the
theta=-0.1 one. The difference here is that the voters' mean distance to
their assigned candidate is much higher than in the "nice" example above.
So in a way, the voting method depends on the candidates. It chooses to
fit the slices so that the case for selecting just this candidate on
behalf of the slice's voters is as strong as possible. But all the
voters still need to be represented somehow, so their choices make up
just what a good fit is.
In RP mechanics, the clustering method looks for some pairwise
preference that's strong within some Hare quota, and locks this pairwise
preference in. This is similar to finding a bunch of voters who are
close to some candidate (or technically speaking, prefers some candidate
to some other candidate). It depends on the candidates because those are
the options.
But it makes no judgement about just what Hare quota to look for, it's
just looking for some Hare quota that feels strongly about the
pairwise preferences. So it's not fitting the voters to preset winners:
who the first winner is is a result of just what voters end up being
part of the strong-opinion Hare quota that the method finds.
If there are 5 seats, perhaps the ideal set of winners is a candidate at
O and four other candidates 90 degrees apart. When the number of seats
is large, we pack them like oranges in a crate.
Yes, in the limit of number of seats (and candidates) going to number of
voters, each voter chooses the candidate closest to himself. Or in
another way: if there are as many seats as voters, and each voter votes
for himself first, then the assembly becomes just ordinary direct democracy.
-km
[1] If this restriction didn't exist, then an election of the type:
1000: A1>A2>A3>A4
1: B
1: C
for three seats -- with all the voters clumped very close around their
respective candidates -- would pick A1, B, and C, because the A-voters
are all satisfied by A and could thus be grouped into a single slice,
and then the B and C voters would be satisfied only by their own
candidates winning. This is a minmax outcome, not a proportional
outcome, see e.g. https://electowiki.org/wiki/Minimax_approval. Methods
of that type can be used for Security Council type elections where a
single veto is enough.
On 09.02.2022 20:51, Richard, the VoteFair guy wrote:
In the new "Hare clustering MAM-based PR, and a tie problem" thread,
Kristofer Munsterhjelm wrote:
.... It's based around the idea of making a
number of virtual constituencies (one for each seat), and
then trying to allocate voters to each so that the case for
the winner (according to the Ranked Pairs method run in
that constituency) is as strong as possible, i.e. the
choice of winner or winning order is as justified as
it can be.
...
Then both Kemeny and RP, in the absence of ties, calls an election by
producing the social ordering that maximizes its respective score
function. That is, Kemeny chooses the one whose sum of consistent
pairwise victories is maximized, and RP the one whose largest pairwise
victory is maximized, and among these, the one whose next largest
pairwise victory is maximized, and so on.
Kristofer, what you're describing sounds similar to the STV version of
VoteFair Representation ranking:
https://electowiki.org/wiki/VoteFair_representation_ranking#STV_version
It is, sort of, but I would say that there are some differences.
-
Your method is house monotone. Since the first seat is chosen with a
Condorcet method, it must therefore fail Droop proportionality, see
https://electowiki.org/wiki/Left,_Center,_Right. -
The deweighting method seems a bit ad hoc, where it tries to reduce
the influence of voters who got the candidate they wanted, but uses a
heuristic to determine just who that is. In contrast, my method doesn't
make up its mind about who the first group of voters (who deserve the
first candidate) is, until it's done finding a candidate for that group;
and once it has done so, it knows exactly who they are.
Your method seems more consistent with the Droop quota than the Hare
quota, as in: mine tries to find a group of voters, then remove them,
while yours tries to find a group of voters and then reweight them (like
ordinary STV).
My method could be made Droop-style, and this would (I think) help
attenuate the tie problems. Instead of the LP step choosing a Hare quota
that's consistent with the defeat magnitudes locked in, it would choose
to magnify a group of voters' weights so that a Droop quota becomes a
majority. Then the mutual majority criterion of original RP (that Kemeny
also passes, by the way) would translate directly to the Droop
proportionality criterion.
Let's say every voter's weight is 1 before we do reweighting, and there
are v voters in total. Then the Droop quota is v/(s+1), so suppose
everybody in this Droop quota gets a weight w, and everybody else
retains the weight of 1. Then we have
wv/(s+1) = 1/2 (wv/(s+1) + (v - v/(s+1))) majority blowup
which gives the solution w=s.
So the LP would set: let each voter's weight be between 1 and s, so that
the total weight distributed is exactly 2sv/(s+1), and set the weights
so that the given pairwise preference's strength is maximized. This is
an additive weights solution, similar to Warren STV. Presumably
multiplicative weights (like Meek) are also possible, but this post is
already long enough :-)
This attenuates tie problems because now the unweighted ballots have
some say in breaking the tie; the chance of a tie would be low even with
very small virtual constituencies because (in effect) the ballots who
are not participating help drag the outcome in their direction.
I added this section to Electowiki recently because there is growing
interest in using STV to elect city councils, yet STV is overly
simplistic, and has flaws similar to IRV flaws (especially ignoring
valid ranking data that's very relevant).
This STV version of VoteFair Representation ranking extends the two-seat
version of it that I designed for partisan elections. The result is an
STV-like non-partisan method.
Of course it's based on the Kemeny method rather than Ranked Pairs.
That's my bias for the reason you mention, namely that locking in a
pairwise win can block additional info. This is similar to the way IRV
blocks lower-ranked preference info from being looked at.
Well, if you're willing to pay the NP tax, then Ranked Pairs can also be
made to optimize its particular metric.
As for Kemeny vs RP, I would say that "taking into account every
candidate" sounds good, but if it's not done with proper insight, the
method can get confused about how much information is available to each
candidate.
That's how Borda gets its teaming incentive: by cloning A, you make the
"weight of evidence" that's about A stronger, relative to the other
candidates, and so the method gets pulled in the direction of A. Because
Kemeny takes the sum of preferences, it's also vulnerable to this sort
of confusion. And sure enough, it's not cloneproof.
In any case, the idea of my method is to generalize Condorcet methods
like RP to proportional representation in a way that's clearly based
around that Condorcet method and not on a candidate elimination method
(like IRV-based STV is). It doesn't completely satisfy this as winners
are still eliminated after winning, and so probably isn't monotone, but
there are no remnants of IRV left. And unlike Schulze STV etc., it's
polynomial time -- barely.
(Now there's a thought: don't eliminate any candidates, but skip past
already elected candidates when choosing the winner for the kth
constituency based on its RP social ordering. It would probably still be
non-monotone, but it should be better behaved.)
-km
El jue., 10 de feb. de 2022 1:23 a. m., Colin Champion
colin.champion@routemaster.app escribió:
Kristofer posted some thoughts about Hare-clustered multi-member PR
which I don't understand.
Would I be right in thinking that the aim of multi-member PR, under a
spatial model, is to elect a set of candidates for a constituency such
that the average distance from a voter to the nearest candidate is
minimised?
I thing tour variational principle is on the right track... it generalizes
the median voter idea as the one whose average distance to the other
voters is minimized.
But the objective function needs to put more pressure on equalizing the
size of the constituencies of the respective representatives.
To that end I suggest electing the slate of candidates that minimizes the
following quotient...
The average distance of the constituents to their representatives...
Divided by
The geometric mean of the cardinalities of the respective constituencies.
In this case, does it not follow that two candidates who are
close to each other ("belong to the same party") will ideally never be
elected?
CJC
Election-Methods mailing list - see https://electorama.com/em for list
info
I don't think this quite works. Suppose that there are 6 seats and that
2/3 of the voters are concentrated at a point X with 1/3 at Y. The best
result is to elect 4 candidates at X and 2 at Y, but neither my metric
nor yours cares what the balance is between candidates elected at the
two points (assuming that 'their representatives' means 'their closest
representatives').
Maybe it's not so easy.
CJC
On 11/02/2022 07:29, Forest Simmons wrote:
But the objective function needs to put more pressure on equalizing
the size of the constituencies of the respective representatives.
To that end I suggest electing the slate of candidates that minimizes
the following quotient...
The average distance of the constituents to their representatives...
Divided by
The geometric mean of the cardinalities of the respective constituencies.
On 11.02.2022 16:09, Colin Champion wrote:
I don't think this quite works. Suppose that there are 6 seats and that
2/3 of the voters are concentrated at a point X with 1/3 at Y. The best
result is to elect 4 candidates at X and 2 at Y, but neither my metric
nor yours cares what the balance is between candidates elected at the
two points (assuming that 'their representatives' means 'their closest
representatives').
Maybe it's not so easy.
You can of course make it a hard constraint. That's what Monroe's method
does:
Let f(v, c) be some function that produces a score for voter v's
preference for candidate c, where greater is better.
Assign (possibly fractional) voters to candidates so that the number of
voters assigned to each candidate is equal, the number of candidates
with some voters assigned is equal to the number of seats, and so that
the sum of f for each voter and his assigned candidate is maximized.
Condorcet variants should be possible, e.g. let X_1 and X_2 be some set
of candidates with cardinality s, then X_1>X_2 is equal to the number of
voters who strictly prefer the assignment in X_1 to the one in X_2.
Trying to engineer the optimization function so that it achieves PR
without needing explicit constraints has usually been the domain of
cardinal advocates because ordinal ballots don't provide any strength of
preference information. See e.g. https://rangevoting.org/QualityMulti.html.
-km