Alternative proofs of Arrow’s general possibility theorem

Abstract

This paper provides two brief proofs of Arrow’s general possibility theorem. The second one is simple and short. Our proofs are inspired by the pioneering work by Inada (Ann. Inst. Stat. Math. 6:115–122, 1954).

1 Introduction

Immediately after the publication of Social Choice and Individual Values (Arrow 1951), Inada (1954) provided alternative proofs of three results in the book, including for Arrow’s general possibility theorem. Later, Blau (1957) pointed out that the original version of the theorem is incorrectly stated; his observation also applies to Inada’s proof. In response to Blau (1957), Arrow (1963) provided a restatement of the general possibility theorem and its proof. Since then, most authors have followed the revised version, which is included in the second edition of Arrow’s book. As Blau (1957) and Arrow (1963) reformulated the set of axioms on which Inada’s proof was based, Inada’s proof has not received much attention in the context of Arrovian social choice theory.

The present article aims to rehabilitate Inada’s proof of Arrow’s general possibility theorem. In line with Inada (1954), we provide two simple proofs of the second version of the general possibility theorem. These proofs have some notable features compared with the existing ones. The standard approach to prove Arrow’s theorem was developed by Arrow (1963) and Sen (1970, 1979).¹ Most proofs of the theorem are constructed along the same lines (Fishburn 1970; Blau 1972; Sen 1986, 1995; Denicolò 1996, 2001; Suzumura 2000). In such proofs, the so-called field expansion lemma is established as the first step: it says that if a group of individuals has decisive power over some pairs of alternatives, then it has decisive power over all pairs. Thus, this lemma shows that the decisiveness structure is invariant across all pairs under Arrow’s axioms.² As the next step, the group-contraction lemma is proved using the field expansion lemma: for any decisive group with more than one individual, there exists some smaller decisive group within it. The theorem immediately follows from this lemma.

In Contrast to the standard proof, Inada and we do not construct the field expansion lemma as an auxiliary step. Instead, we employ the concept of a minimal (almost) decisive set to construct a group-contraction procedure as the first step: we prove that a minimal (almost) decisive set is a singleton for all pairs. Next, we show that the minimal (almost) decisive set is invariant across all pairs. Finally, we explain the relationship between our proofs and Inada’s. Inada used the concept of a decisive set, whereas we apply the concept of an almost decisive set in our first proof.

This difference is because of the difference between the original axioms and those of the 1963 theorem. In our second proof, we reconstruct the argument to apply standard decisiveness. It is one of the simplest proofs of Arrow’s theorem.

2 Terminology

Let $X$ be the set of alternatives; this set must contain at least three alternatives. Let $\succsim$ be a binary relation on $X$. Moreover, the symmetric and asymmetric parts of $\succsim$ are denoted by $\sim$ and $\succ$, respectively.³ A binary relation is said to be an ordering if and only if it is complete and transitive.⁴ Let $\wp$ be the set of all orderings on $X$.

Let $N=\{ 1,2, \dots ,n\}$ be the finite set of individuals.⁵ Each individual $i \in N$ has a preference ordering $\succsim _i \in \wp$ on $X$. Then, a typical profile of individual preference orderings can be denoted by $\succsim _N =(\succsim _i)_{i \in N} \in \wp ^N$. For each $D \subseteq N$, let $\succsim _D := (\succsim _j)_{j \in D}$.

Let $\succsim _N|_{A}$ be the restriction of $\succsim _N \in \wp ^N$ to $A \subseteq X$. Analogically, $\succsim _i|_{A}$ is the restriction of $\succsim _i \in \wp$ to $A \subseteq X$.

A constitution function (or social welfare function) is a function $f{:}\,\wp ^N \rightarrow \wp$ that maps each profile $\succsim _N \in \wp ^N$ to a unique preference ordering $f(\succsim _N) \in \wp$. For simplicity, we often use $\succsim$ to denote $f(\succsim _N)$ in what follows. The individual $i \in N$ is a dictator for $f$ if for all $x, y \in X$ and all $\succsim _N \in \wp ^N$, $x \succ _i y \Rightarrow x \succ y$.

Next, we introduce axioms on $f$. These are formulated in the second edition of Arrow’s book.

Weak Pareto (WP): $\forall \succsim _N \in \wp ^N, \forall x,y \in X$, if $x \succ _i y$ for all $i \in N$, then $x \succ y$.

Independence of Irrelevant Alternatives (IIA): $\forall x, y$ $\in X, \forall \succsim _N, \succsim _N^{\prime } \in \wp ^N$, if $\succsim _N|_{\{ x,y \} } =\succsim _N^{\prime }|_{\{ x,y \} }$, then $[ x \succsim y \Leftrightarrow x \succsim ^{\prime } y ]$ and $[ y \succsim x \Leftrightarrow y \succsim ^{\prime } x ]$, where $\succsim = f(\succsim _N)$ and $\succsim ^{\prime } = f(\succsim _N^{\prime })$.

Non-Dictatorship (ND): There exists no dictator for $f$.

A set $D \subseteq N$ is almost decisive over $(x,y)$ for $f$ if for all $\succsim _N \in \wp ^N$,

$$\begin{aligned}{}[ x \succ _i y \text{ for } \text{ all } i \in D \text{ and } y \succ _i x \text{ for } \text{ all } i \in N \setminus D ] \Rightarrow x \succ y. \end{aligned}$$

A set $D \subseteq N$ is almost decisive for $f$ if it is almost decisive over $(x,y)$ for $f$ for all $(x,y) \in X \times X$.

A set $D \subseteq N$ is decisive over $(x,y)$ for $f$ if for all $\succsim _N \in \wp ^N$,

$$\begin{aligned}{}[ x \succ _i y \text{ for } \text{ all } i \in D] \Rightarrow x \succ y. \end{aligned}$$

A set $D \subseteq N$ is decisive for $f$ if it is decisive over $(x,y)$ for $f$ for all $(x,y) \in X \times X$.

3 The formal statement of Arrow’s theorem and its proofs

Theorem1

There exists no constitution function $f$ that satisfies weak Pareto, independence of irrelevant alternatives, and non-dictatorship.

First Proof Given $a,b \in X$, $M_{ab}$ denotes a minimal almost decisive set over $(a,b)$ for $f$. Since $N$ is a finite set, WP implies that $M_{ab} \ne \emptyset$. We first show that $M_{ab}$ is a singleton for all $a,b \in X$ with $a \ne b$. Take any distinct $x,y \in X$. Let $z \in X \setminus \{x,y \}$, and let $\succsim _N \in \wp ^N$ be such that

$$\begin{aligned} \forall i \in M_{xz} \cap M_{zy}&{:}\, x \succ _i z \succ _i y,\\ \forall i \in M_{xz} \setminus M_{zy}&{:}\, y \succ _i x \succ _i z,\\ \forall i \in M_{zy} \setminus M_{xz}&{:}\, z \succ _i y \succ _i x,\\ \forall i \in N \setminus (M_{xz} \cup M_{zy})&{:}\, y \succ _i z \succ _i x. \end{aligned}$$

By definition of $M_{xz}$ and $M_{zy}$, we have $x \succ z$ and $z \succ y$. Transitivity implies that $x \succ y$. By IIA, $M_{xz} \cap M_{zy}$ is almost decisive over $(x,y)$ for $f$. By WP, any almost decisive set is non-empty, and thus, $M_{xz} \cap M_{zy} \ne \emptyset$. If some individual $i^* \in M_{xz} \cap M_{zy}$ changes his preference to $y \succ _{i^*} z \succ _{i^*} x$, then social preference must be $y \succsim z \succsim x$ by definition of $M_{xz}$ and $M_{zy}$; thus, we have $y \succsim x$ by transitivity. Hence, $M_{xz} \cap M_{zy}$ is a minimal almost decisive set over $(x,y)$. To prove that $M_{xz} \cap M_{zy}$ is a singleton, suppose that $|M_{xz} \cap M_{zy}| \ge 2$. Without loss of generality, assume that $\{ 1,2\} \subseteq M_{xz} \cap M_{zy}$. Let $\succsim _N^{\prime } \in \wp ^N$ be such that

$$\begin{aligned}&z \succ ^{\prime }_1 x \succ ^{\prime }_1 y,\\&x \succ ^{\prime }_2 y \succ ^{\prime }_2 z,\\&\succsim ^{\prime }_{N \setminus \{ 1,2\}}=\succsim _{N \setminus \{ 1,2\}}. \end{aligned}$$

From the minimality of $M_{xz}$ and $M_{zy}$, it follows that $z \succsim ^{\prime } x$ and $y \succsim ^{\prime } z$. Since $\succsim ^{\prime }_{N}|_{ \{ x,y \} }=\succsim _{N} |_{ \{ x,y \} }$, IIA implies that $x \succ ^{\prime } y$. This contradicts transitivity. Thus, $M_{ab}$ is a singleton for all $a,b \in X$ with $a \ne b$.

Suppose that $\{ d \} = M_{xy}$. Since $M_{xy} \cap M_{yz}= M_{xz}$ and each of the sets $M_{xy}, M_{yz}$, and $M_{xz}$ is a singleton, we have $\{ d \} = M_{yz}$ for all $z \in X \setminus \{ x ,y\}$. We also have that $\{ d \} = M_{yx}$ because $M_{yx} \cap M_{xz}= M_{yz} =\{ d \}$. Therefore, if $\{ d \} = M_{xy}$, then $\{ d \} = M_{yz}$ for all $z \in X \setminus \{y\}$. This argument yields that

$$\begin{aligned} \{ d \} = M_{xy}&\Rightarrow \{ d \} = M_{yz} \ \forall z \in X\\&\Rightarrow \{ d \} = M_{zw} \ \forall w \in X. \end{aligned}$$

In other words, if $\{ d\}$ is a minimal almost decisive set over $(x,y)$ for $f$, then it is a minimal almost decisive set over all pairs for $f$. Therefore, there exists $d \in N$ such that $\{ d \}$ is almost decisive over all $(a,b) \in X \times X$ for $f$.

Finally, we show that $d$ is a dictator for $f$. Suppose that there exist $x,y \in X$ and $\succsim _N^{\prime \prime } \in \wp ^N$ such that $x \succ ^{\prime \prime }_d y$ and $y \succsim ^{\prime \prime } x$. Let $\succsim ^*_N \in \wp ^N$ be such that

$$\begin{aligned}&\succsim ^*_N|_{\{x,y\}}=\succsim ^{\prime \prime }_N|_{\{x,y\}},\\&x \succ ^*_d z \succ ^*_d y,\\&i \ne d{:}\, y \succ ^*_i z \text{ and } x \succ ^*_i z. \end{aligned}$$

IIA implies that $y \succsim ^* x$. Since $\{ d \}$ is almost decisive over $(z,y)$ for $f$, $z \succ ^* y$. By transitivity, we have $z \succ ^* x$. This contradicts WP. This completes the proof of the theorem. $\square$

The essential difference between our first proof and Inada’s is that Inada applies the concept of a decisive set, whereas we have applied the concept of an almost decisive set. Inada’s argument is based on the original version of Arrow’s theorem; thus, he postulates positive association of social and individual values (Condition 2 of Arrow’s original axioms). We now state it as follows.

Positive Association of Social and Individual Values: For all $\succsim _N, \succsim _N^{\prime }$, if

• (i) $\forall i \in N: \ x^{\prime } \succsim _i y^{\prime } \Leftrightarrow x^{\prime } \succsim ^{\prime }_i y^{\prime }$ for all $x^{\prime },y^{\prime } \in X \setminus \{ x \}$;

• (ii) $\forall i \in N: \ x \succsim _i y^{\prime }\,\, \Rightarrow x \succsim _i y^{\prime }$ for all $y^{\prime } \in X \setminus \{ x \}$;

• (iii) $\forall i \in N: \ x \succ _i y^{\prime } \,\,\Rightarrow x \succ ^{\prime }_i y^{\prime }$ for all $y^{\prime } \in X \setminus \{ x \}$;

then $x \succ y \Rightarrow x \succ ^{\prime } y$.

In the presence of the positive association, the two decisiveness concepts are equivalent:⁶ if a set is almost decisive over $(x,y)$ for $f$, then it must be decisive over $(x,y)$ for $f$.⁷ Since Inada’s proof depends on the equivalence, we cannot directly follow his argument. In the absence of the positive association, one would have to work with almost decisive sets.

In our second proof, we modify the argument in the first proof to directly apply decisiveness.

Second Proof Given $a,b \in X$, $M^*_{ab}$ denotes a minimal decisive set over $(a,b)$ for $f$. WP implies that $M^*_{ab} \ne \emptyset$. We show that $M^*_{ab}$ is a singleton for all $a,b \in X$ with $a \ne b$. Take any distinct $x,y \in X$. Let $z \in X \setminus \{x,y \}$, and let $\succsim _N \in \wp ^N$ be such that

$$\begin{aligned} \forall i \in M^*_{xz} \cap M^*_{zy}&{:}\, x \succ _i z \succ _i y,\\ \forall i \in M^*_{xz} \setminus M^*_{zy}&{:} \, x \succ _i z,\\ \forall i \in M^*_{zy} \setminus M^*_{xz}&{:} \, z \succ _i y. \end{aligned}$$

By definition of $M^*_{xz}$ and $M^*_{zy}$, we have $x \succ z$ and $z \succ y$. Transitivity implies that $x \succ y$. Since the ranking of $x$ and $y$ is not specified for individuals outside of $M^*_{xz} \cap M^*_{zy}$, IIA implies that $M^*_{xz} \cap M^*_{zy}$ is decisive over $(x,y)$ for $f$. By WP, $M^*_{xz} \cap M^*_{zy} \ne \emptyset$. Suppose that $|M^*_{xz} \cap M^*_{zy}| \ge 2$. Without loss of generality, assume that $\{ 1,2\} \subseteq M^*_{xz} \cap M^*_{zy}$. By definition of $M^*_{xz}$ and $M^*_{zy}$, there exist $\succsim _N^{\prime }, \succsim _N^{\prime \prime } \in \wp ^N$ such that

$$\begin{aligned}{}[ x \succ ^{\prime }_i z \ \forall i \in M^*_{xz} \setminus \{ 1 \} ] \text{ and } z \succsim ^{\prime } x, \end{aligned}$$

and

$$\begin{aligned}{}[ z \succ ^{\prime \prime }_i y \ \forall i \in M^*_{zy} \setminus \{ 2 \} ] \text{ and } y \succsim ^{\prime \prime } z. \end{aligned}$$

Let $\succsim _N^* \in \wp ^N$ be such that $x \succ ^*_1 y$, $x \succ ^*_2 y$, $\succsim _N^* |_{\{ x,z\}}=\succsim ^{\prime } |_{\{ x,z\}}$, and $\succsim _N^* |_{\{ y,z\}}=\succsim ^{\prime \prime } |_{\{ y,z\}}$. IIA implies that $z \succsim ^* x$ and $y \succsim ^* z$. It is clear that $x \succ ^*_i y$ for all $i \in M^*_{xz} \cap M^*_{zy}$. Since $M^*_{xz} \cap M^*_{zy}$ is decisive over $(x,y)$ for $f$, we have $x \succ ^* y$. This contradicts transitivity. Hence, $M^*_{ab}$ is a singleton for all $a,b \in X$ with $a \ne b$.

Suppose that $\{ d \} = M^*_{xy}$. It is clear that $\{ d \} = M^*_{yx}$. Since $M^*_{xy} \cap M^*_{yz}= M^*_{xz}$ and each of the sets $M^*_{xy}, M^*_{yz}$, and $M^*_{xz}$ is a singleton, $\{ d \} = M^*_{yz}$ for all $z \in X \setminus \{ x ,y\}$. Thus, $\{ d \} = M^*_{yz}$ for all $z \in X \setminus \{y\}$. This argument yields that

$$\begin{aligned} \{ d \} = M^*_{xy}&\Rightarrow \{ d \} = M^*_{yz} \ \forall z \in X \\&\Rightarrow \{ d \} = M^*_{zw} \ \forall w \in X. \end{aligned}$$

Thus, $d$ is a dictator. $\square$

Recently, the “pivotal voter” approach has received much attention (Barberá 1983; Geanakoplos 2005; Reny 2001; Cato 2010; Yu 2012). The approach is considered to have an advantage when researchers make simple and short proofs. Moreover, it is intuitively appealing. Yu (2012) indeed constructs a new short proof of Arrow’s theorem along this line.

Our second proof shows that the classical “decisiveness” approach can also provide a one-shot proof of the theorem. The key of our proof is the order of lemmas (the field expansion and group contraction lemmas). In the standard proof of the decisiveness approach, the invariance property of the decisive structure is first proved (the field expansion lemma), and an influential individual is next identified (the group contraction lemma). In our proof, an influential individual is first identified and the decisive structure is clarified next. This order is the same as that in the pivotal voter approach: a pivotal voter is first identified, and then, his decisive power is proved. Hence, our proof is similar to the pivotal voter approach in that an influential individual is identified in the first step.

The difference between our proof and the pivotal voter approach is in what kind of influence is focused. A pivotal voter is an individual who has an influence over a particular pair under a particular profile; we focus on an individual who has an influence over a particular pair under all profiles.⁸