social choice midterm

Plurality Method

method that selects a winner based on whichever
candidate received the highest number of (first choice) votes.

majority candidate

one who is placed first by more than half the voters

has plurality, would be a Condorcet

Spoilers (overall)

Candidates that wouldn’t win and affect the vote for other candidates

(or: candidates excluded from a runoff election)

Runoff election

Secondary election off of a plurality election with two leading candidates

Elimination method

(4+ candidates, works for multiple rounds, one candidate eliminated each round, lowest vote-getter, ends up with last two or a majority) 

Reduced preference schedule

• Summarizes/combines preferences by number of ballots with same rankings, helps to find answers to different questions about the results

• Make scompact all the information you have, compress voters who vote the exact same way

• Works with the Principle of One Person, One Vote

Principle of one person, one vote

If the outcome of an election method only depends on the reduced preference schedule (RPS), then we say it satisfies the principle of one person one vote

Borda Score method

• Uses Borda Points (i.e. 4 possible candidates, 4 points per preference ballot if ranked first on the ballot, 3 points if ranked second, etc.) 

  • Relies on reduced pref. schedules, averages relative rank among all voters

  • Satisfies OPOV principle

  • However many candidates there are = # of points for first place

• Candidate with greatest Borda score wins

pairwise comparison graph

• Draw line from winner to loser (arrow away means that candidate won) 

• Represents societal preferences, candidates score points based on the number of candidates they would beat head to head 

• Greatest possible number of head to head battles a candidate can win in the PWC is 1 less than the number of candidates

Condorcet candidate

• a candidate that would win a head-to-head
  competition against any/every other candidate

(comparison between the only themselves and one other candidate for highest number of votes)

• majority candidate is the Condorcet, you can have CC without plurality

there can only be one CC!

majority fair criterion

IIf a winner selection method would always choose only the majority winner (if there is one), then such a method is considered majority fair

• Majority is not the same as plurality – majority is if you have more than 50% of the vote

Condorcet fair implies majority fair (not reversible)

majority fair methods

• plurality — if a candidate gets a majority of the votes, they are the plurality winner

• elimination

• runoff — both need majority, left with majority winner

• pairwise comparison — majority candidate would win every head to head

• A Priori Smith fair methods

NOT BORDA SCORE

Condorcet-fair criterion

A winner selection method satisfies the Condorcet criterion if it makes any Condorcet candidate—if there is one—the sole winner.

• more strict than majority criterion (CF is MF, not vice versa)

Condorcet fair methods

• pairwise comparison — shows the Condorcet candidate, would win every head to head

• Smith set - if there is a CC, its the only one in the SS

NOT PLURALITY, RUNOFF, ELIMINATION (majority but not condorcet fair), BORDA

Circular Collective Preferences

No Condorcet — when there is no CC, societal preferences work circularly and no candidate wins universally over the others

the unanimity criterion

A winner selection method satisfies the unanimity criterion if it guarantees that candidate Y is not among the winners of the election if there is a candidate X who is preferred to Y by every voter.

if everyone hates one candidate and they are always ranked below another candidate, the mega loser should never win

Unanimity fair methods

• plurality

• runoff

• elimination

• Borda Score

• Pairwise comparison

• Schulze’s beatpath

NOT SEQUENTIAL COMPARISON, SMITH SET

Sequential comparison

• does not satisfy unanimity criterion, but is Condorcet-fair

  Like a bracket – two candidates go head to head, one gets eliminated and the other moves on to the next round 

• Very unstable method – could get vastly different outcomes depending on which pair you start with 

The Independence of Candidate Name principle

• For sequential comparison – the first two choices change the outcome, which we do not want 

• An election that is not affected by order satisfies the ICNP (independent of candidate name) – created to fix the variability of the sequential comparison 

If Candidate X joins the ballot right before the election, Candidate X is not a spoiler if and only if:

1. Candidate X wins the election

   1. (WA = X)

2. Candidate X joins the set of winners, in a system with multiple winners (this winners’ set is otherwise the same as before)

   1. (WA = WB U X)

3. The set of winners is unaffected by Candidate X

   1. (WB = WA)

No spoiler criterion (adding someone)

A method satisfies this criterion if:

In the case of a new candidate being added to the ballot, it guarantees the only possibilities are:

1. the new candidate wins (avoids losing spoilers)

2. the new candidate joins the set of winners (avoids winning spoilers)

3. or the new candidate does not change the set of winners from before (avoids losing spoilers)

Retroactive disqualification criterion (kicking someone off)

Choosing a winner when the winner meets one of the three following scenarios when a candidate is retroactively removed from the ballot (ONLY one of these)

• Removed candidate was the original winner

• Removed candidate was the only original winner not to win after being removed

• Removed candidate does not change the set of winners

Methods that satisfy the no spoiler/retroactive disqualification criteria

If a method satisfies the No Spoiler Criterion, it satisfies the Retroactive Disqualification Criterion

• Not plurality, runoff, elimination, Coombs, Borda, pairwise comparison, or sequential comparison

• No winner selection method based on the principle of One Person, One Vote satisfies the RDC/NSC

  • based on preference ballots

• YES: dictatorship of the Kth/one person has ultimate power, approval voting

Why can’t any winner selection method based on the Principle of ONe Person, One Vote satisfy the retroactive DC or no-spoiler C?

Circular societal preferences

Dictatorship of the Kth Voter

arbitrarily picked one voter’s ballot to declare the winner. This method would have to satisfy the no-spoiler criterion

• never has spoilers

• no democratic gov does this

Approval voting

Instead of ranking candidates, voters pick as many as they like (check boxes for ones they approve of), counted on checks instead of votes 

• Satisfies the NSC/RDC

• If a new candidate X enters the race, only three things could happen:

  • Candidate X gets most checks

  • Candidate X ties for the most checks

  • Candidate X does not get as many checks as some other candidates 

Method to eliminate losing spoilers

Method satisfies requirements 1 and 3

1) Candidate X wins the election, W after = {X} (The book uses the notation W = {X}).
or
3) The set of winners is unaffected, W after = W before (The book uses the notation W = W’)

A losing spoiler is a candidate X ¢ W whose retroactive disqualification changes the set of winners.

Method to eliminate winning spoilers

Method satisfies requirement 2

2) Candidate X joins the winners, W after = W before U {X} (The book uses the notation W = W’ U {X}).

A winning spoiler is a candidate X who belongs to W but is not the only candidate in W (that is, not the only winner), and whose retroactive disqualification leads to a new set of winners W’ 4 W —{X}. 

Empty sets are subsets of ____ ___ ____

every single set

Union of sets

Combining two or more sets’ operations, all things in A or B (inclusive) (the “whole” of two sets is the union)

• “Or” is always inclusive (assumed)

  • U = union symbol 

• When you take the union of intersecting sets (sets with the same element), you don’t repeat elements

Intersection of sets

“what is in common” between two or more sets (looking for shared elements) 

• “Opposite operation” as union (upside down U) 

• All things strictly in A and in B (“and” is always a restriction) 

Set difference

Removing an element from a set

Notation example: S - {X} or A - B

• Useful when thinking of retroactive disqualification 

• Removing element X from set S = “all the elements of S that are not X” / all the elements of A that are not in B

• Can remove multiple elements

Set containment (subset notation)

one set is contained inside another. If A is contained in B, we say A is a subset of B — B contains every single element of A and more

Subset or equal to notation

Any method that relies on _____ cannot satisfy all three no-spoiler criteria

reduced preference schedule

Weak/losing spoiler

A candidate who isn’t a part of the winners’ set but whose retroactive disqualification changes the winners

• satisfies requirement 2 (only winner to lose)

• violates reqs. 1 and 3 (original winner, doesn’t change set of winners)

Winning/No losing spoiler

A candidate who does win but isn’t the only winner, and whose retroactive disqualification leads to a new/different set of winners

• satisfies requirements 1 and 3 (original winner, doesn’t change set of winners)

• violates req 2 (only winner to lose)

the strongest candidate is the ___ candidate

Condorcet (if there is one)

Dominating set

if every candidate X beats every candidate Y/not in the dominating set in a head-to-head competition, we call the winning set (X) the dominating set

• strongest = just the Condorcet

Smith set

The smallest possible dominating set

• only one

• If there is a Condorcet, the SS is just the Condorcet

• violates the unanimity criterion

• if you kick out non-Smith candidates, the election will not change

  • does not allow losing spoilers

• winner of sequential comparison

• Condorcet fair

• does not satisfy unanimity

Primitive dominating set

the smallest dominating set that contains candidate X (Dx)

• includes candidate x, who candidate x does not beat, who they do not beat, etc. … until you run out

  of candidates

• uses pairwise comparison

• for each size of PDS, there can only be one size

• PDS of candidates including each other should match up

Smith fairness

If the set of winners by the election method is guaranteed to be a subset of/equal to the Smith set

Smith fair is ___ fair

Condorcet

• but not in reverse

• The election being Smith fair would mean the only winner would be the CC if there is one

Smith fair methods

Smith set

sequential comparison (Smith candidate would win every head to head against non Smith)

pairwise comparison (non Smith candidates lose, often picks SS subset)

NOT CONDORCET FAIR METHODS ARE NOT (plurality, elimination, runoff)

A Priori Smith Fairness

Any method we have discussed so fair can be made a priori Smith-fair by removing all non-Smith candidates from the ballot and proceed from there

• artificially making Smith fair methods

• eliminates losing spoilers

• majority fair

• plurality, runoff, elimination, Coombs, dictatorship

• OR DEFAULT: Smith, sequential, pairwise, beatpath

Book: if the presence or absence of non-Smith candidates never affects the election outcome. 

A Posteriori Smith Fair

any Smith-fair method that is not a priori Smith-fair

• Borda method

• Winners change

• Methods we can make Smith fair by picking a Smith candidate

A Priori Smith Fairness eliminates ___ spoilers

weak/losing

• if you eliminate the weak spoilers to begin with, they won’t affect the election

No Weak Spoiler Criterion

A winner selection method that guarantees there will never be weak spoilers

• A Priori Smith Fairness (if you eliminate the weak spoilers to begin with, they won’t affect the election)

Issues with A Priori sequential comparison, dictatorship, Smith methods

• do not pass principle of Independence of Candidate Names

• do not pass principle of One Person One Vote

• do not pass unanimity criterion

Schulze’s Beatpath

One considers who beats who in a head-to-head, but also favors candidates who win by bigger margins 

• (uses margins of victory in pairwise comparison)

• beatpaths are assigned to strength of margin of victory (smallest on path)

• majority fair, A Priori SF, Smith fair, avoids losing spoilers, independent of candidate names, satisfies 1P1V and unanimity

• ties v unlikely with a lot of voters

Schulze’s beatpath can have ties but there is always at least ___ winner

one

• The beatpaths have to end (someone’s has to be stronger than someone else’s) – finite number of choices

Beatpath is ____ Smith fair

A Priori

• Any time a Smith and non-Smith candidate go head to head, the non-Smith candidate loses (this method ignores them)

Beatpath ____ the unanimity criterion

satisfies

• If every voter prefers candidate X to candidate Y, then the beatpath X → Y is unmatched

  • Even if it was matched by circular preference like Y → L → X, every voter would have to have these circular preferences (which can’t happen among a single voter)