A method that elects the "most stable" candidate set
-
I'm not sure if this has really been discussed that much on here (I did a search and nothing really came up), but you could have a method that elects the "most stable" set, rather than simply having stability as just one criterion you might want to judge a method/result by.
For example, let's say you use the Hare quota, though you can also use Droop/Hagenbach-Bischoff. Also, I'll stick with approval voting in the examples for simplicity.
2 to elect
2 voters: A1, A2
1 voter: B1, B2In this example both A1, A2 and A1, B1 are stable. If you elect A1, A2, the B faction can't overturn it because they don't have a whole quota (half the votes).
If you elect A1, B1 it is also stable. The A faction would need all the votes to overturn it. (Using Droop would actually remove these plateaus of stability.)
But you can still see which is more stable. The B faction is 1/3 of a quota away from overturning A1, A2. The A faction is 2/3 of a quota away from overturning A1, B1, so it's the more stable set A1, B1 is therefore elected.
In this method, by the way, I would ignore indifferent voters.
For example, a possible winning set might be ABCDEF. But a certain number of voters might prefer G to that set. Normally you'd say 1/6 of voters would need to prefer G to ABCDEF to overturn it. But this method would say that of the voters who prefer either ABCDEF or G to the other, 1/6 must prefer G to be able to overturn ABCDEF. This means that it should pass independence of irrelevant ballots as a method.
A lot of proportional methods are only weakly monotonic, and if perfect representation is possible, they basically stop there. E.g.:
2 to elect
99: AB
99: AC
1: B
1: CMethods obeying perfect representation elect BC, but a strongly monotonic method should elect A. This method would elect AB (or AC).
If AB is a potential winning set, then 1 voter prefers C compared with 99 that prefer AB (and 100 who are indifferent). So that's just 1/100. Almost a whole quota short. 49/50 of a quota to be precise.
But if you look at BC, then although no-one prefers just A, the number who prefer AB is 99 compared with just 1 who prefers BC. That's 99/100 which is just short of two quotas. 1/50 of a quota.
So although AB and BC are both stable, AB is more stable so would be elected. This is quite a good result because most proportional optimised elect-all-candidates-at-once methods elect BC. PAV elects A but it's not properly proportional in many cases.
This method would fail ULC though.
6 to elect:
2 voters: U1, U2, U3, A1, A2, A3
1 voter: U1, U2, U3, B1, B2, B3If you look at the set U1, U2, U3, A1, A2, A3, then 1/3 of the voters prefer U1, U2, U3, B1, but they are 2 quotas of voters short.
If you look at the set U1, U2, U3, A1, A2, B1, then 2/3 of the voters prefer U1, U2, U3, A1, A2, A3 but they are also 2 quotas short of overturning the result.
So these two sets are equally stable. The ULC-compliant result of U1, U2, U3, A1, A2, B1 only ties with the other result.
But anyway, I think this is a decent enough method in its own right. It's not really anything new - just turning stability from a criterion into a method.
-
@toby-pereira said in A method that elects the "most stable" candidate set:
A lot of proportional methods are only weakly monotonic, and if perfect representation is possible, they basically stop there.
Not sure I follow here. Very few proportional rules provide perfect representation; almost all the ones people talk about will elect A at least once in that example you gave.
Also "more stable" I think might not even be resolute whatsoever, forget resolvable in polynomial time. Imagine like a condorcet cycle but of committees.
Just use MES or party-list and be happy
-
@andy-dienes said in A method that elects the "most stable" candidate set:
Not sure I follow here. Very few proportional rules provide perfect representation; almost all the ones people talk about will elect A at least once in that example you gave.
Also "more stable" I think might not even be resolute whatsoever, forget resolvable in polynomial time. Imagine like a condorcet cycle but of committees.
Just use MES or party-list and be happyYeah, I mean lots of methods elect A, but I really meant ones that don't elect sequentially, but elect all candidates in one go. I don't think too many elect A in that case. (E.g. Phragmen methods, Monroe, Chamberlain-Courant)
You might be right about cycles. I don't know really.
-
Monroe, Chamberlain-Courant
I wouldn't call these proportional though. they don't satisfy PJR (not even on party-list profiles!). It's basically only specifically leximax-Phragmen that I know of that I would call proportional and yet satisfies perfect representation.
-
@andy-dienes I'm not sure I see PJR as an absolute requirement to be considered proportional, even if one might consider it to be desirable.
I presume the failures you talk about are related to the example on rangevoting.org on apportionment where Webster/Sainte-Laguë fails.
States A, B and C each have a population of 13; D has 105, making 144 in total. There are 18 seats in total. The number of quotas they have are 1.625 (for each of A to C) and 13.125 for D. And yet the number of seats they win under Webster/Sainte-Laguë are 2, 2, 2, 12. So D is under-represented.
But many people would consider Webster/Sainte-Laguë a purer form of proportionality than Jefferson/D'Hondt. So I don't think it's black and white.
I tend to think that a proportional method should obey perfect representation in the limit as the seats are increased, though not always at the earliest opportunity (because I believe in strong monotonicity). As long as this happens then it's proportional and all the other criteria - PJR, EJR etc - are an overcomplication.
-
I'm not sure I see PJR as an absolute requirement to be considered proportional
I do, so I don't think we'll agree. I don't particularly care about Perfect Representation; it's a nice peculiarity but it's too rarely satiable (at all) and incomparable with other more important notions that it's hard to put much stock in it.
I am not referencing rangevoting or any examples therein; I try to stay very far away from that site.
-
@andy-dienes OK, fair enough. Your position is that Webster/Sainte-Laguë are not proportional, whereas I would consider them to be so, so probably you're right and it's somewhere where we won't agree!
-
@toby-pereira No, that is not my position. Party-list Webster is a bit of a special case.
Yes I know that technically it doesn't give lower quota but the allocations are always within 1 of lower quota, so on party-list profiles I don't see an issue. The problem comes when you try to generalize that definition to arbitrary approval profiles (or ranked even). The generalization of lower quota is very intuitive and relates to a lot of other things (like priceability, stable sets, etc. etc.) and I haven't seen any such generalization nearly so compelling for Webster.
Also, I don't think Webster has much to do with Perfect Representation. It's certainly not guaranteed.
-
@andy-dienes I think if you allow Webster to be proportional but not approval methods that reduce to it, it's just personal preference at that point, and not anything that could be called proportional in an objective sense.
Webster would give perfect representation if the seats exactly matched the population size ratios.
Edit - But as I say, with perfect representation, you wouldn't necessarily expect an approval-based method to pass it in all cases, but to be proportional it should pass it in the limit as the number of candidates increases, as long as the ballots make this possible (if they've approved enough candidates, or if we allow infinite cloning).
-
@toby-pereira said in A method that elects the "most stable" candidate set:
I think if you allow Webster to be proportional but not approval methods that reduce to it, it's just personal preference at that point, and not anything that could be called proportional in an objective sense.
There's a very big difference between party-list profiles and arbitrary approval profiles. If you can show me a compelling generalization of Webster to the latter I might be convinced. My opinion is not at all arbitrary and is very much driven by the (objective) research I've read on the topic.
Webster would give perfect representation if the seats exactly matched the population size ratios.
Again, this is really only relevant for party-list profiles. In general, Perfect Representation is pretty uncompelling to me. It is incompatible with Pareto efficiency, for example, as well as incompatible with EJR, which means it is incompatible with the stable winner set. If you care about the stable winner set then as the original post indicates then you should also reject perfect representation.
-
@andy-dienes said in A method that elects the "most stable" candidate set:
@toby-pereira said in A method that elects the "most stable" candidate set:
I think if you allow Webster to be proportional but not approval methods that reduce to it, it's just personal preference at that point, and not anything that could be called proportional in an objective sense.
There's a very big difference between party-list profiles and arbitrary approval profiles. If you can show me a compelling generalization of Webster to the latter I might be convinced. My opinion is not at all arbitrary and is very much driven by the (objective) research I've read on the topic.
I'm not sure I'd be able to convince you that a proportional approval method that reduces to Webster in the case that everyone happens to vote along party lines is a good thing. However, the arguments about whether it is "good" or "bad" are essentially philosophical at this point, and it couldn't be demonstrated mathematically.
Webster would give perfect representation if the seats exactly matched the population size ratios.
Again, this is really only relevant for party-list profiles. In general, Perfect Representation is pretty uncompelling to me. It is incompatible with Pareto efficiency, for example, as well as incompatible with EJR, which means it is incompatible with the stable winner set. If you care about the stable winner set then as the original post indicates then you should also reject perfect representation.
I think I need to be clear to make a distinction between a method that passes perfect representation whenever possible (which is what passing perfect representation is taken to mean), and a method that would pass it in the limit if you increased the number of candidates arbitrarily. I think the incompatibilities you state only apply to the former. The latter is what I claim to be a requirement for a proper proportional method.
In any case, there are ballot profiles where I would argue that the multi-winner Pareto criterion is not ideal to pass. The same would also apply for set stability. But I don't think these criteria are terrible or anything, and that a method passing these (such as my attempt to start this thread) would still be reasonable.
-
@toby-pereira said in A method that elects the "most stable" candidate set:
and it couldn't be demonstrated mathematically.
This is not at all true. Check out https://arxiv.org/abs/2007.01795 for a recent survey of approval-based multiwinner rules. there are lots of things that can be demonstrated mathematically.
I think the incompatibilities you state only apply to the former.
This is also not true, I'm not sure where you got that idea.
There are very very few rules that provide perfect representation, and none of them can be computed efficiently. On the other hand there is a very large family of axioms, derived independently from a few separate compelling & intuitive notions, that can all be satisfied satisfied simultaneously and efficiently; this family relates to the core (stable sets), which has broader implications for fairness and nonmanipulability. For example, when a Condorcet winner exists it is the unique stable outcome for k=1.
-
@andy-dienes said in A method that elects the "most stable" candidate set:
@toby-pereira said in A method that elects the "most stable" candidate set:
and it couldn't be demonstrated mathematically.
This is not at all true. Check out https://arxiv.org/abs/2007.01795 for a recent survey of approval-based multiwinner rules. there are lots of things that can be demonstrated mathematically.
But my point is that "goodness" isn't one of them. In any case, I can find nothing in that paper that proves your point. However, I did find:
Most axiomatic notions for proportionality are only >applicable to ABC rules that
extend apportionment methods satisfying lower quota >>(see Figure 4.1). This excludes, e.g., ABC rules that >extend the Sainte-Lagu¨e method. As the Sainte-Lagu¨e
method is in certain aspects superior to the D’Hondt >method (Balinski and Young
[2] discuss this in detail), it would be desirable to have >notions of proportionality
that are agnostic to the underlying apportionment method.So I don't think your claims are correct.
I think the incompatibilities you state only apply to the former.
This is also not true, I'm not sure where you got that idea.
There are very very few rules that provide perfect representation, and none of them can be computed efficiently. On the other hand there is a very large family of axioms, derived independently from a few separate compelling & intuitive notions, that can all be satisfied satisfied simultaneously and efficiently; this family relates to the core (stable sets), which has broader implications for fairness and nonmanipulability. For example, when a Condorcet winner exists it is the unique stable outcome for k=1.
There may be very few rules that provide perfect representation in general. That's not the same as saying that they never do.
Also, when someone states that criterion X is incompatible with criterion Y, they are saying that no method can conform to both criteria all the time. It's not to say that there are no methods that occasionally conform to both for individual results. So, when it is said that a criterion is not compatible with perfect representation, the point is that you cannot have both in all cases. I'm unaware of any proof that e.g. multi-winner Pareto is incompatible with perfect representation in the limit. Because passing perfect representation in the limit is not the same as passing the criterion.
-
But my point is that "goodness" isn't one of them.
Various notions of "fairness" and "proportionality" are though. There are dozens of proposed formalizations. Inasmuch as those things are "good" we can measure them.
it would be desirable to have notions of proportionality that are agnostic to the underlying apportionment method.So I don't think your claims are correct.
That's exactly my point, there are very few notions of proportionality that extend Webster. If you can propose one I will listen. These are not "my" opinions or "my" claims, I'm just telling you what the current state of research looks like. Pretty much all the active conversations and open questions across the various academic groups that study Approval-based PR or participatory budgeting revolve around extensions of lower quota; very few extensions of Webster have been proposed or studied.
I'm unaware of any proof that e.g. multi-winner Pareto is incompatible with perfect representation in the limit. Because passing perfect representation in the limit is not the same as passing the criterion.
Just look at proposition A.9 in the Lackner&Skowron book. There is a proof right there. If you mean something else by "in the limit" then you will have to be more precise.
-
@andy-dienes said in A method that elects the "most stable" candidate set:
But my point is that "goodness" isn't one of them.
Various notions of "fairness" and "proportionality" are though. There are dozens of proposed formalizations. Inasmuch as those things are "good" we can measure them.
Sure, but then the goodness of Webster-reducing approval methods wasn't refuted where you told me to look.
it would be desirable to have notions of proportionality that are agnostic to the underlying apportionment method.So I don't think your claims are correct.
That's exactly my point, there are very few notions of proportionality that extend Webster. If you can propose one I will listen. These are not "my" opinions or "my" claims, I'm just telling you what the current state of research looks like. Pretty much all the active conversations and open questions across the various academic groups that study Approval-based PR or participatory budgeting revolve around extensions of lower quota; very few extensions of Webster have been proposed or studied.
But this wasn't your original point that started this. Your original point was that the likes of Monroe and Chamberlain-Courant (and presumably var-Phragmen but we didn't explicitly mention that) were not proportional because they didn't pass PJR (and lower quota). Your point wasn't that methods that don't pass PJR and lower quota could be proportional but haven't been extensively studied.
I'm unaware of any proof that e.g. multi-winner Pareto is incompatible with perfect representation in the limit. Because passing perfect representation in the limit is not the same as passing the criterion.
Just look at proposition A.9 in the Lackner&Skowron book. There is a proof right there. If you mean something else by "in the limit" then you will have to be more precise.
Proposition A.9 gives a ballot profile where there is one possible candidate set that gives perfect representation, but where that set is Pareto dominated by another set.
My "in the limit" thing was that as the number of candidates is increased towards infinity, or even just equal to the number of voters actually. E.g. if there are 100 voters and 100 candidates to be elected, I would say that perfect representation should hold, as long as the ballots allow it, for a deterministic method to be properly proportional. Proposition A.9 has 8 voters and 2 to elect, so I'd want to see a proof with 8 to elect.
In any case I'm not saying that Pareto is compatible with this, just that I don't think it's been shown that it isn't. Also, there are cases where I don't necessarily think this form of Pareto is desirable, but I might start a separate thread on that, and how it also relates to consistency.
-
@toby-pereira Among the metrics/axioms to measure approval-based proportionality that I have ever seen been studied, Monroe and Chamberlin-Courant pass very few (and the latter almost none). Nearly all of these axioms reduce to lower-quota on party-list profiles.
If you can provide a compelling and intuitive axiom which implies Webster on party-lists and relates to other notions in fairness and proportionality as comprehensively as the PJR family do then I will be open to that discussion. Until then, I will consider such rules not proportional.
-
@toby-pereira said in A method that elects the "most stable" candidate set:
Also, any election where k > n (i.e. more seats to elect than voters) cannot have Perfect Representation, so the notion of Perfect Representation "in the limit" is kind of nonsensical except when k exactly equals n.
If you want to take that as your guiding axiom I can't stop you, but it seems rather contrived to me. Especially because when k == n exactly, then (I think) any outcome providing Stable Priceability as defined in http://www.cs.utoronto.ca/~nisarg/papers/priceability.pdf will also provide Perfect Representation, suggesting that even in this restricted case where k == n that stability is still the superior metric.
-
@andy-dienes said in A method that elects the "most stable" candidate set:
@toby-pereira said in A method that elects the "most stable" candidate set:
Also, any election where k > n (i.e. more seats to elect than voters) cannot have Perfect Representation, so the notion of Perfect Representation "in the limit" is kind of nonsensical except when k exactly equals n.
If you want to take that as your guiding axiom I can't stop you, but it seems rather contrived to me. Especially because when k == n exactly, then (I think) any outcome providing Stable Priceability as defined in http://www.cs.utoronto.ca/~nisarg/papers/priceability.pdf will also provide Perfect Representation, suggesting that even in this restricted case where k == n that stability is still the superior metric.
If there cannot be perfect representation when k>n, then that's really just because of the narrow way perfect representation is defined, as they probably didn't consider this case when defining it. It doesn't really change the general principle, and I would just extend it in the way it naturally should be.
Essentially if there are n voters, then if a result allows each voter to be uniquely assigned to 1/n of the representation (whether that's a fraction of a candidate or more than one candidate), then that's "perfect representation" in the way I would extend the definition. So I would still use this in the limit as my defining feature of a proportional approval method.
I think it's simpler than what the acedemics in the field have been trying to do by coming up with a whole zoo of different axioms trying to capture the essence of proportionality.
-
each voter to be uniquely assigned to 1/n of the representation (whether that's a fraction of a candidate or more than one candidate), then that's "perfect representation" in the way I would extend the definition
I just can't shake the feeling that this better describes priceability and (stable priceability) than it does perfect representation. I think many academics, and I personally, agree more or less with this intuition, but formalizing it without introducing unforeseen side-effects of the definition is the hard part. As it happens, I think the attempted formalization in the axiom labeled "perfect representation" does have some unfortunate side-effects, but you can get the same spirit of proportionality in (to me) a more principled way via priceability.
-
@andy-dienes said in A method that elects the "most stable" candidate set:
each voter to be uniquely assigned to 1/n of the representation (whether that's a fraction of a candidate or more than one candidate), then that's "perfect representation" in the way I would extend the definition
I just can't shake the feeling that this better describes priceability and (stable priceability) than it does perfect representation. I think many academics, and I personally, agree more or less with this intuition, but formalizing it without introducing unforeseen side-effects of the definition is the hard part. As it happens, I think the attempted formalization in the axiom labeled "perfect representation" does have some unfortunate side-effects, but you can get the same spirit of proportionality in (to me) a more principled way via priceability.
OK, but does Webster pass priceability? I wouldn't want to throw that out.