Skip to content

Latest commit

 

History

History
366 lines (330 loc) · 19 KB

socialChoice.org

File metadata and controls

366 lines (330 loc) · 19 KB
Raw

Social Choice

1 Aggregating Preferences

1.1 Motivation

  • people have different preferences
  • how should societal decisions be taken?
    • navigate conflicts of preferences
    • respecting individual preferences
  • Examples:
    • political decisions and elections
    • a group of friends wants to go for drinks: how to aggregate the differing preferences over bars
    • aggregating votes of several judges in sports (boxing, figure skating etc.)
    • (expert) committees
    • a family deciding where to spend the summer holiday
    • …

1.2 Social choice theory

  • make ethical premises explicit
  • derive solutions consistent with these premises
  • normative (!)

1.3 Example: Majority voting

  • society ($N>2$ people) has to choose one of 2 alternatives/candidates ($x$ and $y$)
  • assumption for simplicity: everyone has a strict preference over alternatives
  • majority voting:
    • $x\succeq_S y$ if at least $N/2$ people prefer $x$ over $y$
    • $y\succeq_S x$ if at least $N/2$ people prefer $y$ over $x$
  • what normative premises underlie this social welfare function?

1.4 Some criteria (for 2 alternatives)

1.4.1 Anonymity

A social welfare function is anonymous if the names of the agents do not matter, i.e. if a permutation of preferences across agents does not change the social preference.

1.4.2 Neutrality

A social welfare function is neutral if the names of the alternatives do not matter, i.e. the social preferences are reversed if we reverse the preferences of all agents.

1.4.3 Positive responsiveness

A social welfare function is positively responsive if the following holds: if one alternative $x$ is weakly socially preferred to $y$ although $y\succ_i x$ for some $i∈\{1,…,N\}$, then $x$ is strictly socially preferred if we change $i$’s preferences (without changing anyone else’s preferences).

1.5 A first theorem

  • didn’t I claim that social choice starts with premises and then derives solutions?

1.5.1 May’s Theorem

If there are two alternatives, a social welfare function satisfies anonymity, neutrality and positive responsiveness if and only if it is majority voting.

1.5.2 Proof sketch (“only if” for even $N$)

  • Anonymity: only number of people preferring alternative $x$ over $y$ matters for $\succeq_S$.
  • Neutrality: if $N/2$ people prefer $x$ over $y$ and $N/2$ prefer $y$ over $x$, then $x≈_S y$.
  • Positive responsiveness: if more than $N/2$ people prefer $x$ over $y$, $x\succ_S y$ and vice versa.

1.6 Majority voting with more than 2 alternatives

  • How to generalize majority voting with more than 2 alternatives?

1.6.1 Definition

An alternative $x$ is a Condorcet winner if for any other alternative $y$ a majority prefers $x$ over $y$.

1.6.2

1.6.3 Example

A group of students want to tell the teacher their preferences over exam forms (open book, closed book, online exam). How to aggregate the preferences?

bestmiddleworst
/<
Student 1oboecb
Student 2oecbob
Student 3cboboe

Which alternative is Condorcet winner?

1.6.4

2 Formal model and criteria

2.1 Model

  • finite set $X=\{x_1,x_2,…,x_K\}$ of alternatives
  • $N\geq 2$ agents, each has a complete and transitive preference relation over $X$

2.1.1 Social preference relation

A social preference relation is a complete and transitive preference relation on the set $X$.

2.1.2 Social welfare function

A social welfare function assigns to each profile of preferences $(\succeq_1,\succeq_2,…,\succeq_N)$ a social preference relation $\succeq_S$.

2.2 Examples: social welfare function

Are the following social welfare functions desirable?

  • The preferences of agent 1 are the social preferences: $\succeq_S (\succeq_1,\succeq_2,…,\succeq_N)=\succeq_1$
  • Fixed social preference relation: $\succeq_S (\succeq_1,\succeq_2,…,\succeq_N)=x_1\succ_S x_2\succ_S x_3\succ_S…\succ_S x_K$
  • Borda Count:
    • turn every agent’s preference order into points: the $k$ most preferred alternative receives $k$ points
    • for every alternative, sum the points it gets from all agents
    • order alternatives according to points (less points are better)

2.3 Borda and Olympic Ice Skating competition I

  • judging in sports is similar to our problem
    • aggregation of several judges’ rankings
  • final 2002 Olympic figure skating competition
    • Slutskaya is the last skater to perform
    • at that moment: 1. Kwan, 2. Hughes, 3. …
    • Slutskaya is doing well but not super and ends up second
    • who came first? who came third?

2.4 Borda and Olympic Ice Skating competition II

  • table contains the ranks that the 7 judges assign to the three skaters
KwanHughesSlutskaya
/<
judge 1231
judge 2231
judge 3123
judge 4123
judge 5312
judge 6312
judge 7312
Points

2.5 Minimal (?) normative criteria

2.5.1 Weak Pareto principle (unanimity)

If $x\succ_i y$ for all $i=1,2,…,N$, then $x\succ_S y$.

2.5.2 Non-dictatorship

There is no individual $i$ such that $x\succeq_S y$ if and only if $x\succeq_i y$. (no matter what other agents’ preferences are)

2.5.3 Independence of irrelevant alternatives

Take two profiles of preferences $(\succeq_1,\succeq_2,…,\succeq_N)$ and $(\succeq_1’,\succeq_2’,…,\succeq_N’)$. If for every agent $i$ the ranking of $x$ and $y$ is the same under $\succeq_i$ and $\succeq_i’$, then the social ranking of $x$ and $y$ must be the same under these two preference profiles.\footnote{More formally, let the two preference profiles be such that for all agents $i$ $x\succeq_i y$ if and only if $x\succeq_i’ y$. Then $x\succeq_S y$ if and only if $x \succeq_S’ y$.}

3 Arrow’s impossibility theorem

3.1 Arrow’s impossibility theorem

3.1.1 Theorem

Let there be at least 3 alternatives in $X$. There exists no social welfare function that satisfies all 3 criteria (weak Pareto principle, non-dictatorship and independence of irrelevant alternatives).

3.1.2

Proof is somewhat lengthy (see textbook)

3.2 Consequences of Arrow’s theorem

  • no social welfare function satisfies even minimal criteria
  • we have to give up even some of these minimal criteria if we want to proceed!
  • some ways to proceed:
    • pick only one alternative: no complete social ordering necessary
      • leads to similar result
    • domain restriction
      • we implicitly assumed that all preference profiles were possible (in the definition “social welfare function”)
      • more positive results if we can rule out certain preferences
    • cardinal utility
      • we only looked at orderings not at intensity of preference
      • assuming that there is something like intensity of preferences and this intensity is comparable across agents helps to aggregate preferences but is a questionable assumption

4 Domain restrictions

4.1 Domain restriction: Single peaked preferences I

  • imagine alternatives are ordered on the real line: $x_1 &lt; x_2 &lt; … &lt; x_K$
  • assumptions:
    • common ordering of alternatives
    • everyone has a most preferred alternative
    • of two “too high” (or “too low”) alternatives, an agent prefers the one closer to his most preferred alternative
    • for simplicity: odd number $N$ of agents
  • more precisely:
    • each agent $i$ has a most preferred alternative $x^*(i)∈\{x_1,x_2,…,x_K\}$
    • if $x_k,x_m&gt;x^*(i)$, then $x_k \succ_i x_m$ if and only if $x_k &lt; x_m$
    • if $x_k,x_m &lt; x^*(i)$, then $x_k\succ_i x_m$ if and only if $x_k &gt; x_m$
  • if we represent preferences by utility function, this function is “single peaked”

4.2 Domain restriction: Single peaked preferences II

4.2.1 Median agent for single peaked preferences

An agent $i$ is a median agent if\linebreak (i) there are at least $N/2$ agents with most preferred alternatives weakly above $x^*(i)$ and\linebreak (ii) there are at least $N/2$ agents with most preferred alternatives weakly below $x^*(i)$.

4.2.2

Note: a median agent always exists.

4.3 Domain restriction: Single peaked preferences II

4.3.1 Proposition

Let preferences be single peaked and $i$ be a median agent, then $x^*(i)$ is a Condorcet winner.

4.3.2 Proof

  • Consider a pairwise majority vote between $x^*(i)$ and $x_m &gt; x^*(i)$.

    \vspace*{1.5cm}

  • Consider a pairwise majority vote between $x^*(i)$ and $x_m &lt; x^*(i)$.

    \vspace*{1.5cm}

4.4 Domain restriction: Single peaked preferences III

  • consider pairwise majority voting between arbitrary alternatives, i.e. say $x_k$ is socially preferred to $x_m$ if $x_k$ wins in a majority vote over $x_k$ and $x_m$

4.4.1 Proposition

If preferences are single peaked, pairwise majority voting induces a social welfare function.

4.4.2

4.4.3 Proof

to show: resulting preferences are complete and transitive

  • As $N$ is odd and preferences are strict, pairwise majority voting yields a strict winner between any two alternatives.\linebreak $⇒$ social preference ordering resulting from pairwise majority voting is complete and strict.
  • Transitivity: let $x_m\succ_S x_k$ and $x_k\succ_S x_l$ …

\vspace*{2cm}

5 Cardinal utility

5.1 Cardinal utility I

Reminder:

5.1.1 Representation by a utility function

A complete preference relation $\succeq$ over a set $X$ is represented by the utility function $u:X→\Re$ if and only if $$x\succeq y \quad\Leftrightarrow\quad u(x)\geq u(y).$$ If $u$ represents $\succeq$, then $ψ(u)$ also represents $\succeq$ where $ψ:\Re\rightarrow\Re$ is an arbitrary strictly increasing function.

5.1.2

5.2 Cardinal utility II

  • suppose we have 2 agents and $x\succ_1 y$ while $y\succ_2 x$
  • we choose utility functions for the two agents
    • $u_1(x)=3$, $u_1(y)=1$
    • $u_2(x)=0$, $u_2(y)=1$
  • which alternative should society prefer?

5.3 Cardinal utility II

  • if we assign meaning to utility, social welfare function is not invariant to strictly monotone transformations
  • allows to get around Arrow’s impossibility theorem
  • problem: choice of specific agent utility functions implicitly makes normative judgments beyond our criteria
  • for now:
    • accept some given utility functions $u$
    • let welfare depend on the utilities of the agents and be represented by a function $W:\Re^N→\Re$ that aggregates agent utilities into “welfare”
      • we abuse notation and call $W$ also “social welfare function”
    • what are reasonable choices for $W$? what normative judgments are expressed by the choice of $W$?

5.4 Cardinal utility III

5.4.1 Pareto dominance

Alternative $x$ is Pareto dominated by alternative $y$ if and only if $y\succeq_i x$ for all agents $i=1,..,N$ and $y\succ_i x$ for at least one agent.

5.4.2 Pareto efficiency

An alternative $x$ is Pareto efficient if there is no alternative $y$ that Pareto dominates $x$.

5.5 Cardinal utility IV

5.5.1 Pareto criterion and $W$

Pareto dominating alternatives are socially preferred to the alternatives they dominate if social welfare function $W$ is such that $W(u)&gt;W(u’)$ for any two vectors $u=(u_1, u_2,…,u_N)$ and $u’=(u_1’,…,u_N’)$ with $u_i\geq u_i’$ for all $i=1,… N$ and strict inequality for at least one $i$.

5.5.2

note: weak Pareto criterion is satisfied if $W$ is such that for any two vectors $u=(u_1, u_2,…,u_N)$ and $u’=(u_1’,…,u_N’)$ such that $u_i>u_i’$ for all $i=1,… N$, we have $W(u)&gt;W(u’)$.

5.6 Cardinal utility V: Rawlsian welfare

$$WRawls(u_1,…,u_N)=min[u_1,…,u_N]$$

  • $WRawls$ satisfies weak Pareto criterion
  • $WRawls$ is anonymous
  • $WRawls$ is “utility level invariant”:
    • social preferences remain the same if we transform all agent’s utility using the same strictly increasing transformation
  • $WRawls$ satisfies “Hammond Equity”:
    • take two utility vectors $(\bar u_1,\bar u_2,…,\bar u_N)$ and $(\hat u_1,\hat u_2,…,\hat u_N)$ and suppose $\bar u_i=\hat u_i$ for all $i$ except $j$ and $k$
    • suppose further $\bar u_j&lt;\hat u_j&lt;\hat u_k&lt;\bar u_k$
    • Hammond equity states that then $W(\hat u)\geq W(\bar u)$

5.7 Cardinal utility VI: Rawlsian welfare

5.7.1 Proposition

A continuous social welfare function $W$ satisfies Hammond equity and the weak Pareto principle if and only if it can take the Rawlsian form $WRawls(u_1,…,u_N)=min[u_1,…,u_N]$.

5.7.2

  • $≈$ Rawlsian welfare is equivalent to weak Pareto criterion + Hammond equity

5.7.3 Proof

see Jehle and Reny (2011), section 6.3.1

5.8 Cardinal utility VII: Utilitarian welfare

$$Wut(u_1,…,u_N)=∑i=1^N u_i$$

  • most commonly used welfare function (sometimes with individual weights)
  • $Wut$ respects Pareto efficiency
  • $Wut$ is anonymous (not true if weights are used)
  • $Wut$ is “utility-difference invariant”
    • social preferences are the same if we transform all agents utility using the transformation $ψ_i(u_i)=a_i+b u_i$ with $b&gt;0$

5.9 Cardinal utility VIII: Utilitarian welfare

5.9.1 Proposition

A continuous social welfare function $W$ satisfies anonymity, Pareto efficiency and utility-difference invariance if and only if it can take the utilitarian form $Wut=∑i=1^N u_i$.

5.9.2 Proof

see Jehle and Reny (2011), section 6.3.2

5.10 Cardinal utility IX: the veil of ignorance I

  • thought experiment
    • you will be one of the agents in society
    • you have to decide which alternative to choose
    • you do not know which agent you are going to be
    • some people have argued that whatever a “fair-minded” person would choose in this hypothetical situation is a good societal decision

5.11 Cardinal utility X: the veil of ignorance II

  • Harsanyi:
    • my chance of being agent $i$ is $1/N$
    • my choice should maximizes the expected utility $∑i=1^N (1/N) u_i(x)$
    • $→$ utilitarian welfare
  • Rawls:
    • I do not know who I am going to be and there is no basis for assigning probabilities.
    • risk aversion implies maximizing the worst case utility
    • $→$ Rawlsian welfare
  • Arrow:
    • Rawls makes a mistake as he assumes not risk aversion but infinite risk aversion, i.e. risk aversion does not imply maximizing worst case utility.

6 Manipulability

6.1 Manipulability I

  • so far: preferences of all players are known
  • problem: aggregation
  • what if everyone knows his preferences privately?
    • ask for preferences
    • aggregate
  • additional problem: gaming the system by misreporting preferences!
  • result due to Gibbard and Satterthwaite:\linebreak If there are at least three alternatives and a social welfare function is (i) Pareto efficient and (ii) creates no gaming possibilities, then it is dictatorial.

6.2 Manipulability II

  • one example for manipulability

6.2.1 Example: Borda count

most preferredmiddle preferredleast preferred
/<
Agent 1xyz
Agent 2yxz
Agent 3yxz
Points

Could agent 1 manipulate the social preference relation by misrepresenting his own preferences? Would he want to do so?

6.2.2

  • to discuss such topics properly:\linebreak extend decision and game theory to incomplete information
    • that’s what we will do in the coming weeks!

7 Bibliography

bibliographystyle:chicago bibliography:/home/christoph/stuff/bibliography/references.bib