[EM] Sequential Best Assigment (multiwinner method)

[Andy Jennings]

Here's a multiwinner system that's so simple that it should have a name,
but I don't think it does. Let me know if it does.

It uses rated ballots. The goal is to repeatedly find the candidate whose
top quota's-worth of grades are highest and elect that candidate, then
de-weight a quota's-worth of voters. Some names worth considering:

Sequential Best Assignment
Sequential Constituent Matching
Sequential Quota Allocation

The method:

N = Number of voters
S = Number of seats

1. Every voter grades every candidate. (I'd say 4 or 6 grades.)

2. Each voter starts with weight 1.

3. Choose quota Q = N / S. (*)

4. For each candidate, calculate the minimum of their top Q grades. Let G
be the highest minimum. Elect the candidate with that minimum. (Break
ties as in GMJ: calculate for each candidate what fraction of their G
grades are in their top Q grades, and elect the candidate with the smallest
such fraction. Break further ties by choosing the candidate with the least
number of G grades in their top Q grades.)

5. Deweight some voters to decrease the total voter weight by Q, in this
manner:
a) any voter who gave the minimum grade to all remaining candidates is
deweighted to 0.
b) for the voters not deweighted in (a) who gave this candidate a grade
of G or above, find the deweighting D such that when the deweighting
formula:

W_new = max(W_old - D, 0)

is applied, the total voter weight in this round is decreased by Q. (**)

6. Repeat steps 4 and 5, applying voter weights when calculating the top Q
grades, until S seats are filled.


(*) With this quota, when you are filling say, 4 seats, then 25% of the
voting weight gets used up with each seat filled. 25% of the voting weight
will remain when choosing the last seat. That last seat will be determined
by the tie-breaker rule, so it is essentially equivalent to approval
voting, with any above-bottom grade counting as approval.

The other common choice of quota, Q = N / (S + 1), could also be
considered. When filling 4 seats, then, 20% of the voting weight gets used
up with each seat filled. 40% of the voting weight remains to choose the
last seat, so the last seat is essentially filled with a median-based
method (GMJ). 20% of the voters' opinions are, by design, left without a
representative.

(**) I thought about another step (a') where anyone who gave a grade
strictly above G was deweighted completely, but I think it gives the voters
too much incentive to down-weight candidates who they think can get elected
without their help.

I also considered another step (a'') where anyone who graded the chosen
candidates strictly above all other candidates was deweighted completely,
but I don't think there's much benefit for the added complexity.


Any thoughts on which quota is better or on the right name?

~ Andy Jennings

[Jameson Quinn]

This is a good idea.

But on thinking about it further, I'm not sure whether it's not the same as
BTV.

BTV, like Bucklin, works by gradually lowering a "pseudo-approval
threshold", and electing and deweighting candidates as they reach a quota
of "pseudo-approvals". Andy's proposal, like MJ, works by directly looking
at the "quota-th" highest rating, and electing and deweighting the
candidate who's highest by that measure.

But of course, we know that, aside from tiebreakers, MJ and Bucklin are the
same thing. So the more I think about it, the more I think that (aside from
quota choice, tiebreaker, and deweighting scheme; none of which are really
specified by the label "BTV") Andy's proposal and BTV are the same thing.

I could be wrong about this... can anybody else check my logic here?

Still. Even if this is just a new name for BTV, it's a good excuse to
discuss that system.

We could talk about how good it is. Pretty excellent! I like that it avoids
the horrible center-squeeze breakage of STV. Even though the problems with
center squeeze are much less in a multiwinner setting than in IRV, it's
still ugly.

When designing GOLD
<http://wiki.electorama.com/wiki/Geographic_Open_List/Delegated_(GOLD)_voting>,
I chose STV rather than BTV as a substrate. That wasn't because I prefer
STV theoretically; it's just because of its longer track record.

Also, we could talk about the ancillary design decisions: quota choice,
tiebreaker, and deweighting scheme.

Quota choice: I tend to prefer Droop, or a compromise V/(S+.5), over Hare.
Basically, when you're assigning the last seat, you're left with the voters
who are most atypical; the "crumbs" of the party system. If you use a Hare
quota, then at best you'll find a candidate with some appeal to a full
quota; but realistically, you might just find the biggest of a group of
crumbs, who could easily have support from just 35-40% of a quota (based on
1/e, my SWAG for this kind of situation). If you go with a Droop quota, on
the other hand, the entire pool is 2 quotas; and 2/e is 70-80% of a quota,
much closer to fair.

Andy's suggested deweighting scheme might help encourage bigger crumbs, but
I'm not sure about that.

Tiebreaker: I don't have a lot to say about this. GMJ-style seems like a
good choice.

Deweighting: This is where things get interesting. You don't want to have
too much of a free-riding incentive, but you do want to deweight the votes
which are "more satisfied" with the winners and not-deweight those which
are "less satisfied" with the future potential winners.

I like Andy's concept of subtractive, rather than multiplicative,
deweighting. It makes things a little bit harder to describe, but it does
mean that somebody who is "halfway decisive" twice will be fully
deweighted, rather than keeping 1/4 of their voting weight; that seems fair
to me.

I think that Andy's rejected idea of "for those who only gave the new
winner the threshold rating, deweight them last" was doing it wrong, so I'm
not surprised that he decided it led to too big of a free rider incentive.
If you're doing a GMJ tiebreaker anyway, then from a BTV point of view,
those voters are essentially giving a fraction of an approval to the new
winner. I think that only that fraction of their ballot should be at risk
for deweighting; so their subtractive deweighting should be the minimum of
their GMJ fraction and the overall deweighting.

The other way to do things is to try to avoid deweighting voters insofar as
they still have useful opinions about the remaining candidates. That's what
Andy's proposed "completely deweight those who rate all remaining
candidates at 0" rule would do. But this could still leave a very "crumbly"
remainder at the end; imagine if the 100 candidates for the last seat each
had 1% of the remainder giving them a top-rating.

So I can imagine more complicated schemes to do this. For instance:


1. Find the R candidates with the highest quota-th ratings, where R is
the remaining number of seats. In other words, the prospective winners if
you proceeded from here on without any deweighting.
2. Of the deweight-able votes (counting only the GMJ subtractive portion
ot threshold votes), find the Q which have the lowest max rating for those
R candidates. Deweight these completely.

Note that the incentive of the above is not so much to downvote early
winners, as with traditional free riding (though of course that is still
possible if you downvote them below their winning threshold), but rather to
up-vote late winners. That creates a couter-free-riding incentive; a
possibility I'd never considered before.
....

But all-in-all, I think that Andy's suggested deweighting scheme is pretty
good, and I'd rather go for "simple" than "theoretically awesome" here.

Jameson

Post by Andy Jennings
Here's a multiwinner system that's so simple that it should have a name,
but I don't think it does. Let me know if it does.
It uses rated ballots. The goal is to repeatedly find the candidate whose
top quota's-worth of grades are highest and elect that candidate, then
Sequential Best Assignment
Sequential Constituent Matching
Sequential Quota Allocation
N = Number of voters
S = Number of seats
1. Every voter grades every candidate. (I'd say 4 or 6 grades.)
2. Each voter starts with weight 1.
3. Choose quota Q = N / S. (*)
4. For each candidate, calculate the minimum of their top Q grades. Let G
be the highest minimum. Elect the candidate with that minimum. (Break
ties as in GMJ: calculate for each candidate what fraction of their G
grades are in their top Q grades, and elect the candidate with the smallest
such fraction. Break further ties by choosing the candidate with the least
number of G grades in their top Q grades.)
5. Deweight some voters to decrease the total voter weight by Q, in this
a) any voter who gave the minimum grade to all remaining candidates is
deweighted to 0.
b) for the voters not deweighted in (a) who gave this candidate a grade
of G or above, find the deweighting D such that when the deweighting
W_new = max(W_old - D, 0)
is applied, the total voter weight in this round is decreased by Q. (**)
6. Repeat steps 4 and 5, applying voter weights when calculating the top Q
grades, until S seats are filled.
(*) With this quota, when you are filling say, 4 seats, then 25% of the
voting weight gets used up with each seat filled. 25% of the voting weight
will remain when choosing the last seat. That last seat will be determined
by the tie-breaker rule, so it is essentially equivalent to approval
voting, with any above-bottom grade counting as approval.
The other common choice of quota, Q = N / (S + 1), could also be
considered. When filling 4 seats, then, 20% of the voting weight gets used
up with each seat filled. 40% of the voting weight remains to choose the
last seat, so the last seat is essentially filled with a median-based
method (GMJ). 20% of the voters' opinions are, by design, left without a
representative.
(**) I thought about another step (a') where anyone who gave a grade
strictly above G was deweighted completely, but I think it gives the voters
too much incentive to down-weight candidates who they think can get elected
without their help.
I also considered another step (a'') where anyone who graded the chosen
candidates strictly above all other candidates was deweighted completely,
but I don't think there's much benefit for the added complexity.
Any thoughts on which quota is better or on the right name?
~ Andy Jennings
----
Election-Methods mailing list - see http://electorama.com/em for list info

[Richard Lung]

A generalised STV (which is what is my invention of Binomial STV [BTV])
does not have a residual FPTP in the last round.
By including a rational exclusion count, BTV [Binomial Transferable
Vote] avoids the problem of excluding candidates, which seems to be what
much of the discussion on this forum is about.
from
Richard Lung.

I think you're right that this matches BTV in the major details. Is
http://rangevoting.org/BucklinTV.html the best reference for BTV? It
doesn't have a page on Electowiki, yet, right? We should add one.
There aren't many good, simple, rated-ballot, multiwinner systems, so
it deserves to get talked about more, no?
I wasn't suggesting to change the name, but if you are...
Regarding the quota: I see what you're saying about the crumbs. I
just have reservations about a quota that's not even going to try to
represent 1/(s+1) of the population. I realize that STV does it and
STV has a track record. But STV does it because it might come down to
a one-on-one at the end and you want to say that a majority in the
final round is the same as the quota for all the other rounds. A
rated system doesn't have that restriction. I kind of like approval
voting in the last round, even if the winner only gets 30-40%.
If we choose one quota for the default, I'd hope we could add a
footnote that the other one was a possible alternative.
Tiebreaker and deweighting: I don't feel strongly about these, but
it's good that we're considering different options, looking for
simplicity but also looking for corners that cause adverse
incentives. I think it's better to recommend good defaults than just
including a bunch of options.
Tiebreaker: If we were to use Hare quota (and "approval voting" in the
last round), then the critical grade for the last round is going to be
0(F), so a GMJ tiebreaker or "most votes at or above critical" are not
going to help break ties. We'd either have to have a different rule
for the last round, or a second tiebreaker. "Most votes strictly
above critical" would do it.
Deweighting: If we wanted to, we could "assign" voters to the
representatives for whom they were deweighted. In that case, it would
be advantageous to deweight in chunks as large as possible. So
subtractive deweighting would be better than multiplicative and rules
that "deweight completely" are good. But multiplicative is probably
simpler.
~ Andy
On Tue, Jul 25, 2017 at 8:58 AM, Jameson Quinn
This is a good idea.
But on thinking about it further, I'm not sure whether it's not
the same as BTV.
BTV, like Bucklin, works by gradually lowering a "pseudo-approval
threshold", and electing and deweighting candidates as they reach
a quota of "pseudo-approvals". Andy's proposal, like MJ, works by
directly looking at the "quota-th" highest rating, and electing
and deweighting the candidate who's highest by that measure.
But of course, we know that, aside from tiebreakers, MJ and
Bucklin are the same thing. So the more I think about it, the more
I think that (aside from quota choice, tiebreaker, and deweighting
scheme; none of which are really specified by the label "BTV")
Andy's proposal and BTV are the same thing.
I could be wrong about this... can anybody else check my logic here?
Still. Even if this is just a new name for BTV, it's a good excuse
to discuss that system.
We could talk about how good it is. Pretty excellent! I like that
it avoids the horrible center-squeeze breakage of STV. Even though
the problems with center squeeze are much less in a multiwinner
setting than in IRV, it's still ugly.
When designing GOLD
<http://wiki.electorama.com/wiki/Geographic_Open_List/Delegated_%28GOLD%29_voting>,
I chose STV rather than BTV as a substrate. That wasn't because I
prefer STV theoretically; it's just because of its longer track
record.
Also, we could talk about the ancillary design decisions: quota
choice, tiebreaker, and deweighting scheme.
Quota choice: I tend to prefer Droop, or a compromise V/(S+.5),
over Hare. Basically, when you're assigning the last seat, you're
left with the voters who are most atypical; the "crumbs" of the
party system. If you use a Hare quota, then at best you'll find a
candidate with some appeal to a full quota; but realistically, you
might just find the biggest of a group of crumbs, who could easily
have support from just 35-40% of a quota (based on 1/e, my SWAG
for this kind of situation). If you go with a Droop quota, on the
other hand, the entire pool is 2 quotas; and 2/e is 70-80% of a
quota, much closer to fair.
Andy's suggested deweighting scheme might help encourage bigger
crumbs, but I'm not sure about that.
Tiebreaker: I don't have a lot to say about this. GMJ-style seems
like a good choice.
Deweighting: This is where things get interesting. You don't want
to have too much of a free-riding incentive, but you do want to
deweight the votes which are "more satisfied" with the winners and
not-deweight those which are "less satisfied" with the future
potential winners.
I like Andy's concept of subtractive, rather than multiplicative,
deweighting. It makes things a little bit harder to describe, but
it does mean that somebody who is "halfway decisive" twice will be
fully deweighted, rather than keeping 1/4 of their voting weight;
that seems fair to me.
I think that Andy's rejected idea of "for those who only gave the
new winner the threshold rating, deweight them last" was doing it
wrong, so I'm not surprised that he decided it led to too big of a
free rider incentive. If you're doing a GMJ tiebreaker anyway,
then from a BTV point of view, those voters are essentially giving
a fraction of an approval to the new winner. I think that only
that fraction of their ballot should be at risk for deweighting;
so their subtractive deweighting should be the minimum of their
GMJ fraction and the overall deweighting.
The other way to do things is to try to avoid deweighting voters
insofar as they still have useful opinions about the remaining
candidates. That's what Andy's proposed "completely deweight those
who rate all remaining candidates at 0" rule would do. But this
could still leave a very "crumbly" remainder at the end; imagine
if the 100 candidates for the last seat each had 1% of the
remainder giving them a top-rating.
1. Find the R candidates with the highest quota-th ratings, where
R is the remaining number of seats. In other words, the
prospective winners if you proceeded from here on without any
deweighting.
2. Of the deweight-able votes (counting only the GMJ subtractive
portion ot threshold votes), find the Q which have the lowest
max rating for those R candidates. Deweight these completely.
Note that the incentive of the above is not so much to downvote
early winners, as with traditional free riding (though of course
that is still possible if you downvote them below their winning
threshold), but rather to up-vote late winners. That creates a
couter-free-riding incentive; a possibility I'd never considered
before.
....
But all-in-all, I think that Andy's suggested deweighting scheme
is pretty good, and I'd rather go for "simple" than "theoretically
awesome" here.
Jameson
2017-07-24 21:58 GMT-07:00 Andy Jennings
Here's a multiwinner system that's so simple that it should
have a name, but I don't think it does. Let me know if it does.
It uses rated ballots. The goal is to repeatedly find the
candidate whose top quota's-worth of grades are highest and
elect that candidate, then de-weight a quota's-worth of
Sequential Best Assignment
Sequential Constituent Matching
Sequential Quota Allocation
N = Number of voters
S = Number of seats
1. Every voter grades every candidate. (I'd say 4 or 6 grades.)
2. Each voter starts with weight 1.
3. Choose quota Q = N / S. (*)
4. For each candidate, calculate the minimum of their top Q
grades. Let G be the highest minimum. Elect the candidate
with that minimum. (Break ties as in GMJ: calculate for each
candidate what fraction of their G grades are in their top Q
grades, and elect the candidate with the smallest such
fraction. Break further ties by choosing the candidate with
the least number of G grades in their top Q grades.)
5. Deweight some voters to decrease the total voter weight by
a) any voter who gave the minimum grade to all remaining
candidates is deweighted to 0.
b) for the voters not deweighted in (a) who gave this
candidate a grade of G or above, find the deweighting D such
W_new = max(W_old - D, 0)
is applied, the total voter weight in this round is decreased by Q. (**)
6. Repeat steps 4 and 5, applying voter weights when
calculating the top Q grades, until S seats are filled.
(*) With this quota, when you are filling say, 4 seats, then
25% of the voting weight gets used up with each seat filled.
25% of the voting weight will remain when choosing the last
seat. That last seat will be determined by the tie-breaker
rule, so it is essentially equivalent to approval voting, with
any above-bottom grade counting as approval.
The other common choice of quota, Q = N / (S + 1), could also
be considered. When filling 4 seats, then, 20% of the voting
weight gets used up with each seat filled. 40% of the voting
weight remains to choose the last seat, so the last seat is
essentially filled with a median-based method (GMJ). 20% of
the voters' opinions are, by design, left without a
representative.
(**) I thought about another step (a') where anyone who gave a
grade strictly above G was deweighted completely, but I think
it gives the voters too much incentive to down-weight
candidates who they think can get elected without their help.
I also considered another step (a'') where anyone who graded
the chosen candidates strictly above all other candidates was
deweighted completely, but I don't think there's much benefit
for the added complexity.
Any thoughts on which quota is better or on the right name?
~ Andy Jennings
----
Election-Methods mailing list - see http://electorama.com/em for list info
----
Election-Methods mailing list - see http://electorama.com/em for list info

[Richard Lung]

BTV is what I call Binomial Transferable Vote
V/(S + 1/2) is what I call the Harmonic Mean quota. It is a "compromise"
but it is a principled compromise.
Both are described in my book, Scientific Method of Elections.

from
Richard Lung.

Post by Jameson Quinn
This is a good idea.
But on thinking about it further, I'm not sure whether it's not the
same as BTV.
BTV, like Bucklin, works by gradually lowering a "pseudo-approval
threshold", and electing and deweighting candidates as they reach a
quota of "pseudo-approvals". Andy's proposal, like MJ, works by
directly looking at the "quota-th" highest rating, and electing and
deweighting the candidate who's highest by that measure.
But of course, we know that, aside from tiebreakers, MJ and Bucklin
are the same thing. So the more I think about it, the more I think
that (aside from quota choice, tiebreaker, and deweighting scheme;
none of which are really specified by the label "BTV") Andy's proposal
and BTV are the same thing.
I could be wrong about this... can anybody else check my logic here?
Still. Even if this is just a new name for BTV, it's a good excuse to
discuss that system.
We could talk about how good it is. Pretty excellent! I like that it
avoids the horrible center-squeeze breakage of STV. Even though the
problems with center squeeze are much less in a multiwinner setting
than in IRV, it's still ugly.
When designing GOLD
<http://wiki.electorama.com/wiki/Geographic_Open_List/Delegated_%28GOLD%29_voting>,
I chose STV rather than BTV as a substrate. That wasn't because I
prefer STV theoretically; it's just because of its longer track record.
Also, we could talk about the ancillary design decisions: quota
choice, tiebreaker, and deweighting scheme.
Quota choice: I tend to prefer Droop, or a compromise V/(S+.5), over
Hare. Basically, when you're assigning the last seat, you're left with
the voters who are most atypical; the "crumbs" of the party system. If
you use a Hare quota, then at best you'll find a candidate with some
appeal to a full quota; but realistically, you might just find the
biggest of a group of crumbs, who could easily have support from just
35-40% of a quota (based on 1/e, my SWAG for this kind of situation).
If you go with a Droop quota, on the other hand, the entire pool is 2
quotas; and 2/e is 70-80% of a quota, much closer to fair.
Andy's suggested deweighting scheme might help encourage bigger
crumbs, but I'm not sure about that.
Tiebreaker: I don't have a lot to say about this. GMJ-style seems like
a good choice.
Deweighting: This is where things get interesting. You don't want to
have too much of a free-riding incentive, but you do want to deweight
the votes which are "more satisfied" with the winners and not-deweight
those which are "less satisfied" with the future potential winners.
I like Andy's concept of subtractive, rather than multiplicative,
deweighting. It makes things a little bit harder to describe, but it
does mean that somebody who is "halfway decisive" twice will be fully
deweighted, rather than keeping 1/4 of their voting weight; that seems
fair to me.
I think that Andy's rejected idea of "for those who only gave the new
winner the threshold rating, deweight them last" was doing it wrong,
so I'm not surprised that he decided it led to too big of a free rider
incentive. If you're doing a GMJ tiebreaker anyway, then from a BTV
point of view, those voters are essentially giving a fraction of an
approval to the new winner. I think that only that fraction of their
ballot should be at risk for deweighting; so their subtractive
deweighting should be the minimum of their GMJ fraction and the
overall deweighting.
The other way to do things is to try to avoid deweighting voters
insofar as they still have useful opinions about the remaining
candidates. That's what Andy's proposed "completely deweight those who
rate all remaining candidates at 0" rule would do. But this could
still leave a very "crumbly" remainder at the end; imagine if the 100
candidates for the last seat each had 1% of the remainder giving them
a top-rating.
1. Find the R candidates with the highest quota-th ratings, where R
is the remaining number of seats. In other words, the prospective
winners if you proceeded from here on without any deweighting.
2. Of the deweight-able votes (counting only the GMJ subtractive
portion ot threshold votes), find the Q which have the lowest max
rating for those R candidates. Deweight these completely.
Note that the incentive of the above is not so much to downvote early
winners, as with traditional free riding (though of course that is
still possible if you downvote them below their winning threshold),
but rather to up-vote late winners. That creates a couter-free-riding
incentive; a possibility I'd never considered before.
....
But all-in-all, I think that Andy's suggested deweighting scheme is
pretty good, and I'd rather go for "simple" than "theoretically
awesome" here.
Jameson
Here's a multiwinner system that's so simple that it should have a
name, but I don't think it does. Let me know if it does.
It uses rated ballots. The goal is to repeatedly find the
candidate whose top quota's-worth of grades are highest and elect
that candidate, then de-weight a quota's-worth of voters. Some
Sequential Best Assignment
Sequential Constituent Matching
Sequential Quota Allocation
N = Number of voters
S = Number of seats
1. Every voter grades every candidate. (I'd say 4 or 6 grades.)
2. Each voter starts with weight 1.
3. Choose quota Q = N / S. (*)
4. For each candidate, calculate the minimum of their top Q
grades. Let G be the highest minimum. Elect the candidate with
that minimum. (Break ties as in GMJ: calculate for each candidate
what fraction of their G grades are in their top Q grades, and
elect the candidate with the smallest such fraction. Break
further ties by choosing the candidate with the least number of G
grades in their top Q grades.)
5. Deweight some voters to decrease the total voter weight by Q,
a) any voter who gave the minimum grade to all remaining
candidates is deweighted to 0.
b) for the voters not deweighted in (a) who gave this candidate
a grade of G or above, find the deweighting D such that when the
W_new = max(W_old - D, 0)
is applied, the total voter weight in this round is decreased by Q. (**)
6. Repeat steps 4 and 5, applying voter weights when calculating
the top Q grades, until S seats are filled.
(*) With this quota, when you are filling say, 4 seats, then 25%
of the voting weight gets used up with each seat filled. 25% of
the voting weight will remain when choosing the last seat. That
last seat will be determined by the tie-breaker rule, so it is
essentially equivalent to approval voting, with any above-bottom
grade counting as approval.
The other common choice of quota, Q = N / (S + 1), could also be
considered. When filling 4 seats, then, 20% of the voting weight
gets used up with each seat filled. 40% of the voting weight
remains to choose the last seat, so the last seat is essentially
filled with a median-based method (GMJ). 20% of the voters'
opinions are, by design, left without a representative.
(**) I thought about another step (a') where anyone who gave a
grade strictly above G was deweighted completely, but I think it
gives the voters too much incentive to down-weight candidates who
they think can get elected without their help.
I also considered another step (a'') where anyone who graded the
chosen candidates strictly above all other candidates was
deweighted completely, but I don't think there's much benefit for
the added complexity.
Any thoughts on which quota is better or on the right name?
~ Andy Jennings
----
Election-Methods mailing list - see http://electorama.com/em for list info
----
Election-Methods mailing list - see http://electorama.com/em for list info

[Jameson Quinn]

Post by Richard Lung
BTV is what I call Binomial Transferable Vote

I was unaware of Binomial Transferable Vote. I was referring to Bucklin
Transferable vote. BTV:GMJ::STV:IRV. It's been independently invented by
several people now; I was one of them, but I think not the first.