I was considering methods that are well-suited for electing groups of 3 or 5 candidates (for example, choosing regional representatives in a larger body, or appointing a small city coucil). I know of Single Transferrable Vote, which uses a ranked ballot; but I know ranked ballots in single-winner elections are inferior to score-based ballots, due to Arrow’s Theorem. This made me consider cardinal (i.e. score-based) multi-winner elections.
Wikipedia names “proportional approval voting” and “sequential proportional approval voting” as such methods, but both come up short- the first (PAV) is not computationally tractable for large enough races (it defines a score, and says to consider every single possible combination of candidates to find which one maximizes this score), while the second (SPAV) will always appoint the approval winner, even when a more proportional result can be acheived by appointing a different candidate instead.
I devised the following algorithm that runs in O(n), but will often produce a more broadly acceptable result than SPAV:
An algorithm for choosing a good winner in a multi-member form of approval voting
Start with an empty stack of candidates
Tally the approvals of each candidate, and push the most-approved candidate to the stack
Reweight the votes, such that if a voter supports n candidates currently in the stack, their vote is worth 1 / (n + 1) of their original weight
Push the most-approved candidate to the stack
Pop the earliest added candidate off of the stack (they are no longer in it)
Reweight and push a candidate onto the stack
Reweight and push again
Repeat 5 − 7 until the number of candidates on the stack equals the total number of seats
Calculate the satisfaction score of this stack as the sum of [1 + 1⁄2 + … 1/n where n is the number of candidates in the stack that the voter supports] over all voters. Record this stack as well as its satisfaction score.
Pop and push, then record the satisfaction score of the new stack
Repeat step 10 until the number of stacks considered is equal to the number of candidates
Return whichever of the considered stacks has the highest satisfaction score as the output of the election
I was considering methods that are well-suited for electing groups of 3 or 5 candidates (for example, choosing regional representatives in a larger body, or appointing a small city coucil). I know of Single Transferrable Vote, which uses a ranked ballot; but I know ranked ballots in single-winner elections are inferior to score-based ballots, due to Arrow’s Theorem. This made me consider cardinal (i.e. score-based) multi-winner elections.
Wikipedia names “proportional approval voting” and “sequential proportional approval voting” as such methods, but both come up short- the first (PAV) is not computationally tractable for large enough races (it defines a score, and says to consider every single possible combination of candidates to find which one maximizes this score), while the second (SPAV) will always appoint the approval winner, even when a more proportional result can be acheived by appointing a different candidate instead.
I devised the following algorithm that runs in O(n), but will often produce a more broadly acceptable result than SPAV:
An algorithm for choosing a good winner in a multi-member form of approval voting
Start with an empty stack of candidates
Tally the approvals of each candidate, and push the most-approved candidate to the stack
Reweight the votes, such that if a voter supports n candidates currently in the stack, their vote is worth 1 / (n + 1) of their original weight
Push the most-approved candidate to the stack
Pop the earliest added candidate off of the stack (they are no longer in it)
Reweight and push a candidate onto the stack
Reweight and push again
Repeat 5 − 7 until the number of candidates on the stack equals the total number of seats
Calculate the satisfaction score of this stack as the sum of [1 + 1⁄2 + … 1/n where n is the number of candidates in the stack that the voter supports] over all voters. Record this stack as well as its satisfaction score.
Pop and push, then record the satisfaction score of the new stack
Repeat step 10 until the number of stacks considered is equal to the number of candidates
Return whichever of the considered stacks has the highest satisfaction score as the output of the election
I think you mean a queue rather than a stack.
Correct, yeah