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$$

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