[EM] Framework for adapting Single Winner methods to Multiwinner PR

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

[EM] Framework for adapting Single Winner methods to Multiwinner PR

Forest Simmons
We to things:

1. A standard way of converting rankings to pseudo-ratings.
2. A standard way of identifying "runner-ups" in single winner elections.

For now suppose that these problems have been taken care of. I made some suggestions in previous messages, but they are only tentative, so don't stop thinking!

Our main heuristic for the method is this: when a candidate has won a round in the election and thereby qualified to be seated with the other winners [there was a brief typo that said "sinners" instead of "winners."] no ballot that strictly preferred the runner-up to the winner should be penalized in any degree, and even a ballot that ranked the winner ahead of or equal to the runner-up, should only be de-weighted in fair accord with the level of support indicated by the rating or pseudo rating of that winner on the ballot.

So if your ballot rates the winner at 100 percent, then it will suffer the max de-weighting for that round.  If your ballot rates the winner at zero, it dodges the de-weighting bullet unscathed for that round.  If your ballot rates the winner at 50%, then the de-weighting depends on whether or not the runner-up is ranked strictly ahead of the winner or not. If so, there is no de-weightiing; if not, the de-weight effect is half of the full possibility.

That's the idea. Now for a few details. The de-weighting scheme is based on what we could call "satisfaction," or "relief" or "blame" depending on your point of view.  The (additive) increment delta to the "satisfaction" S of a particular ballot B by a round of the election with winner W and runner-up R is computed as follows:

If R is ranked strictly above W, on ballot B, then delta is zero.
Else delta is the (pseudo) rating of W on ballot B.

At some stage, let S be the cumulative satisfaction on one particular ballot from the results of the previous stages, i.e. the sum over all of the winners so far of the ballot satisfaction increments for each of them.  Then the weight of that ballot in the next round is 1/(1+S).

That's it!

Why is this proportional?

Because in a "colour (or color) election," which is one standard test case for proportionality, the voters will vote only at the extremes of equal top and equal bottom, AND in this case the method precisely reduces to Sequential Proportional Approval Voting (SPAV) which is known to satisfy the color criterion (specifically with D'Hondt quotas). 

BTW this is true no matter what method may be used to convert rankings to pseudo-ratings as long as it leaves equal top at the top, and equal bottom at the bottom. 

Nor does the choice of runner-up affect this result, since no matter who the runner-up may be, if the winner is top rated then the increment delta will be one, and if the winner is bottom rated the increment will be zero in accordance with the recipe given above (and repeated here so you can check it):

If R is ranked strictly above W, on ballot B, then delta is zero.
Else delta is the (pseudo) rating of W on ballot B.

In particular, if W is rated at zero, in either case (R > W or both bottom rated), delta will be zero.

It took a few sleepless nights to get this just right before too many EM enthusiasts started exposing the mistakes and weaknesses of the first version. Pressure of pride!  It comes before the fall, but it can also hasten the time of face-saving redemption!





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

Re: [EM] Framework for adapting Single Winner methods to Multiwinner PR

Ted Stern
I encountered another PR method recently that I think is worth adding to the discussion:


In other words, for each candidate, determine the quota threshold rating using

score_total = 0
approve_total = 0
threshold_surplus = 0
threshold_margin = 0
for threshold_rating in maxscore:0:-1 :
   score_total_minus_1 = score_total
   score_total += rating * score[threshold_rating]

   approve_total_minus_1 = approve_total
   approve_total += score[threshold_rating]

   if ( approval_total > quota ) then:
        threshold_surplus = approve_total - quota
        threshold_margin = quota - approve_total_minus_1
        break

end for loop

threshold_score = score_total_minus_1 + threshold_margin * threshold_rating

If the candidate's threshold_rating is > 0, then that candidate gets a composite rating of

    (1, threshold_score/quota, approve_total)

Otherwise, the candidate gets a composite rating of

   (0, threshold_score / quota, approve_total)

Then sort these composite ratings in descending order.

To reweight ballots, Parker Friedland (the originator of the method) uses a relatively complex method of setting ballots giving the winner a rating above threshold_rating a weight of zero, while multiplying the ballots scoring the winner exactly at the threshold_rating by a factor of

   factor = ( 1 - (threshold_margin / score[threshold_rating]) )

(or equivalently, factor = threshold_surplus / score[threshold_rating] )

Alternatively, one could use a simpler factor for all ballots at and above the rating, 

    factor = ( 1 - (quota / approve_total) )

The reason I bring this up is that if you use a Droop quota of  N_ballots / (M_seats + 1), this method isn't really what I would look at as a good single-winner method.  Instead, it is trying to find the strongest preference in the top quota of voters for each candidate, *NOT* the strongest preference of the total remaining weight of ballots.  But I think this is more of what one is trying to achieve for all but the last seat of the multiwinner election, and certainly if you are are trying to satisfy Droop proportionality.

If one used a Hare quota, this method reduces to Score for the last seat.  But I think it might be just as reasonable to use a Condorcet method such as Score Sorted Margins for that last seat.


On Sat, Jan 25, 2020 at 5:15 PM Forest Simmons <[hidden email]> wrote:
We to things:

1. A standard way of converting rankings to pseudo-ratings.
2. A standard way of identifying "runner-ups" in single winner elections.

For now suppose that these problems have been taken care of. I made some suggestions in previous messages, but they are only tentative, so don't stop thinking!

Our main heuristic for the method is this: when a candidate has won a round in the election and thereby qualified to be seated with the other winners [there was a brief typo that said "sinners" instead of "winners."] no ballot that strictly preferred the runner-up to the winner should be penalized in any degree, and even a ballot that ranked the winner ahead of or equal to the runner-up, should only be de-weighted in fair accord with the level of support indicated by the rating or pseudo rating of that winner on the ballot.

So if your ballot rates the winner at 100 percent, then it will suffer the max de-weighting for that round.  If your ballot rates the winner at zero, it dodges the de-weighting bullet unscathed for that round.  If your ballot rates the winner at 50%, then the de-weighting depends on whether or not the runner-up is ranked strictly ahead of the winner or not. If so, there is no de-weightiing; if not, the de-weight effect is half of the full possibility.

That's the idea. Now for a few details. The de-weighting scheme is based on what we could call "satisfaction," or "relief" or "blame" depending on your point of view.  The (additive) increment delta to the "satisfaction" S of a particular ballot B by a round of the election with winner W and runner-up R is computed as follows:

If R is ranked strictly above W, on ballot B, then delta is zero.
Else delta is the (pseudo) rating of W on ballot B.

At some stage, let S be the cumulative satisfaction on one particular ballot from the results of the previous stages, i.e. the sum over all of the winners so far of the ballot satisfaction increments for each of them.  Then the weight of that ballot in the next round is 1/(1+S).

That's it!

Why is this proportional?

Because in a "colour (or color) election," which is one standard test case for proportionality, the voters will vote only at the extremes of equal top and equal bottom, AND in this case the method precisely reduces to Sequential Proportional Approval Voting (SPAV) which is known to satisfy the color criterion (specifically with D'Hondt quotas). 

BTW this is true no matter what method may be used to convert rankings to pseudo-ratings as long as it leaves equal top at the top, and equal bottom at the bottom. 

Nor does the choice of runner-up affect this result, since no matter who the runner-up may be, if the winner is top rated then the increment delta will be one, and if the winner is bottom rated the increment will be zero in accordance with the recipe given above (and repeated here so you can check it):

If R is ranked strictly above W, on ballot B, then delta is zero.
Else delta is the (pseudo) rating of W on ballot B.

In particular, if W is rated at zero, in either case (R > W or both bottom rated), delta will be zero.

It took a few sleepless nights to get this just right before too many EM enthusiasts started exposing the mistakes and weaknesses of the first version. Pressure of pride!  It comes before the fall, but it can also hasten the time of face-saving redemption!




----
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] Framework for adapting Single Winner methods to Multiwinner PR

Kristofer Munsterhjelm-3
On 27/01/2020 21.26, Ted Stern wrote:

> I encountered another PR method recently that I think is worth adding to
> the discussion:
>
> https://electowiki.org/wiki/Sequential_Monroe
>
> In other words, for each candidate, determine the quota threshold rating
> using
>
> score_total = 0
> approve_total = 0
> threshold_surplus = 0
> threshold_margin = 0
> for threshold_rating in maxscore:0:-1 :
>    score_total_minus_1 = score_total
>    score_total += rating * score[threshold_rating]
>
>    approve_total_minus_1 = approve_total
>    approve_total += score[threshold_rating]
>
>    if ( approval_total > quota ) then:
>         threshold_surplus = approve_total - quota
>         threshold_margin = quota - approve_total_minus_1
>         break
>
> end for loop
>
> threshold_score = score_total_minus_1 + threshold_margin * threshold_rating
>
> If the candidate's threshold_rating is > 0, then that candidate gets a
> composite rating of
>
>     (1, threshold_score/quota, approve_total)
>
> Otherwise, the candidate gets a composite rating of
>
>    (0, threshold_score / quota, approve_total)
>
> Then sort these composite ratings in descending order.
>
> To reweight ballots, Parker Friedland (the originator of the method)
> uses a relatively complex method of setting ballots giving the winner a
> rating above threshold_rating a weight of zero, while multiplying the
> ballots scoring the winner exactly at the threshold_rating by a factor of
>
>    factor = ( 1 - (threshold_margin / score[threshold_rating]) )
>
> (or equivalently, factor = threshold_surplus / score[threshold_rating] )
>
> Alternatively, one could use a simpler factor for all ballots at and
> above the rating, 
>
>     factor = ( 1 - (quota / approve_total) )
>
> The reason I bring this up is that if you use a Droop quota of 
> N_ballots / (M_seats + 1), this method isn't really what I would look at
> as a good single-winner method.  Instead, it is trying to find the
> strongest preference in the top quota of voters for each candidate,
> *NOT* the strongest preference of the total remaining weight of
> ballots.  But I think this is more of what one is trying to achieve for
> all but the last seat of the multiwinner election, and certainly if you
> are are trying to satisfy Droop proportionality.
>
> If one used a Hare quota, this method reduces to Score for the last
> seat.  But I think it might be just as reasonable to use a Condorcet
> method such as Score Sorted Margins for that last seat.

The most obvious ways to do Range Monroe sequentially I can think of is:

1. Let the starting set of winners be empty.
2. For each possible non-winner candidate, provisionally put that
candidate in the set and maximize an assignment of voters to candidates
in the set so that at most a Hare quota of voters is assigned to each
candidate, and the total score of voters to the candidate assigned to
them is maximized. (This can be done using the Hungarian algorithm or
linear programming.) Voters who are not assigned to any candidate don't
contribute to the objective function.
3. Find the candidate that optimizes this measure and permanently
include him in the winner set. If you have as many winners as there are
seats, you're done, otherwise go to 1.

To do a house-monotone method, just have the quota be of the current
number of seats (including the provisional candidate) rather than the
numer of desired seats.

As for Hare vs Droop, I have the feeling that the distinction is...
under Hare, each representative represents the whole quota cluster;
under Droop, each representative is elected by a majority. The remaining
Droop quota doesn't get its own representative, but it influences who
that majority is through all the other seats. So Droop will tend to be
more majoritarian and Hare is more representative, but Droop is also
less fragmented. In party list systems, Droop usually translates to a
bonus to the largest party, but in a Condorcet PR system (or Range for
that matter), its majoritarian/utilitarian logic can bias all the seats
in the direction of the true center instead of just the strongest bloc.
----
Election-Methods mailing list - see https://electorama.com/em for list info