Social Choice Theory

Social Preference Aggregation

  • different people may have different preferences over social outcomes
    • in the US, polarized issues include gun control, immigration, civil rights, etc
  • big question: how do we aggregate individual preferences into social preferences?
    • which group's opinion is "correct"?
    • when (and when not to) implement social change?

Social Choice Function

  • input:
    • society of \(N\) people
    • choice set \(X\)
      • example: \(X=\{ \text{Biden}, \text{Harris}, \text{Sanders} \}\)
    • each person has her own preference relation over \(X\)
  • output:
    • single element of \(X\)

Simple Majority: Condorcet Paradox

voter 1 voter 2 voter 3
most preferred Biden Harris Sanders
middle Harris Sanders Biden
least preferred Sanders Biden Harris
  • how many voters think Biden \(\succ\) Harris?
  • how many people think Harris \(\succ\) Sanders?
  • how many people think Sanders \(\succ\) Biden?

Simple Majority: Agenda Manipulation

voter 1 voter 2 voter 3
most preferred Biden Harris Sanders
middle Harris Sanders Biden
least preferred Sanders Biden Harris
  • problem: agenda manipulation
    • suppose agenda setter wants Biden to win
      • step 1: \(\text{Sanders vs Harris}\)
      • step 2: \(\text{winner of step 1 vs Biden}\)

Simple Majority: Strategic Voting

voter 1 voter 2 voter 3
most preferred Biden Harris Sanders
middle Harris Sanders Biden
least preferred Sanders Biden Harris
  • another problem: strategic voting
    • agenda is \(\text{Sanders vs Harris}\), then \(\text{winner vs Biden}\)
    • focus on voter 2 and her vote at step 1
      • vote sincerely: Harris wins step 1, Biden wins step 2
      • vote strategically: Sanders wins step 1, Sanders wins step 2 \(\leftarrow\) voter 1 prefers this so she will vote for the "wrong" candidate at step 1

Desirable Properties of SCF: Completeness

  • full domain / complete ranking (C):
    • returns a social preference for any profile \(\{ \succsim_1, \dots, \succsim_N \}\) of individual preferences

Desirable Properties of SCF: Transitivity

  • transitivity of social ranking / no cycles (T):
    • if \(x \succsim_S y\) and \(y \succsim_S z\), then \(x \succsim_S z\)
  • note: all individual preferences satisfy C and T; we don't want to miss these properties of rationality during aggregation

Desirable Properties of SCF: Pareto

  • Pareto (P):
    • if every person agrees that \(x \succsim_i y\) AND for at least one person \(x \succ_i y\), then \(x \succ_S y\)

Dictatorial Preferences

  • so far we want social ranking to be complete, transitive, and Paretian
    • "easy" way to satisfy all three is pick a dictator
      • person \(i\) is a dictator if \(x \succ_i y \Longrightarrow x \succ_S y\)
        • regardless of others' preferences, social ranking is same as dictator's

Desirable Properties of SCF: No Dictator

  • no dictator (ND):
    • there is no dictator
  • minimum requirement for "democracy"
    • necessary, but not sufficient for democracy

(Logic Reference): Necessity

  • let \(A\) and \(B\) be two (logical) statements
  • \(A\) is necessary for \(B\) if \(\text{not } A \Longrightarrow \text{not } B\) (same as \(B \Longrightarrow A\))
  • example:
    • \(A\) is "there is no dictator" and \(B\) is "society is a democracy"
    • \(\text{not } A \Longrightarrow \text{not } B\): "if not no dictator then not democracy"
      • same as \(B \Longrightarrow A\): "if democracy then no dictator"

(Logic Reference): Sufficiency

  • \(A\) is sufficient for \(B\) if \(A \Longrightarrow B\)
  • example:
    • \(A\) is "there is no dictator" and \(B\) is "society is a democracy"
    • "if no dictator then democracy"

(Back to) Desirable Properties of SCF: IIA

  • independence of irrelevant alternatives (IIA):
    • social preferences between \(x\) and \(y\) depend only on the individual preferences between \(x\) and \(y\), and not other alternatives
    • let \(\{\succsim_1, \dots, \succsim_N\}\) and \(\{\succsim_1', \dots, \succsim_N'\}\) be two profiles of individual preferences
      • ranking of \(x\) and \(y\) is the same in both: \(x \succsim_i y \iff x \succsim_i' y\) for every \(i = 1\dots N\)
      • IIA: social preference must be the same as well: \(x \succ_S y \iff x \succ_S' y\)

Independence of Irrelevant Alternatives

  • consider preference profiles \(\{ \succ_1,\succ_2,\succ_3 \}\) and \(\{ \succ_1',\succ_2',\succ_3' \}\):
voter 1 voter 2 voter 3 voter 1 voter 2 voter 3
most preferred Biden Harris Sanders Biden Harris Biden
middle Harris Sanders Biden Sanders Sanders Sanders
least preferred Sanders Biden Harris Harris Biden Harris
  • same individual rankings between \(\text{Biden}\) and \(\text{Harris}\)
    • IIA: social ranking between Biden and Harris should be the same

Why IIA?

  • individual's intensity of preferences should not determine the social ranking
    • intensity of relative political preference is private info and can easily be misrepresented
  • a good SCF should be stable with respect to adding and removing of alternatives
    • ranking of \(\text{Biden}\) vs \(\text{Harris}\) should not depend on whether \(\text{Sanders}\) is running

Desirable Properties of SCF: Summary

  • we would like our social choice function to satisfy
    • completeness (C)
    • transitivity (T)
    • Pareto (P)
    • no dictator (ND)
    • independence of irrelevant alternatives (IIA)

Example of SCF: Unanimity Rule Without Status Quo

\[ x \succsim_S y \iff x \succsim_i y \text{ for every person } i = 1\dots N \]
  • if everyone prefers \(x\) to \(y\), then \(x\) is socially preferred to \(y\)
  • if everyone prefers \(y\) to \(x\), then \(y\) is socially referred to \(x\)
  • if people do not unanimously agree that \(x\) is better than \(y\) or vice versa, SCF does not return a social preference
C T P ND IIA
- + + + +

Borda "Scoring" Rule

  • every person provides a ranking of all alternatives, worst \(\to\) best
    • worst choice receives \(1\) point; second worst -- \(2\) points, and so on
  • social score of an alternative is the sum of individual scores
  • winner is the alternative with highest score

Borda Rule: Example

voter 1 voter 2 voter 3
most preferred Biden Harris Biden
middle Sanders Sanders Sanders
least preferred Harris Biden Harris
  • Biden: \(3+1+3=7\) \(\leftarrow\) Borda winner
  • Sanders: \(2+2+2 = 6\)
  • Harris: \(1+3+1 = 5\)

Borda Rule: Properties

C T P ND IIA
+ + + + -
  • C: we can calculate score for any alternatives and we can compare any pair of alternatives by comparing scores
  • T: if \(x \succsim_S y\) and \(y \succsim_S z\), then \(\text{score}(x) \geq \text{score}(y) \geq \text{score}(z)\), meaning that \(x \succsim_S z\)
  • P: if every voter prefers \(x\) to \(y\), then \(\text{score}(x) > \text{score} (y)\) and \(x \succsim_S y\)
  • ND: social scores depend on all people's preferences so no individual is a dictator

Borda Rule: IIA Fails

  • consider preference profiles \(\{ \succ_1,\succ_2,\succ_3 \}\) and \(\{ \succ_1',\succ_2',\succ_3' \}\):
voter 1 voter 2 voter 3 voter 1 voter 2 voter 3
\(x\) \(y\) \(z\) \(x\) \(y\) \(z\)
\(y\) \(z\) \(x\) \(y\) \(x\) \(x\)
\(z\) \(w\) \(y\) \(z\) \(z\) \(y\)
\(w\) \(x\) \(w\) \(w\) \(w\) \(w\)
  • do all voters rank \(x\) and \(y\) the same way in \(\succ\) and \(\succ'\)? \(\text{Yes}\)
  • is social ranking of \(x\) and \(y\) the same for \(\succ\) and \(\succ'\)? \(\text{No}\)

Borda Rule: IIA Fails, Another Example

60 voters 40 voters 60 voters 40 voters
Navalny Ivanov Navalny Ivanov
Medvedev Medvedev Medvedev Medvedev
Ivanov Zuganov Ivanov Navalny
Zuganov Navalny
  • social score is
    • Navalny: \(4\cdot 60+1\cdot 40=280\) \(\longrightarrow\) \(3\cdot 60 + 1\cdot 40 = 220^*\)
    • Medvedev: \(3\cdot 60 + 3\cdot 40 = 300^*\) \(\longrightarrow\) \(2\cdot 60 + 2\cdot 40 = 200\)
    • Ivanov: \(2\cdot 60 + 4\cdot 40 = 280\) \(\longrightarrow\) \(1\cdot 60 + 3\cdot 40 = 180\)
    • Zuganov: \(1\cdot 60 + 2\cdot 40 = 140\) \(\longrightarrow\) not participating
  • IIA fails: Medvedev wins but when Zuganov drops out, Navalny wins

Borda Rule: Why Failure of IIA is Bad

60 voters 40 voters 60 voters 40 voters
Navalny Ivanov Navalny Medvedev
Medvedev Medvedev Medvedev Ivanov
Ivanov Navalny Ivanov Navalny

  • social score is

    • Navalny: \(3\cdot 60+1\cdot 40=220^*\) \(\longrightarrow\) \(3\cdot 60 + 1\cdot 40 = 220\)
    • Medvedev: \(2\cdot 60 + 2\cdot 40 = 200\) \(\longrightarrow\) \(2\cdot 60 + 3\cdot 40 = 240^*\)
    • Ivanov: \(1\cdot 60 + 3\cdot 40 = 180\) \(\longrightarrow\) \(1\cdot 60+2\cdot 40 = 140\)

  • Borda rule is subject to strategic manipulation: my misrepresenting their preferences, the 40-group elects their favorite candidate

Big Question of Social Choice Theory

  • so far, all our examples of social choice functions failed at least of desirable property
  • is there any social choice function that satisfies C, T, P, ND, IIA?

Arrow's Impossibility Theorem

  • for any social choice problem with at least three alternatives, there does not exist a social choice function that satisfies C, T, P, ND, IIA
    • interpretation: groups of people do not have well-defined preferences, even if each person is rational

Arrow's Theorem: Alternative Statement

  • "for any social choice problem with at least three alternatives, if a SCF satisfies C, T, P, and IIA, then it must be dictatorial
    • resist the urge to interpret as "we need to have a dictator for society to be rational"
    • AIT merely states that non-dictatorial SCFs have some problems

AIT: Interpretation

  • no non-dictatorial SCF can satisfy all 5 axioms of social choice but many can satisfy \(4/5\)
    • unanimity rule without status quo: all but C
    • simple majority: all but T
    • Borda scoring rule: all but IIA
    • "constant rule" (constant social preferences, e.g. alphabetical ranking): all but P

Are Axioms Too Demanding?

  • IIA has weakest moral basis; Borda rule satisfies all but IIA but has problems:
    • how to measure intensity of preferences?
    • how to avoid strategic manipulation of social ranking by addition/removal of candidates?
  • "my rule is intended for honest men only": Borda, probably

Other Ways Around AIT

  • AIT: "or any social choice problem with at least three alternatives, there does not exist a social choice function that satisfies C, T, P, ND, IIA"
    • does not apply if choice is between two alternatives
    • does not apply if we restrict preferences