Approval voting and Arrow’s impossibility theorem

Abstract

Approval voting has attracted considerable attention in voting theory, but it has rarely been investigated in an Arrovian framework of collective preference (”social welfare”) functions and never been connected with Arrow’s impossibility theorem. The article explores these two directions. Assuming that voters have dichotomous preferences, it first characterizes approval voting in terms of its collective preference properties and then shows that these properties become incompatible if the collective preference is also taken to be dichotomous. As approval voting and majority voting happen to share the same collective preference function on the dichotomous domain, the positive result also bears on majority voting, and is seen to extend May’s and Inada’s early findings on this rule. The negative result is a novel and perhaps surprising version of Arrow’s impossibility theorem, because the axiomatic inconsistency here stems from the collective preference range, not the individual preference domain.

1 Introduction

Approval voting is the rule by which voters can cast votes for as many candidates as they wish, giving no more than one vote to each of them, and those candidates with the greatest vote total are elected. For the purpose of theoretical investigations, approval voting has been defined to be a social choice function, i.e., a mapping that associates a nonempty subset of candidates—the social choice—to every profile of individual characteristics—the individuals’ preferences among candidates in one version, and their choices among them in another version. When it comes to voting generally, this choice-theoretic formalism has good descriptive value and it has the conceptual advantage of connecting well with strategic inquiries, including the landmark Gibbard–Satterthwaite theorem. Since Brams and Fishburn (1978) and Fishburn (1978a, b), it has been applied very effectively to approval voting.¹

The present article departs from this tradition by defining approval voting as a social welfare function, or as we will rather call it to avoid irrelevant welfaristic suggestions, a collective preference function, that is to say, a mapping that associates a collective preference among candidates to every profile of individual preferences among these candidates. This formalism makes sense for a voting rule if the latter can be reinterpreted as an evaluation procedure, which is the case for approval voting. Here, the individuals would be asked to rank candidates into, say, “satisfactory” and “unsatisfactory”, with their answers being pooled, but not necessarily followed by any actual collective decision (think of an opinion poll as against a real vote). To redescribe voting rules in this way is in fact an old idea of social choice theory, dating back to Arrow himself. He thought his original formalism to be applicable to them, and not only to welfare criteria, and accordingly introduced a collective preference function for majority voting (see 1963, ch. V). By taking the same step for approval voting, we shift the focus of its analysis from strategy-proofness to the related, but distinct condition of independence of irrelevant alternatives, as well as further Arrovian conditions such as positive responsiveness and the Pareto principle. To the best of our knowledge, Ju (2010) is the only scholar of approval voting who has already adopted a collective preference framework.

When approval voting is redefined in this way, it is natural to impose the restriction that individual preferences be dichotomous, i.e., have two indifference classes. Actually, since the early days, this restriction is also made in quite a few choice-theoretic analyses.² It will be upheld here, with two possibilities being investigated in turn: the simply dichotomous case, where only individual preferences are dichotomous, and the twice dichotomous case, where collective preferences also are. We present a characterization of approval voting in the former case, and one of dictatorship—thus an impossibility theorem—in the latter case. We may interpret the two results together as saying that the conditions for approval voting become inconsistent when the range of the collective preference function is subjected to the same dichotomous restriction as the domain. Our positive result relates to Ju’s (2010) characterization, which also belongs to the simply dichotomous case; arguably, we go one step further into the Arrovian foundations of approval voting. As to our negative result, it is unprecedented, and it appears to be surprising compared with existing Arrovian impossibilities under restricted domains, because the logical ingredients of these impossibilities are missing here—in particular, the free triple property fails.

In the simply dichotomous case, the collective preference function of approval voting coincides with that of majority voting, as Arrow and followers have defined it. This observation connects our positive result with two classics, i.e., May’s (1952) characterization of majority voting between two candidates, which we considerably extend, and Inada’s (1964) proof that majority voting behaves well with dichotomous individual preferences, which we also recover and deepen (by replacing Inada’s mere claim of possibility with a proper characterization). On the permissive dichotomous domain, majority voting can only be threatened by range restrictions, and this is what the negative result of the paper illustrates.

2 Definitions and aggregative conditions

As usual, a weak preference ordering $R$ on a set $X$ means a binary relation that is transitive, reflexive and complete; equivalently $R$ has an asymmetric part $P$ and a symmetric part $I$, which satisfy the PP, PI, IP, II variants of transitivity. The statements xPy, xIy, xRy have their standard readings, i.e., “$x$ is strictly preferred to $y$”, “$x$ is indifferent to $y$”, “$x$ is strictly preferred or indifferent to $y$”. An indifference class for $R$ is one of the equivalence classes generated by $I$, i.e., a set of the form $\left\{ x\in X:xIx_{0}\right\}$ for some fixed $x_{0}\in X$.

As a particular case of $R$ on $X$, a dichotomous weak preference ordering has one or two non-empty indifference classes. It satisfies the $PP$ variant of transitivity vacuously and (for a sufficient number of elements) the PI, IP and II variants non-vacuously. It can also be described in terms of its indifference classes directly. If $R$ has two indifference classes, we denote by $H$ and $L$ the higher and lower one, respectively, and if $R$ has only one indifference class, a case of complete indifference, we denote this class by CI. The obvious translation rules are:

$$\begin{aligned} xPy&\Leftrightarrow x\in H,y\in L \\ xIy&\Leftrightarrow \text {either }x,y\in H\text { or }x,y\in L\text { or } x,y\in CI\text {.} \end{aligned}$$

Define $\mathcal {O}$ to be the set of all weak preference orderings on $X$, and $\mathcal {D}\subset \mathcal {O}$ to be the set of dichotomous weak preference orderings on $X$.

The technical literature sometimes defines dichotomous preferences to have exactly two non-empty indifference classes, thus excluding complete indifference (e.g., Brams and Fishburn 1978). We show below that our results extends to this stronger definition at a modest cost.

Given a set of candidates $X$ with cardinality $\mid X\mid \ge 3$ and a finite set of voters $N=\left\{ 1,\ldots ,n\right\}$ with $n\ge 2$, we define a collective preference function (CPF) to be a mapping

$$\begin{aligned} F:(R_{1},\ldots ,R_{n})\longmapsto R\text {.} \end{aligned}$$

Throughout, the domain of $F$ will be dichotomous, with two cases considered in succession, i.e., $F:\mathcal {D}^{n}\rightarrow \mathcal {O}$ and $F: \mathcal {D}^{n}\rightarrow \mathcal {D}$; we call them the simply dichotomous and twice dichotomous case, respectively.

Correspondingly, the CPF associated with approval voting can be stated in two different ways.

Notation 1

For any profile $(R_{1},\ldots ,R_{n})$ in $\mathcal {O}^{n}$ or $\mathcal {D}^{n}$ , we put $N(xP_{i}y)=\left\{ i:xP_{i}y\right\}$ and $n(xP_{i}y)=\left| \left\{ i:xP_{i}y\right\} \right|$ (similarly for $R_{i}$, $I_{i}$), and $N(x\in H_{i})=\left\{ i:x\in H_{i}\right\}$ and $n(x\in H_{i})=\left| \left\{ i:x\in H_{i}\right\} \right|$ (similarly for $L_{i}$, $CI_{i}$), and we put

$$\begin{aligned} Max(R_{1},\ldots ,R_{n})=\left\{ x\in X:n(x\in H_{i})\ge n(y\in H_{i}),\forall y\in X\right\} \text {.} \end{aligned}$$

Definition 1

$F$ is approval voting* if, for all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$, $xPy\Leftrightarrow n(x\in H_{i})>n(y\in H_{i}).$

Approval voting* trivially defines an ordering for any profile, and it has range $\mathcal {O}$, not $\mathcal {D}$, if $\mid X\mid \ge 3$. However, we may force the $\mathcal {D}$ range in redefining the CPF thus.

Definition 2

F is approval voting** if, for every $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$,

• if $Max(R_{1},\ldots ,R_{n})\ne X$, then

  $$\begin{aligned} H=Max(R_{1},\ldots ,R_{n})\text { and }L=X{\setminus } Max(R_{1},\ldots ,R_{n})\text {;} \end{aligned}$$

• if $Max(R_{1},\ldots ,R_{n})=X$, then $R=CI$.

Under dichotomous individual preferences, majority voting has the same CPF as approval voting*. Arrow (1963, p. 58) defined the CPF of majority voting by the condition that, for all $(R_{1},\ldots ,R_{n})$ in the domain, $xRy$ if

$$\begin{aligned} n(xR_{i}y)\ge n(yR_{i}x)\text {, or equivalently }n(xP_{i}y)\ge n(yP_{i}x) , \end{aligned}$$

and this definition has been endorsed by social choice theory. If the domain is $\mathcal {D}^{n}$ rather than $\mathcal {O}^{n}$, it collapses into that just given above—we skip the trivial argument. Since approval voting* always defines an ordering, we have by the same token proven Inada’s (1964) classic observation that majority voting defines a transitive CPF on the dichotomous domain.

Now to the properties that CPF may satisfy. We begin by listing those which Arrow (1963) famously declared to be mutually inconsistent.

Notation 2

For all $(R_{1},\ldots ,$ $R_{n})$, $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })$ in $\mathcal {O}^{n}$ or $\mathcal {D}^{n}$, and all $x,y,z,w\in X$, we write $xR_{i}y\approx zR_{i}^{\prime }w$ instead of ($xR_{i}y\Leftrightarrow zR_{i}^{\prime }w$ and $yR_{i}x\Leftrightarrow wR_{i}^{\prime }z$).

Condition 1

Independence of irrelevant alternatives (IIA): For all $(R_{1},\ldots ,$ $R_{n})$, $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xR_{i}y\approx xR_{i}^{\prime }y$ for all $i\in N$, then $xRy\Leftrightarrow xR^{\prime }y$.

Condition 2

Weak Pareto (WP): For all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xP_{i}y$ for all $i\in N$, then $xPy$.

Condition 3

Non-dictatorship (ND): There is no $j\in N$ such that for all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xP_{j}y$, then $xPy$.

Both approval voting* and approval voting** satisfy WP. However, only the former, not the latter, satisfies IIA. The following 3-candidate, 2-individual profiles $(R_{1},R_{2})$, $(R_{1}^{\prime },R_{2}^{\prime })$ illustrates the failure: $xP_{1}yI_{1}z$, $zP_{2}yI_{2}x$ and $xI_{1}^{\prime }z$ $P_{1}^{\prime }y$, $zP_{2}^{\prime }yI_{2}^{\prime }x$; by approval voting**, $x,z\in H,y\in L$, so $xPy$, and $z\in H^{\prime },x,y\in L^{\prime }$, so $xI^{\prime }y$, contradicting IIA. Since approval voting* also satisfies ND, and then all of Arrow’s conditions, his theorem indicates that the domain makes a difference, i.e., $\mathcal {D}^{n}$ does not behave like $\mathcal {O}^{n}$ (this is in effect Inada’s observation). Arrow’s theorem does not teach anything on approval voting** since this CPF does not satisfy IIA.³ The last section of the paper shows that this violation is forced by the range restriction.

3 The collective preference function of approval voting (or majority voting)

Here we characterize approval voting* (or equivalently majority voting) in terms of variant Arrovian conditions. First, this function obviously satisfies a vast strengthening of ND:

Condition 4

Anonymity (A): For all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ and all permutations $\sigma$ of $\left\{ 1,\ldots ,n\right\}$, $F(R_{1},\ldots ,R_{n})=$ $F(R_{\sigma (1)},\ldots ,R_{\sigma (n)})$.

Second, approval voting* satisfies Pareto conditions besides WP:

Condition 5

Pareto indifference (PI): For all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xI_{i}y$ for all $i\in N$, then $xIy$.

Condition 6

Strict Pareto (SP): For all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xR_{i}y$ for all $i\in N$ and $xP_{i}y$ for some $i$, then $xPy$.

It turns out that approval voting* can be characterized by adding IIA to these three conditions, or rather to the first two and WP, because this set will be shown to entail SP.

Theorem 1

A collective preference function $F:\mathcal {D}^{n}\rightarrow \mathcal {O}$ is approval voting* if and only if it satisfies IIA, A, PI, and WP.

The sufficiency part relies on three lemmas. The first derives a classic condition that strengthens IIA and is sometimes taken to be primitive by CPF theory.

Condition 7

Neutrality (N): For all $(R_{1},\ldots ,R_{n})$, $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D}^{n}$ and all $x,y,z,w\in X$, if $xR_{i}y\approx zR_{i}^{\prime }w$ for all $i\in N$, then $xRy\Leftrightarrow zR^{\prime }w$.

Lemma 1

If $F:\mathcal {D}^{n}\rightarrow \mathcal {O}$ satisfies IIA and PI, it satisfies N.

Proof

Consider first the case of four distinct $x,y,z,w\in X$. By assumption, $(R_{1},\ldots ,R_{n})$ and $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D} ^{n}$ are s.t. $xR_{i}y\approx zR_{i}^{\prime }w$ for all $i\in N$. Take $( \overline{R}_{1},\ldots ,\overline{R}_{n})\in \mathcal {D}^{n}$ s.t. $xR_{i}y\approx x\overline{R}_{i}y$ for all $i\in N$, and s.t. $x\overline{I} _{i}z$ and $y\overline{I}_{i}w$ for all $i\in N$. Thus, by construction, $z \overline{R}_{i}w\approx zR_{i}^{\prime }w$ for all $i\in N$. Suppose that $xRy$. Then, $x\overline{R}y$ follows from IIA, $z\overline{R}w$ from PI, and finally $zR^{\prime }w$ from IIA.

Related proofs take care of the two cases in which there are three distinct elements among $x,y,z,w\in X$, $x\ne y$, and the position of the common element is the same in the two pairs, i.e., $x=z$ or $y=w$. Now, suppose that the common element changes position, i.e., $x=w$ or $y=z$. We give a proof for the former case. By assumption, $(R_{1},\ldots ,R_{n})$ and $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D}^{n}$ are s.t. $xR_{i}y\approx zR_{i}^{\prime }x$ for all $i\in N$. Take $(\overline{R} _{1},\ldots ,\overline{R}_{n})\in \mathcal {D}^{n}$ s.t. $xR_{i}y\approx z \overline{R}_{i}y$ for all $i\in N$. From one of the cases with unchanged positions, $xRy\Leftrightarrow z\overline{R}y$. By construction, $zR_{i}^{\prime }x$ $\approx z\overline{R}_{i}y$ for all $i\in N$, so from the other case, $zR^{\prime }x$ $\Leftrightarrow z\overline{R}y$, and finally $xRy\Leftrightarrow$ $zR^{\prime }x$.

If there are three distinct elements among $x,y,z,w\in X$, and $x=y$, or $z=w$, N reduces to PI.

If there are two distinct elements, say $x$ and $y$, which do not exchange positions, N reduces to IIA. Otherwise, suppose that $(R_{1},\ldots ,R_{n})$ and $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })$ $\in \mathcal { D}^{n}$ are s.t. $xR_{i}y\approx yR_{i}^{\prime }x$ for all $i\in N$. Take $z\ne x,y$ and $(\overline{R}_{1},\ldots ,\overline{R}_{n})\in \mathcal {D}^{n}$ s.t. $xR_{i}y\approx x\overline{R}_{i}z$ for all $i\in N$. It follows that $xRy\Leftrightarrow x\overline{R}z$. Take $(\overline{\overline{R}}_{1},\ldots , \overline{\overline{R}}_{n})\in \mathcal {D}^{n}$ s.t. $yR_{i}^{\prime }x\approx y\overline{\overline{R}}_{i}z$ for all $i\in N$. It follows that $yR^{\prime }x\Leftrightarrow y\overline{\overline{R}}z$. Now, by construction, $x\overline{R}_{i}z$ $\approx y\overline{\overline{R}}_{i}z$ for all $i\in N$, whence $x\overline{R}z\Leftrightarrow y\overline{\overline{ R}}z$. Combining the equivalences, one gets $xRy\Leftrightarrow yR^{\prime }x$, as desired. $\square$

The second lemma derives another condition that is sometimes also taken to be primitive. In preparation for the next section, we give it in two variants, the former being weaker than the latter. They are distinguished only by their consequent clauses.

Condition 8

Positive responsiveness 1 (PR1): For all $(R_{1},\ldots ,R_{n})$, $(R_{1}^{\prime },\ldots ,$ $R_{n}^{\prime })\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xP_{i}y\Rightarrow xP_{i}^{\prime }y$ and $xI_{i}y\Rightarrow xR_{i}^{\prime }y$ for all $i\in N$, and $yP_{j}x$ and $xR_{j}^{\prime }y$, or $xI_{j}y$ and $xP_{j}^{\prime }y$, for some $j\in N$, then $xPy\Rightarrow xP^{\prime }y$.

Condition 9

Positive responsiveness 2 (PR2): For all $(R_{1},\ldots ,R_{n})$, $(R_{1}^{\prime },\ldots ,$ $R_{n}^{\prime })\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xP_{i}y\Rightarrow xP_{i}^{\prime }y$ and $xI_{i}y\Rightarrow xR_{i}^{\prime }y$ for all $i\in N$, and $yP_{j}x$ and $xR_{j}^{\prime }y$, or $xI_{j}y$ and $xP_{j}^{\prime }y$, for some $j\in N$, then $xRy\Rightarrow xP^{\prime }y$.

Lemma 2

If $F:\mathcal {D}^{n}\rightarrow \mathcal {O}$ satisfies N and SP, it satisfies PR2.

Proof

To derive PR2, we first assume that $(R_{1},\ldots ,R_{n})$, $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D}^{n}$ and $x,y\in X$ meet the antecedent condition without any full reversal of strict preference, i.e., without any $j$ s.t. $yP_{j}x$ and $xP_{j}^{\prime }y$.

Take $z\ne x,y$ and $(\overline{R}_{1},\ldots ,\overline{R}_{n})\in \mathcal {D} ^{n}$ so defined: for all $i\in N$,

• if $xP_{i}y$ and $xP_{i}^{\prime }y$, then $x\overline{P}_{i}y \overline{I}_{i}z$; if $yP_{i}x$ and $yP_{i}^{\prime }x$, then $z\overline{I} _{i}y\overline{P}_{i}x$; if $xI_{i}y$ and $xI_{i}^{\prime }y$, then $x \overline{I}_{i}y\overline{I}_{i}z$;

• if $yP_{i}x$ and $xI_{i}^{\prime }y$, then $z\overline{P}_{i}x \overline{I}_{i}y$; if $xI_{i}y$ and $xP_{i}^{\prime }y$, then $z\overline{I} _{i}x\overline{P}_{i}y$.

Thus, for all $i\in N$, $xR_{i}y\approx x\overline{R}_{i}z$, $z \overline{R}_{i}y$, and $xR_{i}^{\prime }y\approx x\overline{R}_{i}y$. We also note by inspecting the possibilities that for some $i$, $z\overline{P} _{i}y$. Now, suppose that $xRy$. Then, $x\overline{R}z$ by N, and because SP entails that $z\overline{P}y$, it follows that $x \overline{P}y$, hence $xP^{\prime }y$ by IIA. This completes the proof of PR2 in the case just considered.

If $(R_{1},\ldots ,R_{n})$, $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D} ^{n}$ and $x,y\in X$ meet the antecedent of PR2 in full generality, take $(R_{1}^{\prime \prime },\ldots ,R_{n}^{\prime \prime })\in \mathcal {D}^{n}$ s.t., for all $i\in X$, $xI_{i}^{\prime \prime }y$ if $yP_{i}x$ and $xP_{i}^{\prime }$ $y$, and $xR_{i}^{\prime \prime }y\approx xR_{i}^{\prime }y$ otherwise. Suppose that $xRy$. By the case just proved, $xP^{\prime \prime }y$, and again by this case, $xP^{\prime }y$. $\square$

The third lemma shows that SP can be replaced by WP in the characterization of approval voting*.

Lemma 3

If $F:\mathcal {D}^{n}\rightarrow \mathcal {O}$ satisfies N, WP and A, it satisfies SP.

Proof

Fix $x,y$ and a sequence of profiles $(R_{1}^{k},\ldots ,R_{n}^{k})\in \mathcal {D }^{n}$, $k\in \left\{ 1,\ldots ,n\right\}$, s.t.

$$\begin{aligned} xP_{i}^{k}y,1\le i\le k\text { and }xI_{i}^{k}y,k+1\le i\le n\text {.} \end{aligned}$$

In view of N and A, it is sufficient to show that SP holds for this pair and this sequence (note that $k=n$ corresponds to WP). The proof goes by induction on $k$.

• $k=1$. Suppose that $yR^{1}x$; we reach a contradiction with WP by showing that $yR^{l}x$ holds for all $l\in \left\{ 1,\ldots ,n\right\}$, hence in particular for $l=n$. The initial supposition covers the case $l=1$ ; now suppose we have proved that $yR^{l}x$ for some $l\in \left\{ 1,\ldots ,n-1\right\}$. Let us take the profiles $(R_{1}^{l+1},\ldots ,R_{n}^{l+1}) \in \mathcal {D}^{n}$, and for some $z\ne x,y$, $(\overline{R}_{1}^{l+1},\ldots , \overline{R}_{n}^{l+1})\in \mathcal {D}^{n}$ s.t.

  $$\begin{aligned} x\overline{R}_{i}^{l+1}y&\approx xR_{i}^{l+1}y\text { for all }i\in N\text { , } \\ z\overline{I}_{i}^{l+1}y\text { for all }i&\ne l+1\text { and }z\overline{I} _{l+1}^{l+1}x\overline{P}_{l+1}^{l+1}y\text {.} \end{aligned}$$

  Then, we apply N in a comparison with $(R_{1}^{l},\ldots ,R_{n}^{l})$, and N and A in a comparison with $(R_{1}^{1},\ldots ,R_{n}^{1})$, to get $z\overline{R}^{l+1}x$ and $y\overline{R} ^{l+1}z$, hence $y\overline{R}^{l+1}x$. So we have proved by induction that $yR^{l}x$ holds for all $l\in \left\{ 1,\ldots ,n\right\}$, as desired.

• Suppose SP holds for $(R_{1}^{k},\ldots ,R_{n}^{k})$ and consider $(R_{1}^{k+1},\ldots ,R_{n}^{k+1})$. In the previous definition of $(\overline{R} _{1}^{l+1},\ldots ,\overline{R}_{n}^{l+1})$, replace $l$ by $k$; this defines a profile $(\overline{R}_{1}^{k+1},\ldots ,\overline{R}_{n}^{k+1})$ which, by comparison with $(\overline{R}_{1}^{k},\ldots ,\overline{R}_{n}^{k})$, satisfies $x\overline{P}^{k+1}z$ by SP, and by comparison with $(\overline{R} _{1}^{1},\ldots ,\overline{R}_{n}^{1})$, satisfies $z\overline{P}^{k+1}y$ by A and SP. Hence $x\overline{P}^{k+1}y$, as was to be proved.$\square$

Proof

(Theorem 1) Suppose that there is some $F:\mathcal {D}^{n}\rightarrow \mathcal {O}$ that is not approval voting*. Then, there are $(R_{1},\ldots ,R_{n})\in$ $\mathcal {D}^{n}$ and $x,y\in X$ s.t. either (i) $n(x\in H_{i})=n(y\in H_{i})$ and $xPy$, or (ii) $n(x\in H_{i})>n(y\in H_{i})$ and $yRx$.

In case (i), there are three groups of individuals, i.e., $N(xP_{i}y),$ $N(yP_{i}x),$ $N(xI_{i}y)$ with $n(xP_{i}y)=n(yP_{i}x)$. The first two groups are non-empty by PI. We may take a permutation $\sigma$ that interchanges them and leaves the third group unchanged; by A, the resulting profile $(R_{\sigma (1)},\ldots ,R_{\sigma (n)})$ has the collective preference $xP_{\sigma }y$. Now, observing that for all $i\in N$, $xR_{i}y\approx yR_{\sigma (i)}x$, we apply N to the profile to get the contradiction that $yP_{\sigma }x$.

In case (ii), the three groups of individuals $N(xP_{i}y),N(yP_{i}x),N(xI_{i}y)$ are s.t. $n_{1}=n(xP_{i}y)>n_{2}=n(yP_{i}x)$. The second group is non-empty by SP, and from the inequality, the first group also is. Take a permutation $\sigma$ that interchanges $n_{2}$ individuals in $N(xP_{i}y)$ with those in $N(yP_{i}x)$ and leaves the position of any others unchanged; by A, the resulting profile $(R_{\sigma (1)},\ldots ,R_{\sigma (n)})$ has the collective preference $yR_{\sigma }x$. Now, modify this profile into $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })$ by putting $yP_{i}^{\prime }x$ if $i=\sigma (i)$ is any of the remaining $n_{1}-n_{2}$ individuals of $N(xP_{i}y)$ and leaving any other individual’s preference the same. Given this reinforcement of strict preference for $y$, PR2 entails that $yP^{\prime }x$. However, $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })$ also modifies $(R_{1},\ldots ,R_{n})$ in such a way that N entails that $xR^{\prime }y$, a contradiction. $\square$

Let us briefly check the logical independence of each condition in Theorem 1. That PI is independent of the others can be seen by revising the CPF of approval voting* so as to break ties between $x$ and $y$ when $n(x\in H_{i})=n(y\in H_{i})$; such a function will satisfy all conditions of approval voting* except for PI. For example, one may single out $\overline{x},\overline{y}\in X$ and decide that any tie between either $\overline{x}$ or $\overline{y}$ and $z$ $\ne$ $\overline{x}, \overline{y}$ is broken in favour of $z$, while ties between $\overline{x}$ and $\overline{y}$ are broken thus: $\overline{x}$ prevails if the equal number of supporters is even, and $\overline{y}$ prevails if it is odd; any other tie occurring in $X$ is left unbroken. Not every CPF that satisfies all conditions but PI reduces to a tie-breaking revision of approval voting*.⁴ Fix a function $w$ from $X$ to $\left[ 0,n-1\right]$, with the $w(x)$ not all equal, and replace approval voting* by the following CPF: for all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$,

$$\begin{aligned} xPy\Leftrightarrow n(x\in H_{i})+w(x)>n(y\in H_{i})+w(y)\text {.} \end{aligned}$$

This CPF obviously satisfies IIA and A, and obviously violates PI; it satisfies WP by the range condition on $w$. It differs from the previous class of examples because, for suitable numerical values, it can violate even the strict preference part of approval voting* and it can create ties that this CPF does not have. The conceptual dissimilarity between the two classes suggests that very little structure is left when the only conditions are IIA, A and WP. We eschew the problematic characterization task in this paper.

Similarly, that IIA is independent of the other conditions follows from considering the CPF that corresponds to equal cumulative voting, which is another refinement of approval voting: each voter has one vote and divides it evenly among the candidates he approves of; candidates with the greatest total of fractional votes are elected. The independence of A results from considering dictatorial CPF.

Inspection of the proofs shows that the complete indifference ordering $CI\in \mathcal {D}$ does not occur as an auxiliary profile unless $\mid X\mid =3$ (see the relevant step in the proof of Lemma 2). Thus, denoting $\mathcal {D}^{-}$ $=\mathcal {D}{\setminus } \left\{ CI\right\}$, we have the following extension of the theorem.

Remark 1

If $\mid X\mid \ge 4$, the theorem also holds for $F:(\mathcal {D}^{-} \mathcal {)}^{n}\rightarrow \mathcal {D}$.

With this extension at hand, we can redefine dichotomous preferences to have exactly two indifference classes, as in some of the other work on approval voting.

To the best of our knowledge, only Ju (2010) has characterized approval voting in terms of CPF.⁵ Assuming the simply dichotomous framework, he shows that plurality voting, hence implicitly approval voting*, is that CPF which satisfies A, N , plus a positive responsiveness and a non-trivality condition, here denoted as PR3 and NT, which we now define.

Condition 10

Positive responsiveness 3 (PR3): For all $(R_{1},\ldots ,R_{n})$, $(R_{1}^{\prime },\ldots ,$ $R_{n}^{\prime })\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xP_{i}y\Rightarrow xP_{i}^{\prime }y$ and $xI_{i}y\Rightarrow xR_{i}^{\prime }y$ for all $i\in N$, and $yP_{i}x$ and $xR_{i}^{\prime }y$, or $xI_{i}y$ and $xP_{i}^{\prime }y$, for some $i$, then $xRy\Rightarrow xR^{\prime }y$.

Condition 11

Non-triviality (NT): $F$ does not have the constant value $CI$.

PR3 is weaker than PR2 and by itself incomparable with PR1. However, we can obtain Ju’s characterization from ours by an added step of reasoning. Since N entails IIA and PI , it is sufficient to show that N, PR3, and NT entail WP, and we will have achieved the desired logical connection.

Corollary 1

(Ju 2010) A collective preference function $F:\mathcal {D}^{n}\rightarrow \mathcal {O}$ is approval voting* if and only if it satisfies N, A, PR3 and NT.

Proof

To be shown that WP holds. Given $(R_{1},\ldots ,R_{n})\in \mathcal {D} ^{n}$ and $x,y\in X$ satisfying $xP_{i}y$, $i\in N$, take $z\ne x,y$, $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D}^{n}$ s.t. $zI_{i}^{\prime }xP_{i}^{\prime }y$, $i\in N$, and $(R_{1}^{\prime \prime },\ldots ,R_{n}^{\prime \prime })\in \mathcal {D}^{n}$ s.t. $zP_{i}^{\prime \prime }xI_{i}^{\prime \prime }y$, $i\in N$. N (or PI) leads to $xI^{\prime \prime }y$, PR3 to $xR^{\prime }y$, and IIA to $xRy$. It remains to exclude that $xIy$. If this indifference holds, we can interchange $x$ and $y$ in $(R_{1},\ldots ,R_{n})$ and obtain $(\overline{R}_{1},\ldots ,\overline{R}_{n})\in \mathcal {D}^{n}$ with $y\overline{P}_{i}x$, $i\in N$, and thus $y\overline{I}x$ by $N$. Now, take any profile whatever: by an application of PR3 based on either $(R_{1},\ldots ,R_{n})$ or $(\overline{R}_{1},\ldots ,\overline{R}_{n})$, it follows that $x$ and $y$ are collectively indifferent. This would hold for any choice of $x,y\in X$, hence violate NT. $\square$

Conversely, one may recover our characterization from Ju’s once Lemmas 1 and 2 have been established—his theorem then playing the role of Lemma 3 and the End of Proof. As this further comparison suggests, the two equivalent sets of conditions for approval voting* are not quite at the same axiomatic level. In essence, by adding Lemmas 1 and 2, we replace N by the more Arrovian IIA condition, plus PI, and we reformulate PR the way it should be when this change it made.

As already said, the other available characterizations of approval voting are choice-theoretic, hence not directly comparable with ours. However, Vorsatz (2007) defines social choice functions on profiles of dichotomous individual preferences—our simply dichotomous case—and characterizes the social choice function of approval voting* in terms of four conditions, i.e., Anonymity, Neutrality, Strategyproofness and Strict monotonicity, which are reminiscent of ours. Neutrality is like a much weaker form of N, Strict monotonicity suggests PR3, and IIA holds in effect, as Vorsatz derives its choice-theoretic version from Neutrality and Strategyproofness. By contrast, following Fishburn (1978a, b), Sato (2014) defines social choice functions on profiles individual choices rather than of dichotomous preferences. Thus, his characterization in terms of Anonymity, Neutrality and Faithfulness (another monotonicity condition) is more remote.⁶

If we interpret our CPF in terms of majority voting, as the domain permits, we have a further connection with May’s (1952) classic result on majority voting between two candidates. Expanding on Arrow’s theorem for this special case, May characterized the CPF of majority voting by three conditions, which are N, A and PR2 when translated into the present framework. This is but a modest corollary to Theorem 1. As the latter makes clear, the relevant cardinality restriction bears on the voters’ sets of equivalence classes, and not on the set of candidates. Concerning Inada’s (1964) observation, we have extended it by fully characterizing the CPF of majority voting on the dichotomous domain, instead of simply noting that it satisfies Arrow’s ordering condition on this domain.

4 From approval voting to dictatorship

In this section, we shift to the twice dichotomous case and demonstrate that the conditions characterizing approval voting* in the simply dichotomous case now characterize dictatorship. We actually prove the more powerful result that Arrow’s theorem with its initial conditions holds in the twice dichotomous case.

Theorem 2

No collective preference function $F:\mathcal {D}^{n}\rightarrow \mathcal {D}$ satisfies IIA, WP and ND.

The proof goes through four lemmas.

Condition 12

Pareto Preference (PP): For all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ and all $x,y\in X$, if $xR_{i}y$ for all $i\in N$, then $xRy$.

Lemma 4

If a collective preference function $F:\mathcal {D}^{n}\rightarrow \mathcal {D}$ satisfies IIA and WP, it satisfies PI and PP.

Proof

Consider $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ and $x,y\in X$ s.t. $xR_{i}y$ for all $i\in N$. Take $z\ne x,y$ and $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D}^{n}$ s.t. $xP_{i}^{\prime }z$ and $xR_{i}y\approx xR_{i}^{\prime }y$. (If $xP_{i}y$, $y\in L_{i}^{\prime }$ and if $xI_{i}y$, $y\in H_{i}^{\prime }$). If $xI_{i}y$ for all $i\in N$, then $xI_{i}^{\prime }y$ for all $i\in N$. In this case, WP entails that $xP^{\prime }z$ and $yP^{\prime }z$, so $xI^{\prime }y$ since $F$ has range $\mathcal {D}$ , and $xIy$ by IIA. This completes the derivation of PI. In the general case where $xR_{i}y$ for all $i\in N$, WP entails that $xP^{\prime }z$, and the $\mathcal {D}$ range that $xR^{\prime }y$, whence $xRy$ by IIA. This completes the derivation of PP. $\square$

Lemma 5

If a collective preference function $F:\mathcal {D}^{n}\rightarrow \mathcal {D}$ satisfies IIA and PI, it satisfies N.

Proof

Same as for Lemma 1. (The $\mathcal {D}$ range plays no role in this proof).$\square$

Lemma 6

If a collective preference function $F:\mathcal {D}^{n}\rightarrow \mathcal {D}$ satisfies N and WP, it satisfies PR1.

Proof

As in the proof of Lemma 2, we begin by assuming that $(R_{1},\ldots ,R_{n})$, $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D}^{n}$ and $x,y\in X$ meet the antecedent condition without any full reversal of strict preference. With $z\ne x,y$ and $(\overline{R}_{1},\ldots ,\overline{R} _{n})\in \mathcal {D}^{n}$ as defined in this proof, we have again that, for all $i\in N$, $xR_{i}y\approx x\overline{R}_{i}z$, $z\overline{R}_{i}y$, and $xR_{i}^{\prime }y\approx x\overline{R}_{i}y$. Since N implies IIA, PP holds by Lemma 4, hence $z\overline{R}y$. Now if $xPy$, then $x\overline{P}z$ by N, and from the last fact, $x \overline{P}y$, whence $xP^{\prime }y$ by IIA. The end of the proof parallels that of Lemma 2.$\square$

A group $M\subseteq N$ is said to be decisive if for all pairs $(x,y)\in X^{2}$ and all profiles $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$,

$$\begin{aligned} xP_{i}y,i\in M\Longrightarrow xPy\text {,} \end{aligned}$$

and it is said to be semi-decisive on the pair $(x,y)\in X^{2}$ in the profile $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ if

$$\begin{aligned} xP_{i}y,i\in M\text {, }yR_{i}x,i\in N{\setminus } M\text {, and }xPy\text {.} \end{aligned}$$

Lemma 7

If a collective preference function $F:\mathcal {D}^{n}\rightarrow \mathcal {D}$ satisfies N and PR1, any group $M\subseteq N$ that is semi-decisive on a pair $(x,y)\in X^{2}$ in a profile $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ is decisive.

Proof

Take $M$ as specified, partition $N{\setminus } M$ into $G_{1}=$ $\left\{ i\mid yP_{i}x\right\}$ and $G_{2}=\left\{ i\mid yI_{i}x\right\}$, and consider the profiles $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })\in \mathcal {D}^{n}$ s.t.

$$\begin{aligned} xP_{i}^{\prime }y,i\in M\text {, }yP_{i}^{\prime }x,i\in G_{1}\text {, and } yP_{i}^{\prime }x\text { for at least one }i\in G_{2}\text {.} \end{aligned}$$

If we show that $M$ is semi-decisive on the given $(x,y)$ for all such profiles $(R_{1}^{\prime },\ldots ,R_{n}^{\prime })$, the conclusion that $M$ is decisive will follow by PR1 and N.

To establish the desired property that $xP^{\prime }y$, take $z\ne x,y$ and $(R_{1}^{\prime \prime },\ldots ,R_{n}^{\prime \prime })$ s.t. for all $i\in N$, $zR_{i}^{\prime \prime }y\approx xR_{i}y$ and $xR_{i}^{\prime \prime }y\approx xR_{i}^{\prime }y$. N entails that $zP^{\prime \prime }y$ and would entail $yP^{\prime \prime }x$ if $yP^{\prime }x$ held, but this is prohibited by the $\mathcal {D}$ range. Hence $xR^{\prime }y$. It remains to show that $xI^{\prime }y$ is impossible.

If $xI^{\prime }y$, then $xI^{\prime \prime }y$ by N, and $zP^{\prime \prime }x$ follows. From IIA, any profile $(R_{1}^{\prime \prime \prime },\ldots ,$ $R_{n}^{\prime \prime \prime })\in \mathcal {D}^{n}$ s.t. for all $i\in N$, $zR_{i}^{\prime \prime \prime }x$ $\approx zR_{i}^{\prime \prime }x$ satisfies $zP^{\prime \prime \prime }x$. The $\mathcal {D}^{n}$ domain contains such a profile with $xR_{i}^{\prime \prime \prime }y\approx xR_{i}y$ for all $i\in N$. (For a proof, see the construction:

• $x,z\in H_{i}^{\prime \prime \prime }$ and $y\in L_{i}^{\prime \prime \prime }$ if $i\in M$;

• $y\in H_{i}^{\prime \prime \prime }$ and $x,z\in L_{i}^{\prime \prime \prime }$ if $i\in G_{1}$;

• $xI_{i}^{\prime \prime \prime }yI_{i}^{\prime \prime \prime }z$ if $i\in G_{2}$ and $xI_{i}^{\prime }y$;

• $z\in H_{i}^{\prime \prime \prime }$ and $x,y\in L_{i}^{\prime \prime \prime }$ if $i\in G_{2}$ and $yP_{i}^{\prime }x$.

Now, IIA entails $xP^{\prime \prime \prime }y$, which is impossible given the $\mathcal {D}$ range. This completes the proof that $xP^{\prime }y$. $\square$

Define $V\subseteq 2^{N}$ to be the set of all decisive groups. To contradict ND is tantamount to showing that $V$ contains a singleton, and we proceed to this last stage of the argument.

Proof

(Theorem 2) The set $V$ is non-empty because $N\in V$ in virtue of WP. Since $N$ is finite, there exists in $V$ a group of smallest cardinality $M^{*}$, which cannot be $\varnothing$ in virtue of the PP property secured by Lemma 4. With Lemmas 5 and 6 at hand, the conclusion of Lemma 7 follows. We use it to show that $M^{*}$ is a singleton.

Suppose by way of contradiction that $\mid M^{*}$ $\mid \ge 2$, so that $M^{*}$ can be partitioned into two non-empty groups $M_{1}^{*}$ , $M_{2}^{*}$. We take $x,y,z\in X$ and a profile $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ with the following properties:

• for all $i\in M_{1}^{*}$, $xP_{i}yI_{i}z$;

• for all $i\in M_{2}^{*}$, $zI_{i}xP_{i}y$;

• for all $i\in N{\setminus } M^{*}$, $yP_{i}xI_{i}z$.

It follows, first, that $xPy$ because $M^{*}=$ $M_{1}^{*}\cup M_{2}^{*}$ is decisive, and second, that $yRz$ because $zPy$ would mean that $M_{2}^{*}$ is semi-decisive on $(z,y)$ in $(R_{1},\ldots ,R_{n})$, hence decisive, and this would contradict the minimality of $M^{*}$. The two conclusions entail that $xPz$, but this would mean that $M_{1}^{*}$ is semi-decisive on $(x,z)$ in $(R_{1},\ldots ,R_{n})$, hence decisive, another contradiction with the minimality of $M^{*}$. $\square$

Like Arrow’s theorem for $F:\mathcal {O}^{n}\rightarrow \mathcal {O}$, Theorem 2 says that $F:\mathcal {D}^{n}\rightarrow \mathcal {D}$ satisfying IIA and WP is a dictatorship, i.e., there is $j\in N$—the dictator—such that, for all $(R_{1},\ldots ,R_{n})$ in the respective domain and for all $x,y\in X$, if $xP_{j}y$, then $xPy$. However, more is true with the present $F$ than with Arrow’s. By the same argument that proves PI in Lemma 4, $j$ also dictates collective indifference, i.e., for all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{n}$ and all $x,y\in X$, $xP_{j}y$ if and only if $xPy$. It follows that SP cannot hold with the present $F$, this unusual restriction being due to its range. Consistently, the proof of Lemma 3, which derives SP for $F:\mathcal {D}^{n}\rightarrow \mathcal {O}$, made use of at least three indifference classes.

Inspection of the present proof (see Lemmas 6 and 7) shows that Remark 1 also applies to Theorem 2.

The formal argument has gone through the three stages of neutrality, positive responsiveness, and finally dictatorship, which are familiar from early proofs in social choice theory, but dichotomous individual preferences do not support arguments that make active use of PP-transitivity, so each stage needed a special proof based on either the domain $\mathcal {D}^{n}$ or both this domain and the range $\mathcal {D}$ (in Lemmas 4 and 7). Relatedly, there is no use here for the free triple property, which is the main sufficient condition on individual preference domains to derive an Arrovian impossibility. Social choice theory rarely, if ever, considers restrictions put on both the domain and range of the CPF; see the surveys by Gaertner (2002) and Breton and Weymark (2011).

At virtually each stage, we made flexible use of the voters’ indifference relation, i.e., we interpreted $xI_{i}y$ as being sometimes $x,y\in H_{i}$, sometimes $x,y\in L_{i}$, depending on what was to be proved. The dictatorial conclusion would collapse without this convenience. To illustrate, consider the subset $\mathcal {D}^{S}$ of those weak dichotomous orderings the higher class of which is a singleton. There exist non-dictatorial $F:(\mathcal {D}^{S})^{n}\rightarrow \mathcal {D}$ satisfying both IIA and WP, e.g., the following CPF: for all $(R_{1},\ldots ,R_{n})\in \mathcal {D}^{S}$, if $xP_{i}y$ for all $i\in N$, then $xPy$; otherwise,

$$\begin{aligned} F(R_{1},\ldots ,R_{n})=CI. \end{aligned}$$

However, dictatorhip would be reinstated if the conditions applied to $F:(\mathcal {D}^{S})^{n}\rightarrow \mathcal {D}^{S}$. We do not prove this further Arrovian variant here.

A final comment is in order. One may wonder how to place Theorem 2 vis-à-vis the current analysis of approval voting in terms of social choice functions. The answer is that it has no analogue in this framework. Superficially, dichotomous preferences resemble choices, since both divide the set of candidates into a higher and a lower subset. However, an expressed choice can result from preferences having more than two indifference sets, so that indifference within the higher subset and within the lower subset cannot be presumed in the case of choice, whereas the H and L of a dichotomous preference are indifference sets by construction. Thus, the formalism of Theorem 2 is much more assertive than a choice-theoretic one could ever be. This holds even when the social choice function is defined on dichotomous individual preferences, since the gap between preference and choice remains at the collective level. In sum, although the choice-theoretic and the preference-theoretic formalisms are both suited for positive characterizations of approval voting, only the former can reach the critical level of Theorem 2.