% LaTeX2.09 file Arrow_anonymity_v4.tex
% This version adds the bibliographic information 
% to the final manuscript
% submitted to Social Choice and Welfare

\documentstyle[11pt]{article}

\title{Anonymity and Neutrality in Arrow's Theorem with Restricted 
Coalition Algebras\thanks{The running title is ``Anonymity and neutrality 
in Arrow's Theorem.'' 
A version of this paper is available as ewp-pe/9411001 from the 
EconWPA.}}
\author{H.  Reiju Mihara\thanks{The author thanks 
KamChau Wong, whose comments are 
used in the proof of Proposition~\protect\ref{anonymity1}.  The comments 
by Andrew McLennan and a referee were helpful.}
\\ {\tt reiju@ec.kagawa-u.ac.jp}
\\ Economics, Kagawa University,
Takamatsu, Kagawa 760,
Japan}
\date{March, 1996\\
\protect [Social Choice and Welfare (1997) 14: 503--512]}

%aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
\def\P{{\cal P}}
\newcommand{\B}{{\cal B}}
\newcommand{\p}{{\bf p}}
\newcommand{\pref}{\succ_i^\p}
\newcommand{\profile}{\mbox{$(\pref)_{i\in I}$}}   
\newcommand{\Pbi}{\P_\B^I}                
\newcommand{\Preci}{\P_{\rm REC}^I}      
\newcommand{\xprefy}{\{\,i:{x\pref y}\,\}}   
\newcommand{\U}{{\cal U}}
\newcommand{\Us}{{\cal U}_\succ}
\newcommand{\toto}{\to\!\to}
\newcommand{\qed}{\enspace\enspace \vrule height 6pt width5pt
depth2pt}
\newcommand{\N}{{\bf N}}
\newcommand{\swf}{social welfare function}
\newcommand{\alps}{\alpha_\succ}
\newcommand{\bA}{\overline{A}}
%aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{lemma}{Lemma}

%\renewcommand{\baselinestretch}{1.8}

\begin{document} % End of preamble and beginning of text. 

\maketitle

\begin{abstract} In the very general setting of Armstrong (1980) for 
Arrow's Theorem, I show two results.  First, in an infinite society, 
Anonymity is inconsistent with Unanimity and Independence if and only if a 
domain for social welfare functions satisfies a modest condition of 
richness.  While Arrow's axioms can be satisfied, unequal treatment 
of individuals thus persists.  Second, Neutrality is consistent with Unanimity 
(and Independence).  However, there are both dictatorial and nondictatorial 
social welfare functions satisfying Unanimity and Independence but not 
Neutrality.  In Armstrong's setting, one can naturally view Neutrality as a 
stronger condition of informational simplicity than Independence. 

{\em Journal of Economic Literature\/} Classification: D71.  

{\em Keywords:} Arrow impossibility theorem, informational simplicity, 
coalitions, Boolean algebras, ultrafilters.  
\end{abstract}

\pagebreak
\section{Introduction}  

In social choice theory, along with Arrow's conditions for his 
impossibility theorem~\cite{arrow63}, the axioms of anonymity and 
neutrality have long history.  For example, May~\cite{may52} characterized 
the simple majority rule, using these axioms.  Roughly speaking, Anonymity 
is a condition of equal treatment of individuals (voters) and Neutrality is 
a condition of equal treatment of alternatives (candidates).  The simple 
majority rule satisfies both axioms.

In view of Arrow's Theorem, which states that in societies with finitely 
many individuals any social welfare function satisfying Unanimity and 
Independence is dictatorial, investigating compatibility of (each or both 
of) Anonymity and Neutrality with Unanimity and Independence is not very 
interesting, as far as finite societies are concerned.  For the problem is 
reduced to that of investigating properties of dictatorial \swf s.  It is 
trivial that imposing Unanimity and Independence entails violation of 
Anonymity but not necessarily violation of Neutrality, because dictatorial 
social welfare functions violate Anonymity but not necessarily Neutrality 
(though the latter is less obvious).

However, with the appearance of Fishburn's resolution~\cite{fishburn70} of 
Arrow's impossibility in which he allowed an infinite set of individuals, 
the problem has suddenly become more interesting.  For, with infinitely 
many individuals, there are now nondictatorial social welfare functions 
satisfying Unanimity and Independence.  This means that there might be {\em 
nondictatorial\/} social welfare functions that satisfy Anonymity or 
Neutrality along with Unanimity and Independence.

I explore the axioms of Anonymity and Neutrality in Armstrong's 
setting~\cite{armstrong80,armstrong85} for Arrow's Theorem, where there can 
be infinitely many individuals and where the observable coalitions can be 
restricted to an arbitrary Boolean algebra on the set of individuals.  
(Armstrong's papers extend what could be called an ``ultrafilter approach'' 
due to Kirman and Sondermann~\cite{kirman-sondermann72}, who characterize 
decisive coalitions associated with a \swf\ satisfying Unanimity and 
Independence.) There are two reasons for me to adopt Armstrong's setting 
instead of Fishburn's setting.

An obvious reason is that the results I obtain will be more general since 
Fishburn's setting is a special case of Armstrong's setting.

But a more important reason is that Armstrong's setting allows me to 
give~\cite{mihara94b,mihara.thesis} a new and practical (as opposed to 
ethical) significance to the condition of Neutrality.  Some social 
choice theorists (e.g., Kelly~\cite[ch.~3]{kelly78}) have regarded 
Independence, a weaker condition than Neutrality, as a condition of 
computational simplicity.  This is because Independence allows a 
planner to determine the social preference on a pair~$\{x,y\}$ of 
alternatives based only on the individual preferences on the pair.  
Suppose that Independence is satisfied and suppose that the planner 
has a procedure (``algorithm'') that does this task for a set 
$\{x,y\}$.  Under Independence alone, the procedure for determining 
the social preference on the set~$\{x,y\}$ might not work for 
determining the social preference on another set~$\{x',y'\}$.  The 
planner might thus need many procedures, each working only for a 
particular pair.  I argue~\cite{mihara94b,mihara.thesis} however that 
if Neutrality is satisfied, the planner can use a single procedure for 
all pairs.  In this sense, Neutrality is a stronger condition (than 
Independence) for efficient information processing.  Armstrong's 
setting allows me to discuss information processing, or computability, 
more adequately than Fishburn's setting.  (The discussion of 
Neutrality is dropped in some revisions of the discussion 
paper~\cite{mihara94b}.)

Corollary~\ref{main} shows that given an infinite set of individuals and a 
domain for \swf s, there is no \swf\ (on the domain) satisfying Unanimity, 
Independence, and Anonymity if and only if the domain satisfies a modest 
condition of richness.  The richness condition requires that the planner 
can observe at least a pair of coalitions of the same cardinality that 
complement each other.  As I argue below, the violation of this condition 
severely trivializes a social choice problem.  While Arrow's axioms can be 
satisfied for an infinite society, unequal treatment of individuals thus 
persists.  This result is quite negative, strongly qualifying the 
resolutions (by Fishburn and by Armstrong) of Arrow's impossibility.

The proof of the ``only if'' direction (Proposition~\ref{anonymity2}) of 
Corollary~\ref{main} goes as follows: If the richness condition is 
violated, then each coalition~$A$ has its complement that is ``strictly 
larger'' or ``strictly smaller'' than~$A$.  In the latter case, $A$ can be 
regarded as a ``majority'' of the society.  Then a \swf\ can be defined 
that follows the preferences of the ``majorities.'' The function satisfies 
Anonymity.  In this construction, it would be clear that the violation of 
the richness condition makes the social choice problem trivial.

Theorem~\ref{theorem2} indicates that there is a natural class of \swf s 
that satisfy Unanimity and Neutrality (hence Independence).  These are the 
\swf s that Armstrong~\cite{armstrong85,armstrong92} is mainly concerned 
with in his successive papers.  One might thus have an impression that all 
\swf s satisfying Unanimity and Independence also satisfy Neutrality.  
However, I give an example below that shows there are both dictatorial and 
nondictatorial \swf s violating Neutrality while satisfying Unanimity and 
Independence.


\section{Formulation} \label{dom.res:formu}

$I$ is a set of {\em individuals}, which is either finite or infinite. An 
example of $I$ is the set $\N$ of nonnegative integers. $X$ is a set of 
{\em alternatives}, which has at least three elements. $\P$ is the set of 
(strict) {\em preferences}, i.e., asymmetric and negatively transitive 
binary relations on $X$. 

A {\em Boolean algebra\/} $\B$ consisting of subsets of $I$ satisfies the 
following: (i) $\emptyset$, $I\in\B$; (ii) $A\cup B$, $A\cap B$, 
$\overline{A}\in \B$ if $A$, $B\in\B$ (where $\overline{A}$ denotes the 
complement of $A$).  If $I$ denotes the set of individuals, then 
intuitively, an element of a Boolean algebra is a coalition observable by 
the planner.  For example, the family of all subsets of~$I$ forms a Boolean 
algebra; so does the family of all {\em recursive\/} subsets (i.e., 
effectively decidable sets) of~$\N$; so does the family~$\B_f$ of finite or 
cofinite subsets of~$I$.  A {\em filter\/} $\cal F$ on $\B$ is a family of 
sets in $\B$ satisfying: (i) $\emptyset \notin \cal F$; (ii) if $A\in \cal 
F $ and $A\subseteq B$, then $B\in \cal F$; (iii) if $A$, $B\in \cal F$, 
then $A\cap B\in \cal F$.  We may think of a filter as a family of 
``large'' sets.  An {\em ultrafilter\/} is a filter $\U$ that satisfies: if 
$A\notin \U$, then $\overline{A}\in \U$.  For $\B\supseteq \B_f$, we say an 
ultrafilter $\cal F$ is {\em fixed\/} if it is of the form ${\cal 
F}=\{\,A\in\B: i\in A\,\}$ for some $i\in I$; otherwise, it is called {\em 
free\/} and does not contain any finite sets.

A {\em profile\/} is a list $\p=\profile\in\P^I$ of {\em individual 
preferences\/} $\pref$, $i\in I$. The weak preference $\succeq_i^\p$ is the 
negation of $\prec_i^\p$ (defined from $\pref$ in an obvious manner), and 
the indifference relation $\sim_i^\p$ is the symmetric part of 
$\succeq_i^\p$. A profile $\profile$ is $\B$-{\em measurable\/} if 
$\xprefy\in\B$ for all $x$, $y\in X$. Denote by $\Pbi$ the set of all 
$\B$-measurable profiles. 

A $\B$-{\em social welfare function\/} is a function $\succ\colon\Pbi\to\P$ 
mapping each profile $\p=\profile$ to a social preference 
$\succ\!(\p)=\:\succ^{\p}$.  (Using the notation $\succ$ for a function 
would not cause a confusion since preferences are expressed in the form 
$\pref$ or $\succ^\p$, with profile $\p$ always present as a superscript.) 
Social relations $\succeq^\p$, $\sim^\p$, $\prec^\p$, etc., are defined in 
an obvious manner.

We list Arrow's conditions for $\B$-social welfare functions:
\begin{description}
\item[Unanimity] For any $x$, $y\in X$ and $\p\in\Pbi$, if
$\xprefy=I$, then $x\succ^\p y$.
\item[Independence] For any $x$, $y\in X$ and $\p$, $\p' \in\Pbi$,
if ($x\neq y$ and)
 ${\succ_i^{\p}\cap \{x,y\}^2}=
{\succ_i^{\p'}\cap \{x,y\}^2}$ for all $i\in I$, then
$\succ^{\p}\cap\{x,y\}^2={\succ^{\p'}\cap\{x,y\}^2}$.
\item[Nondictatorship] There is no $i\in I$ such that for all 
$x$,~$ y\in X$ and all $\p \in\Pbi$, 
$x\pref y\Longrightarrow x\succ^\p y.$
\end{description}
A $\B$-social welfare function violating 
Nondictatorship is called {\em dictatorial}. 

\medskip

{\em Remark}.  Nondictatorship may not be a very meaningful axiom when the 
Boolean algebra~$\B$ is pathological.  For example, if $\B$ consists only 
of $\emptyset$ and~$I$, then it can be shown that Nondictatorship is 
violated if a $\B$-\swf~$\succ$ satisfies Unanimity.  In fact, every 
individual~$i\in I$ is a dictator in this case.  One might think having 
more than one dictators is inconsistent with the sense of the word 
``dictator.'' Though I do not require it formally, one natural way to avoid 
the multiplicity of dictators is to assume that $\B$ contains at least all 
single-element sets (hence, all finite and cofinite 
sets).\enspace$\diamondsuit$

\medskip

Finally, we list two more conditions for a $\B$-social welfare function. 
Recall that a 
permutation of $I$ is a one-to-one function on $I$ that is onto $I$.
%
\begin{description}
\item[Anonymity]  For all $\p$,~$\p'\in \Pbi$ and for any
 permutation $\pi\colon I\to I$, if 
$\succ_i^{\p'}=\:\succ_{\pi(i)}^{\p}$ for all~$i\in I$, then
$\succ^{\p'}=\:\succ^\p$.
\item[Neutrality]  For all $x$, $x'$, $y$, $y'\in X$, 
and all $\p$, $\p'\in\Pbi$, 
if [($x \pref y \leftrightarrow x'\succ_i^{\p'} y'$) \& ($y\pref x 
\leftrightarrow y'\succ_i^{\p'} x'$)] for all $i\in I$, then
($x\succ^\p y \leftrightarrow x'\succ^{\p'} y'$).
\end{description}
Anonymity requires that social preferences be invariant with respect to 
permutations of individual preferences. Neutrality requires that if a 
profile $\p$ treats a pair~$(x,y)$ in the same way as a profile $\p'$ 
treats a pair~$(x',y')$, then the resulting two social preferences must 
treat the respective pairs in the same way. Clearly, Anonymity implies 
Nondictatorship if there are at least two individuals in~$I$ and 
$\B\supseteq\B_f$. Neutrality implies Independence.

\medskip

{\it Remark}.  Two modifications of the above notion of Anonymity were 
suggested to me: (i)~restricting permutations to those that permute only 
finitely many individuals and (ii)~restricting permutations to those~$\pi$ 
that are measurable in the sense that $\pi^{-1}(B)\in \B$ for all $B\in\B$.

As for~(i), it is a corollary of Lemma~\ref{arm3.2a} below that {\em any\/} 
$\B$-\swf\ satisfying Independence, Unanimity, and Nondictatorship 
satisfies the modified notion of anonymity.  While trivial, this is 
certainly an interesting result, which complements the results in this 
paper.

As for~(ii), the problem seems more complicated and I will not enter into 
details.  (Proposition~\ref{anonymity2} still holds under the modified 
notion of anonymity.) One nice thing about the modified notion is that we 
can dispense with the condition that $\p'\in\Pbi$ since the other 
conditions imply $\p'\in\Pbi$.  Since I do not require measurability 
of~$\pi$, I cannot drop the condition in my definition of Anonymity.  While 
measurability of~$\pi$ ensures that the inverse images of {\em all\/} 
coalitions in $\B$ are also in~$\B$, I do not feel strongly that we should 
be interested in all coalitions.  Given measurable profiles $\p$ and~$\p'$, 
all the coalitions that we should be interested in are those coalitions 
$\xprefy$ and $\{\,i:x\succ_i^{\p'} y\,\}$ that prefer $x$ to~$y$, for some 
$x$, $y\in X$, and their Boolean combinations.  And whether or not $\pi$ is 
measurable, these ``interesting'' coalitions {\em are\/} in~$\B$, since 
$\p$ and $\p'$ are measurable.  As the following example shows, it is not 
true that the existence of a permutation between two (complementing) 
measurable coalitions implies the existence of a {\em measurable\/} 
permutation.\enspace$\diamondsuit$

\medskip

{\em Example}.  Let $I=\{1,2,\ldots\}$ and let $\B$ be the $\sigma$-algebra 
generated by $\{1\}$, $\{2,3\}$, $\{4,5,6,7\}$, \ldots, $\{2^n, 2^n+1, 
\ldots, 2^{n+1}-1\}$, \ldots.  Measurability of $\pi\colon I\to I$ entails
\begin{equation}	\label{measurability}
\pi^{-1}(\{2^n, 2^n+1, \ldots, 2^{n+1}-1\})
	= \{2^n, 2^n+1, \ldots, 2^{n+1}-1\}
\end{equation}
for all $n$.  (This algebra was brought to my attention by a referee for a 
different purpose.) Suppose under $\p$, $\p'\in\Pbi$, individuals are 
partitioned into two classes $A$ and~$B$: $A$ consists of those belonging 
to $\{2^n, 2^n+1, \ldots, 2^{n+1}-1\}$ for even~$n$ and $B$ consists of 
those belonging to $\{2^n, 2^n+1, \ldots, 2^{n+1}-1\}$ for odd~$n$.  For 
each of the two profiles, all individuals in the same class have the same 
preferences.  Suppose that no individual is indifferent between any two 
distinct alternatives, and that for individuals $a\in A$ and for 
individuals $b\in B$,
\[
x\succ_a^\p y \iff y\succ_b^\p x 
\iff y\succ_a^{\p'} x \iff x\succ_b^{\p'} y
\]
for all $x$, $y\in X$.  It is easy to see that there is a permutation 
between $A$ and~$B$ but there is no {\em measurable\/} permutation between 
them.  My position in the above Remark, if applied to these particular 
profiles on the $\sigma$-algebra, can be expressed as follows: all the 
coalitions that we should be interested in are $\emptyset$, $A$, $B$, 
and~$I$; hence the measurability conditions~(\ref{measurability}) need not 
be imposed.\enspace$\diamondsuit$



\section{Unanimity, Independence, and Anonymity}\label{Anonimity}

\begin{lemma}[Armstrong {\rm\cite[Proposition~3.2]{armstrong80}}] 
\label{arm3.2a}
Let $\B$ be a Boolean algebra on $I$. Suppose a $\B$-social welfare 
function $\succ$ satisfies Unanimity and Independence. Then there is a 
unique ultrafilter $\U_\succ$ on $\B$ such that for all 
$\p=\profile\in\Pbi$ and $x$, $y\in X$, 
\begin{equation}                         \label{arm3.2a:eq}
	\xprefy\in\U_\succ\Longrightarrow x\succ^\p y.
	\end{equation}
\end{lemma} 

{\it Remark}.  The uniqueness follows from Proposition~3.1 of 
Armstrong~\cite{armstrong80}.\enspace$\diamondsuit$

{\it Remark}. Armstrong~\cite{armstrong85} corrects an error in 
Proposition~3.2 of his earlier work~\cite{armstrong80}. 
Lemma~\ref{arm3.2a} is the corrected version.\enspace$\diamondsuit$ 

\medskip

Before stating Theorem~\ref{anonymity}, I treat the case corresponding 
to Fishburn's setting~\cite{fishburn70}, where the domains of a \swf\ are 
unrestricted. 

\begin{prop} \label{anonymity1} 
Let $I$ contain at least two individuals. 
Let $\B$ be the Boolean algebra consisting of {\em all subsets\/} of~$I$.
 Suppose a 
$\B$-social welfare function $\succ$ satisfies Unanimity and Independence. 
Then $\succ$ violates Anonymity. \end{prop} 

{\it Proof}. By Lemma~\ref{arm3.2a}, choose the ultrafilter $\Us$ 
satisfying (\ref{arm3.2a:eq}) for all $\p$ and $x$,~$y$. If $I$ is finite, 
then $\succ$ violates Anonymity since it is dictatorial, for the 
ultrafilter~$\Us$ must be fixed. 

So, suppose $I$ is infinite, say, of cardinality~$\alpha$. We show that $I$ 
is partitioned into subsets $A$ and~$B$ that are equivalent with each 
other: Since the cardinalities of the disjoint sets $I$ and $I\times\{0\}$ 
are $\alpha$, the cardinality of the union of these sets is 
$\alpha+\alpha$; but the last cardinality is equal to the 
cardinality~$\alpha$ of~$I$ since $I$ is infinite. It follows that there is 
a one-to-one mapping $f$ from $I\cup(I\times\{0\})$ onto $I$. Let $A=f(I)$ 
and $B=f(I\times\{0\})$. Then $A$ and~$B$ have the same cardinality and 
form a partition of $I$. 

Since only one of the sets $A$ and~$B$ is in $\Us$, assume without loss of 
generality that $A\in\Us$.  Then consider some $\{x,y\}$ and two profiles 
$\p$ and~$\p'$: $x\pref y$ if $i\in A$, and $y\pref x$ if $i\in B$; 
$y\succ_i^{\p'} x$ if $i\in A$, and $x\succ_i^{\p'} y$ if $i\in B$; the two 
profiles are empty on $X\setminus\{x,y\}$; and $x$ and~$y$ are preferred to 
the other alternatives under both profiles.  Obviously, $\p'$ is obtained 
by permuting the preferences in $\p$ of individuals.  However, $x\succ^\p 
y$ since $\xprefy$, being the set $A$, is in $\Us$; on the other hand, 
$y\succ^{\p'} x$.  This contradicts Anonymity.\qed

\medskip

The above proof depends on the fact that $\B$ contains complementing sets 
of the same cardinality. This condition is adopted in the hypothesis of the 
following theorem. An interesting case is when $I$ is 
infinite. 

\begin{thm}\label{anonymity}
	Let $I$ contain at least two individuals.  Let $\B$ be a Boolean algebra 
	that contains a set that is of the same cardinality as its complement.
	Suppose that a $\B$-\swf~$\succ$ satisfies Unanimity and Independence.
	  Then, $\succ$ violates Anonymity.
\end{thm}

{\em Proof}.  We have a set $A\in\B$ that has the same cardinality as its 
complement~$\bA$.  Let $B=\bA$ and argue as in the last paragraph of the 
proof of Proposition~\ref{anonymity1}.  Note that both $\p$ and~$\p'$ are 
easily seen to be $\B$-measurable.\qed

\medskip

Some Boolean algebras do not satisfy the hypothesis of 
Theorem~\ref{anonymity}.  An extreme example is the following:

\medskip

{\em Example}.  Let $\B$ consist of $\emptyset$ and $I$ only.  This is the 
case in which any $\B$-\swf\ is defined only for unanimous profiles.  Then, 
it is intuitively clear that any $\B$-\swf\ satisfies Anonymity.  Indeed, 
the antecedent ($\forall i \succ_i^{\p'}=\,\succ_{\pi(i)}^\p$) in the 
statement of Anonymity can be satisfied only when $\p=\p'$, since for any 
measurable profile~$\p$ and for all~$x$ and~$y$, either (i)~$x\pref y$ for 
all~$i$ or (ii)~$\neg x\pref y$ for all~$i$.  (If~(i), then for all~$i$, 
$x\succ_{\pi(i)}^\p y$ for any permutation~$\pi$ of $I$; similarly 
for~(ii).) Since the antecedent is satisfied only when $\p=\p'$, in which 
case the consequent is trivially satisfied, Anonymity is 
established.\enspace$\diamondsuit$

\medskip

There are less trivial Boolean algebras that do not satisfy the hypothesis 
of Theorem~\ref{anonymity}. For example, let 
\[ \B_f=\{\,A\subseteq I: 
\mbox{$A$ is finite or cofinite}\,\}. 
\] 
(A {\em cofinite\/} set is a set whose complement is finite.) Then $\B_f$ 
is a Boolean algebra that does not contain complementing sets of~$I$ that 
have the same cardinality, if $I$ is infinite.  The same is true for the 
Boolean algebra consisting of countable or co-countable elements, if $I$ is 
uncountable.


However, the following proposition shows that the hypothesis for Boolean 
algebras is necessary for the conclusion of the theorem if $I$ is infinite.

\begin{prop}
	\label{anonymity2}
	Let~$I$ be infinite.  Let $\B$ be a Boolean algebra on~$I$ that does 
	not contain complementing sets of the same cardinality.  
	   Then, there is 
	a $\B$-\swf\ satisfying Unanimity, Independence, and Anonymity.
\end{prop}

Before giving a proof, we introduce the following:

\begin{lemma}[Armstrong {\rm\cite[Proposition~3.1]{armstrong80}}]             
\label{arm3.1}
Let $\B$ be a Boolean algebra on $I$. 
Suppose $\U$ is an ultrafilter on $\B$.  Then the map $\succ$ on $\Pbi$
defined for $\p\in \Pbi$ and $x$, $y\in X$ by  
\begin{equation}\label{arm3.1eq}
	x\succ^{\p}
	y\iff\xprefy\in \U\end{equation}
  is a $\B$-social welfare function satisfying
Unanimity and Independence.
\end{lemma}

{\em Proof of Proposition~\ref{anonymity2}}.  (This proof involves some 
cardinal arithmetic.  Enderton~\cite[ch.~6]{enderton77} is a 
straightforward exposition.)

Let
\begin{equation}
	\U=\{\, A\in \B:|A|>|\bA|\,\},
	\label{majority}
\end{equation}
where $|A|$ denotes the cardinal number of $A$.  We show that $\U$ is an 
ultrafilter:
\newcommand{\bB}{\overline{B}}
\begin{enumerate}
	\item  [(i)]  $\emptyset\notin\U$ since 
	$|\emptyset|<|\overline{\emptyset}|=|I|$.
	
	\item[(ii)]  Suppose $A\in \U$ and $A\subseteq B\in\B$. 
	Then $|A| > |\bA|$ and 
	$|A| \leq |B|$.  Also, $|\bA|\geq |\bB|$ since $\bA\supseteq\bB$.
	From these inequalities, we get
	\[ |B| \geq |A| > |\bA| \geq |\bB|. \]
	Hence, $|B| > |\bB|$, implying $B\in\U$.
	
	\item  [(iii)] Suppose $A$, $B\in\U$.  Then $|\bA| < |A|$ and
	$|\bB| < |B|$.  Without loss of generality, assume $|\bB|\leq |\bA|$.  
	We have to show that $|A\cap B| > |\overline{A\cap B}|$.  Suppose 
	otherwise.  Then $|A\cap B| \leq |\overline{A\cap B}|$.  So,
	\begin{eqnarray*}
		|I| & = & |(A\cap B) \cup (\overline{A\cap B})|  \\
		 & = &|A \cap B|+|\overline{A\cap B}|  \\
		 & \leq & |\overline{A\cap B}| +|\overline{A\cap B}|  \\
		 & = & |\bA\cup\bB|+|\bA\cup\bB|  \\
		 & \leq & |\bA|+|\bB|+|\bA|+|\bB|   \\
		 & \leq & |\bA|+|\bA|+|\bA|+|\bA|.
	\end{eqnarray*}
	Let $\alpha$ be the last expression.
	If $\bA$ is finite, then $\alpha<|I|$ since $I$ is infinite.  If $\bA$ 
	is infinite, then by the absorption law, $\alpha=|\bA|<|A|\leq |I|$. 
	In either case, we have established that $|I|<|I|$, which is  
	contradiction.
	\item  [(iv)] Suppose that $\bA\in\B$ but $\bA\notin\U$.  Then, 
	$|\bA|\leq|A|$.  But $|\bA|\neq|A|$ by the hypothesis on~$\B$.  Hence, 
	$|A|>|\bA|$.  So, $A\in\U$.
\end{enumerate}

Now, define a $\B$-\swf~$\succ$ by (\ref{arm3.1eq}).  $\succ$ satisfies 
Unanimity and Independence.

To show Anonymity, let $\p$, $\p'\in\Pbi$, let $\pi$ be a permutation of 
$I$, and suppose that $\succ_i^{\p'}=\,\succ_{\pi(i)}^\p$ for all~$i$.  
Fix~$x$ and~$y$.  (We have to show $x\succ^{\p'} y\leftrightarrow x\succ^\p 
y$.) Then, the cardinal numbers of $\{\,i:x\succ_i^{\p'} y\,\}$ and of 
$\xprefy$ are the same.  Also, the complements of these sets are of the 
same cardinality.  It follows that {\em either\/} both 
$\{\,i:x\succ_i^{\p'} y\,\}$ and $\xprefy$ are in $\U$ {\em or\/} neither 
is in $\U$.  Hence, Lemma~\ref{arm3.1} implies that $x\succ^{\p'} y$ iff 
$x\succ^\p y$.\qed

\medskip

{\it Remark}.  It can be shown that $\U$ in (\ref{majority}) is in fact 
$\{\, A\in \B:|A|=|I|\,\}$.  One can give a shorter proof using this 
fact.\enspace$\diamondsuit$

\begin{cor}\label{main}
	Let $I$ be infinite and let $\B$ be a Boolean algebra on~$I$.  
	Then there is no $\B$-\swf\ satisfying Unanimity, Independence, 
	and Anonymity if and only if $\B$ contains a set that has the same 
	cardinality as its complement.
\end{cor}


\section{Unanimity, Independence, and Neutrality}\label{Neutrality}

Let $\B$ be a Boolean algebra on $I$.  Let $\U$ be an ultrafilter on~$\B$.  
Lemma~\ref{arm3.1} above shows that the map $F_\U$ from $\p\in\Pbi$ to a 
binary relation~$F_\U^\p$ on $X$ defined by
\begin{equation}\label{precise}
	x F_\U^\p y \iff \xprefy\in\U.
\end{equation}
is a $\B$-\swf\ satisfying Unanimity and Independence.  We say that a 
$\B$-\swf~$\succ$ is {\em precisely diktatorial\/} if $\succ\,=F_\U$ for 
some ultrafilter~$\U$.  (Armstrong~\cite{armstrong85} calls such \swf s 
``precisely dictatorial.'' I reserve the word {\em dictatorial\/} for those 
\swf s violating Nondictatorship.) Precisely diktatorial \swf s are the 
social welfare functions~$\succ$ whose ultrafilter~$\Us$ (in 
Lemma~\ref{arm3.2a}) of decisive coalitions precisely determines the social 
preference in the sense that ``$\Longrightarrow$'' in (\ref{arm3.2a:eq}) 
can be replaced by ``$\Longleftrightarrow$.''


There are some $\B$-social welfare functions satisfying Unanimity and 
Independence that are not precisely diktatorial.  An example is a social 
welfare function with a primary dictator (dictator in the true sense) and a 
secondary dictator such that the latter's preference determines the social 
preference between two alternatives in case the primary dictator is 
indifferent between the alternatives.  It is easy to see that a social 
welfare function can be constructed similarly for any finite ``hierarchy'' 
of dictators (or of ultrafilters).  In fact, the following discussion 
generalizes this construction to any well-ordered sequence of ultrafilters.

Let $\B$ be a Boolean algebra on $I$. Let $U=\{\,\U^\alpha:\alpha\in 
\Gamma\,\}$ be a well-ordered family of ultrafilters on $\B$. Define a map 
$H_U$ from $\p\in\Pbi$ to a binary relation $H_U^\p$ on $X$ as follows: 
for $\p\in\Pbi$, and for $x$,~$y\in X$, 
\begin{equation}\label{hierarchical.swf}
	x H_U^\p y \iff (\exists\alpha\in\Gamma)
	 [(\forall\beta<\alpha)(\{\,i:x\sim_i^\p y\,\}\in\U^\beta)\ \&\
	 \xprefy\in\U^\alpha].  
\end{equation}
	 
\noindent 
Then, by~\cite[Proposition~17]{armstrong92}, $H_U$ is a 
$\B$-\swf\ satisfying Unanimity and Independence. We call 
$H_U\colon\Pbi\to\P$ the {\em hierarchical\/} \swf\ {\em associated with\/} 
the sequence~$U$. 

\begin{thm}\label{theorem2}
	Let $H_U\colon\Pbi\to\P$ be the hierarchical \swf\ associated with a 
	well-ordered sequence $U$ of ultrafilters on $\B$.  Then, $H_U$ 
	satisfies Unanimity and Neutrality.
\end{thm}

{\em Proof}.   It is discussed above that $H_U$ is a $\B$-social welfare 
function satisfying Unanimity.

To show Neutrality, suppose that 
($x \pref y \leftrightarrow x'\succ_i^{\p'} y'$)
and  ($y\pref x \leftrightarrow y'\succ_i^{\p'} x'$) for all $i\in I$. 
 Then 
\[
\{\,i:x\sim_i^{\p} y\,\}=\{\,i:x'\sim_i^{\p'} y'\,\}
\]
and
\[
\xprefy=\{\,i:x'\succ_i^{\p'} y'\,\}.
\]
So, (\ref{hierarchical.swf}) implies that 
\[
x H_U^\p y \iff x' H_U^{\p'} y'.
\]
Therefore, Neutrality is satisfied.\qed

\begin{cor}
	Precisely diktatorial $\B$-\swf s satisfy Neutrality.
\end{cor}

Theorem~\ref{theorem2} implies that if $I$ is infinite and 
$\B\supseteq\B_f$ (i.e., $\B$ contains all finite and cofinite subsets 
of~$I$),  then there are both (i)~dictatorial and 
(ii)~nondictatorial $\B$-\swf s satisfying Unanimity and Neutrality (hence 
Independence). To see that (i)~there is a dictatorial one, just let an 
ultrafilter $\U$ in (\ref{precise}) be fixed. To see that (ii)~there is a 
nondictatorial function, let $\U$ in (\ref{precise}) be a free ultrafilter 
on~$\B$. (A free ultrafilter can be obtained by extending the filter of 
cofinite elements of $\B$ using Zorn's lemma.) 

Because of Theorem~\ref{theorem2}, in order to find a social welfare 
function violating Neutrality but satisfying Unanimity and Independence, we 
have to consider a \swf\ that is not the hierarchical~$H_U$ associated with 
a well-ordered sequence~$U$ of ultrafilters.  The following example shows 
that there are such social welfare functions both among dictatorial ones 
(set $\U$ be a fixed ultrafilter) and among nondictatorial ones (set $\U$ 
be free), provided that $I$ is infinite and $\B\supseteq\B_f$.  (The 
example is a special instance of attaching a {\em Deux ex Machina\/} to a 
hierarchical \swf, discussed in Armstrong~\cite[p.~39]{armstrong92}.  It is 
easy to see that addition of a {\em Deux ex Machina\/} to a hierarchy 
destroys Neutrality.)

\medskip

{\em Example}. Let $P$ be an arbitrary nonempty preference in $\P$. Let 
$\B$ be a Boolean algebra on~$I$. Let 
$\U$ be an arbitrary ultrafilter on $\B$. Define a map $\succ$ from 
$\p\in\Pbi$ into a binary relation $\succ^\p$ on $X$ as follows: for 
$\p\in\Pbi$, and for $x$,~$y\in X$, 
\begin{equation}\label{example.eq}
\begin{array}{lcl}
	x\succ^\p y & \mbox{iff} & \mbox{(a) $\xprefy\in\U$ or}  \\
	 &  & \mbox{(b) $\{\,i:x\sim^\p_i y\,\}\in\U\ \&\  x P y$.}
\end{array}
\end{equation}

First, note that (\ref{example.eq}) can be rewritten as:
\begin{equation}\label{example.eq2}
\begin{array}{lcl}
	x\succ^\p y & \mbox{iff} & \mbox{(a) $x F_U^\p y$ or}  \\
	 &  & \mbox{(b) $\neg x F_U^\p y$\ \&\  $\neg y F_U^\p x$
	 \ \&\ $x P y$.}
\end{array}
\end{equation}
where $F_U$ is given by~(\ref{precise}).  
Armstrong~\cite[Lemma~1]{armstrong85} proves the following:
\begin{lemma}
	Let $P$, $P'\in\P$.  Define a binary relation $P''$ on $X$ by $xP''y$
	 if {\rm (a)}~$x P' y$ or 
	 {\rm (b)}~$\neg xP'y$ \& $\neg yP'x$ \& $xPy$.  
	 Then, $P''\in\P$.
\end{lemma}

For the $\succ$ defined by (\ref{example.eq}), we show the following 1--4: 
\begin{enumerate}
    \item {\em $\succ$ is a $\B$-\swf}. We must show that for each 
$\p\in\Pbi$, $\succ^\p$ is in $\P$. Fix $\p\in\Pbi$. Then since $\succ^\p$ 
is defined from $F_U^\p$ and~$P\in\P$ as in (\ref{example.eq2}), above 
Lemma applies immediately and we get $\succ^\p\in \P$.

     \item  {\em $\succ$ satisfies Unanimity}. This is obvious from 
(\ref{example.eq}). 

	\item  {\em $\succ$ satisfies Independence}. Suppose that 
$\pref\cap\{x,y\}^2=\,\succ_i^{\p'}\cap\{x,y\}^2$ for all $i\in I$. To show 
contradiction, assume $x\succ^\p y$ but $\neg x\succ^{\p'} y$ without loss 
of generality. That $x\succ^\p y$ implies that either (a) or (b) 
in~(\ref{example.eq}). In case~(a), $\{\,i:x\succ_i^{\p'} y\,\}\in\U$ since 
$\xprefy\in\U$ and these two coalitions are the same. 
By~(\ref{example.eq}), $x\succ^{\p'} y$, contradicting the assumption. In 
case~(b), $\{\,i:x\sim_i^{\p'} y\,\}\in\U$ (since $\{\,i:x\sim_i^{\p} 
y\,\}\in\U$ and these two coalitions are the same) as well as $xPy$. 
By~(\ref{example.eq}), $x\succ^{\p'} y$, contradiction. 

\item {\em $\succ$ violates Neutrality}.  Let $\p\in\Pbi$ and $x$, $y\in 
X$ be such that $\{\,i:x\sim_i^\p y\,\}=I$ and $xPy$.  (Since $P$ is not 
empty, there are such $x$ and~$y$.) Then, $x\succ^\p y$.  Let $\p'=\p$, and 
$x'=y$, $y'=x$.  Clearly, $y'\succ^{\p'} x'$.  Hence, $\neg x'\succ^{\p'} 
y'$, violating the consequent in the statement of the Neutrality condition.  
On the other hand, the antecedent of the Neutrality condition is satisfied 
since all individuals are indifferent between the two alternatives.  Hence, 
Neutrality is violated.\enspace$\diamondsuit$

\end{enumerate}

\pagebreak

\begin{thebibliography}{10}

\bibitem{armstrong80}
Armstrong TE (1980)
\newblock Arrow's {T}heorem with restricted coalition algebras:
\newblock {J Math Econ} 7:55--75

\bibitem{armstrong85}
Armstrong TE (1985)
\newblock Precisely dictatorial social welfare functions: Erratum and addendum
  to `{Arrow's Theorem} with restricted coalition algebras':
\newblock {J Math Econ} 14:57--59

\bibitem{armstrong92}
Armstrong TE (1992)
\newblock Hierarchical {A}rrow social welfare functions:
\newblock {Econ Theory} 2:27--41

\bibitem{arrow63}
Arrow KJ (1963)
\newblock {Social choice and individual values}, 2nd edition.
\newblock Yale University Press, New Haven

\bibitem{enderton77}
Enderton HB (1977)
\newblock {Elements of set theory}.
\newblock Academic Press, Orlando

\bibitem{fishburn70}
Fishburn PC (1970)
\newblock Arrow's {impossibility} {theorem}: Concise proof and infinite 
voters:
\newblock {J Econ Theory} 2:103--6

\bibitem{kelly78}
Kelly JS (1978)
\newblock {Arrow impossibility theorems}.
\newblock Academic Press, New York

\bibitem{kirman-sondermann72}
Kirman AP and Sondermann D (1972)
\newblock Arrow's {Theorem}, many agents, and invisible dictators:
\newblock {J Econ Theory} 5:267--277

\bibitem{may52}
May KO (1952)
\newblock A set of independent, necessary and sufficient conditions for simple
  majority decision:
\newblock {Econometrica} 20:680--84

\bibitem{mihara94b}
Mihara HR (1994)
\newblock Arrow's {T}heorem and {T}uring computability:
\newblock Discussion Paper 276, Center for Economic Research, University of
  Minnesota
\newblock A revision available as ewp-pe/9408001 from the Working Paper Archive
 (econ-wp) at Washington University in St.\ Louis
%  some revisions dropped Neutrality

\bibitem{mihara.thesis}
Mihara HR (1995)
\newblock {Arrow's {T}heorem, {T}uring computability, and oracles}.
\newblock PhD thesis, University of Minnesota, Minneapolis

\end{thebibliography}

\end{document}             % End of document.

%%%%%%%%%%%