[EM] A Framework for adapting single winner methods to the task of Proportional Representation in multi winner districts

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

[EM] A Framework for adapting single winner methods to the task of Proportional Representation in multi winner districts

Forest Simmons

The Multiwinner Method I have in mind chooses the winners sequentially. 
It is based on the idea that ballots have an initial weight of one, and that as candidates supported by a ballot are added to the winners' circle, the weight is reduced according to some rule designed to diminish the influence of the voters who have already achieved some level of satisfaction.

At each stage in the election the new seat is filled by the candidate picked by the single winner method applied to the entire ballot set with the current ballot weights in force.

How, in general, do we diminish the weight of a ballot? Perhaps the simplest way is to make the current weight 1/(1+S) where S is the current satisfaction obtained by comparing the ballot preferences (whether ratings or rankings) with the winners elected so far. As long as the current satisfaction is zero, the weight remains at one since 1/(1+0) is just one.

Let's use Sequential Proportional Approval voting as a guide for what to do. In SPAV the current satisfaction is simply the number of winners so far that are approved on the ballot in question.  So what would we use in place of that approval?  How could we reliably estimate how many of the current winners would be approved when no approval cutoff is provided by the ballot?

Here's what I propose: bear with me and the rationale will become clear as we proceed.

For each ballot we form a square matrix P whose entry in row i and column j is given as follows

P(i, j) is 100% if candidate i is ranked or rated strictly above candidate j. If j is ranked or rated strictly above candidate i, then P(i, j) is zero.  If i and j have the same ranking or rating or are both truncated, then P(i, j) equals P(i,i) = P(j,j), and the common value is  100% or zero percent for equal top or equal bottom respectively.  If they are rated equal and strictly between the two extremes, then P(i, i) is their common rating.  If they are ranked (without ratings) strictly between  the extremes, then P(i, i) is taken to be fifty percent.

We can think of P(i, j) as the probability that the voter who marked this ballot would approve candidate i in an approval election where candidate j was the main rival of candidate i.

Now let p(i) be the minimum over j of P(i , j).  This value may be thought of as the minimum probability that the voter of this ballot would approve candidate i no matter which j turned out to be the main rival candidate.

Now we can define the voter satisfaction for the voter of this ballot: it is just the sum of the p(i) as i ranges over the current winners.

If the ballots are approval style, then this method reduces to Sequential Proportional Approval Voting.  But it applies to any method based on ranking or ratings with equal rankings and truncation allowed.

In particular, it seems (IMHO) to be the simplest, reasonable way to convert River, BeatPath, RankedPairs, or MAM into a multiwinner PR method.

I admit this is a very terse description of the method, so I expect lots of questions.  Especially people new to the EM List, I hope you will ask questions for the benefit of all.  And everybody (new or not) make your strongest criticisms so we can improve it (or discard it, if hopeless)!

Thanks,

Forest






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

Re: [EM] A Framework for adapting single winner methods to the task of Proportional Representation in multi winner districts

Kristofer Munsterhjelm-3
On 1/22/20 12:05 AM, Forest Simmons wrote:

>
> The Multiwinner Method I have in mind chooses the winners sequentially.
> It is based on the idea that ballots have an initial weight of one, and
> that as candidates supported by a ballot are added to the winners'
> circle, the weight is reduced according to some rule designed to
> diminish the influence of the voters who have already achieved some
> level of satisfaction.
>
> At each stage in the election the new seat is filled by the candidate
> picked by the single winner method applied to the entire ballot set with
> the current ballot weights in force.
>
> How, in general, do we diminish the weight of a ballot? Perhaps the
> simplest way is to make the current weight 1/(1+S) where S is the
> current satisfaction obtained by comparing the ballot preferences
> (whether ratings or rankings) with the winners elected so far. As long
> as the current satisfaction is zero, the weight remains at one since
> 1/(1+0) is just one.

A quick reply (been a bit busy lately): Approval methods need to pass a
weaker proportionality criterion than ranked methods. For Approval, you
just need to give X a seat if enough voters approve X, but Droop
proportionality is nested: a vote can contribute to multiple solid
coalitions at once.

Thus I'm not sure basing a ranked proportional method on Approval will
lead to a good outcome, at least not if that's not explicitly taken into
account.

E.g. consider the "D'Hondt without lists" proposal from 2002. It
combined reweighting with pairwise matrices, but I'm pretty sure it
fails the DPC.
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

[EM] How to estimate ratings from a set of ranked ballots (was A Framework for adapting single winner methods to the task of Proportional Representation in multi winner districts)

Forest Simmons

Kristopher,

Thanks for your constructive comments.  That first version left a lot of room for improvement, so here goes a second attempt:

As you mentioned methods like PAV based on approval ballots and versions of Proportional Range Voting based on cardinal ratings style ballots are not naturally adapted to ordinal ranking style ballots.

In my first attempt at a general framework I basically said if you want to convert rankings to approval style ballots, just use implicit approval.  Obviously that leaves much to be desired. So the next approximation would be to give "equal top" rank full approval, while only half approval is given to rankings strictly between top and bottom, which is what I used in my first attempt (although omitted from the partial quote below 🙂).

So I want to use this message to take care of this problem, i.e. how to approximate ratings from rankings:

First let's review why Borda is inadequate.  Borda assumes that ranked candidates are equally spaced in utility. But this assumption is incompatible with clone independence:

40 A>B>C>D>E
60 E>A>B>C>D

Assuming equal spacing (as in non-parametric statistics) we have

40 A(4)>B(3)>C(2)>D(1)
60 E(4)>A(3)>B(2)>C(1)

So A is the winner with a score of 4*40 + 3*60, beating out the Condorcet winner E whose total score is only 4*60, tied with the Pareto dominated candidate B!

The Pareto dominated candidates B, C, and D artificially prop up candidates A and B to the point of taking the wind out of the ballot CW.

How do we fix this?

First we tally first place preferences or "favorite" scores for all of the candidates.  In the above example  A gets forty, E gets 60, and the other candidates get zero each.

Then we use these tallys to construct the random favorite probability distribution: P(A)=40%, P(B)=0=P(C)=P(D), and P(E)=60%.

On any given ballot our estimated rating for candidate X will be R=L /(H+L), where L is the  probability that  (on this ballot) a random favorite will be ranked Lower (or unranked)) than X, and H is the probability that a random favorite will be ranked strictly Higher than X on this ballot.

Notice that the highest ranked candidate will have H = 0. so that its rating will be L/(0 + L) which is 1, or 100 percent.  Similarly any bottom candidate on a ballot will have a value of L equal to zero, so its estimated rating will be 0/(H + 0), which is zero. 

If some candidate X on a ballot has the same  values for L and H, which means that a random favotite is just as likely to be ranked below X as above X, then the estimated rating is given by L/(H+L) = L/(L+L), which equals 1/2 or fifty percent.

So on any ballot from the first faction the estimated ratings of the reaspective candidates are given by R(A) = 60/(0 +60), which equals 1 or 100 percent. While R(E) = 0/(60+0), which equals zero. And R(B) =R(C)=R(D) which are all equal to 60/(40+60) or 60 percent.

Similarly on any ballot from the second faction in our example the estimated ratings are given by R(E) =40/(0+40) or 100 percent, and R(A) = 0/(60+0) = 0, and R(X) for the remaining candidates is given by 0/(100+0) = 0.

So the score totals (over all ballots) are T(A) = 40*100% + 60*0, T(E) = 40*0 + 60* 100%, and T(X) = 40*60% +60*0,  (for each of the clones of A).

In sum, E wins with a total of 60, followed by A with a total score of 40, and finally the (near) clone candidates that are Pareto dominated by A, with 24 points.each.

(I say "near" clones because in this context where equal first and equal bottom are allowed, if a candidate falls into one of those extremes on a ballot and a clone doesn't, then that clone is only a near clone IMHO.)

In my next messaage I'll fix the other problems with my first attempt at a generalized frameworrk for adapting single winner methods to multiwinner elections satisfying Proportional Representation.



Kristofer Munsterhjelm <[hidden email]> wrote:
On 1/22/20 12:05 AM, Forest Simmons wrote:
>
> The Multiwinner Method I have in mind chooses the winners sequentially.
> It is based on the idea that ballots have an initial weight of one, and
> that as candidates supported by a ballot are added to the winners'
> circle, the weight is reduced according to some rule designed to
> diminish the influence of the voters who have already achieved some
> level of satisfaction.
>
> At each stage in the election the new seat is filled by the candidate
> picked by the single winner method applied to the entire ballot set with
> the current ballot weights in force.
>
> How, in general, do we diminish the weight of a ballot? Perhaps the
> simplest way is to make the current weight 1/(1+S) where S is the
> current satisfaction obtained by comparing the ballot preferences
> (whether ratings or rankings) with the winners elected so far. As long
> as the current satisfaction is zero, the weight remains at one since
> 1/(1+0) is just one.

A quick reply (been a bit busy lately): Approval methods need to pass a
weaker proportionality criterion than ranked methods. For Approval, you
just need to give X a seat if enough voters approve X, but Droop
proportionality is nested: a vote can contribute to multiple solid
coalitions at once.

Thus I'm not sure basing a ranked proportional method on Approval will
lead to a good outcome, at least not if that's not explicitly taken into
account.

E.g. consider the "D'Hondt without lists" proposal from 2002. It
combined reweighting with pairwise matrices, but I'm pretty sure it
fails the DPC.

----
Election-Methods mailing list - see https://electorama.com/em for list info