A note on Murakami’s theorems and incomplete social choice without the Pareto principle

Abstract

In Arrovian social choice theory assuming the independence of irrelevant alternatives, Murakami (Logic and social choice, Dover Publications, New York, 1968) proved two theorems about complete and transitive collective choice rules satisfying strict non-imposition (citizens’ sovereignty), one being a dichotomy theorem about Paretian or anti-Paretian rules and the other a dictator-or-inverse-dictator impossibility theorem without the Pareto principle. It has been claimed in the later literature that a theorem of Malawski and Zhou (Soc Choice Welf 11(2):103–107, 1994) is a generalization of Murakami’s dichotomy theorem and that Wilson’s impossibility theorem (J Econ Theory 5(3):478–486, 1972) is stronger than Murakami’s impossibility theorem, both by virtue of replacing Murakami’s assumption of strict non-imposition with the assumptions of non-imposition and non-nullness. In this note, we first point out that these claims are incorrect: non-imposition and non-nullness are together equivalent to strict non-imposition for all transitive collective choice rules. We then generalize Murakami’s dichotomy and impossibility theorems to the setting of incomplete social preference. We prove that if one drops completeness from Murakami’s assumptions, his remaining assumptions imply (i) that a collective choice rule is either Paretian, anti-Paretian, or dis-Paretian (unanimous individual preference implies noncomparability) and (ii) that adding proposed constraints on noncomparability, such as the regularity axiom of Eliaz and Ok (Games Econ Behav 56:61–86, 2006), restores Murakami’s dictator-or-inverse-dictator result.

1 Introduction

In an innovative monograph applying multi-valued logic to social choice theory, Murakami (1968) proved the first theorems in what has become a subgenre of the social choice literature on “social choice without the Pareto principle” (see, e.g., Wilson 1972; Fountain and Suzumura 1982; Border 1983; Kelsey 1984; Campbell 1989; Malawski and Zhou 1994; Miller 2009; Cato 2012, 2016; Coban and Sanver 2014; Holliday and Pacuit 2018). Working in the setting of Arrovian social choice assuming the independence of irrelevant alternatives, Murakami’s method was to first prove a dichotomy theorem for Paretian or anti-Paretian rules and then, by analyzing each case, to prove a dictator-or-inverse-dictator theorem without the Pareto principle. In this note, we first correct a misconception in the literature about the strength of Murakami’s theorems relative to later results of Wilson (1972) and Malawski and Zhou (1994). We do so by proving an equivalence between strict non-imposition, assumed in Murakami’s theorems, and the combination of non-imposition and non-nullness, assumed in the later results, where this equivalence holds not only for the complete and transitive collective choice rules to which the cited results apply but more generally for all transitive collective choice rules. We then generalize Murakami’s theorems to the setting of possibly incomplete social preference (see, e.g., Sen 1970; Barthelemy 1983; Weymark 1984; Pini et al. 2008; Cato 2013, 2018). Under the assumptions of his dichotomy theorem except for completeness, we prove a trichotomy theorem: a collective choice rule is either Paretian, anti-Paretian, or dis-Paretian (unanimous individual preference implies noncomparability). Finally, by analyzing each case of the trichotomy theorem, we prove a dictator-or-inverse-dictator theorem first under the assumption of regularity of social preference (Eliaz and Ok 2006) and then under the weaker assumption of minimal comparability (Cato 2018).

Let us briefly recall the setup of Arrovian social choice. Fix a nonempty set X of alternatives and a nonempty set V of voters. We assume that $|X|\ge 3$ and V is finite (though we will lift this finiteness assumption in the next section). For a binary relation R on some $Y\subseteq X$, we write ‘xRy’ for $(x,y)\in R$ and define binary relations P(R), I(R), and N(R) on Y by: xP(R)y if and only if xRy and notyRx; xI(R)y if and only if xRy and yRx; and xN(R)y if and only if neither xRy nor yRx. We say that R is complete if for all $x,y\in Y$, xRy or yRx; R is transitive if for all $x,y,z\in Y$, if xRy and yRz, then xRz; and R is quasi-transitive if P(R) is transitive. If R is transitive, then it is quasi-transitive and satisfies the following for all $x,y,z\in Y$:

$$\begin{aligned}&PR\text{-transitivity: } \text{ if } xP(R)y \text{ and } yRz\text{, } \text{ then } xP(R)z; \end{aligned}$$

(1)

$$\begin{aligned}&RP\text{-transitivity: } \text{ if } xRy \text{ and } yP(R)z\text{, } \text{ then } xP(R)z. \end{aligned}$$

(2)

Let B(Y) be the set of all binary relations on Y and O(Y) the set of all complete and transitive binary relations on Y. A profile on$Y\subseteq X$ is a function ${\mathbf {R}}: V\rightarrow O(Y)$. For ${i\in V}$, we write ‘${\mathbf {R}}_i$’ for ${\mathbf {R}}(i)$. We call a profile on X simply a profile, and for any profile ${\mathbf {R}}$ and $Y\subseteq X$, we define ${\mathbf {R}}|_{Y}$ to be the profile on Y assigning to each $i\in V$ the relation ${\mathbf {R}}_i\cap Y^2$. A collective choice rule (CCR) is a function $f:D\rightarrow B(X)$ where D is some nonempty set of profiles. A CCR f satisfies universal domain (UD) if D is the set of all profiles; f is complete (resp. transitive) if for all ${{\mathbf {R}}\in \mathrm {dom}(f)}$, $f({\mathbf {R}})$ is complete (resp. transitive); f is a social welfare function (SWF) if for all ${\mathbf {R}}\in \mathrm {dom}(f)$, $f({\mathbf {R}})$ is complete and transitive; f is null if for all $x,y\in X$ and ${{\mathbf {R}}\in \mathrm {dom}(f)}$, not$xP(f({\mathbf {R}}))y$; f is Paretian (resp. anti-Paretian) if for all $x,y\in X$ and ${\mathbf {R}}\in \mathrm {dom}(f)$, if $xP({\mathbf {R}}_i)y$ for all $i\in V$, then $x P(f({\mathbf {R}}))y$ (resp. $y P(f({\mathbf {R}}))x$); and f is dictatorial (resp. inversely dictatorial) if there is an $i\in V$ such that for all $x,y\in X$ and ${\mathbf {R}}\in \mathrm {dom}(f)$, if $xP({\mathbf {R}}_i)y$, then $xP(f({\mathbf {R}}))y$ (resp. $yP(f({\mathbf {R}}))x$). The first result in Sect. 2 concerns a logical relation between the following axioms for CCRs:

• free triple property (FT): for any $Y=\{x,y,z\}\subseteq X$ and profile ${\mathbf {Q}}$ on Y, there is an ${\mathbf {R}}\in \mathrm {dom}(f)$ such that ${\mathbf {R}}|_Y={\mathbf {Q}}$.

• independence of irrelevant alternatives (IIA): for all ${\mathbf {R}},{\mathbf {R}}'\in \mathrm {dom}(f)$ and $x,y\in X$, if ${\mathbf {R}}|_{\{x,y\}}={\mathbf {R}}'|_{\{x,y\}}$, then $x f({\mathbf {R}})y$ if and only if $x f({\mathbf {R}}')y$.

• non-nullness (NN): f is not null.

• non-imposition (NI): for all $x,y\in X$, there is an ${\mathbf {R}}\in \mathrm {dom}(f)$ such that $xf({\mathbf {R}})y$.

• strict non-imposition (SNI) (called ‘citizens’ sovereignty’ in Arrow 1951): for all ${x,y\in X}$ with $x\ne y$, there is an ${\mathbf {R}}\in \mathrm {dom}(f)$ such that $x P(f({\mathbf {R}}))y$.

For the sake of simplicity, we state all theorems in this section in terms of the same domain condition, UD, rather than FT or other domain conditions used in the original theorems or later refinements (see Campbell and Kelly 2002). But for the sake of generality, we prove several results in Sect. 2 under the weaker assumption of FT.

Arrow’s (1951) original impossibility theorem¹ states that any SWF satisfying UD, IIA, SNI, and an additional axiom of positive association of social and individual values (PA) is dictatorial. Later Arrow (1963, p. 97, Theorem 2) replaced SNI and PA by the assumption that the SWF is Paretian, resulting in the statement usually quoted as Arrow’s Theorem today: any Paretian SWF satisfying UD and IIA is dictatorial.

Murakami (1968) clarified the relation between Arrow’s theorems and the Pareto principle with the following results.

Theorem 1

(Murakami 1968, p. 101, Theorem 6-1) Any SWF satisfying UD, IIA, and SNI is either Paretian or anti-Paretian.

Theorem 2

(Murakami 1968, p. 103, Theorem 6-2) Any SWF satisfying UD, IIA, and SNI is either dictatorial or inversely dictatorial.

Murakami originally stated the second theorem as an impossibility theorem: there is no SWF satisfying UD, IIA, SNI, non-dictatorship, and non-persecution (f is not inversely dictatorial). The logically equivalent form in Theorem 2 is the form given in Cato 2012.²

It has been suggested in the subsequent literature that Murakami’s theorems were “generalized” or “strengthened” by the following results (with Theorem 3 stated in the form given in Cato 2012).

Theorem 3

(Malawski and Zhou 1994) Any SWF satisfying UD, IIA, and NI is either null, Paretian, or anti-Paretian.

Theorem 4

(Wilson 1972) Any SWF satisfying UD, IIA, and NI is either null, dictatorial, or inversely dictatorial.

Concerning the logical relation between Theorems 1 and 3, Malawski and Zhou (1994, p. 107) claim that their result is “slightly more general” than Murakami’s. Where P and AP stand for the Paretian and anti-Paretian properties, respectively, they write:

Using the notations developed in the paper, Proposition 1 [Theorem 3] can be stated as: [FT, IIA, and NI] $\Rightarrow$ [P, or AP, or nullness], while Murakami’s result is: [FT, IIA, and SNI] $\Rightarrow$ [P or AP]. Since SNI is a condition stronger than NI and excludes the possibility of nullness, Murakami’s result is implied by Proposition 1. (p. 107)

Similarly, Cato (2012, p. 874) writes, “Malawski and Zhou (1994) establish a generalization of Murakami’s Theorem 6-1.”

But these claims of generalization are incorrect. For the implication

$$\begin{aligned} \text{[FT, } \text{ IIA, } \text{ and } \text{ NI] } \Rightarrow \text{[P, } \text{ or } \text{ AP, } \text{ or } \text{ nullness] } \end{aligned}$$

is logically equivalent to

$$\begin{aligned} \text{[FT, } \text{ IIA, } \text{ NI, } \text{ and } \text{ NN] } \Rightarrow \text{[P } \text{ or } \text{ AP], } \end{aligned}$$

which is not a generalization of Murakami’s implication

$$\begin{aligned} \text{[FT, } \text{ IIA, } \text{ and } \text{ SNI] } \Rightarrow \text{[P } \text{ or } \text{ AP], } \end{aligned}$$

due to the following fact (implied by Proposition 5 below):

$$\begin{aligned} \text{[FT } \text{ and } \text{ IIA] } \Rightarrow \text{[(NI } \text{ and } \text{ NN) } \Leftrightarrow \text{ SNI]. } \end{aligned}$$

Concerning the logical relation between Theorems 2 and 4, Campbell and Kelly (2002, p. 53) write that Murakami’s theorem “is in the same vein as Wilson’s Theorem, but not as strong”. Similarly, Cato (2012, p. 874) writes: “Wilson (1972) imposes NI instead of SNI, and obtains a stronger result” than Murakami (and in Cato 2010, p. 269: “Murakami’s theorem (1968, Theorem 6.2, p. 103) is weaker than Wilson’s theorem”). But these statements are incorrect for the same reason as noted above. Where D and ID stand for the dictatorial and inversely dictatorial properties, respectively, Wilson’s implication

$$\begin{aligned} \text{[UD, } \text{ IIA, } \text{ and } \text{ NI] } \Rightarrow \text{[D, } \text{ or } \text{ ID, } \text{ or } \text{ nullness] } \end{aligned}$$

is logically equivalent to

$$\begin{aligned} \text{[UD, } \text{ IIA, } \text{ NI, } \text{ and } \text{ NN] } \Rightarrow \text{[D } \text{ or } \text{ ID], } \end{aligned}$$

which is not stronger than Murakami’s implication

$$\begin{aligned} \text{[UD, } \text{ IIA, } \text{ and } \text{ SNI] } \Rightarrow \text{[D } \text{ or } \text{ ID], } \end{aligned}$$

due to the fact that NI and NN are together equivalent to SNI relative to UD and IIA (again, by Proposition 5 below).

In fact, Wilson’s own theorem refutes the claim that Theorem 4 is stronger than Theorem 2. For Wilson proves

$$\begin{aligned} \text{[UD, } \text{ IIA, } \text{ NI, } \text{ and } \text{ NN] } \Rightarrow \text{[D } \text{ or } \text{ ID], } \end{aligned}$$

and clearly

$$\begin{aligned} \text{[UD } \text{ and } \text{(D } \text{ or } \text{ ID)] } \Rightarrow \text{ SNI }, \end{aligned}$$

so we see that Murakami’s assumptions are implied by Wilson’s:

$$\begin{aligned} \text{[UD, } \text{ IIA, } \text{ NI, } \text{ and } \text{ NN] } \Rightarrow \text{[UD, } \text{ IIA, } \text{ and } \text{ SNI] }. \end{aligned}$$

Hence Wilson’s theorem is not a stronger result. By analogous reasoning, Malawski and Zhou’s own theorem refutes the claim that Theorem 3 is a generalization of Theorem 1, as clearly $\text{[FT } \text{ and } \text{(P } \text{ or } \text{ AP)] } \Rightarrow \text{ SNI }$.

Moreover, the equivalence between SNI, on the one hand, and the combination of NI and NN, on the other, holds in an even more general setting than that of Murakami (1968), Wilson (1972), and Malawski and Zhou (1994). Since at least Sen (1970), there has been interest among social choice theorists in dropping the requirement that the social preference relation be complete (Barthelemy 1983; Weymark 1984; Pini et al. 2008; Cato 2013, 2018). In this setting, all of the theorems cited above fail (see Remark 7). Yet we will prove that the equivalence of SNI and the combination of NI and NN holds in the incomplete setting, in which we then prove generalizations of Theorems 1 and 3 and Theorems 2 and 4 .

2 Results

We now let V be of arbitrary cardinality, so the next two results apply to social choice with infinite electorates, where Wilson’s theorem does not hold without additional assumptions (see, e.g., Fishburn 1970; Kirman and Sondermann 1972; Campbell 1990) and hence cannot be used to prove even the special case of Proposition 5 for SWFs.

Proposition 5

If f is a transitive CCR satisfying FT and IIA, then f satisfies NI and NN if and only if f satisfies SNI.

Proof

For any CCR f, SNI clearly implies NI and NN. So we are left to show that if f is a transitive CCR that satisfies FT, IIA, NI, and NN, then f satisfies SNI. Fix $z,w\in X$ such that $z \ne w$. We show there is an ${\mathbf {R}}\in \text{ dom }(f)$ such that $z P(f({\mathbf {R}}))w$. By NN, there are some $x\ne y$ and ${\mathbf {R}}^{x,y}\in \text{ dom }(f)$ such that $x P(f({\mathbf {R}}^{x,y}))y$. There are six cases to consider:

$$\begin{aligned} \begin{array}{ll} 1.\,z=y\hbox { and }w=x; &{} 4.\,z=y\hbox { and }w\ne x,y; \\ 2.\,z\ne x,y\hbox { and }w=y;\qquad \qquad &{} 5.\,z\ne x,y\hbox { and }w=x; \\ 3.\,z=x\hbox { and }w\ne x,y; &{} 6.\,z\ne x,y\hbox { and }w\ne x,y. \end{array} \end{aligned}$$

For case 2, by NI, let ${\mathbf {R}}^1\in \text{ dom }(f)$ be such that $zf({\mathbf {R}}^1)x$. For each $i\in V$, define a binary relation $Q_i^0$ on $\{x,y,z\}$ by:

$$ \begin{aligned}&aQ_i^0a \text{ for } \text{ all } a\in \{x,y,z\};&\\&xQ_i^0z\Leftrightarrow x{\mathbf {R}}^1_iz, \text{ and } zQ_i^0x\Leftrightarrow z{\mathbf {R}}^1_ix;&\\&xQ_i^0y\Leftrightarrow x{\mathbf {R}}^{x,y}_iy, \text{ and } yQ_i^0x\Leftrightarrow y{\mathbf {R}}^{x,y}_ix;&\\&yQ_i^0z\Leftrightarrow [ y{\mathbf {R}}^{x,y}_ix\; \& \; x{\mathbf {R}}^1_iz ], \text{ and } zQ_i^0y\Leftrightarrow [z{\mathbf {R}}^1_ix\; \& \;x{\mathbf {R}}^{x,y}_iy].&\end{aligned}$$

Then $Q_i^0$ is a transitive relation on $\{x,y,z\}$. It follows (see Szpilrajn 1930; Arrow 1963, p. 64) that there is a complete and transitive relation $Q_i$ on $\{x,y,z\}$ such that $Q_i^0\subseteq Q_i$ and $P(Q_i^0)\subseteq P(Q_i)$. Let ${\mathbf {Q}}$ be the profile on $\{x,y,z\}$ that assigns $Q_i$ to voter i. Then by FT, there is an ${\mathbf {R}}\in \text{ dom }(f)$ such that ${\mathbf {R}}|_{\{x,y,z\}}={\mathbf {Q}}$. By IIA, $zf({\mathbf {R}}^1)x$ implies $zf({\mathbf {R}})x$, and $x P(f({\mathbf {R}}^{x,y}))y$ implies $x P(f({\mathbf {R}}))y$, so $z P(f({\mathbf {R}}))y$ by (2).

For case 3, by NI, take ${\mathbf {R}}^1\in \text{ dom }(f)$ with $yf({\mathbf {R}}^1)w$. Then, as in case 2, there is an ${\mathbf {R}}\in \text{ dom }(f)$ with ${\mathbf {R}}|_{\{x,y\}}={\mathbf {R}}^{x,y}|_{\{x,y\}}$ and ${\mathbf {R}}|_{\{y,w\}}={\mathbf {R}}^1|_{\{y,w\}}$. By IIA, $x P(f({\mathbf {R}}) )y$ and $yf({\mathbf {R}})w$, so $xP(f({\mathbf {R}}))w$ by (1).

For case 4, by NI, take ${\mathbf {R}}^1\in \text{ dom }(f)$ with $y f({\mathbf {R}}^1)x$. By case 3, take ${\mathbf {R}}^2\in \text{ dom }(f)$ with $x P(f({\mathbf {R}}^2))w$. Then, as above, there is an ${\mathbf {R}}\in \text{ dom }(f)$ with ${\mathbf {R}}|_{\{x,y\}}={\mathbf {R}}^1|_{\{x,y\}}$ and ${\mathbf {R}}|_{\{x,w\}}={\mathbf {R}}^2|_{\{x,w\}}$. By IIA, $yf({\mathbf {R}})x$ and $xP(f({\mathbf {R}}))w$, so $y P(f({\mathbf {R}}))w$ by (2).

We now prove case 1. By case 4, take ${\mathbf {R}}^1\in \text{ dom }(f)$ with $yP(f({\mathbf {R}}^1))w$. By NI, take ${\mathbf {R}}^2\in \text{ dom }(f)$ with $wf({\mathbf {R}}^2)x$. Then, as above, there is an ${\mathbf {R}}\in \text{ dom }(f)$ with ${\mathbf {R}}|_{\{y,w\}}={\mathbf {R}}^1|_{\{y,w\}}$ and ${\mathbf {R}}|_{\{w,x\}}={\mathbf {R}}^2|_{\{w,x\}}$. By IIA, $yP(f({\mathbf {R}}))w$ and $wf({\mathbf {R}})x$, so $y P(f({\mathbf {R}}))x$ by (1).

For case 5, by case 1, take ${\mathbf {R}}^1\in \text{ dom }(f)$ with $y P(f({\mathbf {R}}^1))x$. By NI, take ${\mathbf {R}}^2\in \text{ dom }(f)$ with $zf({\mathbf {R}}^2)y$. Then, as above, there is an ${\mathbf {R}}\in \text{ dom }(f)$ with ${\mathbf {R}}|_{\{y,x\}}={\mathbf {R}}^1|_{\{y,x\}}$ and ${\mathbf {R}}|_{\{z,y\}}={\mathbf {R}}^2|_{\{z,y\}}$. By IIA, $zf({\mathbf {R}})y$ and $y P(f({\mathbf {R}}))x$, so $zP(f({\mathbf {R}}))x$ by (2).

For case 6, by case 5, take ${\mathbf {R}}^1\in \text{ dom }(f)$ with $zP(f({\mathbf {R}}^1))x$. By case 3, take ${\mathbf {R}}^2\in \text{ dom }(f)$ with $xP(f({\mathbf {R}}^2))w$. Then, as above, there is an ${\mathbf {R}}\in \text{ dom }(f)$ with ${\mathbf {R}}|_{\{z,x\}}={\mathbf {R}}^1|_{\{z,x\}}$ and ${\mathbf {R}}|_{\{x,w\}}={\mathbf {R}}^2|_{\{x,w\}}$. By IIA, $zP(f({\mathbf {R}}))x$ and $xP(f({\mathbf {R}}))w$, so $zP(f({\mathbf {R}}))w$. $\square$

Remark 6

Our definition of NN (there are $x,y\in X$ and ${\mathbf {R}}\in \mathrm {dom}(f)$ with $xP(f({\mathbf {R}}))y$) follows Campbell and Kelly (2002, p. 43) and Cato (2010, 2012, 2016). Wilson (1972) and Malawski and Zhou (1994) use a different definition of NN: there are $x,y\in X$ and ${\mathbf {R}}\in \mathrm {dom}(f)$ such that not$xf({\mathbf {R}})y$. Let us call our version and their version strict NN (SNN) and weak NN (WNN), respectively. Then SNN and WNN are equivalent for SWFs, but WNN is weaker than SNN for arbitrary transitive CCRs. In addition, Proposition 5 fails for WNN in place of SNN. To see this, fix a voter $i\in V$. Define a CCR f such that for all $x,y\in X$ and profiles ${\mathbf {R}}$:

• if $xI({\mathbf {R}}_i)y$, then $x I(f({\mathbf {R}}))y$;

• otherwise, $x N(f({\mathbf {R}}))y$.

Then f satisfies UD, IIA, NI, and WNN, and f is transitive. For if $xf({\mathbf {R}})y$ and $yf({\mathbf {R}})z$, then $xI({\mathbf {R}}_i)y$ and $yI({\mathbf {R}}_i)z$, so $xI({\mathbf {R}}_i)z$ by the transitivity of ${\mathbf {R}}_i$. Thus, $xf({\mathbf {R}})z$. But f does not satisfy SNI. Hence f is neither Paretian nor anti-Paretian, and neither dictatorial nor inversely dictatorial. Therefore, like Proposition 5, all of the theorems in Sect. 1 fail if we replace SWFs with transitive CCRs and NN with WNN.

Remark 7

All of the theorems in Sect. 1 fail if we replace SWFs with transitive CCRs and maintain the assumption of NN, i.e., SNN, discussed in Remark 6. Thus, none of those theorems can be used to prove Proposition 5. To see that the theorems fail in this setting, fix distinct voters $i,j\in V$. Define a CCR f such that for all $x,y\in X$ and profiles ${\mathbf {R}}$:

• if $xI({\mathbf {R}}_i)y$ and $xP({\mathbf {R}}_j)y$, then $xP(f({\mathbf {R}}))y$;

• if $xI({\mathbf {R}}_i)y$ and $yP({\mathbf {R}}_j)x$, then $yP(f({\mathbf {R}}))x$;

• otherwise, $xN(f({\mathbf {R}}))y$ (except if $x=y$, in which case $xf({\mathbf {R}})x$).

Then f satisfies UD, IIA, and SNI, and f is transitive. For if $xf({\mathbf {R}})y$ and $yf({\mathbf {R}})z$, then $xI({\mathbf {R}}_i)y$, $xP({\mathbf {R}}_j)y$, $yI({\mathbf {R}}_i)z$, and $yP({\mathbf {R}}_j)z$, which together imply $xI({\mathbf {R}}_i)z$ and $xP({\mathbf {R}}_j)z$ by the transitivity of ${\mathbf {R}}_i$ and ${\mathbf {R}}_j$. Thus, $xP(f({\mathbf {R}}))z$. However, f is neither Paretian nor anti-Paretian and hence neither dictatorial nor inversely dictatorial.

Remark 8

A number of authors have investigated CCRs f for which $f({\mathbf {R}})$ is required to be complete and quasi-transitive but not necessarily transitive (see, e.g., Sen 1969; Guha 1972; Mas-Colell and Sonnenschein 1972; Hansson 1976; Fountain and Suzumura 1982; Gibbard 2014a, b). For this class of CCRs, the analogue of Proposition 5 does not hold. To see this, fix a voter $i\in V$ and distinct alternatives $a,b\in X$. Define a CCR f such that for all $x,y\in X$ and profiles ${\mathbf {R}}$:

• if $\{x,y\}\ne \{a,b\}$, then $xf({\mathbf {R}})y$;

• if $\{x,y\}=\{a,b\}$, then $xf({\mathbf {R}})y$ if and only if $x {\mathbf {R}}_i y$.

Then f is complete and quasi-transitive (as there are no x, y, z such that $xP(f({\mathbf {R}}))y$ and $yP(f({\mathbf {R}}))z$), and f satisfies UD, IIA, NI, and NN, but not SNI.

Next, we use Propositon 5 to show that together NI and NN are sufficient (given FT and IIA) to prove a generalization of Murakami’s Theorem 1 and hence also of Malawski and Zhou’s Theorem 3 to incomplete CCRs. Define a CCR to be dis-Paretian if for all $x,y\in X$ and ${\mathbf {R}}\in \mathrm {dom}(f)$, if $xP({\mathbf {R}}_i)y$ for all $i\in V$, then $xN(f({\mathbf {R}}))y$.

Theorem 9

Any transitive CCR satisfying FT, IIA, NI, and NN is either Paretian, anti-Paretian, or dis-Paretian.

Proof

Let f satisfy the hypothesis of the theorem. We say that V is weakly decisive (resp. weakly inversely decisive) on$x,y\in X$forf if for any ${\mathbf {R}}\in \mathrm {dom}(f)$, if $xP({\mathbf {R}}_i)y$ for all $i\in V$, then $xf({\mathbf {R}})y$ (resp. $yf({\mathbf {R}})x$). We say that V is decisive (resp. inversely decisive) on$x,y\in X$forf if for any ${\mathbf {R}}\in \mathrm {dom}(f)$, if $xP({\mathbf {R}}_i)y$ for all $i\in V$, then $xP(f({\mathbf {R}}))y$ (resp. $yP(f({\mathbf {R}}))x$). We first show that if V is weakly decisive (resp. weakly inversely decisive) on some pair x, y, then f is Paretian (resp. anti-Paretian).

Suppose V is weakly decisive (resp. weakly inversely decisive) on x, y. Let $a\in X{\setminus } \{x,y\}$. We show that V is decisive (resp. inversely decisive) on x, a. Let ${\mathbf {R}}\in \mathrm {dom}(f)$ be such that $xP({\mathbf {R}}_i)a$ for all $i\in V$. Since f satisfies NI and NN, f satisfies SNI by Proposition 5. Thus, there is an ${\mathbf {R}}^{y,a}\in \mathrm {dom}(f)$ such that $yP(f({\mathbf {R}}^{y,a}))a$ (resp. $aP(f({\mathbf {R}}^{y,a}))y$). By FT, there is an ${\mathbf {R}}'\in \mathrm {dom}(f)$ such that:

$$\begin{aligned} {\mathbf {R}}'|_{\{x,a\}}={\mathbf {R}}|_{\{x,a\}};\\{\mathbf {R}}'|_{\{y,a\}}={\mathbf {R}}^{y,a}|_{\{y,a\}};\\xP({\mathbf {R}}'_i)y \text{ for } \text{ all } i\in V. \end{aligned}$$

Since V is weakly decisive (resp. weakly inversely decisive) on x, y, we have that $xf({\mathbf {R}}')y$ (resp. $yf({\mathbf {R}}'))x$). By IIA, $yP(f({\mathbf {R}}'))a$ (resp. $aP(f({\mathbf {R}}'))y$). So by (2) (resp. (1)), $xP(f({\mathbf {R}}'))a$ (resp. $aP(f({\mathbf {R}}'))x$). Hence by IIA, $xP(f({\mathbf {R}}))a$ (resp. $aP(f({\mathbf {R}}))x$). Therefore, V is decisive (resp. inversely decisive) on x, a. By similar reasoning, V is decisive (resp. inversely decisive) on any $a,b\in X$, so f is Paretian (resp. anti-Paretian).

We now prove the trichotomy. Fix $x,y\in X$ and let ${\mathbf {R}}\in \mathrm {dom}(f)$ be such that $xP({\mathbf {R}}_i)y$ for all $i\in V$. If $xf({\mathbf {R}})y$ (resp. $yf({\mathbf {R}})x$), then by IIA, V is weakly decisive (resp. weakly inversely decisive) on x, y and hence f is Paretian (resp. anti-Paretian) by the previous paragraph. Lastly, suppose $xN(f({\mathbf {R}}))y$, so f is neither Paretian nor anti-Paretian. Then for any $a,b\in X$ and ${\mathbf {R}}'\in \mathrm {dom}(f)$, if $aP(f({\mathbf {R}}'_i))b$ for all $i\in V$, then $aN(f({\mathbf {R}}'))b$ by the previous reasoning. Hence f is dis-Paretian. $\square$

The CCR defined in Remark 7 shows that the third case of the trichotomy is possible.

Remark 10

Inspection of the proofs of Proposition 5 and Theorem 9 shows that full transitivity is not needed. It suffices that f satisfies the conditions of PR-transitivity and RP-transitivity from Sect. 1. To see that the combination of these properties is weaker than transitivity,³ fix distinct alternatives $a,b\in X$ and consider the CCR f defined as follows for any $x,y\in X$ and profile ${\mathbf {R}}$:

• if $xP({\mathbf {R}}_i)y$ for all $i\in V$, then $xP(f({\mathbf {R}}))y$;

• if $yP({\mathbf {R}}_i)x$ for all $i\in V$, then $yP(f({\mathbf {R}}))x$;

• if $\{x,y\}\ne \{a,b\}$ and $xI({\mathbf {R}}_i)y$ for all $i\in V$, then $xI(f({\mathbf {R}}))y$;

• otherwise, $xN(f({\mathbf {R}}))y$ (except if $x=y$, in which case $xf({\mathbf {R}})x$).

Then f satisfies UD, IIA, SNI, and PR- and RP-transitivity. To see that f does not satisfy transitivity, fix $y \in X{\setminus } \{a,b\}$ and consider a profile where $aI({\mathbf {R}}_i)yI({\mathbf {R}}_i)b$ for all $i\in V$. Then since $aI({\mathbf {R}}_i)b$ for all $i\in V$, it follows that $aI(f({\mathbf {R}}))y$ and $yI(f({\mathbf {R}}))b$ but $aN(f({\mathbf {R}}))b$.

Finally, as a sample application of Theorem 9, we prove two generalizations of Murakami’s impossibility theorem, Theorem 2, in the setting of incomplete social preference. Weymark (1984, Corollary 2) observed that by dropping completeness from Arrow’s axioms, while retaining the Paretian assumption, Arrow’s conclusion weakens from a dictatorship to an oligarchy. Below we drop both completeness and the Paretian assumption, but we add an axiom that distinguishes noncomparability, N(R), from indifference, I(R). The result is a Murakami-style dictatorship-or-inverse-dictatorship theorem. The additional axiom comes from the choice-theoretic analysis of noncomparability vs. indifference by Eliaz and Ok (2006), who propose the following property of noncomparability: for all $x,y\in X$, if xN(R)y, then there is a $z\in X$ such that one of the following holds: xP(R)z and zN(R)y; zP(R)x and zN(R)y; yP(R)z and xN(R)z; or zP(R)y and xN(R)z. They call a binary relation Rregular if N(R) satisfies this property,⁴ and we call a CCR regular if $f({\mathbf {R}})$ is regular for every ${\mathbf {R}}\in \mathrm {dom}(f)$. Intuitively, the key difference between N(R) and I(R) is as follows: if x and y are equally good, and if we change x to a better alternative $x'$ or a worse alternative $x'$, then $x'$ should be better than y or worse than y, respectively; whereas if x and y are noncomparable, then $x'$ and y may still be noncomparable in either case (cf. Chang 1997). Regularity requires that there be a witness to this difference between N(R) and I(R). For the following result, we again assume that V is finite.

Theorem 11

Any transitive and regular CCR satisfying UD, IIA, NI, and NN is either dictatorial or inversely dictatorial.

Proof

Assume f is a CCR satisfying the hypothesis of the theorem. By Theorem 9, f is Paretian, anti-Paretian, or dis-Paretian. First, we claim that f cannot be dis-Paretian in light of regularity. Let L be a linear order on X, and let ${\mathbf {R}}$ be a profile such that ${\mathbf {R}}_i=L$ for all $i\in V$. Then $xN(f({\mathbf {R}}))y$ for all distinct $x,y\in X$, so f is not regular. Next suppose f is Paretian. Then by Corollary 2 of Weymark 1984, there is a nonempty coalition $C\subseteq V$ that is decisive, i.e., for any $x,y\in X$ and profile ${\mathbf {R}}$, if $xP({\mathbf {R}}_i)y$ for all $i\in C$, then $xP(f({\mathbf {R}}))y$, and such that each $i\in C$ has a strong veto, i.e., for any $x,y\in X$ and profile ${\mathbf {R}}$, if $xP({\mathbf {R}}_i)y$, then not$yf({\mathbf {R}})x$. If $|C|\ge 2$, then take $i,j\in C$ with $i\ne j$. Fix some linear order L on X, and define a linear order $L'$ by $xL'y$ if and only if yLx. Let ${\mathbf {R}}$ be a profile with ${\mathbf {R}}_i=L$ and ${\mathbf {R}}_j=L'$. Then $xN(f({\mathbf {R}}))y$ for all distinct $x,y\in X$, since i, j have strong vetoes. Again this contradicts regularity. Hence $|C|=1$, which with the decisiveness of C implies that f has a dictator. Finally, if f is anti-Paretian, then the CCR $f^\top$ defined by $xf^\top ({\mathbf {R}})y$ if and only if $yf({\mathbf {R}})x$ is a transitive and regular CCR satisfying UD, IIA, NI, and NN, which is Paretian. Hence by the previous reasoning, $f^\top$ has a dictator, so f has an inverse dictator. $\square$

Remark 12

Adding to Theorem 11 the assumption that f is Paretian of course yields that f is dictatorial. A referee informed us that Cato (2019, Theorem 2) independently proved this impossibility result assuming Pareto. Our result is therefore a generalization of his without the Pareto principle. Note that Cato proves his result using an ultrafilter approach whereas our proof in the Paretian case uses Weymark’s (1984) oligarchy theorem.

We also learned that Cato (2018) proved a related dictatorship result using the condition of minimal comparability—for all ${\mathbf {R}}\in \mathrm {dom}(f)$, there are distinct $x,y\in X$ such that $xf({\mathbf {R}})y$—which is implied by regularity but not vice versa: any transitive and Paretian CCR satisfying UD, IIA, and minimal comparability is dictatorial. Inspection of our proof of Theorem 11 shows that it is minimal comparability that is violated if there is no dictator or inverse dictator. Thus, we obtain the following generalization of Cato’s (2018) result.⁵

Theorem 13

Any transitive CCR satisfying UD, IIA, NI, NN, and minimal comparability is either dictatorial or inversely dictatorial.

3 Conclusion

The results of Wilson (1972) and Malawski and Zhou (1994) have not strengthened or generalized Murakami’s (1968) original theorems. However, we have obtained genuine generalizations of Murakami’s theorems in Theorem 9 and Theorems 11 and 13. In proving Theorems 11 and 13, we extended what Cato (2012) calls “Murakami’s method” to the incomplete setting: just as Murakami proved his impossibility theorem by analyzing each case of his dichotomy theorem, we proved an impossibility theorem by analyzing each case of the trichotomy theorem. A natural next step is to use Murakami’s method to prove further impossibility results assuming axioms for social preference other than those considered here. We leave the details of further applications of Murakami’s method to incomplete social choice for future work.