Proportionality Guarantees of Allocated Score (approvals)

@keithedmonds 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 higherlevel 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.

@andydienes 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.
@andydienes 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,
@andydienes said in Proportionality Guarantees of Allocated Score (approvals):
it relies on iterating an optimization program until an arbitrary tolerance level is reached

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


Hi @marylander,
In a chat with @AndyDienes 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 shortchanges 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.


@keithedmonds 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) @KeithEdmonds , but the proof does not apply to AS.

@andydienes 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, AThis 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)

@andydienes 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.

@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.

another way to look at the difference between EPA and AS (at least, on approval ballots) is that EPA spends ballot power such the variance in amount spent per utility gain is exactly minimized, and AS spends ballot power such that the variance in amount spent per utility is exactly maximized. Despite their similarities, in that respect they represent two ends of an extreme.