% LaTeX2.09 file  Arrow_comp_sub2_v2.tex
% Arrow's Theorem and Turing computability
% H Reiju Mihara

% This version adds the bibliographic information 
% to the final manuscript
% submitted to Economic Theory

\documentstyle[11pt]{article}
\title{Arrow's Theorem and Turing computability\thanks{This paper is based 
on Theorem~1 of my thesis~\protect\cite{mihara.thesis} submitted to the 
University of Minnesota.  I am indebted to my thesis adviser Marcel K.  
Richter and to Wayne Richter for their comments and guidance.  Thanks are 
also due to Edward J.  Green, Leonid Hurwicz, James S.  Jordan, Kenji 
Kashiwabara, Andrew McLennan, Ravindra R. Ranade and to the participants 
of the seminar on economic theory and foundations, spring 1994 at 
Minnesota, especially to KamChau Wong.  The paper was presented at the 
Econometric Society Seventh World Congress, Tokyo 1995.}} 
\author{H.  Reiju Mihara\\ 
{\tt reiju@ec.kagawa-u.ac.jp}\\
Economics, Kagawa University, Takamatsu, Kagawa 760,
Japan}
\date{August 1996\\
\protect[Economic Theory {\bf 10}, 257--276 (1997)]}

%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}$}}  %redefined later 
\newcommand{\Pbi}{\P_\B^I}                %redefined later
\newcommand{\Preci}{\P_{\rm REC}^I}      %redefined later
\newcommand{\xprefy}{\{\,i:{x\pref y}\,\}}   %redefined later
\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{\betas}{{\beta_\succ}}
\newcommand{\gammas}{\gamma_\succ}

\newcommand{\evecim}{\mbox{$\langle e_1, e_2, e_3\rangle$}}
\newcommand{\pairxy}{\mbox{$(x,y)$}}

\newcommand{\revised}{\marginpar{$\bullet$}}
%aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{lemma}{Lemma}

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

\maketitle % Produces the title. 

\vspace{2.5cm}

\noindent Received:\hspace{3cm} revised version

\bigskip

\noindent {\bf Summary.}
A social welfare function for a denumerable society satisfies {\em Pairwise 
Computability\/} if for each pair~\pairxy\ of alternatives, there exists an 
algorithm that can decide from any description of each profile on~$\{x,y\}$ 
whether the society prefers $x$ to~$y$.  I prove that if a social welfare 
function satisfying Unanimity and Independence also satisfies Pairwise 
Computability, then it is dictatorial.  This result severely limits on 
practical grounds Fishburn's resolution~(1970) of Arrow's impossibility.  
I also give an interpretation of a denumerable ``society.''

\bigskip

\noindent JEL Classifications: D71, C69, D89.

\bigskip

\noindent 
[Keywords:  Arrow impossibility theorem, Hayek's knowledge problem, 
algorithms, recursion theory, ultrafilters.]
 
\pagebreak

\section{Introduction} 

\subsection{Overview}
%\subsubsection{}
\label{IntroOverview1}

Computability analysis of social choice is concerned with algorithmic 
properties of social decision-making.  It aims at identifying which social 
choice rules can be algorithmically executed, and at determining how 
complex such rules are.  This paper reconsiders Arrow's Impossibility 
Theorem~\cite{arrow63} from a viewpoint of computability analysis of social 
choice.

Arrow's Impossibility Theorem states that there is no social welfare 
function that satisfies the Unanimity, the Independence and the 
Nondictatorship axioms.  Here, a {\em social welfare function\/} maps each 
profile of individual preferences into a ``social preference.'' The 
preferences are defined on a set of at least three (social) alternatives 
and there are no restrictions on the preferences beyond the usual ordering 
properties.  {\em Unanimity\/} says that when all individuals prefer an 
alternative $x$ to another alternative $y$, then society must ``prefer'' 
$x$ to~$y$.  {\em Independence\/} means that the only information relevant 
for determining ``social preference'' on a set $\{x,y\}$ is the individual 
preferences on the set.  {\em Nondictatorship\/} rules out an individual 
such that whenever he prefers $x$ to~$y$, society must ``prefer'' $x$ 
to~$y$.  Henceforth, I apply the word ``preferences'' and related 
expressions to society as well as to individuals without the quotation 
marks.

In this paper, I intend to study feasibility of centralized decision-making 
such as voting.  I will interpret feasibility of executing a social choice 
rule by a central authority as algorithmic computability of the rule.  This 
is in effect the same as regarding such an authority as an algorithm (or a 
digital computer) that computes the rule.  Support for this comes from 
several sources.  First, well-known schemes (for variable, finite number of 
voters), such as the simple majority rule, the unanimity rule, and the 
Condorcet and the Borda rules, are all algorithms.  Noncomputable social 
choice rules cannot be carried out systematically no matter how 
well-specified.  (Kelly~\cite{kelly88} gives examples of noncomputable 
social choice rules.) Second, the use of the language by social choice 
theorists suggests that the social welfare functions they consider are in 
fact computable ones.  For example, Arrow defined a social welfare function 
to be a ``process or rule'' which, for each profile of individual 
preferences, ``states'' a corresponding social 
preference~\cite[p.~23]{arrow63}, and called the function a 
``procedure''~\cite[p.~2]{arrow63}.  Indeed, he later 
wrote~\cite[p.~S398]{arrow86} in a slightly different context, ``The next 
step in analysis, I would conjecture, is a more consistent assumption of 
computability in the formulation of economic hypotheses.'' Finally, there 
is a normative reason for supporting algorithmic computability.  
Algorithmic social choice rules specify the procedures in such a way that 
the same results will be obtained irrespective of who carries out a 
computation.  They leave no room for personal judgments by the authority.  
In this sense, computability of social choice rules formalizes the notion 
of ``due process.''

However, social choice theory has not traditionally paid much attention to 
formal problems of computability.  This is understandable, for 
computability of social welfare functions is automatically satisfied by 
assuming a fixed, finite set of alternatives and a fixed, finite set of 
individuals---a common assumption in the literature.  Computability is 
satisfied since, in such cases, a finite table can be constructed 
expressing the function.

As a modification to Arrow's setting, I discard the finite framework.  
Fishburn~\cite{fishburn70} and Kirman and 
Sondermann~\cite{kirman-sondermann72} showed that when there are infinitely 
many individuals in a society, there is a social welfare function 
satisfying the axioms of Unanimity, Independence, and Nondictatorship.  
Armstrong~\cite{armstrong80,armstrong85} proved that this result is 
unaffected even when profiles are restricted to those measurable with 
respect to a Boolean algebra of coalitions.  Here, a profile is said to be 
{\em measurable\/} with respect to a Boolean algebra if for all 
alternatives $x$ and~$y$, the coalition that prefers $x$ to~$y$ belongs to 
it.

I apply Armstrong's framework to a particular set of individuals and a 
particular Boolean algebra of coalitions suitable for considering 
computability, namely the set~$\N$ of nonnegative integers and the Boolean 
algebra of all recursive coalitions.  The {\em recursive\/} coalitions are 
the coalitions for which there is an algorithm to decide their membership.  
The domain restriction thus requires the members of a coalition to be 
algorithmically identifiable.  We can name recursive coalitions using the 
G\"odel numbers (codes) of these algorithms.  We can then describe each 
measurable profile restricted on a set $\{x,y\}$ by giving names to (i)~the 
coalition that prefers $x$ to~$y$, (ii)~the coalition that prefers $y$ 
to~$x$, and (iii)~the coalition that is indifferent between $x$ and~$y$.

Suppose that a \swf\ for a denumerable (i.e., countably infinite) society 
satisfies Independence.  The \swf\ satisfies {\em Pairwise Computability\/} 
if for each pair~\pairxy\ of alternatives, there exists an algorithm that 
can decide, for each measurable profile of individual preferences and for 
each description of the profile on~$\{x,y\}$, whether the society prefers 
$x$ to~$y$, from the description.  I prove (Theorem~\ref{main.theorem1}) 
that if a \swf\ satisfying Unanimity and Independence also satisfies 
Pairwise Computability, then it must be dictatorial.  A more desirable 
notion of computability (``Strong Pairwise Computability'') for a social 
welfare function satisfying Independence {\em could\/} be 
introduced~\cite{mihara.thesis}; however, the negative result of 
Theorem~\ref{main.theorem1} implies that strengthening the condition of 
computability is not very interesting.  On the other hand, the proof of 
Proposition~\ref{main2} shows through examples that while there are some 
dictatorial \swf s that satisfy Pairwise Computability, not all do.

Pairwise Computability requires neither a finite set of alternatives, nor 
computable individual preferences.  Also, the information necessary for 
computation is readily obtainable, being a description of a profile only on 
a set~$\{x,y\}$.  Theorem~\ref{main.theorem1} severely limits on practical 
grounds Fishburn's resolution, re-establishing Arrow's negative result even 
for denumerable societies.

%%%%%
\medskip

Since speaking of infinitely many people involved in social choice might 
seem unrealistic, I discuss a natural example of a denumerable ``society'' 
derived from only finitely many people.  The example does not assume people 
extending into the indefinite future.  I postpone a concrete example to 
Section~\ref{dom.res:swf} and give an abstract version here.

Consider a social choice problem in which there are finitely many people 
and there is uncertainty expressed by a denumerable set of states of the 
world.  Assume that it cannot be known which state will be realized by the 
time social choice is made.  Then, it is reasonable to suppose that people 
express their preferences conditioned on states: ``person $j$ prefers 
social alternative $x$ to~$y$ if the state is $s$''---which is denoted by 
$x\succ_j^s y$.

A denumerable ``society'' is derived from the society of people facing 
uncertainty as follows.  Regard {\em person\/}~$j$'s preference~$\succ_j^s$ 
in state $s$ as the preference $\succ_{(j,s)}$ of the newly named {\em 
individual\/}~$(j,s)$.  Since there are only finitely many people and 
denumerably many states, we have a denumerable set of individuals~$(j,s)$.  
This derivation of an infinite ``society'' as well as the domain 
restrictions might seem artificial.  However, they are in fact natural and 
even have some advantages.  First, inter-state comparisons are avoided, in 
the same sense that inter-personal comparisons are avoided in Arrow's 
setting.  Second, in this formulation, people can express their preferences 
without estimating probabilities.  Third, the domain restriction requires, 
for example, that each person can identify (in a finite way) the set $\{\, 
s:x\succ_j^s y\,\}$ of states in which he prefers $x$ to~$y$, for each $x$ 
and~$y$.  This is a natural epistemological condition since, instead of 
having to make infinitely many statements (whether $x\succ_j^s y$ for 
infinitely many~$s$) without any recognizable pattern among the statements, 
he does have a finite rule that can make those infinitely many statements.

%%%
\medskip

Hayek~\cite{hayek45} points out that economic data, or knowledge, is 
dispersed: assuming data to be given to a single mind is a trivialization 
of social problems.  This paper gives an example of a ``trivialized'' 
problem that is impossible to solve nevertheless once feasibility of 
information processing is formally required.  In this sense, the paper 
strengthens Hayek's thesis about the difficulty of informationally 
centralized decision-making.

The negative result (Theorem~\ref{main.theorem1}) suggests relaxing the 
notion of Pairwise Computability to see if the resulting condition can be 
met by a \swf\ satisfying Arrow's axioms.  A positive result, using oracle 
Turing programs, is discussed in my dissertation~\cite{mihara.thesis}.  (In 
a paper~\cite{mihara96a} attempting to avoid the Gibbard-Satterthwaite 
impossibility, I use the essence of the proof of the positive result to 
construct a coalitionally strategyproof social choice function.) 

%\subsubsection{} 

The paper is organized as follows.  The rest of the Introduction surveys 
the related literature.  The main results are stated in 
Section~\ref{theorems}, which is preceded by informal discussion in 
Section~\ref{discussion}.  Section~\ref{theorems} assumes a few 
terminologies in Appendix~\ref{RecTh} on recursion theory (the study of 
algorithms).  Appendix~\ref{alternatives} discusses two notions of 
computability not covered in the main body.  The proofs of the main results 
are given in Appendix~\ref{proofs}, where the knowledge of recursion theory 
covered in Appendix~\ref{RecTh} is assumed.


\subsection{Related Literature} \label{Literature} 

The modern paradigm of social choice theory began with Arrow's 
Impossibility Theorem~\cite{arrow63} in 1951.  Surveys (e.g., 
Sen~\cite{sen86}) of later developments in social choice reveal that issues 
relating to computability in social choice have largely been ignored.  This 
lack of interest is surprising, given that social choice theory has had a 
significant impact on philosophy and economics~\cite{hausman-mcpherson93}: 
Philosophers have been concerned about algorithmic computability in their 
study of logical reasoning processes; economists have 
witnessed~\cite{lavoie85r} the socialist calculation debate among Mises, 
Hayek~\cite{hayek45}, Lange, and Lerner.

Algorithmic (Turing) computability has been studied in the related areas by 
Canning~\cite{canning92} in game theory, by Spear~\cite{spear89} on 
learning rational expectations, by Wong~\cite{wong_kc94} in general 
equilibrium theory, and by Lewis~\cite{lewis85} in individual choice 
theory.

In social choice theory, computability is studied from the recursion 
theoretic point of view by the following authors.

Kelly~\cite{kelly88} considers computability of variable-voter social 
choice rules.  He is interested in finding a {\em non}computable rule 
satisfying a subset of axioms characterizing the simple majority rule 
(which is computable), since he wants to see which properties of the rule 
lead to computability.

The paper most closely related with the present study is 
Lewis~\cite{lewis88}, which is motivated by constructive mathematics.  It 
discusses Arrow's Theorem ``within the recursion theoretic setting.'' 
Although the set of individuals he considers is the same as mine (the set 
of natural numbers), our frameworks are different:(i)~the set of 
alternatives in Lewis is a countable set that contains at least three 
elements, while my set of alternatives can be uncountable; (ii)~his set of 
preferences is countable, while mine can be uncountable; (iii)~Lewis 
restricts profiles to be recursive (i.e., there is an algorithm to 
determine for each individual and each pair of alternatives, his preference 
on the pair)---such profiles form a strict subclass of my REC-measurable 
profiles to be defined later; (iv)~Lewis assumes that coalitions are 
recursively enumerable, while in my framework each coalition that prefers 
one alternative to another is recursive.  Lewis states that in his 
``recursive'' setting, there is a ``dictator.'' But, in his theorems, he is 
using the word ``dictator'' in a much weaker sense than mine: in essence, 
he claims that for {\em each\/} profile, there is a ``dictator'' whose 
preference determines the social preference for that particular profile; by 
contrast, I prove existence of a single dictator for all profiles.  
(Although he presents the result without referring to the Unanimity or the 
Independence axioms, I suppose it is an oversight.)

\section{Discussion}\label{discussion}

This Section is an informal exposition of the framework and the results in 
Section~\ref{theorems}.

{\em In the rest of the paper, I informally use the word {\em person\/} 
({\em people}) to refer to a person in the ordinary sense, a human being.  
The word {\em individual\/} is used in a technical sense.} An individual 
may be either a person or a name representing a person at a certain date or 
state.

\subsection{Domain Restrictions}\label{dom.res}

In this Section, I introduce for a social welfare function a domain 
suitable for consideration of computability issues in the setting of 
Arrow's Theorem.  The treatment is based on Armstrong's 
extensions~\cite{armstrong80} of Arrow's Impossibility Theorem 
\cite{arrow63} and of Fishburn's resolution~\cite{fishburn70}.

\subsubsection{Naming Individuals}\label{dom.res:name}

Since Arrow's impossibility persists for any finite set of individuals (a 
corollary of Proposition~\ref{arm3.2a} in Appendix~\ref{proofs}), I 
consider as a set~$I$ of (the names of) {\em individuals\/} one of the 
simplest infinite sets, namely the set $\N$ of nonnegative integers.  A 
denumerable set of individuals arises naturally in social choice.

For example, a denumerable set of individuals may arise when a national 
government is evaluating alternative policies that can affect future 
generations.  We can, for example, assign a name to each person as follows: 
if a person is a female, she is given a name starting from a nonzero even 
number; otherwise, an odd number.  Likewise, economic, social, political 
classifications can be coded into a name.

Another example of a denumerable set of individuals is given by the case of 
finitely many people facing a set~$X$ of alternatives and uncertainty 
expressed by a denumerable set~$S$ of states of the world.  This was 
discussed in the Introduction.

%% coalitions
\subsubsection{Coalitions}\label{dom.res:coalitions}

I assume that only some {\em coalitions\/} (sets of individuals) are 
observable.  Intuitively, the observations are made by an 
agent, called a {\em social planner}, a human or machine that executes a 
social welfare function.  Since an observation is a cognitive activity, it 
seems natural to introduce a structure for observable coalitions.  
Following Armstrong~\cite{armstrong80}, I require that the family of 
observable coalitions form a {\em Boolean algebra}.  Namely, if two 
coalitions are observable so must be their union, intersection, and 
complements.  For instance, (i) the family of all subsets of $I=\N$ and 
(ii) the family of all finite sets and {\em cofinite\/} sets (i.e., the 
complements of a finite set) of $I=\N$, each forms a Boolean algebra.

Since I am concerned with algorithmic computability, I restrict coalitions 
to those which can be recognized by some algorithm.  Then, we will see that 
(i) becomes too broad a family, being uncountable, while (ii) is 
unnecessarily restrictive, excluding the intuitively ``describable'' 
coalition of even numbers, for example.  The observable coalitions that I 
propose are the {\em recursive\/} sets of individuals.  These are the 
coalitions whose membership is effectively decidable, i.e., the ones for 
which there is an algorithm that can decide for each name~$i$, whether 
individual~$i$ is in the coalition.  The algorithmically decidable nature 
of recursive coalitions seems to capture the idea of what we mean by a 
coalition that is ``observable'' or ``recognizable'' or ``identifiable.'' 
The recursive coalitions form a Boolean algebra.


\subsubsection{Social Welfare Functions}
\label{dom.res:swf}

A {\em \swf\/}\ (formally, an REC-\swf) maps a {\em profile\/} 
(list)~$\p=\profile$ of individual preferences~$\pref$ (on a set $X$ of 
alternatives) to a social preference~$\succ^\p$.  I assume that the set~$I$ 
of individuals is $\N$, and that the domain includes all those 
profiles~$\p$ such that for any $x$ and~$y$, the {\em coalition $\xprefy$ 
that prefers $x$ to~$y$\/} is recursive.  Such profiles are called {\em 
measurable\/} (with respect to the Boolean algebra~REC of recursive 
coalitions).  Measurable profiles are understood to be the ones for which 
the social planner will be required to give a social preference.

\medskip

{\it Remark}.  The measurability condition might appear unreasonable since 
it implies that the preferences of different individuals are correlated in 
some way.  To defend the condition, I give two interpretations.  The first 
is given by the uncertainty example in the Introduction, where there are 
only finitely many people facing denumerably many states.  In this case, 
the measurability condition simply reflects the reasonable epistemological 
requirement that each person can identify the set of states in which he 
prefers an alternative to another alternative.  The second interpretation 
is when a society is made up of infinitely many people extending into the 
indefinite future.  In this case, it is reasonable to suppose that we are 
dealing with imagined preferences rather than actual preferences.  The 
measurability condition reflects the reasonable requirement that what is 
imagined should be describable.\enspace$\diamondsuit$

 
% FDA example 

\medskip {\it Example}.  Suppose that the Administration of Food, Drug, 
Cosmetics, and Medical Devices (FDCA) is to adopt a usage policy for a 
newly developed medicine.  The FDCA consults some selected set of people, 
or ``experts'' about their preferences among alternatives policies such as 
``prescription only'' or ``experimental use only on nonhumans.'' These 
policies form the set~$X$ of alternatives.  The experts are not comfortable 
with giving definite answers since the medicine is new and so there are 
uncertainties that cannot be resolved by the time a policy has to be 
adopted.  So, the FDCA decides to specify conditions on which experts may 
base their opinions.  These conditions constitute the set of states of the 
world that may involve with, for example, (i)~the potential benefits~$s_1$ 
of research for the next dozen years in case only experimental use is 
allowed or (ii)~the cost~$s_2$ in terms of human lives for the next decade 
in case a unrestrictive policy is adopted.  Each state~$s$ specifies a 
value to these variables $s_1$ and~$s_2$, among others.  It is natural to 
assume that the set~$S$ of states is denumerable.  The discussion of 
finitely many people facing uncertainty (Section~\ref{IntroOverview1}) 
applies to this example.\enspace$\diamondsuit$

%%%
\subsection{Computability}

Proposition~\ref{arm3.1} in Appendix~\ref{proofs} implies that if the 
set~$I$ of individuals is $\N$ and a social planner only observes 
measurable profiles (with respect to~REC, the Boolean algebra of recursive 
coalitions), then a social welfare function (not necessarily computable) 
exists that satisfies Arrow's conditions.  In this section, I introduce a 
modest condition for computability of social welfare functions and consider 
whether there is a {\em computable\/} \swf\ satisfying Arrow's axioms.


\subsubsection{Naming Restricted Profiles}\label{main:name.coal}

My notion of computability will be weak in the sense that they are only 
local requirements: they are concerned about how to obtain, for each 
pair~\pairxy, the social preference on~\pairxy\ from a description of a 
profile restricted to the set~$\{x,y\}$.  For this purpose, I describe the 
restriction~$(\pref\cap\{x,y\}^2)_{i\in\N}$ of a measurable profile~$\p\in 
\P_{\rm REC}^\N$ to a set~$\{x,y\}$ by a natural number~$e$ (as in 
Section~\ref{thms.comp}).  When this is done, I say that $e$ {\em 
represents\/} $\p$ {\em at\/}~\pairxy.  A natural number~$e$ is {\em 
illegitimate\/} if $e$ does not represent any measurable profile at 
(any)~\pairxy; $e$ is {\em legitimate\/} otherwise.  (If $e$ represents a 
profile at~\pairxy, then it represents all the profiles (at~\pairxy) whose 
restriction to the set~$\{x,y\}$ is identical.  In this sense, each natural 
number represents at most one restricted profile.)


\subsubsection{The Notion of Computability} 
\label{two.notn}

I only consider \swf s~$\succ$ satisfying Independence (so that social 
preference on a pair $\{x,y\}$ is determined by the profile restricted to 
the pair).

I say that a \swf~$\succ$ satisfies {\em Pairwise Computability\/} (PC) if 
for each pair~\pairxy, there exists an algorithm that can decide, for each 
measurable profile~$\p$ and for each legitimate representation~$e$ of the 
profile at~\pairxy, whether the society prefers $x$ to~$y$ according to 
$\succ^\p$, from the representation~$e$.  (If such an algorithm can be 
chosen so that it works uniformly for all~\pairxy, then I say that the 
\swf\ satisfies Strong Pairwise Computability~\cite{mihara.thesis}.) Note 
that the computability condition implies that the value given by a deciding 
algorithm must be invariant over different~$e$ that represent the same 
profile at~\pairxy.  Also, note that PC does not require that a single 
algorithm work for all pairs.

The main result, Theorem~\ref{main.theorem1}, states that if a \swf\ 
satisfying Unanimity and Independence also satisfies PC, then it must be 
dictatorial.\footnote{The PC here should not be confused with ``Political 
Correctness.''} The Introduction interprets this result as strengthening 
both Arrow's Theorem and Hayek's thesis.

On the other hand, Proposition~\ref{main2} shows that while there are some 
dictatorial \swf s that satisfy PC, not all do.  {\em Precisely 
dictatorial\/} \swf s (where social preference is always identical with the 
dictator's preference) are examples that do satisfy (Strong) PC\@.

%%%%%%%%%%%%%%%%%%
\renewcommand{\profile}{(\pref)_{i\in I}}  %redefined later 
\renewcommand{\Pbi}{\P_\B^I}                %redefined later
\renewcommand{\Preci}{\P_{\rm REC}^I}      %redefined later
\renewcommand{\xprefy}{\{\,i\in I:{x\pref y}\,\}}   %redefined later
%%%%%%%%%%%%%%%%%%


\section{Theorem} \label{theorems}
\subsection{Framework}\label{formulation}

$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, let {REC} consist of all recursive subsets of 
$\N$. Then {REC} forms a Boolean algebra. 

A {\em profile\/} is a list $\p=\profile\in\P^I$ of {\em individual 
preferences\/} $\pref$, $i\in I$.  A weak preference $\succeq_i^\p$ is the 
negation of $\prec_i^\p$ (defined from $\pref$ in the 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 
the obvious manner.

I 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}. 


%ddddddddddddddddddddddddddddddddddddddddddddddddddd
\renewcommand{\profile}{(\pref)_{i\in \N}}
\renewcommand{\Pbi}{\P_\B^\N}
\renewcommand{\Preci}{\P_{\rm REC}^\N}
\renewcommand{\xprefy}{\{\,i:x\pref y\,\}}
%ddddddddddddddddddddddddddddddddddddddddddddddddddd

\subsection{Computability}\label{thms.comp}

I will define computability for \swf s using Turing computability.  {\em 
Turing computability\/} is (one of several equivalents of) the generally 
accepted formalization of the intuitive notion of algorithmic 
computability.  Informally, an algorithm is a finite list of instructions 
that, given a symbolic input, yields after a finite number of steps a 
symbolic output.  According to this intuition, a computation by an 
algorithm is exact, deterministic and performed in a discrete manner; 
inputs and outputs are finitely describable (equivalently, {\em describable 
by natural numbers\/}); and so on~\cite[pp.~1--5]{rogers87}.  Turing 
computability meets all these intuitive requirements.

The basic idea of a \swf\ is that it maps each profile~$\p$ to a social 
preference~$\succ^\p$.  So, when one accepts Turing computability, the 
first approach that one might attempt in introducing a condition of 
computability for \swf s is to represent profiles~$\p$ and social 
preferences by integers, and then, to define computability in terms of 
these integers.  This approach is unsatisfactory in general (for example, 
it is problematic even when I restrict attention to REC-\swf s) unless $X$ 
is finite.  The reason is that when $X$ is infinite, the domain of a \swf\ 
is not necessarily countable (e.g., $\Preci$ is 
uncountable~\cite{mihara.thesis}), while only countably many profiles~$\p$ 
can be represented by a natural number.  This implies a possibility that 
any algorithm used for obtaining social preferences fails to compute an 
output for ``almost all'' profiles in the domain.  One way out of this 
problem would be to consider only countable domains for social welfare 
functions.

However, there is a different solution, which does not require countable 
domains.  To describe the solution, I henceforth let the set~$I$ of 
individuals be the set~{\bf N} of nonnegative integers and I let the 
Boolean algebra~$\B$ of coalitions be REC, the Boolean algebra of recursive 
sets.  (So, I am considering only REC-\swf s~$\succ\colon\Preci\to\P$.)

A key assumption that I make for my solution is the Independence axiom: I 
suppose that $\succ$ is an REC-\swf\ satisfying Independence.  
Corresponding to each profile~$\p$ is the social preference~$\succ^\p$, 
which determines for each pair~\pairxy\ of alternatives, whether $x\succ^\p 
y$ or not.  By Independence, all that is needed to determine that, is the 
restriction of profile~$\p$ to~$\{x,y\}$.  The Definition below introduces 
a method of representing such restricted profiles by a natural number~$e$.  
Such representation (by integers) enables me to apply the notion of Turing 
computability.  The notion of computability for \swf s will be introduced 
afterward.

\medskip

{\em Remark}.  Restricting my attention to REC-\swf s satisfying 
Independence is reasonable since my main purpose is to determine whether 
there is a nondictatorial \swf\ among those satisfying Unanimity and 
Independence.  Furthermore, the Independence axiom can be regarded as a 
part of the computability condition.  After all, Independence is a 
stringent form of an informational viability condition, which requires 
finiteness in some aspects of information to be 
processed.\enspace$\diamondsuit$

\medskip

A {\em characteristic index\/} for a recursive set~$A$ is the G\"{o}del 
number (name) of an algorithm computing the characteristic function 
for~$A$.  When a characteristic index for~$A$ is known, one can effectively 
recover the algorithm from the index; using this algorithm, one can decide, 
for any number~$e_1\in\N$, whether $e_1$ is in~$A$.  Recall from 
Appendix~\ref{RecTh} that $e=\evecim$ is the coding (by integer) of a 
triple $(e_1,e_2,e_3)$ of integers.

To describe the restriction of a measurable profile~$\p$ on a 
pair~$\{x,y\}$, I first describe each of $\xprefy$, $\{\,i: y\pref x\,\}$, 
and~$\{\,i: x\sim_i^\p y\,\}$ by its characteristic index and then 
aggregate the three indices using the above coding for triples. 
Formally, I have the following definition:

 \begin{description}
\item[Definition] $e=\evecim\in \N$ {\em represents\/} a profile 
$\p=\profile\in\Preci$ {\em at\/} a pair $(x,y)\in X\times X$ if $e_1$, 
$e_2$, and~$e_3$ are characteristic indices for $\xprefy$, $\{\,i: y\pref 
x\,\}$, and~$\{\,i: x\sim_i^\p y\,\}$ respectively.
\end{description}
\noindent
If $e$ represents $\p\in \Preci$ at $(x,y)$, then $e$ describes the 
restricted profile \mbox{$(\pref\cap\{x,y\}^2)_{i\in\N}$} of~$\p$ on 
$\{x,y\}$ completely (in the sense that one and only one restricted profile 
corresponds to $e$).  Note that I need at least two of the three 
characteristic indices above to describe the restricted profile completely.

The following definition of computability requires that the process of 
determining whether $x\succ^\p y$ holds, be an algorithmic process; it uses 
as input a representation~$e$ of the restricted profile.  Pairwise 
Computability allows different algorithms to be used for different 
pairs~\pairxy.  (In contrast, Strong Pairwise 
Computability~\cite{mihara.thesis} requires a single algorithm to work for 
all pairs.)

\begin{description}
\item[Pairwise Computability (PC)] For each pair $\pairxy\in X^2$, there 
is a partial recursive function~$\gamma$ such that \\ 
(a)~for each profile~$\p\in\Preci$ and for each integer~$e\in\N$, if $e$ 
represents $\p$ at~\pairxy, then 
  \begin{itemize}
	\item[]
	\mbox{$x \succ^\p y \Longrightarrow \gamma(e)=1$, and}
	\item[] $\neg x \succ^\p y \Longrightarrow \gamma(e)=0$.
  \end{itemize}
\end{description}

Obviously, ``$\Longrightarrow$'' in~(a) above can be replaced by 
``$\iff$.'' But notice that $e$ is restricted to those representing some 
$\p\in\Preci$ at~\pairxy. 

\medskip

{\em Remark}. In order to appreciate the above notion, it is instructive 
to consider several other notions of computability. I give two alternative 
notions of computability in 
Appendix~\ref{alternatives}.\enspace$\diamondsuit$ 

\medskip

I now give the main theorem, whose proof appears in Appendix~\ref{proofs}.  
It re-establishes Arrow's negative result even for denumerable societies.

\begin{thm}\label{main.theorem1}
Let $\succ\colon\Preci\to \P$ be an {{\rm REC}}-social welfare function  
satisfying Unanimity and Independence. Then~$\succ$ is dictatorial if it 
satisfies Pairwise Computability.
\end{thm}

While Theorem~\ref{main.theorem1} asserts necessity of dictatorship for 
computability, the next proposition shows that it is not sufficient.

\begin{prop}\label{main2}
Among the {\rm REC}-\swf s satisfying Unanimity and Independence, there are 
{\rm (i)}~a dictatorial function satisfying Pairwise Computability, and 
{\rm (ii)}~a dictatorial function not satisfying Pairwise Computability.
\end{prop}

{\em Proof}.  Items (i) and (ii) are proved by Examples 1, 
2 respectively.  Details are in Appendix~\ref{proofs}.\qed

\medskip

{\em Example~1}.  Let \[ \U_0=\{\,A\in {\rm REC}: 0\in A\,\} \] and 
define by Proposition~\ref{arm3.1} the \swf\ $\succ\colon\Preci\to\P$ for 
$\p\in\Preci$, and for $x$,~$y\in X$ by 
\[
x\succ^\p y \iff \xprefy\in\U_0.
\]
That is, the individual~0 is the ``precise dictator.''  
Proposition~\ref{arm3.1} establishes that $\succ$ satisfies Unanimity and 
Independence.  Appendix~\ref{proofs} shows that $\succ$ satisfies (Strong) 
Pairwise Computability.\enspace$\diamondsuit$ 

\medskip

{\em Example~2}.  Let $\U_0$ be as in Example~1 and let $\hat{\U}$ be an 
arbitrary {\em free ultrafilter\/} (Appendix~\ref{proofs}) on~REC\@.  
Define a map $\succ$ from $\p\in\Preci$ into a binary relation $\succ^\p$ 
on $X$ as follows: for $\p\in\Preci$, and for $x$,~$y\in X$,
\[
\begin{array}{lcl}
	x\succ^\p y & \mbox{iff} & \mbox{(a) $\xprefy\in\U_0$ or}  \\
&  & \mbox{(b) $\{\,i:x\sim^\p_i y\,\}\in\U_0\ \&\  \xprefy\in\hat\U$.}
\end{array}
\]
It can be shown~\cite{armstrong85,mihara94a} that $\succ$ is a dictatorial 
REC-\swf\ satisfying Unanimity and Independence.  
The proof that $\succ$ does not satisfy Pairwise Computability appears in 
Appendix~\ref{proofs}.\enspace$\diamondsuit$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%% Appendices %%%%%%%%%%%%%%%%%

\appendix
%the following section done.

\section{Strengthening Pairwise Computability}\label{strengthen.PC}
\label{alternatives}
%% Was: alternative notins of computability


A minor problem with the definition of Pairwise Computability occurs when 
an input number~$e$ for a deciding algorithm (for a partial recursive 
function~$\gamma$ in (a) in PC) for a \swf\ is illegitimate, so that it 
does not represent any measurable profile at the pair.  In this case, 
application of the algorithm might give a social preference on~$(x,y)$ 
improperly.  This problem is minor since I can safely think of a scenario 
in which a planner only processes inputs whose legitimacy she can prove.  
While there is no algorithmic procedure to give a proof of legitimacy for 
{\em every\/} input, there is no inconsistency in assuming that only 
numbers for which legitimacy can be proved are input to the \swf.

Having said that, let me consider some ways of avoiding obtaining social 
preferences for illegitimate inputs, for a planner might incorrectly 
believe that her input is legitimate.  Computability~A below requires 
illegitimate inputs to be indicated by a certain output; Computability~B 
requires that outputs are given {\em only\/} for legitimate inputs.  Though 
these notions may be appealing on intuitive grounds, they are both stronger 
than Pairwise Computability, and therefore, the main 
Theorem~\ref{main.theorem1} applies {\it a fortiori}.  However, I show here 
that {\em no\/} social welfare function satisfying Independence meets 
either of these computability conditions.  These impossibility results 
further justify the use of PC (or Strong PC) as a notion of computability.

Suppose in the following that $\succ\colon \Preci\to\P$ is an REC-\swf\ 
satisfying Independence. 

\medskip

1.  In the definition of Pairwise Computability, it is required that an 
algorithm exist that can decide the restricted social preference given a 
representation~$e$ of a profile at a pair of alternatives.  However, there 
is no requirement as to what the algorithm should do for an integer 
$e\in\N$ that is illegitimate (i.e., that does not represent any 
REC-measurable profile at the pair).  It would be desirable if the 
algorithm could decide for each integer $e$ whether $e$ is legitimate or 
not, in addition to deciding the restricted social preference.  This leads 
to the following definition:

\begin{description}
  \item[Computability~A]  For each pair $\pairxy\in X^2$, 
   there is a  recursive function~$\gamma$ such that the condition~(a) in 
   Pairwise Computability is satisfied, and \\
   (b)~for each integer~$e\in\N$, if $e$ does not represent 
		any~$\p\in\Preci$ at~\pairxy, then $\gamma(e)=2$.
\end{description}

Unfortunately, Computability~A cannot be met by any REC-\swf\ that 
satisfies Independence. To see why, fix $(x,y)$ and suppose a recursive 
$\gamma$ satisfies (a) and~(b). Then it must be that 
$S=\{\,e:\mbox{$\gamma(e)=1$ or~0}\,\}$ is r.e.\ (in fact, recursive). This 
is because $S$ is the domain of the partial recursive function $\gamma'$ 
which is defined by $\gamma'(e)=\gamma(e)$ iff $\gamma(e)=1$ or~0, and 
$\gamma'(e)\uparrow$ iff $\gamma(e)=2$. (That $\gamma'$ becomes partial 
recursive is straightforward from the Graph Theorem.) However, 
Lemma~\ref{nonre.dom} in Appendix~\ref{proofs} shows that 
$S=\{\,e:\mbox{$e$ represents some~$\p\in\Preci$ at~\pairxy} \,\}$ is not 
r.e. 

\medskip

2. One of the most obvious conditions of computability that one might 
think of is the following.  It requires existence of a deciding 
algorithm (for the restricted social preferences) that gives an output 
only for legitimate representations of a profile at a pair.
\begin{description}
  \item[Computability~B]  For each pair $\pairxy\in X^2$, 
   there is a  partial recursive function~$\gamma$ 
   such that the condition~(a) in 
   Pairwise Computability is satisfied, and \\
   	(c)~for each integer~$e\in\N$, if $e$ does not represent 
		any~$\p\in\Preci$ at~\pairxy, then $\gamma(e)\uparrow$.
\end{description}

The same argument (that $S$ is not r.e.) shows that no REC-\swf\ that 
satisfies Independence can satisfy Computability~B. 


\section{Recursion Theory}\label{RecTh} 

This appendix reviews the definitions and results from recursion theory 
necessary for understanding technical sections of the present paper. I 
mostly follow the notations and terminologies in Soare~\cite{soare87}. 
Other references on recursion theory include Rogers~\cite{rogers87} and 
Davis and Weyuker~\cite{davis-weyuker83}. 

In this appendix, $x$, $y$ and~$z$ denote nonnegative integers. For sets 
$A$ and~$B$, $\overline{A}$ denotes the complement of $A$; $A-B$ denotes 
the set theoretic difference $A\cap\overline{B}$. 

\subsection{Partial Functions}

A {\em partial function\/} on $\N^n$, where $n\geq 1$ is an integer,
is a function (into natural numbers) whose domain is a subset of 
$\N^n$.  If the domain of a partial function on $\N^n$ is $\N^n$, then 
it is called {\em total}.  For partial functions $\phi$ and~$\theta$, 
$\phi(x)\downarrow$ denotes that $\phi(x)$ is defined; $\phi(x)\uparrow$ 
denotes that $\phi(x)$ is undefined; $\phi=\theta$ denotes that for all 
$x$, $\phi(x)\downarrow$ iff $\theta(x)\downarrow$, and if 
$\phi(x)\downarrow$ then $\phi(x)=\theta(x)$; ${\rm dom}\,\phi$ denotes 
the domain of $\phi$.

\subsection{Algorithms}

Informally, an {\em algorithm\/} (for a partial function $\phi$ on $\N$) is 
a finite list of instructions that, given an input $x$, yields an output 
$y=\phi(x)$ after a finite number of steps if $\phi(x)$ is defined. (It 
should not yield an output if $\phi(x)$ is undefined.) The algorithm must 
specify how to obtain each step in the computation from the previous steps 
and from the input. Informally, if a partial function is computed by an 
algorithm, it is called {\em partial recursive}. 

We accept {\em Church's Thesis\/} which identifies the informal class of 
algorithmically computable partial functions with the class of partial 
functions computed by a Turing program. {\em Turing programs\/} can be 
defined precisely, but we do not do that here. For our purpose, it suffices 
to know that we can list all Turing programs in such a way that for any 
program we can algorithmically find its place (the code number) in the list 
and conversely. We choose one such algorithmic listing (or coding or {\em 
G\"{o}del numbering}) and fix it. 

\subsection{Computability Theory}

Code (G\"odel number) all Turing programs. For $e\in\bf N$, let 
$\varphi_e^{(n)}$ be the partial function of $n$ variables computed by the 
$e$th Turing program. A partial function $\phi$ of $n$ variables is {\em 
partial recursive\/} if $\phi=\varphi_e^{(n)}$ for some $e$. A partial recursive 
function is {\em recursive\/} if it is total. Write $\varphi_e$ for 
$\varphi_e^{(1)}$. 

A set $A\subseteq \N$ is {\em recursive\/} ($A\in\mbox{REC}$) if the 
characteristic function for $A$ is recursive.  $e$ is a {\em characteristic 
index\/} for $A$ if $\varphi_e$ is the characteristic function for~$A$.  
(The characteristic function for~$A$ takes the value 1 iff an input belongs 
to~$A$; it takes 0 otherwise.)

Let $W_e={\rm dom}\,\varphi_e=\{\,x:\varphi_e(x)\downarrow\,\}$. A set 
$A\subseteq \bf N$ is {\em recursively enumerable\/} (r.e.) if $A=W_e$ for 
some $e$. $W_e$ is the $e$th r.e.\ set. 

The {\bf Enumeration Theorem} states \cite[p.~15]{soare87} that there is a 
partial recursive function~$\varphi_z^{(2)}$ of two variables such that 
$\varphi_z^{(2)}(e,x)=\varphi_e(x)$ for all $e$ and~$x$.

The {\bf Parameter Theorem} ($s$-$m$-$n$ {\bf Theorem}) states 
\cite[p.~16]{soare87} that for every $m$, $n\geq 1$, there exists a 
one-to-one recursive function $s_n^m$ of $m+1$ variables such that for all 
$x$, $y_1$, \ldots ,~$y_m$, 
$$\varphi^{(n)}_{s_n^m(x,y_1, \ldots , 
y_m)}(z_1, \ldots ,z_n)= \varphi_x^{(m+n)}(y_1, \ldots ,y_m,z_1, \ldots 
,z_n)$$
 for any $z_1$, \ldots ,~$z_n$.

The {\bf Graph Theorem} states \cite[p.~29]{soare87} that a partial function 
is partial recursive iff its graph is r.e.

We let $\langle x,y\rangle$ denote the image of $(x,y)$ under the standard 
pairing function $(x^2+2xy+y^2+3x+y)/2$, which is a one-to-one recursive 
function from $\N\times \N$ onto~$\N$. Let $\langle x,y,z\rangle$ denote 
$\langle\langle x, y\rangle, z\rangle$. 

%We write $\varphi_{e,s}(x)=y$ if $x<s$, $y<s$, $e<s$ and $y$ is the output 
%of $\varphi_e(x)$ in $<s$ steps of the $e$th Turing program, if such a $y$ 
%exists. 

%%%%%%%%%%%%%%%%%%

\subsection{Lemmas}

The following two lemmas will be used in the proofs of Theorem~1 and of 
Proposition~\ref{main2}.

\begin{lemma}\label{reverse}
There is a one-to-one recursive function $r$ such that for all $e$ and~$u$,

\begin{equation}
	\varphi_{r(e)}(u)=\left\{
	\begin{array}{ll}
		1 & \mbox{\rm if $\varphi_e(u)=0$,}  \\
		0 & \mbox{\rm if $\varphi_e(u)\downarrow$ and 
		$ \varphi_e(u)\neq 0$,}\\
		\uparrow &  \mbox{\rm if $\varphi_e(u)\uparrow$.}
	\end{array}
	\right.
	\label{reverseeq}
\end{equation}
In particular, if $e$ is a characteristic index for a set~$A$, then $r(e)$ 
is a characteristic index for its complement~$\overline{A}$.
\end{lemma}

{\em Proof}.  The right hand side is equal to $\psi(e,u)=1- \varphi_e(u)$, 
where $-$ is the limited subtraction.  Since the limited subtraction is 
recursive, $\psi$ is partial recursive by the Enumeration Theorem.  Then by 
the Parameter Theorem, there is a one-to-one recursive function $r$ such 
such that $\varphi_{r(e)}(u)=\psi(e,u)$.

{\em Details}.  Since $\psi$ is partial recursive, $\psi=\varphi_z^{(2)}$ 
for some $z$.  By the Parameter Theorem, there is a one-to-one recursive 
function~$s$ such that \[ \varphi_{s(z,e)}(u)=\varphi_z^{(2)} 
(e,u)=\psi(e,u).\] Let $r(e)=s(z,e)$.  Then $r$ is one-to-one and 
recursive.\enspace$\diamondsuit\qed$


\begin{lemma}\label{CRec}
Let \[ {\rm CRec}=\{\,e\in\N: \mbox{\rm $e$ is a characteristic index for a 
recursive set}\,\}.\]
Then {\rm CRec} is not r.e.
\end{lemma}

{\em Proof}.  (This proof involves deeper recursion theory than that 
covered in Appendix~\ref{RecTh}.)  Fix a $\Sigma_2$ set~$A$.  
Then, by \cite[IV.3.2, p.~66]{soare87}, there is a recursive function~$f$ 
such that
\[ e\in A\Longrightarrow \varphi_{f(e)}(u)\downarrow\mbox{\ for only 
finitely many $u$} \]
and
\[ e\notin A\Longrightarrow \mbox{$\varphi_{f(e)}(u)=0$ for all $u$.}\]
It follows that
\[ e\in A\Longrightarrow f(e)\notin {\rm CRec} \]
and 
\[ e\notin A\Longrightarrow f(e)\in {\rm CRec}.\]
This shows that $\overline{A}\leq_m {\rm CRec}$, namely, $\overline{A}$ is 
many-one reducible to~CRec.

Now, suppose that CRec is r.e., that is, ${\rm CRec}\in\Sigma_1$. Then by 
\cite[IV.1.3(v), p.~61]{soare87}, $\overline{A}\in\Sigma_1$, i.e., $A\in 
\Pi_1$. This means that any $\Sigma_2$ set $A$ is $\Pi_1$, a contradiction. 
Hence, CRec is not r.e.$\qed$ 

%%%%%%%%%%%%%

\section{Proofs}\label{proofs}

In this Appendix, we prove Theorem~\ref{main.theorem1} and 
Proposition~\ref{main2} in Section~\ref{theorems}.

The following Lemma is used in Appendix~\ref{strengthen.PC} and in the 
proof of Theorem~\ref{main.theorem1}.

\begin{lemma}\label{nonre.dom}
	Let $\pairxy\in X^2$.  Then the set 
	\[ S=\{\,e: \mbox{\rm $e$ represents some 
	$\p\in\Preci$ at~\pairxy}\,\}\]
    is not r.e.
\end{lemma}

{\em Proof}. Fix $\succ$ and \pairxy. Suppose that $S$ is r.e. Let $e_3'$ 
be an arbitrary characteristic index for an empty set. Let $r$ be a 
recursive function satisfying~(\ref{reverseeq}) in Lemma~\ref{reverse}. Let 
CRec be the set of characteristic indices for some recursive set. 

{\bf Claim}  $\langle e_1, r(e_1), e'_3\rangle\in S$ iff $e_1\in{\rm 
CRec}$.

{\em Details}.  ($\Longrightarrow$).  Suppose that $\langle e_1, r(e_1), 
e'_3\rangle\in S$.  Then $e_1$ is a characteristic index for $\xprefy$.

($\Longleftarrow$).  Suppose that $e_1$ is a characteristic index for an 
$A\subseteq \N$.  Choose a $\p\in\Preci$ such that $A=\xprefy$ and 
$\overline{A}=\{\,i:y\pref x\,\}$.  Then $r(e_1)$ is a characteristic index 
for $\overline{A}$ by Lemma~\ref{reverse}.  So, $e_1$, $r(e_1)$, and~$e_3'$ 
are characteristic indices for $\xprefy$, $\{\,i:y\pref x\,\}$, and 
$\{\,i:x\sim_i^\p y\,\}=\emptyset$ respectively.\enspace$\diamondsuit$

\medskip

Now since $S$ is assumed to be r.e., Claim implies that CRec is r.e.

{\em Details}.  The function $f$ defined by $f(e_1)=\langle e_1, r(e_1), 
e'_3\rangle$ is recursive.  Since $S$ is r.e., it is the domain of the 
partial recursive function~$\varphi_z$ for some $z$.  We have, by the 
above Claim, that $e_1\in{\rm CRec}$ iff $f(e_1)\in{\rm dom}\varphi_z$.  
But the latter is equivalent with $e_1\in {\rm dom}(\varphi_z\circ f)$.  
This means that CRec is the domain of $\varphi_z\circ f$; hence,
r.e.\enspace$\diamondsuit$

\medskip

However, this contradicts Lemma~\ref{CRec} which states that CRec is not 
r.e.$\qed$

\medskip

Before proving Theorem~\ref{main.theorem1} and Proposition~\ref{main2}, we 
must introduce some preliminary results and notions.

Let $\B$ be a Boolean algebra.  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$.  If $\U$ is an ultrafilter, then 
$A\cup B\in\U$ implies that $A\in\U$ or $B\in\U$.  Suppose $\B$ contains 
all finite sets of $I$.  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.


%ddddddddddddddddddddddddddddddddddddddddddddddddddd
\renewcommand{\profile}{\mbox{$(\pref)_{i\in I}$}}  %redefined later 
\renewcommand{\Pbi}{\P_\B^I}                %redefined later
\renewcommand{\Preci}{\P_{\rm REC}^I}      %redefined later
\renewcommand{\xprefy}{\{\,i\in I:{x\pref y}\,\}}   %redefined later
%ddddddddddddddddddddddddddddddddddddddddddddddddddd

%%\subsection{Propositions}\label{dom.res:prop}

\begin{prop}[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{prop} 

{\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}. 
Proposition~\ref{arm3.2a} is the corrected version.\enspace$\diamondsuit$ 

\begin{prop}[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  $$x\succ^{\p}
y\iff\xprefy\in \U$$  is a $\B$-social welfare function, satisfying
Unanimity and Independence.
\end{prop}

%ddddddddddddddddddddddddddddddddddddddddddddddddddd
\renewcommand{\profile}{(\pref)_{i\in \N}}
\renewcommand{\Pbi}{\P_\B^\N}
\renewcommand{\Preci}{\P_{\rm REC}^\N}
\renewcommand{\xprefy}{\{\,i\in {\bf N}:x\pref y\,\}}
%ddddddddddddddddddddddddddddddddddddddddddddddddddd


Let $\succ\colon\Preci\to \P$ be an {REC}-social welfare function {\em 
satisfying Unanimity and Independence}. Given $\succ$, let $\beta_\succ$ be 
the partial function on~$\N$ defined by
\begin{equation}
	\label{beta:eq}
	\beta_\succ(e_1)=\left\{
	    \begin{array}{ll}
		1 & \mbox{if $e_1$ is a characteristic index for a recursive
	set in $\U_\succ$,}  \\
		0 & \mbox{if $e_1$ is a characteristic index for a recursive
	set not in $\U_\succ$,}  \\
		\uparrow & \mbox{if $e_1$ is not a characteristic
	index for a recursive set,}
	\end{array}
	\right.
\end{equation}
where $\Us$ denotes the ultrafilter in Proposition~\ref{arm3.2a}. Note that 
$\beta_\succ$ is well-defined since each $e_1\in\N$ can be a characteristic 
index for at most one set. 

We define a computability condition for an {REC}-\swf\ satisfying Unanimity and 
Independence using the partial function $\beta_\succ$ defined 
by (\ref{beta:eq}):
\begin{description}
	\item[Decidability of Decisive Coalitions (DDC)] 
	 $\beta_\succ$ has an extension to a partial recursive function.
\end{description}


\begin{lemma}\label{mainA}
	Let $\succ\colon\Preci\to\P$ be an 
	{\rm REC}-social
	welfare function satisfying Unanimity and Independence.  Then $\succ$ 
	is dictatorial if and only if it satisfies DDC\@.  
\end{lemma}
	
{\em Proof}.  
($\Longrightarrow$).  Suppose $\succ$ is dictatorial.  Then
the ultrafilter $\Us$ in Proposition~\ref{arm3.2a} corresponding to
$\succ$ is principal; namely,  for some
$i_0\in\N$, 
$\Us=\{\,W\in{\rm REC}: i_0\in W\,\}.$

Define $\beta'$ by $$\beta'(e)=\cases{\varphi_e(i_0) &if $\varphi_e(i_0)=0$ 
or 1,\cr \uparrow &otherwise.\cr}$$ Then, clearly, $\beta'$ is an extension 
of $\beta_\succ$.  Also, $\varphi_e(i_0)$ is a partial recursive function 
of $e$ by the Enumeration Theorem.  Hence, $\beta'$ is partial recursive.

($\Longleftarrow$).  Let $\succ$ satisfy the hypothesis and suppose DDC is 
satisfied but $\succ$ is not dictatorial.  In this case, the ultrafilter 
$\U_\succ$ corresponding to $\succ$ is free: it does not contain any finite 
sets.  Let $\beta'$ be an extension of $\beta_\succ$ which is partial 
recursive.  Note that $\betas(e)=1$ if $e$ is a characteristic index for a 
cofinite set since $\Us$ is a free ultrafilter.

Let $K=\{\,e:e\in W_e\,\}$; $K$ is a nonrecursive r.e.\ set.  Since $K$ is 
r.e., there is \cite[II.1.2, p.~28]{soare87} a recursive set 
$R\subseteq\N\times\N$ such that $e\in K\iff \exists z R(e,z)$.  Using the 
Parameter Theorem, define a recursive function $f$ by 
$$\varphi_{f(e)}(u)=\cases{1 &if $\exists z\leq u\ R(e,z)$,\cr 0 
&otherwise.\cr}$$

{\it Details}.  The function $h$ defined by 
$$h(e,u)=\cases{1 &if $\exists z\leq u\ R(e,z)$,\cr
0 &otherwise\cr}$$
is recursive.  Hence, for some $z$, $h=\varphi_z^{(2)}$.  By the Parameter 
Theorem, there is a recursive function $s$ such that 
$$\varphi_{s(z,e)}(u)=\varphi_z^{(2)}(e,u)=h(e,u).$$ Let $f(e)=s(z,e)$.  
Then $f$ is recursive.\enspace$\diamondsuit$

Now, 
\begin{eqnarray*}
	e\in K & \Longrightarrow &  \varphi_{f(e)}(u)=1\mbox{\
                                except for finitely many $u$'s} \\
	 & \Longrightarrow & f(e) \mbox{\ is a characteristic index for a cofinite
                         set}   \\
	 & \Longrightarrow &  \beta'(f(e))=\betas(f(e))=1,
	 \end{eqnarray*}
but
\begin{eqnarray*}
	e\notin K & \Longrightarrow & \varphi_{f(e)}(u)=0 \hbox{\ for all
                                  $u$}  \\
	 & \Longrightarrow &  f(e) \hbox{\ is a characteristic 
	                       index for $\emptyset$}  \\
	 & \Longrightarrow & \beta'(f(e))=\betas(f(e))=0.
\end{eqnarray*}
This implies that $K$ is recursive, contradiction.\qed 

%%%%%%%%%%%%%%%%%%%%%%%%%% end of the proof of Lemma mainA.

\medskip

%%%%%%%%%%%% Theorem

{\em Proof of Theorem~\ref{main.theorem1}}.  (Preliminaries for this proof 
begin after the proof of Lemma~\ref{nonre.dom}.) Let $\succ$ satisfy the 
hypotheses and PC\@.  Fix~\pairxy.  There is a partial recursive~$\gamma$ 
that satisfies the condition~(a) in PC\@.  We will show that 
DDC is satisfied.

Let $e'_3$ be an arbitrary characteristic index for an empty set and 
let $r$ be a recursive function satisfying~(\ref{reverseeq}) in 
Lemma~\ref{reverse}.  Then 
\begin{equation}	\label{tokuni.nashi}
\betas(e_1)=\gamma(\langle e_1, r(e_1), e'_3 \rangle)
\end{equation}
for all $e_1\in \rm CRec$. ((\ref{tokuni.nashi}) means that when nobody is 
indifferent between $x$ and~$y$, then to determine the social preference 
on~\pairxy, all the planner need to know is the coalition~$\xprefy$ that 
prefers $x$ to~$y$.) 

{\em Details\/}. Suppose $e_1\in {\rm CRec}$, the domain of $\betas$. Then 
by the Claim in the proof of Lemma~\ref{nonre.dom}, $e=\langle e_1, r(e_1), 
e_3'\rangle$ represents some $\p \in \Preci$ at~\pairxy. In particular, 
$e_1$ and $r(e_1)$ are characteristic indices for $A=\xprefy$ and 
$\overline{A}=\{\,i:y \pref x\,\}$ respectively. 

(i)~Suppose that $\betas(e_1)=1$. Then by~(\ref{beta:eq}), $\xprefy\in\Us$. 
Then (\ref{arm3.2a:eq}) in Proposition~\ref{arm3.2a} implies that $x 
\succ^\p y$. So, (a) in PC implies that $\gamma(e)=1$. 

(ii)~Suppose $\betas(e_1)=0$. Then by~(\ref{beta:eq}), $A\notin\Us$. Since 
$\Us$ is an ultrafilter, it follows that $\overline{A}=\{\,i:y\pref 
x\,\}\in\Us$. By~(\ref{arm3.2a:eq}), $y\succ^\p x$. By asymmetry, we have 
$\neg x\succ^\p y$. Hence $\gamma(e)=0$ by (a) in PC.\enspace$\diamondsuit$ 

\medskip

Now, the partial function~$\psi$ defined by $\psi(e_1)=\gamma(\langle 
e_1,r(e_1), e'_3\rangle)$ is clearly partial recursive. 
By~(\ref{tokuni.nashi}), $ \betas(e_1)=\psi(e_1) $ for all $e_1\in{\rm 
CRec}$. Hence, the partial recursive function $\psi$ is an extension of 
$\betas$. So, DDC is satisfied. By Lemma~\ref{mainA}, it 
follows that $\succ$ is dictatorial.$\qed$ 

\medskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\em Proof of Proposition~\ref{main2}}.  (Preliminaries for this proof 
begin after the proof of Lemma~\ref{nonre.dom}.)
(i)~Let $\succ$ be the \swf\ in Example~1.  We show $\succ$ satisfies 
PC\@.  Since $\succ$ is dictatorial, Lemma~\ref{mainA} implies that 
DDC is satisfied.  So, there is a partial recursive 
function~$\beta'$ that extends~$\betas$.  Define a partial 
function~$\gamma$ by
\[  \gamma(\evecim)=\beta'(e_1). \]
Then, for any natural number~$e=\evecim$, $\gamma(e)=\beta'(\pi(e))$, where 
$\pi\colon e\mapsto e_1$.  Since $\pi$ and $\beta'$ are partial recursive, 
$\gamma$ is partial recursive.

We show that $\gamma$ satisfies (a) in PC for all~\pairxy.  Fix~\pairxy\ 
and suppose $e=\evecim$ represents a $\p$ at~\pairxy.  Then $e_1$ is a 
characteristic index for $\xprefy$ and so $\betas(e_1)\downarrow$.
\begin{itemize}
	\item  Suppose $x\succ^\p y$.  Then by the definition of $\succ$, 
	$\xprefy\in \U_0$.  This implies that 
	$\gamma(e)=\beta'(e_1)=\betas(e_1)=1$.
	\item  Similarly, if $\neg x\succ^\p y$ then $\gamma(e)=0$.  
\end{itemize}

(ii)~Let $\succ$ be the \swf\ in Example~2.  To show $\succ$ does not 
satisfy PC, suppose otherwise.  Choose~\pairxy\ arbitrarily.  Then there is 
a partial recursive $\gamma$ that satisfies (a) in PC.  Let $g$ be a 
recursive function such that if $e$ is a characteristic index for a set $A$ 
then $g(e)$ is a characteristic index for $A-\{0\}$.  Such a $g$ exists 
by~\cite[II.2.3, p.~33]{soare87}.  Let $r$ be a recursive function 
satisfying (\ref{reverseeq}) in Lemma~\ref{reverse} and let $e'_2$ be an 
arbitrary characteristic index for an empty set.  Define a partial 
recursive function $\beta'$ by
\[
\beta'(e_1)=\gamma(\langle g(e_1), e'_2, r(g(e_1)) \rangle).
\]
We show that $\beta'$ extends~$\beta_{\hat\succ}$, where 
$\hat{\succ}\colon \Preci\to\P$ is defined by 
\[
x\hat{\succ}^\p y \iff \xprefy\in\hat{\U}.
\]
Notice that $\U_{\hat{\succ}}=\hat{\U}$.
\begin{itemize}
\item Suppose $e_1$ is a characteristic index for a recursive set~$A$ in 
$\hat\U$.  Then $e=\langle g(e_1), e'_2, r(g(e_1)) \rangle$ represents a 
$\p$ at~\pairxy; in particular, $g(e_1)$ being a characteristic index for 
$\xprefy=A-\{0\}$.  Clearly, $\xprefy$ does not belong to~$\U_0$ since it 
does not contain~0.  Hence its complement $\{\,i: x\sim_i^\p y\,\}$ belongs 
to~$\U_0$.  Now, $\xprefy\in\hat\U$ since $\xprefy$ and $A$ are different 
at most by the finite set~$\{0\}$ and $A$ is in the free 
ultrafilter~$\hat\U$.  Hence, by the definition of $\succ$, it follows that 
$x\succ^\p y$.  This implies, by~(a) in PC, that $\gamma(e)=1$.  So, 
$\beta'(e_1)=1$.
\item Similarly, if $e_1$ is a characteristic index for a recursive set not 
in~$\hat\U$, then $\beta'(e_1)=0$.
\end{itemize}

We have shown that $\beta_{\hat\succ}$ has an extension~$\beta'$ that is 
partial recursive.  This means that $\hat\succ$ satisfies DDC, 
contradicting Lemma~\ref{mainA} since $\hat\succ$ is not dictatorial.\qed

%%%%%%

\begin{thebibliography}{10}

\bibitem{armstrong80}
Armstrong, T.~E.:
\newblock Arrow's {T}heorem with restricted coalition algebras.
\newblock {Journal of Mathematical Economics} 7, 55--75 (1980)

\bibitem{armstrong85}
Armstrong, T.~E.:
\newblock Precisely dictatorial social welfare functions: Erratum and addendum
  to `{Arrow's Theorem} with restricted coalition algebras'.
\newblock {Journal of Mathematical Economics} 14, 57--59 (1985)

\bibitem{arrow63}
Arrow, K.~J.:
\newblock {Social choice and individual values, 2nd edition}.
\newblock  New Haven: Yale University Press 1963

\bibitem{arrow86}
Arrow, K.~J.:
\newblock Rationality of self and others in an economic system.
\newblock {Journal of Business} 59, S385--S399 (1986)

\bibitem{canning92}
Canning, D.:
\newblock Rationality, computability, and {Nash} equilibrium.
\newblock {Econometrica} 60, 877--888 (1992)

\bibitem{davis-weyuker83}
Davis, M.~D., Weyuker, E.~J.:
\newblock {Computability, complexity, and languages: fundamentals of
  theoretical computer science}.
\newblock Computer Science and Applied Mathematics. San Diego: Academic 
Press 1983

\bibitem{fishburn70}
Fishburn, P.~C.:
\newblock Arrow's impossibility theorem: concise proof and infinite voters.
\newblock {Journal of Economic Theory} 2, 103--6 (1970)

\bibitem{hausman-mcpherson93} 
Hausman, D.~M., McPherson, M.~S.:
\newblock Taking ethics seriously: economics and contemporary moral philosophy.
\newblock {Journal of Economic Literature} 31, 671--731 (1993)

\bibitem{hayek45}
Hayek, F.~A.:
\newblock The use of knowledge in society.
\newblock {American Economic Review} 35, 519--30 (1945)

\bibitem{kelly88}
Kelly, J.~S.:
\newblock Social choice and computational complexity.
\newblock {Journal of Mathematical Economics} 17, 1--8 (1988)

\bibitem{kirman-sondermann72}
Kirman, A.~P., Sondermann, D.:
\newblock Arrow's {Theorem}, many agents, and invisible dictators.
\newblock {Journal of Economic Theory} 5, 267--277 (1972)

\bibitem{lavoie85r}
Lavoie, D.:
\newblock {Rivalry and central planning: the socialist calculation debate
  reconsidered}.
\newblock Historical Perspectives on Modern Economics. Cambridge: 
Cambridge University Press 1985

\bibitem{lewis85}
Lewis, A.~A.:
\newblock On effectively computable realizations of choice functions.
\newblock {Mathematical Social Sciences} 10, 43--80 (1985)

\bibitem{lewis88}
Lewis, A.~A.:
\newblock An infinite version of {Arrow's} {Theorem} in the effective setting.
\newblock {Mathematical Social Sciences} 16, 41--48 (1988)

\bibitem{mihara.thesis}
Mihara, H.~R.:
\newblock {Arrow's {T}heorem, {T}uring computability, and oracles}.
\newblock PhD Thesis, Minneapolis: University of Minnesota 1995

\bibitem{mihara94a}
Mihara, H.~R.:
\newblock Anonymity and neutrality in {A}rrow's {T}heorem with restricted
  coalition algebras.
\newblock Mimeo, 1996.  To appear in {Social Choice and Welfare}.  
Available as ewp-pe/9411001 from the Economics WPA

\bibitem{mihara96a}
Mihara, H.~R.:
\newblock Existence of a coalitionally strategyproof social choice function: 
a constructive proof.
\newblock Working Paper~15, Institute of Economic Research, Kagawa University,
 April 1996.
\newblock A version available as ewp-pe/9604002 from the Economics WPA

\bibitem{rogers87}
Rogers, H., Jr.:
\newblock {Theory of recursive functions and effective computability}, 
paperback edition.
\newblock Cambridge: MIT Press 1987

\bibitem{sen86}
Sen, A.~K.: 
\newblock Social choice theory.
\newblock In Arrow, K.~J., Intriligator, M.~D., editors, {Handbook of
  mathematical economics}, volume III, chapter~22, pages 1073--1181,  
  Amsterdam: Elsevier 1986

\bibitem{soare87}
Soare, R.~I.:
\newblock {Recursively enumerable sets and degrees: a study of computable
  functions and computably generated sets}.
\newblock Berlin: Springer-Verlag 1987

\bibitem{spear89}
Spear, S.~E.: 
\newblock Learning rational expectations under computability constraints.
\newblock {Econometrica} 57, 889--910 (1989)

\bibitem{wong_kc94}
Wong, K.:
\newblock {Economic equilibrium theory: a computability viewpoint}.
\newblock PhD Thesis, Minneapolis: University of Minnesota 1994

\end{thebibliography}

\end{document}             % End of document.