Sequentially Spent Score

From electowiki

Sequentially Spent Score (SSS) is a sequential Multi-Winner Cardinal voting system. Voters score candidates, generally from 0-5, using Score voting ballots. Each round's winner is the candidate who has the highest sum total score. When tabulating the ballots, each voter begins with 5 stars to spend in order to gain representation and voters spend those stars when a candidate they supported is elected. If a voter scored a candidate 3 stars, that voter could only spend up to three stars to help elect that candidate.-- Voters cannot influence subsequent rounds more than the stars they have remaining. This property of spending stars is a particular implementation of Vote Unitarity.


Background

Sequentially Spent Score was invented by Keith Edmonds and is also known as Sequentially Subtracted Score or Unitary Cardinal Voting. The concept of Vote Unitarity was defined to describe its underlying theory.

Procedure

Each voter starts with 5 stars, (the max possible score which can be given to any candidate.) Depending on the number of seats up for election, each seat also has a set max cost.

  • Max cost to win a seat = (number of voters / number of seats up for election)) x 5

Sequentially Spent Score works by a four-step process:

  1. Elect the candidate with the highest total sum of score.
  2. Each voter spends the amount of stars they gave the elected candidate. Voters may get some "change" back if the candidate received more support than needed.
    • If a voter had given the winner 3 stars they would spend all 3 stars. If a voter had given the winner 1 star they only spend 1.
    • If the set of voters supporting the highest scoring candidate collectively put up more than the max cost to elect a candidate, some "change" (surplus handling) is returned to those voters.
  3. For ballots which spent stars to elect a candidate, the amount of stars available for remaining candidates is then reduced by that amount through fractionally reducing the ballot weight.
    • Max possible score remaining = 5 - (stars given to winner) + change
    • If the number of stars is reduced to 3 from 5 by spending 2 the ballot weight is reduced to 3/5 and all scores on the ballot are reduced to 3/5 their original value.
  4. Repeat until all the necessary seats are filled.


Surplus Handling

For the second step, if that candidate had received more than a predefined threshold of points (usually defined as a Hare Quota of the ballots multiplied by 5), then the amount of score points to take away from the ballots supporting that round's winner is to be reduced proportionally to ensure that only the equivalent in ballot weight of that predefined threshold of points is removed. This is known as Fractional Surplus Handling.

Specifically, in the second step, the score given to the winner is divided by (the total score given to that winner) * (Total number of Winners)/ (Total number of voters). This is a number greater than 1 and hence reduces the amount spent on that winner by each voter.

Python Implementation

Given a Pandas dataframe S with columns representing candidates and rows representing voters the entries would encode the score of all the ballots. For a max score of K and a desired number of winners W.

import pandas as pd
import numpy as np

def SSS(K, W, S):
    #Normalize score matrix
    ballots = pd.DataFrame(S.values/K, columns=S.columns)
    
    #Find number of voters
    V = ballots.shape[0]
    quota = V/W
    ballot_weight = pd.Series(np.ones(V),name='weights')
    
    #Populate winners in a loop
    winner_list = []
    while len(winner_list) < W:
    
        weighted_ballots = ballots.multiply(ballot_weight, axis="index")
       
        #Select winner
        w = weighted_ballots.sum().idxmax()
    
        #Add winner to list
        winner_list.append(w)
    
        #Check for Surplus
        surplus_factor = max( weighted_ballots[w].sum()/quota , 1.0)
                
        #Score spent on winner by each voter
        score_spent =  weighted_ballots[w] / surplus_factor
        
        #remove winner from ballot
        ballots.drop(w, axis=1, inplace=True)
        
        #Total score left to be spent by each voter
        ballot_weight = (ballot_weight-score_spent).clip(0.0,1.0)
    
    return winner_list

Variants

Capping variant

A variant of this method can be made in step 3 of the procedure by "capping" instead "scaling" to adjust ballot support for candidates after the ballot's weight has been adjusted. Capping is when, if a ballot's weight has been reduced by a certain amount, a ballot that gives a candidate more support than its weight allows is edited to give that candidate only as much support as its ballot weight. In other words, if a ballot is at 50% weight (50% power), yet it gives a candidate 80% support (a score of 8 out of 10, for example), it is adjusted to give that candidate 50% support instead(a score of 5 out of 10, for example).

The standard Scaling version is when the amount of support a ballot gives a candidate is proportionally adjusted by how much weight it has remaining. In other words, a ballot with 50% weight that originally gave a candidate 80% support when it had full weight will now give that candidate 40% support. Not that this is 10% less than in the capping version. The reason why capping makes sense is that a candidate who has 50% weight "should" be able to give all that support to a candidate they expressed 80% for on their ballot.

This is the original version of SSS it was abandoned when examples such as the following were found.

There are 17 candidates A, B1, ... B4, C1, C2, D1, ..., D10.
Unless specified explicitly, assume a voter gives zero stars to a candidate.
5 voters give 3 stars to A and 5 stars to D1
5 voters give 3 stars to A and 5 stars to D2
6 voters give 3 stars to B1, 2 stars C1 and 5 stars to D3
6 voters give 3 stars to B1, 2 stars C1 and 5 stars to D4
6 voters give 3 stars to B2, 2 stars C1 and 5 stars to D5
6 voters give 3 stars to B2, 2 stars C1 and 5 stars to D6
6 voters give 3 stars to B3, 2 stars C2 and 5 stars to D7
6 voters give 3 stars to B3, 2 stars C2 and 5 stars to D8
6 voters give 3 stars to B4, 2 stars C2 and 5 stars to D9
6 voters give 3 stars to B4, 2 stars C2 and 5 stars to D10

The number of voters is n = 58. Assume the committee size is W = 6. The capped version SSS will select B1, B2, B3, B4, C1, C2. This means that the first group of 10 voters will get no representative they like in the elected committee. Yet they form more than 1/6th of the society. If D1 and D2 were not in the election then the first group of 10 voters would have given 5 stars to A electing A. Candidate A would be selected in either situation by the standard scaling variant. This example shows a failure of Justified representation by the capping version.

Procedure

SSS procedure

Each voter starts with 5 stars, (the max possible score which can be given to any candidate.) Depending on the number of seats up for election, each seat also has a set max cost.

  • Max cost to win a seat = (number of voters / number of seats up for election)) x 5

Sequentially Spent Score works by a four-step process:

  1. Elect the candidate with the highest total sum of score.
  2. Each voter spends the amount of stars they gave the elected candidate. Voters may get some "change" back if the candidate received more support than needed.
    • If a voter had given the winner 3 stars they would spend all 3 stars. If a voter had given the winner 1 star they only spend 1.
    • If the set of voters supporting the highest scoring candidate collectively put up more than the max cost to elect a candidate, some "change" (surplus handling) is returned to those voters.
  3. For ballots which spent stars to elect a candidate, the amount of stars available for remaining candidates is then capped at the number of stars that voter has left, (max possible score remaining). Recalculate the sum total for each candidate using the capped ballot scores.
    • Max possible score remaining = 5 - (stars given to winner) + change
    • Capped ballot scores = 5 - score spent in preceding rounds, or, the original score given, whichever is higher.
  4. Repeat until all the necessary seats are filled.


Python Implementation

Given a Pandas dataframe S with columns representing candidates and rows representing voters the entries would encode the score of all the ballots. For a max score of K and a desired number of winners W.

import pandas as pd
import numpy as np

def SSS_clipped(K, W, S):
    #Normalize score matrix
    ballots = pd.DataFrame(S.values/K, columns=S.columns)

    #Find number of voters
    V = ballots.shape[0]
    quota = V/W
    ballot_weight = pd.Series(np.ones(V),name='weights')

    #Populate winners in a loop
    winner_list = []
    while len(winner_list) < W:

        #Select winner
        w = ballots.sum().idxmax()

        #Add winner to list
        winner_list.append(w)

        #Check for Surplus
        surplus_factor = max( ballots[w].sum() /quota , 1.0)

        #Score spent on winner by each voter
        score_spent =  ballots[w] / surplus_factor
        
        #remove winner from ballot
        ballots.drop(w, axis=1, inplace=True)
        
        #Total score left to be spent by each voter
        ballot_weight = (ballot_weight-score_spent).clip(0.0,1.0)

        #Update Ballots as the minimum of original score and score remaining
        mins = np.minimum(ballots.values,ballot_weight.values[:, np.newaxis])
        ballots = pd.DataFrame(mins, columns = ballots.columns)
        
    return winner_list

Sorted Surplus Handling

The standard surplus handling treats everybody equally which can result in a potential centrist bias. Consider the 5 winner toy example

  • 41% A:5 B:2 C:0
  • 20% A:0 B:5 C:0
  • 41% A:0 B:2 C:5

where only Bs are elected. This bias gives strategic incentives to truncate. To avoid this scenario one can take the quota of score form the most highly endorsing voters first. This adds additional complexity as a sort is difficult manually but some consider it worth the tradeoff.

Quota of Ballot Selection

In the first step one need not choose the Utilitarian winner. A reasonable alternative is to take the winner as the candidate who has the highest sum of score in the Hare (or Droop ) Quota of Ballots that most support them. This is the selection method from Sequential Monroe

Dynamic Quota

Sequentially Shrinking Quota is a modification to limit Free riding

Vickrey Quota

There is an argument that taking a whole Hare Quota of score is not justified when the runner up did not get that much support. This is because the candidate need only to beat their closest competitor and so taking more score than that from their supporters will distort later rounds. This is similar to the Dynamic Quota in Sequentially Shrinking Quota but it is not retroactive. What is done in this variant is to only subtract off a Vickrey Quota when the runner up has less than a Hare Quota. A Vickrey Quota is the smaller of the runner up's total score and a Hare Quota. It derives its name from Vickrey auctions.

Sequentially Spent STAR voting

Sequentially Spent STAR voting is a variation of Sequentially Spent Score in which a runoff is added to the final seat up for election, so that the two highest scoring candidates are finalists and the finalist preferred by more voters wins the seat. This variation is helps to incentivize voters to show their full preference order.

Related Systems

It is the natural extension of the Hamilton method which is used in Partisan Systems to Multi-Member System. In this sense it fits into the Monroe class of Proportional Representation. Since score is a conserved quantity which is spent like money there is a natural analogy to Market based voting.

Criteria

Monotone Pareto IIA Clone proof Participation Hare Quota Criterion Universally liked candidate criterion
Sequentially Spent Score Yes Yes Yes Yes No Yes Yes

Participation

Because this system is a Monroe type which is derived from the Hamilton method it fails participation. An illustrtive example is as follows.

To simplify, let's consider a 2-seat election in a max=10 score. The candidates are all clones of type A and B.

Case 1:

30 voters: A=10, B=0
9 voters: A=0, B=10
1 voter: A=1, B=10

Without the 1 voter giving a score of 1 to A, it would be a tie for the second seat so this score means that A gets both seats. But then if you add one voter.

Case 2:

30 voters: A=10, B=0
9 voters: A=0, B=10
1 voter: A=1, B=10
1 voter: A=1, C=10

The extra voter changes the quota size and causes B to get the second seat, even though they prefer A to B.

Math Details

For Case 1

Score quota = 40*10/2=200

A is the first winner with 301

Ballots spend 200/301 times their support for A

30 voters: A=3.4, B=0
9 voters: A=0, B=10
1 voter: A=1, B=9.33

A has 100.66 and B has 99.33. Close but the winner set is {A,A}

For Case 2

Score quota = 41*10/2=205

A is the first winner with 302

Ballots spend 205/302 times their support for A

30 voters: A=3.2, B=0
9 voters: A=0, B=10
1 voter: A=1, B=9.32
1 voter: A=1, C=10

A has 98.36 and B has 99.32. Close but the winner set is {A,B}. So the C supporter ruined it for the second A candidate. This is a failure of participation.