[EM] A sequential PR method based on Ranked Pairs

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

[EM] A sequential PR method based on Ranked Pairs

Kristofer Munsterhjelm-3
I can think of two PR methods based on Ranked Pairs. The first one is
just STV with RP loser elimination. It's relatively simple and more well
behaved than IRV STV due to RP's LIIA compliance. However, it prefers
the voting median, and thus is biased towards the consensus candidate
(the single-winner RP outcome).

Depending on your views on factional politics, you might consider that a
bug or a feature.

There's something to be said for the idea that in a kingmaker scenario,
the Condorcet winner breaks the tie; it would mitigate the pattern where
fringe parties hold a coalition ransom in a PR system. However, I can
also understand the PR purist perspective that such a bias dirties the
method.

So here's an idea for a sequential Ranked Pairs method that isn't
dirtied in such a way. It's based around a "blow-up" idea: that
increasing the weights of a Droop quota to a majority makes
majority-related properties hold for Droop -- e.g. it turns mutual
majority into the DPC.

The remaining voters (whose weights are attenuated) have an influence on
the outcome, so it's not like Monroe or the Hare quota where voters
outside of the bloc in question have no effect on the representative of
that bloc.

The procedure works as follows:

For each pairwise preference that hasn't been locked in, find a Droop
quota of voters that can be blown up (reweighted) to a majority so that
the support for that pairwise preference is maximized. Then lock in the
pairwise preference that attains the greatest maximum, and that won't
conflict with preferences that are already locked in. Repeat until you
have an unambiguous order, like RP itself. Elect the winner and
eliminate the Droop quota's worth of voters who were blown up to make
that candidate win.

Like my Bucklin method, the method itself is agnostic to what voters
make up the Droop quota until it's determined who the winner is. (Some
thoughts about this after the example.)

An example:

32: L>C>R
31: R>C>L
26: C>R>L
 1: C>L>R

two to elect. The Droop quota is 30 voters.

I choose this one because the DPC forces L and R to be elected, but the
Condorcet winner is C. In addition, both L and R directly exceed a Droop
quota, so it'll show how the method breaks the tie between the two.

First pairwise preference: Since nothing has been locked in yet, the
pairwise preference with the greatest blown-up support must be the
pairwise preference with the greatest support before any blow-up. That
is C>R.

The maximum blown-up support for C>R is attained by e.g. blowing up 26
C>R>L voters and four L>C>R voters. The support is then 45 (the Droop
quota blown up to half the voters) plus 21.75 (29 out of the 60 other
voters prefer C>R, but the 60 other voters' weights have been shrunk to
45, hence 29 * 45/60 = 21.75); in total 66.75.

Second pairwise preference: now we have to try them all. The objective
is to find a pairwise preference with maximum support among a Droop
quota's worth of voters, subject to that the C>R support when that Droop
quota is blown up is 66.75.

So take them in order:
        C>L: The C>R constraint can be satisfied by blowing up 26 C>R>L voters,
one C>L>R voter, and three L>C>R voters. There aren't enough C>L voters
to fill the whole Droop quota while also keeping the C>R support at its
maximum. Hence the C>L support is 27 of the 30 blown up to 45, i.e.
(27/30 * 45) = 40.5, plus the C>L voters outside: 31 * 45/60 = 23.25, in
total 63.75.
        C>R: (already locked in)

        R>C: Can't be locked in no matter what, because it contradicts C>R.
        R>L: The C>R constraint can be satisfied by blowing up 30 of the 31
voters who prefer C>R>L. That gives a full support of 45 from the
blown-up group, plus 27 voters outside, reweighted down: 45 + 27*45/60 =
65.25.

        L>C: The C>R constraint can be satisfied by blowing up 30 of the 32
voters who prefer L>C>R. That gives a full support of 45 inside, and 28
outside, reweighted down: 45 + 28*45/60 = 66.
        L>R: The C>R constraint can be satisfied by blowing up 30 of the 32
voters who prefer L>C>R. But that's about it: the support is 45 from
that group, plus the three voters outside (two L>C>R voters and one
C>L>R voter): 45 + 3*45/60 = 47.25

So L>C is the winning pairwise preference and is locked. (Note that in
the example, the Droop quota of voters it considered blowing up for C>R
differed from the one it considered blowing up for L>C.)

From these two locked preferences, we can get a full ordering. It is
L>C>R, so the system elects L and removes 30 of the L>C>R voters.

The second seat election is thus:
 2: C>R
31: R>C
26: C>R
 1: C>R

Since it's the last seat, no complex calculations are needed, just
ordinary Ranked Pairs. And since R is the majority winner of that
election, it gets the second seat.

So the outcome is {L, R}, as desired.



The method doesn't know just what Droop quota to blow up until it's done
setting the preferences. This gives it some flexibility but also makes
it rather hard to implement. I'd think the "natural" algorithm would be
linear programming, but there's a problem. The linear programming matrix
would have a number of nonzeroes equal to the number of voters times
pairwise preferences, and have a dimension equal to the number of voters
squared. If the number of voters is in the millions, it's going to be
very hard to determine the outcome.

I constructed this method in an attempt to find something that wouldn't
have exponential complexity wrt the number of candidates the way CPO-STV
and Schulze STV has. But the accomplishment kinda fades when the
constant factors are so extreme.

Maybe I can think of a better algorithm later. Any ideas? :-)
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] A sequential PR method based on Ranked Pairs

Richard Lung
 
Another algorithm is FAB STV.
Science is measurement. And it measures a complete dimension of choice. That's its scientific significance. The method uses all the preferential information, including abstentions. This means that no candidates are either elected or excluded, before the count is complete, so no preferential information is lost. However, that requires a binomial count, rational counts, both of election and exclusion.
This removes irrationalities of ad hoc exclusion procedures. Tho, their effect may be exaggerated, in conventional STV.

Richard Lung.



On 3 Feb 2021, at 11:32 am, Kristofer Munsterhjelm <[hidden email]> wrote:

I can think of two PR methods based on Ranked Pairs. The first one is
just STV with RP loser elimination. It's relatively simple and more well
behaved than IRV STV due to RP's LIIA compliance. However, it prefers
the voting median, and thus is biased towards the consensus candidate
(the single-winner RP outcome).

Depending on your views on factional politics, you might consider that a
bug or a feature.

There's something to be said for the idea that in a kingmaker scenario,
the Condorcet winner breaks the tie; it would mitigate the pattern where
fringe parties hold a coalition ransom in a PR system. However, I can
also understand the PR purist perspective that such a bias dirties the
method.

So here's an idea for a sequential Ranked Pairs method that isn't
dirtied in such a way. It's based around a "blow-up" idea: that
increasing the weights of a Droop quota to a majority makes
majority-related properties hold for Droop -- e.g. it turns mutual
majority into the DPC.

The remaining voters (whose weights are attenuated) have an influence on
the outcome, so it's not like Monroe or the Hare quota where voters
outside of the bloc in question have no effect on the representative of
that bloc.

The procedure works as follows:

For each pairwise preference that hasn't been locked in, find a Droop
quota of voters that can be blown up (reweighted) to a majority so that
the support for that pairwise preference is maximized. Then lock in the
pairwise preference that attains the greatest maximum, and that won't
conflict with preferences that are already locked in. Repeat until you
have an unambiguous order, like RP itself. Elect the winner and
eliminate the Droop quota's worth of voters who were blown up to make
that candidate win.

Like my Bucklin method, the method itself is agnostic to what voters
make up the Droop quota until it's determined who the winner is. (Some
thoughts about this after the example.)

An example:

32: L>C>R
31: R>C>L
26: C>R>L
1: C>L>R

two to elect. The Droop quota is 30 voters.

I choose this one because the DPC forces L and R to be elected, but the
Condorcet winner is C. In addition, both L and R directly exceed a Droop
quota, so it'll show how the method breaks the tie between the two.

First pairwise preference: Since nothing has been locked in yet, the
pairwise preference with the greatest blown-up support must be the
pairwise preference with the greatest support before any blow-up. That
is C>R.

The maximum blown-up support for C>R is attained by e.g. blowing up 26
C>R>L voters and four L>C>R voters. The support is then 45 (the Droop
quota blown up to half the voters) plus 21.75 (29 out of the 60 other
voters prefer C>R, but the 60 other voters' weights have been shrunk to
45, hence 29 * 45/60 = 21.75); in total 66.75.

Second pairwise preference: now we have to try them all. The objective
is to find a pairwise preference with maximum support among a Droop
quota's worth of voters, subject to that the C>R support when that Droop
quota is blown up is 66.75.

So take them in order:
   C>L: The C>R constraint can be satisfied by blowing up 26 C>R>L voters,
one C>L>R voter, and three L>C>R voters. There aren't enough C>L voters
to fill the whole Droop quota while also keeping the C>R support at its
maximum. Hence the C>L support is 27 of the 30 blown up to 45, i.e.
(27/30 * 45) = 40.5, plus the C>L voters outside: 31 * 45/60 = 23.25, in
total 63.75.
   C>R: (already locked in)

   R>C: Can't be locked in no matter what, because it contradicts C>R.
   R>L: The C>R constraint can be satisfied by blowing up 30 of the 31
voters who prefer C>R>L. That gives a full support of 45 from the
blown-up group, plus 27 voters outside, reweighted down: 45 + 27*45/60 =
65.25.

   L>C: The C>R constraint can be satisfied by blowing up 30 of the 32
voters who prefer L>C>R. That gives a full support of 45 inside, and 28
outside, reweighted down: 45 + 28*45/60 = 66.
   L>R: The C>R constraint can be satisfied by blowing up 30 of the 32
voters who prefer L>C>R. But that's about it: the support is 45 from
that group, plus the three voters outside (two L>C>R voters and one
C>L>R voter): 45 + 3*45/60 = 47.25

So L>C is the winning pairwise preference and is locked. (Note that in
the example, the Droop quota of voters it considered blowing up for C>R
differed from the one it considered blowing up for L>C.)

From these two locked preferences, we can get a full ordering. It is
L>C>R, so the system elects L and removes 30 of the L>C>R voters.

The second seat election is thus:
2: C>R
31: R>C
26: C>R
1: C>R

Since it's the last seat, no complex calculations are needed, just
ordinary Ranked Pairs. And since R is the majority winner of that
election, it gets the second seat.

So the outcome is {L, R}, as desired.



The method doesn't know just what Droop quota to blow up until it's done
setting the preferences. This gives it some flexibility but also makes
it rather hard to implement. I'd think the "natural" algorithm would be
linear programming, but there's a problem. The linear programming matrix
would have a number of nonzeroes equal to the number of voters times
pairwise preferences, and have a dimension equal to the number of voters
squared. If the number of voters is in the millions, it's going to be
very hard to determine the outcome.

I constructed this method in an attempt to find something that wouldn't
have exponential complexity wrt the number of candidates the way CPO-STV
and Schulze STV has. But the accomplishment kinda fades when the
constant factors are so extreme.

Maybe I can think of a better algorithm later. Any ideas? :-)
----
Election-Methods mailing list - see https://electorama.com/em for list info
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] A sequential PR method based on Ranked Pairs

Kristofer Munsterhjelm-3
On 03/02/2021 20.34, Richard Lung wrote:

>  
> Another algorithm is FAB STV.
> Science is measurement. And it measures a complete dimension of
> choice. That's its scientific significance. The method uses all the
> preferential information, including abstentions. This means that no
> candidates are either elected or excluded, before the count is complete,
> so no preferential information is lost. However, that requires a
> binomial count, rational counts, both of election and exclusion.
> This removes irrationalities of ad hoc exclusion procedures. Tho,
> their effect may be exaggerated, in conventional STV.

It's hard to reason about a method without having an implementation of
it. Do you have some source code or proposed legislative language that
implements FAB STV?

-km
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] A sequential PR method based on Ranked Pairs

Richard Lung

There's various summaries, as well as a full procedural explanation,
with worked example, in the second part of my e-book, FAB STV: Four
Averages Binomial Single Transferable Vote.

The algorithm is not translated into other languages, machine or human,
both being beyond me. I can answer questions about it, tho.

https://www.smashwords.com/books/view/806030

RL


On 04/02/2021 09:36, Kristofer Munsterhjelm wrote:

> On 03/02/2021 20.34, Richard Lung wrote:
>>  
>> Another algorithm is FAB STV.
>> Science is measurement. And it measures a complete dimension of
>> choice. That's its scientific significance. The method uses all the
>> preferential information, including abstentions. This means that no
>> candidates are either elected or excluded, before the count is complete,
>> so no preferential information is lost. However, that requires a
>> binomial count, rational counts, both of election and exclusion.
>> This removes irrationalities of ad hoc exclusion procedures. Tho,
>> their effect may be exaggerated, in conventional STV.
> It's hard to reason about a method without having an implementation of
> it. Do you have some source code or proposed legislative language that
> implements FAB STV?
>
> -km
----
Election-Methods mailing list - see https://electorama.com/em for list info