\documentclass[psamsfonts]{amsart}
\usepackage{amssymb,amsfonts}
\usepackage[all,arc]{xy}
\usepackage{enumerate}
\usepackage{mathrsfs}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{condition}{Condition} 

     \begin{document}
     \author{Honi Sanders}
     \title{Arrow's Impossibility Theorem of Social Choice}
     \maketitle     
     \begin{abstract}
     A proof of Arrow's Impossibility Theorem based on the five conditions he imposed on the social-welfare function in his 1950 paper, ``A Difficulty in the Concept of Social Welfare."\end{abstract}
     
     In order to make policy decisions, some algorithm must be used to choose one alternative out of all the available possibilities of action based on the preferences of the constituency.  One might call this algorithm an election.  The plurality election where the option with the most people preferring that option to any other is the one on which our mayorial, congressional, and most other elections are decided.  One problem is that it could be that 30\% of the population prefers a to b and b to c, 30\%  of the population prefers b to a and a to c, and 40\% of the population prefers c to b and b to a.  In this case, c would win, even though the majority of the population would rather anything but c.  Many other election methods have been proposed as alternatives, but each either has outcomes that are unacceptable in certain cases or does not always give a winner.  In his 1950 paper, ``A Difficulty in the Concept of Social Welfare," Kenneth Arrow sets out guidelines for what he believes is a fair election method and proves that no such method exists.  
     \textrm The social decision under consideration can be represented as a finite or infinite set $S$, and the options are represented as the elements $x_k\in{S}$.  We can describe preference as a relation on the set.  For an individual $i$, we will define relations $R_i$ and $P_i$.
     \newtheorem{definition}{Definition}
      \begin{definition} If individual $i$ prefers $x_k$ to $x_j$ or is indifferent between $x_k$ and $x_j$, then $x_k R_i x_j$.\end{definition}
      Using this definition we can define $P_i$ in terms of $R_i$:
      \begin{definition} $\sim x_k R_i x_j \equiv x_j P_i x_k$ \end{definition} 
      The relations $R_i$ and $P_i$ on $S$ are comparable to the relations $\geq$ and $>$, respectively, on $\mathbb{Z}$, so Definition 2 is comparable to defining $>$ in terms of $\geq$: $x \ngeq y \equiv y > x$.  \\
      We assume that all individuals are rational and preference is based on relative utility, so preference and indifference are transitive.  From the transitivity property of $R_i$ and $P_i$, and following directly from the definition, we have
      \begin{itemize} 
      \item[(i)] $x_k R_i x_j, x_j R_i x_m \rightarrow x_k R_i x_m$
      \item[(ii)] $x_k P_i x_j, x_j R_i x_m \rightarrow x_k P_i x_m$
      \item[(iii)] $x_k P_i x_j \rightarrow x_k R_i x_j$
      \end{itemize} 
      Our goal is to find a social-welfare function, that is, an algorithm to determine relations $R$ and $P$, representing the societal preference, on the set $S$ given the relations $\{R_i\}$.  Kenneth Arrow listed five conditions that he thought one should expect the social-welfare function and the relations $R$ and $P$ that it produces to fulfill.  
      \begin{condition}The social-welfare function must have an output $R$ and $P$ for any set of relations $\{R_i\}$. \end{condition} 
      \begin{condition}If  $\{ R_i \}$ changes s.t. all $x_k R_i x_j$ hold except for relations involving $x_m$, and $\forall R_i, \{ x_k | x_m R_i x_k$ before$ \}  \subset \{x_k | x_m R_i x_k$ after$\}$ and $\{ x_k | x_m P_i x_k$ before$ \}  \subset \{x_k | x_m P_i x_k$ after$\}$, then $\{ x_k | x_m P x_k$ before$ \}  \subset \{x_k | x_m P x_k$ after$\}$.  (That is, if people think more highly of $x_m$ and nothing else changes, then $x_m$ should not be thought of lower by society as a whole.)\end{condition}
     \begin{condition}[Independence of Irrelevant Alternatives]$\forall C \subset S$ with relation $R'$ on $C$ (\{$R_i$\} are relations on $C$ by transitivity), for $x_k, x_j\in C, x_k R x_j \leftrightarrow x_k R' x_j$.  (The ordering of given options should not change with the presence of other options.)  \end{condition}  
     \begin{condition}[Citizen Sovereignty] $\nexists x_k, x_j$ s.t. $x_k R x_j \forall \{R_i\}$. (Any societal preference is allowed.)\end{condition} 
      \begin{condition}[Nondictatorship] $\nexists$ individual $i$ s.t. $x_k P_i x_j \rightarrow x_k P x_j$.\end{condition} 
      Arrow then proved that these five conditions imply a contradiction.  He used a society with two individuals and three elements in $S$.  By Condition 3, disproving the existence of a social-welfare function on a set with three elements disproves it for all numbers of elements.  He uses a mathematical wave of the hand on the generalizability of proofs involving societies with two individuals: "The restriction to two individuals may be more serious; it is conceivable that there may be suitable social welfare functions which cab be defined for three individuals but not for two, for example.  In fact, this is not so, and the results stated in this paper hold for any number of individuals."
      \begin{lem}[Pareto Efficiency] $x_k P_i x_j \forall i \rightarrow x_k P x_j$.\end{lem}
      \begin{proof} Assume that $x_k P_i x_j \forall i \nrightarrow x_k P x_j$.  Then, $\exists x_k, x_j$ s.t. $x_k P_i x_j \forall i$ but $x_j R x_k$.  Condition 4 is equivalent to the statement $\forall x_k, x_j \exists \{R_i\}$ s.t. $x_k P x_j$.  Take that $\{R_i\}$, which is not $x_k P_i x_j \forall i$ by assumption, and change only relations dealing with $x_k$ so that $\forall i$ and $\forall x_m, x_k P_i x_m$.  We now have a $\{R_i\}$ where $x_k P_i x_j \forall i$.  But by construction following Condition 2, because $x_k P x_j$ before the change, it must be that $x_k P x_j$ after the change, which contradicts the original assumption.   \end{proof}
      It is at this point that Arrow's proof begins to deal with only societies with two  people.  
       \begin{lem}If $x_k P_1 x_j, x_j P_2 x_k, x_k P x_j$, then $x_k P_1 x_j \rightarrow x_k P x_j$.\end{lem}
       \begin{proof} Take $R_1$ where $x_k P_1 x_j$ and any $R_2$.  Change $R_2$ only with respect to $x_k$ to $R_2'$ so that $\forall x_m, x_m P_2' x_k$, so $x_j P_2' x_k$.  With $R_1$ and $R_2'$, $x_k P' x_j$ by assumption.  Change $R_2'$ back to $R_2$ only by changing relations dealing with $x_k$, which is a change following Condition 2, meaning that $x_k P x_j$.   \end{proof}
       \begin{lem}$x_k P_1 x_j, x_j P_2 x_k \rightarrow x_k R x_j, x_j R x_k$\end{lem}
       \begin{proof} Assume $x_k P_1 x_j, x_j P_2 x_k \nrightarrow x_k R x_j, x_j R x_k$.  That is, $\exists R_1, R_2$ where $x_k P_1 x_j, x_j P_2 x_k$ and either $x_k P x_j$ or $x_j P x_k$.  \\
       With $S=\{a,b,c\}$, set $x_k=a, x_j=b$ without loss of generality.  We will prove a contradiction assuming $a P b$, and the case of $b P a$ can be proved by the same process.  By Lemma 2, we have \begin{equation} a P_1 b \rightarrow a P b.\end{equation}
       Take $R_1$ where $a P_1 b, b P_1 c$ and $R_2$ where $b P_2 c, c P_2 a, b P_2 a$.  $a P b$ by (1), and $b P c$ by Lemma 1, so $a P c$ by transitivity.  By Lemma 2, \begin{equation} a P_1 c \rightarrow a P c.\end{equation}
       Take $R_1$ where $b P_1 a, a P_1 c$ and $R_2$ where $c P_2 b, b P_2 a$. Then, $b P a$ by Lemma 1 and $a P c$ by (2); so by Lemma 2, \begin{equation} b P_1 c \rightarrow b P c.\end{equation}
       Take $R_1$ where $b P_1 c, c P_1 a$ and $R_2$ where $c P_2 a, a P_2 b$, $c P a$ by Lemma 1 and $b P c$ by (3); so by Lemma 2, \begin{equation} b P_1 a \rightarrow b P a.\end{equation}
       Take $R_1$ where $c P_1 b, b P_1 a$ and $R_2$ where $a P_2 c, c P_2 b$, $c P b$ by Lemma 1 and $b P a$ by (4); so by Lemma 2, \begin{equation} c P_1 a \rightarrow c P a.\end{equation}
       Take $R_1$ where $c P_1 a, a P_1 b$ and $R_2$ where $a P_2 b, b P_2 c$, $a P b$ by Lemma 1 and $c P a$ by (5); so by Lemma 2, \begin{equation} c P_1 b \rightarrow c P b.\end{equation}
       Equations (1)-(6) can be summarized as $\forall x_m, x_n\in S, x_m P_1 x_n \rightarrow x_m P x_n$ which establishes individual 1 as a dictator, and contradicts Condition 5.  \end{proof} 
      Now we can prove our main theorem:
            \begin{thm}[Arrow's Impossibility Theorem] There is no social-welfare function which fulfills Conditions 1-5 and produces a rational societal preference ordering.\end{thm}
      \begin{proof}Take $R_1$ where $a P_1 b, b P_1 c$ and $R_2$ where $c P_2 a, a P_2 b$.  By Lemma 1, $a P b$.  $b P_1 c, c P_2 b \rightarrow b R c, c R b$ by Lemma 2, so $a P c$ by (ii), but $a P_1 c, c P_2 a \rightarrow a R c, c R a$.  \end{proof}
      \begin{thebibliography}{9}

\bibitem{Arrow}
Kenneth J. Arrow.
A Difficulty in the Concept of Social Welfare.
The Journal of Political Economy, Vol. 58, No. 4.  August, 1950  pp. 328-346.
 

\end{thebibliography}


     \end{document}