A method that elects the "most stable" candidate set
-
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.
-
@toby-pereira said in A method that elects the "most stable" candidate set:
@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.
As Andy said, it does not, since Webster does not pass lower quota.
-
@spelunker Fair enough. I'm not as familiar with priceability and what it rules out, though I have read the definition. I knew Webster failed PJR.
-
@A Former User said in A method that elects the "most stable" candidate set:
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 happyJust to revisit the initial topic - If there was a cycle of "most stable" then like with single-winner Condorcet methods, there could be a system in place to determine the winner. Also if this sort of thing were ever adopted in any sort of election, it would likely have to be used sequentially for computational reasons, which should make it workable.
And on Condorcet methods, it has been said that this core stability is a sort of multi-winner analogue of Condorcet.
Another thing about Condorcet methods is that the Condorcet winner is, as far as I understand, the game theoretically stable winner for approval voting. I don't think core stability in the sense that it's discussed for multi-winner cardinal methods is necessarily the same as game theoretically stable. So perhaps that would be an interesting thing to investigate. I think it would be interesting to see what winner sets were game theoretically stable under, for example, single non-transferable vote.
Has Andy left the forum by the way?