Threshold Equal Approval

From electowiki

Threshold Equal Approval (TEA) is a proportional representation voting method using 5 star ballots.[1]

Description

Winners in Threshold Equal Approval are selected in rounds. The threshold starts at 5 stars, and each round the threshold, above which counts as an approval, is decreased until some candidate gets a quota of approvals. That candidate is elected and a quota's worth of ballot power is taken from the supporters. If multiple candidates get a quota of approvals, the tie is broken by electing the one who can spread out the cost of ballot power more evenly over their supporters.

Classification

Threshold Equal Approval is a sequential, multi-winner, cardinal, proportional representation voting method. Being essentially only a minor modification of the well-studied Method of Equal Shares (MES), it inherits all the proportionality guarantees of MES (as appropriately extended to rated ballots) and is thus among the most axiomatically robust known proportional multiwinner rules.

Procedure

Each voter scores all candidates on a [0,5] scale

  1. Initialize the threshold at 5 stars.
  2. If there is any candidate scored a 5 on at least a quota's worth of ballots, then elect the one who can spread their cost (one quota of ballot weight) most evenly over their supporters.
  3. If there is no candidate getting a quota of 5-star ballots, reduce the threshold to 4 stars, and try again. If still none, reduce threshold to 3 stars, etc.
  4. Subtract an equal amount of ballot weight from all voters supporter the winner above the threshold such that a total cost of one quota is taken
  5. Repeat this process until all the seats are filled.

Just like MES, this procedure may not be resolute. That is, it maybe be possible that in step 3 there is no candidate who gets a positive score from more than a quota of ballot weight. A very simple procedure to finish the election is simply to then elect the candidate scored positively on the most ballots (weighted by ballot weight) and exhaust all such ballots; this will reduce to Hamilton in the party-list case and is provided in the Julia/Python implementations below. A more sophisticated (and potentially more theoretically compelling) procedure to finish the election is to run rounds of seq-Phragmen using scores above zero as approvals, with the initial loads being given by the spent budgets of the voters---this is the procedure that MES uses in its second stage, and it will reduce to Jefferson/D'Hondt in the party-list case.

Motivation

Many designs for sequential cardinal proportional methods rely heavily on the assumption of linearly additive utilities over sets; that is, if a voter's score for candidate A is 3, and their score for candidate B is 2, and their score for candidate C is 5, then the voter is presumed to be just as happy with the outcome {A, B} as they would be with {C}. The problem with this line of thinking is that the number of seats in a committee is fixed, and each candidate elected comes at the opportunity cost of a more-preferred candidate. It may not even be possible to map a voter's preferences over sets of candidates to a single linearly additive utility for each candidate individually.

By way of example, suppose from a voter's perspective they are facing an election where there are four parties fielding candidates: {Amazing, Ok, PrettyDarnBad, and MorallyDespicable}. Putting aside the question of strategic voting for a moment, how can a voter even begin to try to sincerely score these parties, knowing that the scores will assume linearly additive utilities over sets. It seems clear Amazing should be scored 5 stars, and MorallyDespicable 0 stars. But now, if the voter scores PrettyDarnBad 2 stars, would it be reasonable for the method to say that the voter is equally satisfied with five winners from the PrettyDarnBad party as they would be with two winners from the Amazing party? Probably not. Fundamentally, there just might not exist *any* set of scores that the voter can give to the parties such that they are equally satisfied by any choice of 5-stars-worth of candidates, and this is because this interpretation of the scores cannot capture the opportunity cost arising from the fixed number of seats.

Another drawback of the linearly additive utility assumption for set-valued preferences is that it creates an inherent trade-off between a voter's ability to express preference within their own coalition, and their ability to express preferences over other coalition's candidates. If a `quota' is measured in score, in that five quotas of 3 stars is equivalent to 3 quotas of 5 stars, then coalitions are rewarded for being `more cohesive,' in the sense that they can only guarantee their deserved number of seats if every single member of the coalition awards the maximum score of 5 stars to every single candidate in that coalition. Any amount of vote-splitting or intra-party preference will lead to lower sums-of-score, and will be regarded by the method as a lack of cohesion and punished with fewer seats.

To try to avoid (or at least mitigate) some of these problems, Expanding Approvals entirely rejects the linearly additive interpretation of utilities, and instead tries to extend the guarantee of lower quota as far as it will go. In particular, Threshold Equal Approvals will satisfy the mathematical property that:

 For any group of voters at least T quotas in size, and for any score S, it must be true that either
1. the group has (in aggregate) at least T elected winners scored at least S, OR
2. there is no suitable unelected candidate that the group can agree on with a score >= S

The above guarantee is basically an extension of Justified representation to apply simultaneously at every single possible score threshold. An intuitive view of how scores are interpreted under this paradigm might be that each score S from a voter answers the question "do you want to be inside or outside this candidate's S-coalition? ", so a voter in the previous example might decide they want to be in the 5-star coalition for Amazing, in the 2-star coalition for Ok, and 1-star coalition for PrettyDarnBad; since all 5-star coalitions will be represented before any 2-star coalition, the voter can be sure they will not be "cheated" with 3 Ok seats in lieu of a singular Amazing seat.

Julia Implementation

Input a DataFrame with columns representing candidates and rows representing voters, so the entries encode the score of all the ballots.

using DataFrames

function max_voter_weight_taken(ballot_weight::Vector{Float64}, quota) 
    # This will be a helper function. Given a set of ballot weights for voters supporting
    # a winner, it spreads the cost of the winner equally over the supporters and returns
    # the maximum amount of weight needed to take such that one quota in total is allocated.

    total_support = sum(ballot_weight)
    if total_support < quota && !isapprox(total_support, quota)
        # In this case, the supporters do not comprise a full quota of ballot weight
        return Inf
    end

    cost_remaining = quota
    voters_remaining = size(ballot_weight, 1)
    for current_voter_weight in sort(ballot_weight)
        # There will be some cost per voter such that every voter with weight less than that
        # value gets fully exhausted (aka allocated), and all the voters with greater than that
        # value spend an equal amount. So, starting from the voters with the least weight, try
        # to exhaust them and split the remaining cost equally over remaining supporters.
        

        if current_voter_weight * voters_remaining   cost_remaining
            # In this case, remaining voters can split remaining cost equally
            break
        end

        if isapprox(current_voter_weight * voters_remaining, cost_remaining)
            # Same as above, but catches edge cases that fail due to floating point imprecision
            break
        end

        cost_remaining -= current_voter_weightvoter_weight
        voters_remaining -= 1
    end

    ρ = cost_remaining / voters_remaining
    @assert(ρ  1)
    return ρ
end

function ThresholdEqualApproval(ballots::DataFrame, seats::Int; maxscore::Int=5, clones=false)
    numvoters = size(ballots, 1)

    # Default to Hare quota
    quota = numvoters / seats

    # Initialize each voter with a ballot weight of one
    voter_weights = ones(numvoters)

    # Initialize threshold at top score
    threshold = maxscore

    elected = []
    while length(elected) < seats
        if clones
            df = ballots
        else
            # If clones are not allowed, we have to drop previous winners from consideration.
            df = ballots[!, Not(elected)]
        end

        if threshold == 0
            # No candidate is supported by at least a quota of ballot weight.
            # Default to highest weighted score
            candscore, candname = findmax(eachcol(
                mapcols(voter_scores -> sum((voter_scores .> 0) .* voter_weights), df)
            ))

            # Exhaust all voters supporting the winner
            voter_weights[df[!, candname] .> 0] .= 0
            push!(elected, candname)
            continue
        end

        # The below function will take a list of voters' scores for a candidate, alongside their remaing budget and
        # together with the current approval threshold and quota will compute the equal weight taken from all voters.
        cost(voter_scores) = max_voter_weight_taken(voter_weights[voter_scores .≥ threshold], quota)

        # Now map the cost function over each candidate and select the one with lowest cost
        candcost, candname = findmin(eachcol(
            mapcols(cost, df)
        ))
        candcost = first(candcost)

        if isinf(candcost)
            # So no candidate was affordable at this threshold. Reduce and try again
            threshold -= 1
            continue
        end

        # Subtract the equal cost from each voter scoring above the threshold.
        # Exhaust if cost greater than remaining ballot weight.
        voter_weights[df[!, candname] .≥ threshold] .= max.(0, voter_weights[df[!, candname] .≥ threshold] .- candcost)
        push!(elected, candname)

    end

    return elected
end


function main()
    TN = DataFrame(zeros(100, 4), ["Memphis", "Nashville", "Chattanooga", "Knoxville"])
    
    TN[!, "Memphis"][1:42] .= 5

    TN[!, "Nashville"][1:42] .= 2
    TN[!, "Nashville"][43:68] .= 5
    TN[!, "Nashville"][69:83] .= 3
    TN[!, "Nashville"][84:100] .= 2

    TN[!, "Chattanooga"][1:42] .= 1
    TN[!, "Chattanooga"][43:68] .= 2
    TN[!, "Chattanooga"][69:83] .= 5
    TN[!, "Chattanooga"][84:100] .= 4

    TN[!, "Knoxville"][43:68] .= 1
    TN[!, "Knoxville"][69:83] .= 3
    TN[!, "Knoxville"][84:100] .= 5

    println(ThresholdEqualApproval(TN, 2))
end
main()

Python Implementation

Input a DataFrame with columns representing candidates and rows representing voters, so the entries encode the score of all the ballots.

import pandas as pd
import numpy as np

def ThresholdEqualApproval(ballots: pd.DataFrame, seats: int, maxscore=5, clones=False):
    ballots = ballots.copy()
    numvoters, _ = ballots.shape

    quota = numvoters / seats
    voter_weights = np.ones(numvoters)
    threshold = maxscore
    elected = []

    while len(elected) < seats:

        if threshold == 0:
            winner = ballots.ge(0).mul(voter_weights, axis=0).sum().argmax()

            voter_weights[ballots[winner] > 0] = 0

            elected.append(winner)
            if not clones:
                ballots = ballots.drop(winner, axis=1)

            continue
        
        # Above is default exhaustion with weighted score
        ##################################################
        # Below is searching for a threshold lower quota

        sort_weights = np.sort(voter_weights)
        sort_ballots = ballots.loc[np.argsort(voter_weights), :]

        approval_df = (sort_ballots >= threshold)
        weighted_approvals = approval_df.mul(sort_weights, axis=0)
        cost_remaining = quota - (
            weighted_approvals.shift(fill_value=0).cumsum()
        )
        supporters_remaining = approval_df.sum() - (
            approval_df.shift(fill_value=False).cumsum()
        )

        split_cost = cost_remaining / supporters_remaining
        split_cost.replace(-np.inf, np.inf, inplace=True)

        quota_filled = (split_cost <= weighted_approvals) | np.isclose(split_cost, weighted_approvals)

        if not quota_filled.max().max():
            threshold -= 1
            continue

        has_quota = quota_filled.max()
        split_voters = quota_filled.idxmax()

        winner = split_voters[has_quota].idxmin()
        uniform_cost = split_cost[winner][split_voters[winner]]

        voter_weights[ballots[winner] >= threshold] -= uniform_cost
        voter_weights = voter_weights.clip(0, 1)

        elected.append(winner)
        if not clones:
            ballots.drop(winner, axis=1, inplace=True)

    return elected

if __name__=="__main__":
    TN = pd.DataFrame()

    for col in ["Memphis", "Nashville", "Chattanooga", "Knoxville"]:
        TN[col] = np.zeros(100)

    TN["Memphis"][0:42] = 5

    TN["Nashville"][:42] = 2
    TN["Nashville"][42:68] = 5
    TN["Nashville"][68:83] = 3
    TN["Nashville"][83:100] = 2

    TN["Chattanooga"][0:42] = 1
    TN["Chattanooga"][42:68] = 2
    TN["Chattanooga"][68:83] = 5
    TN["Chattanooga"][83:100] = 4

    TN["Knoxville"][42:68] = 1
    TN["Knoxville"][68:83] = 3
    TN["Knoxville"][83:100] = 5

    print(ThresholdEqualApproval(TN, 2))

Related

Threshold Equal Approval is very similar to Expanding Approvals Rule and even more similar (practically identical) to the Method of Equal Shares (MES) on ordinal ballots, and these both share similarities to what has been called the Bucklin Transferable Vote; the main difference to all of these is the cardinal ballot and the allowance of skipped ratings, and the sum-of-score behavior in the ending rounds if no candidate can get a quota.

Links

References