Proportionality Guarantees of Allocated Score (approvals)

Keith Edmonds

@andy-dienes said in Proportionality Guarantees of Allocated Score (approvals):

spending equally from that set of voters.

I do not find this last part specific enough. Say voter A and B support the winner with a score of 1 and 2 respectively. Will A spend half of what B spent on the winner or will they both spend the same. ie spend equally per voter or equally per score?

@keith-edmonds At all times, a voter will either a) spend 0 on a winner, or b) spend the same as everybody else (ignoring exhaustions)

Say X is a winner.

1/2 a quota of budget scores X a 5, 1/3 a quota of budget scores X a 4, 1/3 a quota of budget scores X a 3,

then the threshold score will be set at 3. call the set of voters who gave X a score of 3 or higher N. Then N holds 7/6 of a quota of budget total. An equal amount will be spent from each voter in N such that 1 quota of budget is taken.

Also btw, the utilitarian and egalitarian guarantee proofs of 1/k and 1 - 1/e should also extend to SSS with approval ballots (aka Enestrom-Phragmen). The proof of the proportionality degree relies on the equal payments so it will not automatically extend as well, but I would not be surprised if nonetheless they have the same lower bound.

Keith Edmonds

@andy-dienes Right so it is same per voter. When designing SSS I made a specific choice to make it same per score. The 1/2 a quota who scores X a 5 is getting more out of their winning than those who scored a 4 or a 3. It seems unfair to charge them the same amount of weight.

All these tradeoffs seem to be something you are getting your head around very well. Are you taking detailed notes?

The ecosystem of tradeoffs between AS, EPA, SSS and MES is very nuanced. When I talked to Piotr about this he fell back on the fact that MES satisfied Full justified representation. However, he fully admitted that MES and FJR are defined as a pair. One could define a different form of Justified representation such that MES fails and SSS passes based on this choice.

The reason I bring this up is that your EPA system is making a similar assumption to MES. Specifically MES is designed such that somebody who endorses a winner with a score of 1 can spend their whole ballot. My intuition is that this is unfair. Your system, makes as similar assumption but it is even less tied to the score than MES. MES applies their multiplier to the score but yours completely erases all the score data. That is sort of like Allocated Score that takes all people above a threshold. I think the utility expressed by the voter is needs to be accounted for in the reweighting.

To be more scientific and systematic what we should do is document each assumption and follow it to its logical conclusion. That way if the public said we feel that A, B and C are the assumptions we want then we could say which system fits that. Of course some assumptions exclude others so they cannot choose freely but I hope you get my meaning.

I would like to know what assumptions about fairness are being made which lead to MES, EPA and SSS. I tried to document this for SSS in the concept of vote unitarity. I think you are adding a lot with the proofs you are doing because they are more rigorous mathematically. Please tell me you are keeping good notes.

@keith-edmonds (long reply coming )

Yes, I strongly agree that there are tradeoffs to be made all over the place. You can be more utilitarian or more egalitarian, but rarely both. You can have proportionality of welfare or proportionality of influence, but the two are incompatible. And if you want to be resistant (at all) to strategy, you cannot be proportional (at all).

In fact, even comparing these spectra to each other you can even prove that there are rules which are both more utilitarian and more egalitarian.... as long as you give up proportionality.

Among these tradeoffs, I prefer the latter of all three (more diverse committees, influence of a voter to change the outcome does not depend on the size of that voter's coalition, and the committee should satisfy strong proportionality guarantees). That is not to say the other choices are objectively worse, and there are good arguments for any choice of the tradeoffs, but largely on philosophical grounds I prefer these ends of the spectra.

The case of approval ballots makes comparisons of voting rules on these grounds much more tractable from a theoretical standpoint, to which end I have focused on:

The justified representation class of criteria
Proportionality degree
Utilitarian and egalitarian guarantees
Priceability, particularly with stable & equal payments when possible.
Behavior on certain bespoke preference profiles, particularly those including party-lists, laminar party-lists, and overlapping party-lists

And with respect to average-case behavior looking at

Maximin support
Nash product welfare

As an aside, an objective like that in this paper is what I would probably view as in theory the most desirable to optimize, but it’s not really possible to measure, and taken to its logical conclusion gives you sortition, which is not particularly instructive for how to elect representatives.

Anyway, as you know well, the greater expressivity of a score ballot means the space of potential voting rules is massive, many of which can all sound intuitive while returning very different results. I think it makes a lot of sense to restrict the space of these rules to those that have good theoretical guarantees on approval ballots, especially since it is a common heuristic that strategic voters will always min-max.

Nonetheless, despite the (relatively) small selection of proportional approval rules with good properties, for each of these there are usually many different ways to extend to score ballots that can really change their behavior in unexpected ways, and even two rules that coincide on approval ballots can look strikingly different. The clear tradeoffs among the approval rules as you have noted—such as those among MES, EPA, SSS, PAV, etc.—are less clear for scored rules, and it’s somewhat common for one extension to just be better than another across the board with no downsides necessary (or worse across the board lol, turns out some ideas are just bad).

EPA started as something trying to be as similar to Allocated Score as possible while maybe presenting a slight improvement in both the average case and worst case guarantees. To extend it to scores, the selection (weighted score) was the most natural choice analogous to weighted approval (aka “most budget remaining”). The reasoning behind the reweighting was born out of two patterns I noticed out of the dozens of variations/combinations of rules I tried.

Treating scores as ranks seemed to make the election process more robust to the different types of preference distributions that might be encountered; qualitatively it seemed more likely to give each voter a more equal influence on the outcome whether they had very highly clustered utilities for the candidates, very polarized utilities, and everything in-between.
Likewise, the ‘equal prices’ method of exhaustion tended to give more egalitarian outcomes, as well as being more likely to avoid strange edge cases or chaotic behavior exhibited by Allocated Score

So armed with these two observations, both of which push the method in my preferred direction on the spectra of tradeoffs mentioned above, there was only one thing which made sense to do, which was find the score above which lies a quota of budget, and then exhaust equal prices from those voters. Experimentally I can say I tried dozens and dozens of variations & recombinations of selection/reweighting rules, and this was among the best.

Just to quickly respond to some of your individual points:

One could define a different form of Justified representation such that MES fails and SSS passes based on this choice.

This is true. My personal opinion is Proportional Justified Representation is a good lower bound—anything not even passing PJR on approval ballots is not worth considering. However strengthening past that seems to be perhaps mostly a novelty.

yours completely erases all the score data. [...] I think the utility expressed by the voter is needs to be accounted for in the reweighting

Not to nitpick, but the utility expressed definitely affects the reweighting! Just, it is converted to a binary value “is above the threshold.” Also note that due to the way skipped ratings are handled, it’s not quite the same as just treating the ballot like a ranked one.

somebody who endorses a winner with a score of 1 can spend their whole ballot. My intuition is that this is unfair.

I agree that this is undesirable, but in the same sense that Perfect Representation is not always achievable, neither is it possible to only exhaust voters for their favorites. The alternative is to sometimes have broad swaths of voter budget go unspent; this is the approach that SSS takes—which has some benefits, most notably that of a more proportional distribution of welfare—but in my view it has also drawbacks in that voters will not pay equal amounts for their winners (aka less proportional distribution of influence), which can lead to bad failures of party support monotonicity.

To be more scientific and systematic what we should do is document each assumption and follow it to its logical conclusion. [...] I would like to know what assumptions about fairness are being made

I definitely agree this is a useful approach. Although sometimes, trying to build a rule from some first-principles is not particularly informative as it can lead to rules that are good, but not poly-time computable (e.g. max-Phragmen, PAV, or Chamberlin-Courant), or it leads to rules which are just very weird or bad for other, possibly unexpected, reasons (e.g. Monroe, Minimax, Sortition). That said, it does always seem useful to at least attempt to answer the questions “what motivates this method? why is it the right choice?”

Of course, this line of questioning can always lead you to one method or another depending on the level of abstraction of the fairness assumptions: for example, if you take as an assumption “the only fair outcome is the one that is the most-preferred of a majority of voters, unless none exist in which case remove the outcome most-preferred by the fewest voters,” then that leads you right to choose IRV, even though we know there might be other fairness assumptions which conflict with that choice. But in any case, you might arrive at Block Approval, for example, by demanding both

maximal utilitarianism of welfare
some incentive-compatibility guarantees

Or you might arrive at EPA by demanding

maximal egalitarianism of influence
decent proportionality guarantees

But, that is definitely not specific enough to exactly characterize EPA, and likewise there are probably other ways you could arrive at the rule.

I hope that helped explain a little bit my thought process in this proposal, and especially why I am focusing on these approval guarantees. My main point was to improve Allocated Score specifically with minimal modification and also provide some proofs (details on request), but of course I love talking about PR in a more general sense as well and I'm happy to answer any follow-ups.

Keith Edmonds

I think it makes a lot of sense to restrict the space of these rules to those that have good theoretical guarantees on approval ballots, especially since it is a common heuristic that strategic voters will always min-max.

That makes sense to me

chaotic behavior exhibited by Allocated Score

Do you have some examples of this? I have not seen that work.

Not to nitpick, but the utility expressed definitely affects the reweighting! Just, it is converted to a binary value “is above the threshold.” Also note that due to the way skipped ratings are handled, it’s not quite the same as just treating the ballot like a ranked one.

OK, point taken but the point still holds. A lot of the information expressed on the ballot it obscured. I like the MES and SSS handling of score much better.

I agree that this is undesirable, but in the same sense that Perfect Representation is not always achievable, neither is it possible to only exhaust voters for their favourites. The alternative is to sometimes have broad swaths of voter budget go unspent; this is the approach that SSS takes—which has some benefits, most notably that of a more proportional distribution of welfare—but in my view it has also drawbacks in that voters will not pay equal amounts for their winners (aka less proportional distribution of influence),

This is sort of the trade off I was talking about. I am trying to think more in terms of public outreach and referendums. If the choice of "unspent budget" vs "Spend more than you score" translates to welfare proportionality vs influence proportionality that is worth highlighting. The public will only have an opinion on the first tradeoff because the second is too technical.

In the end the goal is to move the reform effort away from STV to a better system. I think any of Allocated Score, EPA, SSS or MES would be preferable to STV but it can be the case that too many options is a problem. If we knew what axioms the public really cared about we could try to come up with a proposal which we could all agree on.

There are many slight variants of Allocated Score. It is very hard for me to know which I like best unless there is a axiom I like which constrains the options to one. So what is the choice being made which turns Allocated score into EPA/

@keith-edmonds

Do you have some examples of this? I have not seen that work.

Clarifying: EPA and AS are the same like 99% of the time—they are more similar even than AS and SSS. Just, when they do return different answers, usually it's the AS one that looks weird and it's due to edge cases with the threshold. I'll try to find a specific example.

If the choice of "unspent budget" vs "Spend more than you score" translates to welfare proportionality vs influence proportionality that is worth highlighting.

I'm not 100% sure if the tradeoff is this clear cut, but it's probably a decent heuristic for many cases!

So what is the choice being made which turns Allocated score into EPA

Great question. Here are some of my reasons, in no particular order

While I can prove a proportionality degree of (ℓ - 1)/2 for EPA, the proof relies on equal payments and I do not know how to get the result for AS
Qualitatively, it just seems more fair that voters approving the same winner should all pay the same. This is corroborated by the many nice theoretical properties of MES.
Intuitively, EPA will be slightly more egalitarian (as opposed to utilitarian) than AS, because if you think about the reweighting scheme as returning 'surplus' budget, the surplus is returned to those who started with the most; and those who started with the most are those least likely to have been represented yet.
Intuitively, EPA will be slightly more strategy-resistant than AS. This is because AS has 2 points at which it might be advantageous to try to lower a score to free-ride (1. just above threshold 2. on the threshold). Meanwhile EPA everybody on and above the threshold pay the same so there is only one point it may be advantageous to free ride. This is also one of the main reasons one might prefer either of EPA/AS over MES/SSS since the latter have an incentive at every point. The more sensitive the reweighting is to expressed utility, the more opportunities voters have to strategically manipulate their expression.
The above two intuitions are not just fantasy; I corroborated these experimentally across many preference profile distributions and strategy heuristics.
In fact, experiments were one of the main ways I landed on EPA before looking at theoretical guarantees. Empirically EPA returns better results than AS basically across the board on every metric besides total utility. In particular, the variance of utility tends to be significantly lower on instances where they disagree. While the axiom might be 'equal payments' for mostly qualitative reasons, the experiments suggest that this is a good axiom to take.

preferable to STV but it can be the case that too many options is a problem

Lol, ironically one of the things I'm finding is that in STV often too many options is the problem. It seems in terms of measuring the outcomes STV does usually get reasonable results—edge cases notwithstanding, and only so long as there are sufficiently many candidates—but empirically speaking it was competitive with the other methods.

However, it appears that the 'later-no-harm'ness for voter strategy translates into clone-positivity (teaming) for candidate strategy, so you can see some ridiculous elections in, e.g. New South Wales where there are 21 seats but literally over 700 candidates.

And the number of candidates does not appear to scale linearly with seats either. It's about what you might expect when seats are in the 5-6 range, but when #seats gets past 10 the number of candidates often really explodes.

Additionally, not to beat a dead horse, but for all we worry about complexity of rules like MES, variants of STV like Meek's (used in New Zealand) are really heinously complicated. Did you know it relies on iterating an optimization program until an arbitrary tolerance level is reached? Imagine if we could get away with that, I'd have a bunch more methods I'd like to suggest...

Anyway, that's just to say if your main goal is to shift reform effort away from STV, I would not focus on elected outcomes because in my opinion the elected outcomes compared to other PR rules (preference profiles held equal) are fine. I would focus more on the side of

candidate strategy; right now it seems that parties just throw as many candidates on their list as possible in the hopes that a voter will like one of them and rank the whole list. In something like EPA/SSS/MES/AS, this will backfire for the voter (because they fail later-no-harm), so there will likely not be as much of a clone-positive incentive.
the voter experience (e.g. maybe these methods provide a better solution than AU's forcing every voter to provide at least some minimum number of ranks)

Keith Edmonds

While I can prove a proportionality degree of (ℓ - 1)/2 for EPA, the proof relies on equal payments and I do not know how to get the result for AS

But AS could perform the same? Based on the similarity I would expect it to perform similarly.

Qualitatively, it just seems more fair that voters approving the same winner should all pay the same. This is corroborated by the many nice theoretical properties of MES.

They only differ when there is a surplus. In AS there is a threshold on score given. Above the threshold everybody pays the same (ie their whole ballot). Below the threshold everybody pays 0 even if they scored the winner. The people on the threshold pay an amount to match the quota. This does not seem unfair to me. The middle group pays some amount in the middle. In EPA the difference is that the above threshold group and the threshold group are treated the same, right? There can still be people who scored the winner who pay nothing, right? It does not seem clearly true that one method is more fair than the other as long as the distinction for how much somebody pays is based on their level of endorsement for the winner.

This is also one of the main reasons one might prefer either of EPA/AS over MES/SSS since the latter have an incentive at every point.

@Jameson-Quinn Made this point and it was ultimately why Equal Vote chose to endorse AS over SSS. This argument relies on the fact that a voter will actually be able to do such a calculation successfully. Or at least believe that they can. I am unconvinced. In fact I would argue the opposite. Since AS and EPA have major thresholds and somebody could allocated their whole ballot, they may be incentivised to put all their 1s and 2s to 0. In SSS you could only ever spend 2 on a 2 and 1 on a 1 so you are guarded from over spending. Voters will likely not behave rationally so much of it will come down to messaging anyway. Is it easier to explain to voters why they should vote sincerely in one system based on its mechanics. I would argue the mechanic in SSS does this but I am biased.

The above two intuitions are not just fantasy; I corroborated these experimentally across many preference profile distributions and strategy heuristics.

Can you give more detail? If you are saying that you have accurately simulated strategy then I am not going to believe you.

In fact, experiments were one of the main ways I landed on EPA before looking at theoretical guarantees. Empirically EPA returns better results than AS basically across the board on every metric besides total utility. In particular, the variance of utility tends to be significantly lower on instances where they disagree. While the axiom might be 'equal payments' for mostly qualitative reasons, the experiments suggest that this is a good axiom to take.

This work also included SSS and MES right? The simulations were based on my code from the "wolf Committee" right? Would you like to spend some time going through this on zoom?

variants of STV like Meek's (used in New Zealand) are really heinously complicated. Did you know it relies on iterating an optimization program until an arbitrary tolerance level is reached? Imagine if we could get away with that, I'd have a bunch more methods I'd like to suggest...

I think there needs to be a clean way to explain the system even if it is not 100% accurate to the final implementation. In campaigns, STV advocates rarely even mention surplus handling. To be acceptable a system needs to be able to be explained simply and the justification needs to be intuitive. I think MES could be acceptable if somebody came up with a good way to simply explain the selection mechanism.

Anyway, that's just to say if your main goal is to shift reform effort away from STV, I would not focus on elected outcomes because in my opinion the elected outcomes compared to other PR rules (preference profiles held equal) are fine.

The goal is not to move away from STV just because I hate STV. The goal is to offer a system which is monotonic, has a simple ballot to fill (ie not rank), can express level of endorsement (ie score) and gives something close to justified representation or sable winner sets. STV fails all these. I do not want to remove STV from its position as favourite PR system for any reason other than that it is subpar. I realize that in the majority of cases it does not matter but I think democracy is something where it really matters to be precise.

candidate strategy; right now it seems that parties just throw as many candidates on their list as possible in the hopes that a voter will like one of them and rank the whole list. In something like EPA/SSS/MES/AS, this will backfire for the voter (because they fail later-no-harm), so there will likely not be as much of a clone-positive incentive.

I do not understand this. Score systems are clone proof in the sense that your score for one candidate does not restrict the score for another. Are you saying that a party has incentive to put so many candidates that the candidates from another party are never reached when eliminating? This just points out another issue with STV. While it is technically non-partisan, in practice a bit of partisanship sneaks back in. Furthermore, the complexity of ranking incentivises people to "vote above the line" in Australia which reduces it to Party List. Only score systems allow independents to be free of parties. There are no modern examples of score systems but the theory is that they will lower partisanship via that mechanism.

the voter experience

Scoring is simple and faster than ranking.

STV is basically PR enough. I do not think that we will convince anybody to abandon it because it is not quite as PR as some of the score systems. STV is bad for other reasons. Some are listed above. If we can agree that STV is bad and there are systems which are better in all aspects then the problem becomes choosing between these other systems. This is the problem I am trying to solve. I believe the AS/EPA/SSS/MES area of models is the right one to look in. I do not think Thiele (RRV/SPAV) type systems are.

What Equal Vote did was to to rebrand AS as STAR PR. This way if a tweak like EPA turns out to be better then we can just pivot to that. This is sort of what is done with STV. It is not a single rule but a class of rules.

However, we still need to agree on a specific implementation and be able to justify it to the public.

@keith-edmonds

But AS could perform the same? Based on the similarity I would expect it to perform similarly.

Very possibly, but I have neither a proof nor a disproof.

In AS there is a threshold on score given

Well, to be pedantic, it is a threshold on weighted score. EPA is a threshold on original score. I believe an earlier iteration of AS did this same thing, but it led to a monotonicity failure, so that failure was resolved by sorting voters by weighted score. EPA also resolves that particular failure. Remember the main idea behind EPA is 'equal prices,' so any two voters who score a candidate the same should pay the same amount for that candidate, unless one of them is exhausted. This is violated by both AS and SSS.

This argument relies on the fact that a voter will actually be able to do such a calculation successfully. Or at least believe that they can. I am unconvinced.
Can you give more detail? If you are saying that you have accurately simulated strategy then I am not going to believe you.
This work also included SSS and MES right? The simulations were based on my code from the "wolf Committee" right? Would you like to spend some time going through this on zoom?

I do not have enough hubris to say that I accurately simulated strategy, but I did make an attempt to see the effects of a few different strategic heuristics. These include top-k bullet voting, bullet voting up to a frontrunner, above-average-counterfactual-utility bullets, etc.

I agree the question "what strategies are likely to be recognized and acted upon by voters" is extremely difficult to answer. I did notice general patterns like throwing out a lot of score information during the reweighting did not affect quality much and made the rules much more robust to different preference distributions, including ad-hoc strategic ones.

I included SSS and MES and dozens of other variations. I rewrote the sims in Julia for better performance so it is my own code, but your simulations had many good ideas I riffed on. Happy to find a time to discuss---maybe this weekend?

What Equal Vote did was to to rebrand AS as STAR PR. This way if a tweak like EPA turns out to be better then we can just pivot to that.

This is exactly what I'm shooting for!

Score systems are clone proof in the sense that your score for one candidate does not restrict the score for another.

Well, kind of, if voters are indeed willing to score both. Chicken dilemma (voter strategy) can cause vote-splitting though, which on the side of candidate strategy creates small incentive to stay out of the race. On the other hand, in STV there is basically no danger (for voter strategy) in ranking many candidates, so on the side of candidate strategy they may be incentivized to join the race because "what the heck, maybe I'll get lucky pick up a bunch of preferences."

I think this is another one of those tradeoffs where if you want more resistance to voter strategy you lose resistance to candidate strategy, and vice versa.

Note that I am not saying that there are large chicken dilemma issues in EPA/SSS, etc. nor are there necessarily large clone-positive issues in STV, just that it seems likely you can't be entirely free of both.

I do think some amount of partisanship will always be present in large elections—there is just no other way citizens have to organize campaign funding and marketing, communicate platforms quickly, etc. etc... but that discussion is a big can of worms so maybe not worth opening on this thread.

STV is basically PR enough [...] it is bad for other reasons
Scoring is simple and faster than ranking.

I think I like STV more than you do, but I agree with both statements. To me, one of these score PR variants > STV, but nonetheless STV >>> single winner.

As an aside: funny enough, STV on approval ballots (where the voter's weight is split evenly over remaining approvals) actually performs pretty well, but obviously is a very different scenario than regular STV. I haven't tried to analyze any of the theoretical properties though, so I have no idea what the guarantees are; probably quite poor in the worst case even if it does well on average. This paper is an interesting perspective on this type of "approval-STV"-ish rule.

By the way, I am not necessarily saying I believe EPA is superior to MES or SSS, which are harder comparisons, only that I believe it is superior to AS with few downsides.

Keith Edmonds

I believe an earlier iteration of AS did this same thing, but it led to a monotonicity failure, so that failure was resolved by sorting voters by weighted score.

Correct but not a monotonicity failure on the score. It was more like a vote management vulnerability.

I did notice general patterns like throwing out a lot of score information during the reweighting did not affect quality much and made the rules much more robust to different preference distributions, including ad-hoc strategic ones.

This also implies you get the same results between two situations when there is a nuanced difference in preference. I think this is a tradeoff which would be hard to distinguish between.

To me, one of these score PR variants > STV, but nonetheless STV >>> single winner.

Single winner STAR is better if you care more about local representation than PR. In places like Canada with large sparsely populated areas you could end up with 5 member districts the size of Europe.

Marylander

@keith-edmonds said in Proportionality Guarantees of Allocated Score (approvals):

Correct but not a monotonicity failure on the score. It was more like a vote management vulnerability.

Looking back on the debate about Allocated Score at the end of the Wolk committee, I am thinking that sorting by weighted score was effectively a janky way of trying to make the reweighting step of AS spend midrange scores for a party before all of the higher-level scores are spent. I call it jank because in my opinion, the following reweighting step is more consistent with the underlying logic of sorting by weighted score (but it is also more complex; essentially it continuously recalculates weighted score as it spends weight from the ballots):

Sort the ballots by the weighted score they gave the elected candidate. B_(1) is the ballot with the highest weighted score, B_(2) second highest, and so on.
If B_(1) has a higher weighted score than B_(2), then spend enough weight from B_(1) such that B_(1) and B_(2) have the same weighted score.
After that, if B_(1) and B_(2) have higher weighted scores than B_(3), then spend enough weight from B_(1) and B_(2) so that they will have the same weighted score as B_(3).
Keep repeating this process until a quota of weight is spent. If B_(i) is the last ballot to require any of its weight to be spent, then only spend enough weight from ballots B_(1),...,B_(i) so that a full quota will be spent, and proportion the spend such that their weighted score for the winning candidate will be equal.

For example, the case that motivated the shift:
Red = 21%: A5,B0,C0
Green = 41%: A0,B4,C5
Blue = 38%: A0,B3,C0
(5 winners)

The first winner is from party B. Standard allocated score allocates 20% worth of green ballots to the first winner.

This alternative reweighting step would first spend 10.25% from the green ballots. After that, the weighted score for party B that the green and blue ballots have become equal, but there is still 9.75% that needs to be spent. Approximately 4.36% of this comes from green, and 5.39% from blue.

So in total, ~14.61% is spent from green, and ~5.39% is spent from blue to elect the first candidate.

@marylander That's quite an interesting idea, I haven't seen it before.

Although, may I ask why it is important to you that the price paid by a voter depends at all on their current ballot weight? It has always felt a little weird to me that one voter may pay less than another for the same amount of utility, just because that voter happened to have another winner already elected. After all, the other voter might have another winner elected in a future round, and we do not go back and retroactively credit them some ballot weight.

Marylander

@andy-dienes said in Proportionality Guarantees of Allocated Score (approvals):

Although, may I ask why it is important to you that the price paid by a voter depends at all on their current ballot weight?

I'm not necessarily advocating this as a method. I just think that understanding this reweighting procedure is important to understanding what the change to allocated score to sort the ballots by weighted score rather than unweighted score actually does, because it is a "limit case" of the allocated score reweighted step. If instead of applying one allocated score reweighting step to spend the entire quota, we applied many reweighting steps that each spent a tiny portion of the quota (like partitioning an interval), then as the size of the largest reweighting step approached 0, the result would approach that of the procedure I described.

@andy-dienes said in Proportionality Guarantees of Allocated Score (approvals):

After all, the other voter might have another winner elected in a future round, and we do not go back and retroactively credit them some ballot weight.

I did make a method that did just that. (It's an SSS variant.) However, similar to what you said about Meek STV,

@andy-dienes said in Proportionality Guarantees of Allocated Score (approvals):

it relies on iterating an optimization program until an arbitrary tolerance level is reached

@marylander

If instead of applying one allocated score reweighting step to spend the entire quota, we applied many reweighting steps that each spent a tiny portion of the quota (like partitioning an interval)

Ok, I understand the perspective now. I know you are not advocating for this, but I will admit its motivation seems pretty poor to me.

Just to illustrate, I've found it helpful to think of these reweighting schemes visually; consider what happens in the approval case. Imagine we choose a winner, and we line up the voters from left to right in decreasing order of budget, which we plot on the y axis.

Assume there is a surplus, so we need to pick some subset of that budget such that the integral = 1 quota.

The way, e.g. SSS picks that subset is to scale the entire curve down a little bit, and spend that amount from each voter below the curve.
MES (and EPA) will draw a horizontal line and spend the budget below that line.
Allocated Score (sorting only on score) will do the same thing as SSS.
Allocated Score (sorting on weighted score) will give you two horizontal lines, one at 1 for all above the threshold, and one at some intermediate value on the threshold. Budget below those lines is spent.

If I am understanding this reweighting procedure correctly, it will draw a horizontal line and then spend all the budget above that line. This also has the effect that, no matter how many prior winners, after electing a winner almost all her supporters will be set to the same budget.

However, it will actually probably still satisfy many of those theoretical bounds I originally posted, since most of those only require that 1. a quota of budget is spent from supporters (but doesn't really matter how) and 2. the cand with highest weighted vote wins

Keith Edmonds

Hi @marylander,

In a chat with @Andy-Dienes the other day we came up with a new idea which is somewhat like what sequentially Shrinking Quotas does. There are are least two ways to implement it but the way I like best is as follows:

It is the same as SSS except if there is a shortfall in reaching a quota to spend
In that case you ADD some amount of "Ballot Weight" such that the "weighted Ballot" when summed for the winner is exactly a quota

It is doing the same thing as SSQ except that instead of changing the quota size to achieve the goal it it changes every bodies amount of ballot to spend. This gives voting power to those who will elect a candidate in subsequent steps but also to those who are already exhausted. Voters can come back from exhaustion. It gives the same result as SSS in most cases. I can give code if you would like.

I think it is actually doing what the true intent of SSS is better than SSS. That intent is to elect a utilitarian winner then adjust every bodies ballot weight "fairly". I tried to formalized "Fairly" with the concept of Vote Unitarity but I think I originally missed something. I think it is important to only subtract away the amount of influence they used to elect the winner. In the case of surplus the amount is reduced proportionally to that influence. In the case of shortfall I had thought it was fair to just take it all since that was the amount and no other group was going to put up that much for another candidate. However, This short-changes the prior winner and people with overlapping preferences. Since in the case of a shortfall I am effectively giving them ballot weight I need to give that amount to others.

Do you have thoughts on this idea? I can add code of you want.

Marylander

@keith-edmonds

@keith-edmonds said in Proportionality Guarantees of Allocated Score (approvals):

Do you have thoughts on this idea? I can add code of you want.

That would be useful. How do you decide whom to give weight back to? Is it even across the ballots?

(Sorry I am getting to this so late. I haven't had the spare time I'd need to read the forum posts carefully.)

Just going to add that I recently worked out a proof of another guarantee.

Call a group weakly (B, M)-cohesive if it comprises at least M quotas, and each voter approves at least B of some set of M candidates. We can extend PJR to "weakly" cohesive groups by requiring that they get at least B winners in total. If EJR is extended this way then you get "Fully Justified Representation" as was introduced in the same paper introducing MES.

We can also extend proportionality degree to weakly cohesive groups, asking "what is the average number of winners approved per ballot in a weakly cohesive group."

It is not hard at all to show that all of AS, SSS, MES, EPA satisfy the PJR extension above. However what's more interesting, the proof I worked out concludes that for both MES and EPA the proportionality degree of a weakly cohesive group is at least (B - 1)/2.

edit: I think the same result should actually hold for SSS (on approval ballots) @Keith-Edmonds , but the proof does not apply to AS.

Marylander

~~@andy-dienes I see it as a "continuous" version of the AS reweighting procedure. One motivation for it is that the AS reweighting procedure being discontinuous can lead to chaotic outcomes.~~

~~25: A5 C3~~
~~25: A5~~
~~50: B5 C3~~
~~1: A5 B4~~
~~4 winners~~
~~A, B, C, A~~

This was a draft that got posted by mistake.

@marylander I'm not sure I quite understand the example. Won't Allocated Score in this instance also give ABAB? And even still, I think ABAC is not entirely unreasonable (although I agree it is probably worse)

Marylander

@andy-dienes Sorry I actually didn't mean to post that. I had it saved in drafts but hadn't fully worked out the example. I should probably check to make sure that other drafts of mine didn't get posted by mistake.

Edit: Yeah I think all of my drafts were posted because of some glitch with the mobile website.

Keith Edmonds

@marylander said in Proportionality Guarantees of Allocated Score (approvals):

That would be useful. How do you decide whom to give weight back to? Is it even across the ballots?

I sent you an email. Let me know if you don't get it.