A method that elects the "most stable" candidate set
-
@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?
-
If this was extended to score voting, I think it should elect the Condorcet winner in the single-winner case, if there is one. Otherwise, obviously it would have to choose between the candidates in some way, like other Condorcet methods do so it's not a big problem.
When there's more than one winner, what happens depends on how you interpret the scores. You could measure a voter's satisfaction by adding up the scores the voters have given to the elected candidates, but I think that might be unsatisfactory in a few ways. There's always debate about how to interpret scores and what they mean, and whether absolute numerical values should really be used in their raw form.
Instead, the scores could be used as layers of approval. This basically means that a voter's satisfaction with a candidate set is determined by the single highest score they've given to a candidate in the set, next best used as a tie-break, and so on. So for scores out of 5, a single 5 is better than multiple 4s etc.
This should keep it relatively simple. Also if candidates are elected sequentially, it should be simple enough to calculate the results.
I think this should be a decent enough method and I think I'd prefer it to things like Allocated Score and Sequentially Spent Score.
Obviously COWPEA Lottery using scores as layers of approval is God-tier in terms of criterion compliance, and very simple to implement, but it is non-deterministic, which might be too much for some people, so this method could be a good compromise.
Edit - You'd have to work out exactly how to measure the stability of a candidate set though. Let's say the first 2 candidates elected are AB. Then you need to test e.g. ABC, ABD, ABE etc. to find the 3rd candidate. But I think you might be able to test them against each individual candidate not in the set. So test ABC against, D, E, F etc. separately.
Edit 2 - You'd probably have to test each potential set against all the other subsets. So ABC would go against ABD, ABE etc., plus AD, AE, BD, BE, as well as D, E etc. Still not that many in the general scheme of things.