Social choice correspondences with infinitely many agents: serial dictatorship

Abstract

We study social choice correspondences (SCC) assigning a set of choices to each pair consisting of a nonempty subset of the set of alternatives and a weak preference profile. The SCC satisfies unanimity if when there is a weakly Pareto dominant alternative, the SCC selects this alternative. Stability requires that the SCC is unaffected by withdrawal of losing alternatives. Independence implies that the SCC selects the same outcome from a subset of the set of alternatives for two preference profiles that are the same on this set. We characterize the SCC satisfying the three axioms, when the set of alternatives is finite but includes more than three alternatives, and the set of agents can have any cardinality. We show that the SCC is a serial dictatorship à la Eraslan and McLennan (J Econ Theory 117:29–54, 2004) and that a serial dictatorship can include “invisible serial dictators” à la Kirman and Sondermann (J Econ Theory 5:267–277, 1972).

1 Introduction

In this paper, we consider social choice correspondences assigning a set of choices to each pair consisting of a nonempty subset of the set of alternatives and a weak preference profile. We impose three axioms, namely unanimity, stability, and independence. The SCC satisfies unanimity if when there is a weakly Pareto dominant alternative, the SCC selects this alternative.¹ Stability requires that the SCC selects an alternative from a set if and only if it is chosen from any subset that contains it. Finally, independence implies that the SCC selects the same outcome from a subset of the set of alternatives for two preference profiles that are the same on this set. We characterize the SCC satisfying the three axioms, when the set of alternatives is finite but includes more than three alternatives, and the set of agents can have any cardinality. Our main theorem establishes that the SCC satisfying the three axioms is a serial dictatorship à la Eraslan and McLennan (2004).² Our second theorem shows that a serial dictatorship may include “invisible serial dictators” à la Kirman and Sondermann (1972).

In the literature of social choice theory, the possibility of a democratic mechanism has been a central interest since Arrow’s impossibility theorem in Arrow (1951). Gibbard (1973) and Satterthwaite (1975) show that dictatorship is the unique unanimous mechanism to prevent manipulative voting. In the literature of strategic candidacy, Dutta et al. (2001) show that only a dictatorship satisfies unanimity, independence, and stability when the agents have only strict preferences. Eraslan and McLennan (2004) allow the agents’ indifference among alternatives to show that even when agents may have weak preferences, a serial dictatorship arises.

Recently, there has been a renewed interest in applications of infinite-population Arrovian social choice, particularly the infinite-horizon social choice problems (e.g., Bossert and Suzumura 2008). As described in Bossert and Suzumura (2008), political decisions could have a long-lasting effect in the future. For example, in a pension design, we have to consider the payment and return for the future generations; in a highway construction, its cost and benefit concerns the tax payers in the long future; in an environmental issue, fair allocations of resources between the current and future generations are a key factor. For a democratic mechanism involving the future generations, analyses with infinitely many agents become important.

This paper explores whether a serial dictatorship similar to the one defined in Eraslan and McLennan (2004) still holds when there are infinitely many agents. The answer is yes and we characterize such SCCs by using a hierarchy of ultrafilters. Our result indicates that we still cannot find a democratic mechanism that satisfies the three axioms when the number of agents can be infinite.

Although we formally define an ultrafilter in Sect. 4, here we briefly explain what an ultrafilter is.³ A filter on a set X is a collection of subsets of X that satisfies the three conditions: (a) the empty set is not included in the collection; (b) a superset of a set in the collection is also included; and (c) an intersection of finitely many sets in the collection is also included. A filter $\mathscr {U}$ is an ultrafilter if for any subset A of X, either A or $X {\setminus } A$ is an element of $\mathscr {U}$. An ultrafilter is used to describe a family of decisive coalitions. The notion of a decisive coalition lies at the heart of our analysis. A coalition is a subset of the whole population. A coalition is decisive if the members of this set can determine the social choice whenever they exhibit unanimous strict preference for this choice, whatever the alignment of preferences of the complementary population is.

An important innovation of this paper is the concept of coherence. Coherence is a condition that two different ultrafilters satisfy. When one set contains another set and the smaller set is a decisive coalition for the larger set, coherence requires that the intersections between the smaller set and the decisive coalitions for the larger set are decisive coalitions for the smaller set. That is, when the total population is $\mathcal {N}$, consider two subsets $N \subset N'$ such that N is in the ultrafilter for $N'$. Coherence requires that M is in the ultrafilter for $N'$ if and only if $M \cap N$ is in the ultrafilter for N. A hierarchy of ulterfilters determines a sequence of decisive coalitions, while each ultrafilter defines a set of decisive coalitions. Thinking of a veto process, when some agents’ preferences are not yet consulted, a hierarchy of ultrafilters defines a priority of decisive coalitions defined on the set of remaining agents in each stage of a veto process, i.e., whose preference should be consulted next. When the number of agents is infinite, there may be an arbitrarily small decisive coalition, and we may not be able to identify an individual dictator. By applying the concept of coherent hierarchy of ultrafilters, without identifying one individual dictator, we can identify a sequence of decisive coalition and a coherent hierarchy of ultrafilters provide a hierarchical structure of dictatorship when the number of agents is not finite. In other words, even if we cannot identify each individual dictator, we can specify the order of decisive coalitions by using a coherent hierarchy of ultrafilters.

After defining the notion of coherence, our main theorem characterizes the SCC satisfying the three axioms. A hierarchy of ultrafilters determines a series of coalitions and each coalition consists of agents with the same preference. Recursively, a hierarchy of ultrafilters selects a sequence of preferences and this preference vetoes alternatives that are less preferred to other alternatives. Finally, the sequence of preferences and a tie-breaking rule reach a set of not-vetoed alternatives. By defining the set of not-vetoed alternatives as a social choice, a hierarchy of ultrafilters induces an SCC. We further show that if a coherent hierarchy of ultrafilters and a tie-breaking rule induce an SCC, then it satisfies unanimity, stability and independence. Conversely, we show that if an SCC satisfies unanimity, stability and independence, it is induced by a coherent hierarchy of ultrafilters and a tie-breaking rule.

An ultrafilter defined on a set is called principal if all the sets in the ultrafilter contains a common element, otherwise, it is called non-principal. In the mathematical literature of ultrafilters, Ulam (1929) proves the existence of non-principal ultrafilters by using the axiom of choice when the set, on which the ultrafilter is defined, is infinite. In the social choice literature, Kirman and Sondermann (1972) prove that the family of decisive coalitions forms an ultrafilter. By the existence theorem for non-principal ultrafilters of Ulam (1929), when there are infinitely many agents an ultrafilter can be nonprincipal. When the family of decisive coalitions forms a principal ultrafilter, a social choice is controlled by a single agent, which belongs to all the sets in the ultrafilter. When the family of decisive coalitions forms a non-principal ultrafilter, a social choice is controlled by an ultrafilter, but not a single agent. Kirman and Sondermann (1972) call such a group of agents, which dictates a social preference, an invisible dictator.

Finally, after the characterization of a serial dictatorship, the question remains if there actually exist invisible serial dictators. In other words, we ask whether non-principal ultrafilters serially arise, and whether they satisfy the condition of coherence. Hurd and Loeb (1985) provide a concise existence proof of non-principal ultrafilters by using Zorn’s lemma, which is equivalent to the axiom of choice. By using Zorn’s lemma, we show the second result that is the existence theorem of hierarchical non-principal ultrafilters, which also satisfy the coherence condition.

The organization of the paper is as follows. The next section reviews the related literature and discusses the relation of our work with previous works. Section 3 presents the model. Section 4 defines a generalized serial dictatorship and provides the main theorem. Section 5 proves the main theorem. Section 6 discusses the relationship between our main result and other relevant results in the literature. Section 7 shows the existence of a hierarchy of non-principal ultrafilters.

2 Related literature

Given a social welfare function satisfying Arrow’s axioms of independence and unanimity, Fishburn (1970) shows that when the number of agents is infinite, it is impossible to identify a dictator whose preference dictates the outcome. In replying to Fishburn (1970), Kirman and Sondermann (1972) show that even in the case of infinitely many agents, a set of decisive coalitions is an ultrafilter and, in a sense, a dictatorship still persists. The difference between the finite and the infinite case lies in the fact that in the latter the dictator may “act behind the scenes,” which is called invisible dictatorship. In this paper, we show that invisible dictators may arise serially (see Theorem 2).

Since Kirman and Sondermann (1972), Arrovian social choice for an infinite population structure has been analyzed (see Bossert and Suzumura 1975; Hansson 1976; Monjardet 1983; Bossert and Suzumura 2009; Cato 2011), particularly applications of infinite-population Arrovian social choice (e.g., Bossert and Suzumura 2008). Campbell and Kelly (2000) study under what characteristics of the environment, e.g., a domain restriction, the collection of decisive coalitions forms an ultrafilter.⁴ Recently, Cato (2013b) introduces the notion of conditional decisiveness to clarify the underlying power structure behind aggregation rules that satisfy unanimity⁵ and binary independence, which requires that preferences for two alternatives is unaffected by the inclusion of a third alternative. Consider two sets of agents A and B. When all the agents in A are indifferent between two alternatives in a set of alternatives, all the agents in B have the same preference over the two alternatives, and the preference of all the agents in B over the two alternatives determines the social preference over the two alternatives, then B is called A-conditionally decisive over the two alternatives. Further, B is A-conditionally decisive for the set of alternatives, when it is A-conditionally decisive over all pairs of alternatives in the set. Cato (2013b) shows that if an aggregation rule satisfies unanimity and binary independence, then the family of conditionally decisive coalitions is an ultrafilter. Further, Cato (2013a) defines a quasi-ultrafilter to study incomplete social judgements when the set of agents can be infinite.

In the literature of strategic candidacy, Dutta et al. (2001) initiate the study of manipulation of voting procedures by a candidate who withdraws from the election. Rodríguez-Álvarez (2006) extends the analysis by Dutta et al. (2001) to multi-valued voting rule. Also, Eraslan and McLennan (2004) extend the framework of Dutta et al. (2001) by allowing: (a) the outcome of the procedure to be a set of candidates; (b) some or all of the voters to have weak preference orderings of the candidates. A multi-valued voting procedure is strong candidate stable (SCS) if it is immune to manipulation through unilateral withdrawal of candidacy. Then they show that a voting correspondence satisfies unanimity, independence of irrelevant alternatives and SCS, if and only if it is serially dictatorial, when there are more than three candidates and the number of agents is finite. As we discuss in Sect. 6, our main theorem provides a related result, which shows the theorem under strategic candidacy in Eraslan and McLennan (2004) when the number of agents can be infinite.

Further, there is a literature studying a common framework for Arrow’s impossibility theorem and the Gibbard–Satterthwaite theorem.⁶ Man and Takayama (2013a) characterize an SCC satisfying the three axioms in the case of finitely many agents and derive many well-known impossibility theorems including the result in Eraslan and McLennan (2004) as corollaries to their main theorem.⁷ We will also provide a result that extends the characterization in Man and Takayama (2013a) to the case of infinitely many agents in Sect. 6.

3 The axioms

Let $\mathcal {X}$ be the set of alternatives. We assume that $3 \le |\mathcal {X}| < \infty$. Let $\mathcal {N}$ be the set of agents. Let $\mathcal {R}$ denote the space of weak preferences over $\mathcal {X}$. A typical preference profile on $\mathcal {X}$ is denoted by $R \in \mathcal {R}^{\mathcal {N}}$, with component $R_i \in \mathcal {R}$ for every $i \in \mathcal {N}$. For each $x,y\in \mathcal {X}$, we write $x P_i y$ if x is strictly preferred to y, i.e., $x R_i y$ but not $y R_i x$, and $x I_i y$ if x is indifferent to y, i.e., $x R_i y$ and $y R_i x$. For an arbitrary set Z, let $\mathscr {P}(Z) \equiv 2^{Z} \backslash \{\varnothing \}$. An SCC is a mapping $\phi : \mathscr {P}(\mathcal {X}) \times \mathcal {R}^{\mathcal {N}} \rightarrow \mathscr {P}(\mathcal {X})$ such that, for each $X \in \mathscr {P}(\mathcal {X})$ and $R \in \mathcal {R}^{\mathcal {N}}$, $\phi (X, R) \subset X.$ Next, we define three properties that we impose on $\phi$. For $R \in \mathcal {R}^{\mathcal {N}}$ and $X \in \mathscr {P}(\mathcal {X})$, alternative $x \in X$ is called weakly Pareto dominant in X if for every $y\in X$, $x R_i y$ for every $i\in \mathcal {N}$, and $x P_j y$ for at least one $j\in \mathcal {N}$.

Definition 1

(Unanimity) An SCC $\phi$ satisfies unanimity if, for each $X \in \mathscr {P}(\mathcal {X})$, $\phi (X, R)=\{x\}$ holds for all $R \in \mathcal {R}^{\mathcal {N}}$ such that $x \in X$ is weakly Pareto dominant in X.

Let $R|_X$ be the restriction of R to $X \in \mathscr {P}(\mathcal {X})$ that agrees with R: for all $i \in \mathcal {N}$ and $x, y \in X$, $x R_i|_X y$ if and only if $x R_i y$. We say that profiles R and $R'$ agree on X if $R|_X = R'|_X$.

Definition 2

(Independence) An SCC $\phi$ satisfies independence if, for each $X\in \mathscr {P}(\mathcal {X})$ and each $R,R' \in \mathcal {R}^{\mathcal {N}}$, $R|_X \ = \ R'|_X$ implies $\phi (X, R)=\phi (X, R')$.

Definition 3

(Stability) An SCC $\phi$ satisfies stability if, for each $X, X' \in \mathscr {P}(\mathcal {X})$ and each $R \in \mathcal {R}^{\mathcal {N}}$, $X'\subset X$ and $\phi (X, R)\cap X' \ne \varnothing$ imply $\phi (X', R)=\phi (X, R)\cap X'$.

4 The main theorem: serial dictatorship

Eraslan and McLennan (2004) define a serial dictatorship in the case of finitely many agents. To extend their results to the case where the number of agents can be infinite, this section defines a serial dictatorship on an environment where the number of agents can be infinite. To do this, we start by introducing our tool, an ultrafilter.⁸

Definition 4

(Ultrafilter) A family $\mathscr {F}\subset 2^A$ is an ultrafilter of a set A if

• (a) $\varnothing \notin \mathscr {F}$.

• (b) $\text {If} \ S\in \mathscr {F}, \ \text {and} \ S'\supset S, \ \text {then} \ S'\in \mathscr {F}$.

• (c) $\text {If} \ S, S'\in \mathscr {F}, \ \text {then} \ S\cap S'\in \mathscr {F}$.

• (d) $\text {If} \ S \subset A, \ \text {then either} \ S\in \mathscr {F}\ \text {or} \ A\backslash S \in \mathscr {F}$ (but not both).

An ultrafilter is called principal or non-principal when the intersection of all its members is nonempty or empty, respectively. If $\mathscr {F}$ is principal, then $\mathscr {F}= \{S \subset A: i \in S\}$ for some $i \in A$, because by properties (c) and (d), $\bigcap _{S \in \mathscr {F}} S \in \mathscr {F}$ cannot have more than one element. We call such an i a principal element of $\mathscr {F}$. If A is finite, due to properties (a) and (c), the intersection of all the sets in the ultrafilter belongs to the ultrafilter and is not empty. Thus, if A is finite, all ultrafilters are principal.

Lemma 1

If $\mathscr {F}$ is an ultrafilter on A and $\Pi$ is a finite partition of A, then there exists exactly one set $S \in \Pi$ such that $S \in \mathscr {F}\cap \Pi$.

Proof

First, suppose that there are two sets $S_0, S_1 \in \Pi \cap \mathscr {F}$. Then $\varnothing = S_0 \cap S_1 \in \mathscr {F}$, which contradicts the property (a) of ultrafilters. Second, suppose that there is no set $S \in \Pi$ with $S \in \mathscr {F}$. Then $\varnothing = \bigcap _{S \in \Pi } \left( A {\setminus } S \right) \in \mathscr {F}$, which is a contradiction. $\square$

Definition 5

A hierarchy of ultrafilters $\mathscr {U}$ assigns an ultrafilter $\mathscr {U}(N)$ over N to each $N\in \mathscr {P}(\mathcal {N})$.

Fix such a $\mathscr {U}$. Let $R \in \mathcal {R}^{\mathcal {N}}$ and $N \in \mathscr {P}(\mathcal {N})$. As $\mathcal {X}$ is finite, there are finitely many possibilities for a preference ordering $R \in \mathcal {R}^{\mathcal {N}}$, and so the sets $\{i \in \mathcal {N}\ | \ R_i = \succsim \text { for some } \succsim \in \mathcal {R}\}$ are a finite partition $\Pi (R)$ of $\mathcal {N}$. By Lemma 1, exactly one set in $\Pi (R)$ belongs to $\mathscr {U}(N)$, that is, there exists $S \in \Pi (R)$ such that $\mathscr {U}(N)\cap \Pi (R) =\{S\}$. Thus, there exists a unique $\succsim _{(R, \mathscr {U}(N))} \in \mathcal {R}$ such that $\{i \in N \ | \ R_i = \succsim _{(R, \mathscr {U}(N))} \} \in \mathscr {U}(N)$, which we regard as $\mathscr {U}(N)$’s preference.

$\mathscr {U}$ determines a series of coalitions such that each coalition consists of agents with the same preferences. With the series of coalitions that $\mathscr {U}$ defines, we can derive an SCC iteratively. Let $X \in \mathscr {P}(\mathcal {X})$ and consider a preference profile $R|_X$ restricted on X. Let $C_0(R|_X)\equiv \mathcal {N}$. By Lemma 1, there exists a unique $S_1(R|_X)\in \mathscr {U}(C_0(R|_X))\cap \Pi (R|_X)$ and we obtain the preference of $\mathscr {U}(C_0)$, $\succsim _{(R|_X, \mathscr {U}(C_0))}$. Then let $C_1(R|_X) \equiv C_0(R|_X)\backslash S_1(R|_X)$ and $S_2(R|_X)\in \mathscr {U}(C_1(R|_X))\cap \Pi (R|_X)$. In the same way with the preference of $\mathscr {U}(C_0)$, we obtain the second preference $\succsim _{(R|_X, \mathscr {U}(C_1))}$. Recursively, $\mathscr {U}$ determines a sequence of preferences for $R|_X \in \mathcal {R}^\mathcal {N}$. Thus, we obtain the following lemma.

Lemma 2

For each $X \in \mathscr {P}(\mathcal {X})$ and $R|_X \in \mathcal {R}^\mathcal {N}$, $\mathscr {U}$ determines the sequence of preference profiles $\{\succsim _{R|_X, k}\}_{k=1}^{K(R|_X)}$ and the sequences of subsets $\{C_k(R|_X)\}_{k=0}^{K(R|_X)}$ and $\{S_k(R|_X)\}_{k=1}^{K(R|_X)}$ such that $K(R|_X) = |\Pi (R|_X)|$, $C_0(R|_X)=\mathcal {N}$ and for each $k = 1, \cdots , K(R|_X)$, (i) $S_k(R|_X)\in \mathscr {U}(C_{k-1}(R|_X))\cap \Pi (R|_X)$; (ii) $C_k(R|_X)= C_{k-1}(R|_X)\backslash S_k(R|_X)$; (iii) $C_{K(R|_X)}=\varnothing$; and (iv) $\succsim _{R|_X,k} = \succsim _{(R|_X, \mathscr {U}(C_{k-1}))}$.

To obtain an SCC for each $(X, R) \in \mathscr {P}(\mathcal {X}) \times \mathcal {R}^{\mathcal {N}}$, we define a top set as follows: for each $\succsim \in \mathcal {R}$ and nonempty $X \subset \mathcal {X}$, let

$$\begin{aligned} \mathrm {Top}(X, \succsim )\equiv \{x\in X \ | \ \text {for each} \ y \in X, \ x \ \succsim \ y \}. \end{aligned}$$

Definition 6

$\mathscr {U}$ induces an SCC $\phi ^{\mathscr {U}}$ if for every $(X, R) \in \mathscr {P}(\mathcal {X}) \times \mathcal {R}^{\mathcal {N}}$ and every $k = 1, \ldots , K(R)$,

• (i) $T_0(X, R) = X$,

• (ii) $T_k(X,R)= \mathrm {Top}(T_{k-1}(X,R), \succsim _{R,k})$,

• (iii) $\phi ^{\mathscr {U}}(X, R) = T_{K(R)}(X, R).$

Further, $\mathscr {U}$ and a tie-breaking rule⁹ $\rho \in \mathcal {R}$ induce an SCC $\phi ^{\mathscr {U}, \rho }$ if for every $(X, R) \in \mathscr {P}(\mathcal {X}) \times \mathcal {R}^{\mathcal {N}}$,

• (iv) $\phi ^{\mathscr {U}, \rho }(X,R) = \mathrm {Top}(\phi ^{\mathscr {U}}(X, R), \rho )$.

The process defined by Conditions (i)–(iv) is a veto process such that a group of agents with the same preference vetoes alternatives that are not in their top set, recursively, until everybody’s preference has been consulted.¹⁰ Notice that K(R) and $C_k(R)$ only depend on a preference profile R, while $T_k(X,R)$ depends on X and R. The veto process continues until it becomes impossible to further eliminate alternatives, after which $\rho$ is applied. Since $\Pi (R)$ is finite, this process ends at some finite stage.

Definition 7

$\mathscr {U}$ is coherent if for all $N, N' \in \mathscr {P}(\mathcal {N})$ with $N \in \mathscr {U}(N')$, and all $M \in \mathscr {P}(N')$, $M \in \mathscr {U}(N')$ if and only if $M \cap N \in \mathscr {U}(N)$.

Definition 8

An SCC $\phi$ is a serial dictatorship if $\phi = \phi ^{\mathscr {U}, \rho }$ for a coherent $\mathscr {U}$ and a tie-breaking rule $\rho$.

Theorem 1

An SCC $\phi$ satisfies unanimity, independence, and stability if and only if it is a serial dictatorship.

Eraslan and McLennan (2004) show that there exists a sequence of dictators when $\mathcal {N}$ is finite and a voting procedure satisfies unanimity, independence and strong candidate stability. Theorem 1 shows that when $\mathcal {N}$ is finite, we obtain a sequence of principal ultrafilters, so at each round, there exists one agent who is contained in all the sets of the ultrafilter. This sequence of agents corresponds to the serial dictators in Eraslan and McLennan (2004). We will discuss the relationship between their main theorem and Theorem 1 in more details in Sect. 6. Here, we state the following result, which explains the relationship between a coherent hierarchy of ultrafilters and a permutation aligning serial dictators in the case of finitely many agents.

When $\mathcal {N}= \{1, \ldots , n\}$ for some finite n, define $\{\pi _1, \ldots , \pi _n\}$ to be the permutation of $\mathcal {N}$ such that for each $k = 1, \ldots , n$, $\pi _k$ is a principal element of $\mathscr {U}(N_k)$ where $N_1 = \mathcal {N}$ and $N_k = \mathcal {N}{\setminus } \{\pi _1, \ldots , \pi _{k-1}\}$ for each $k \ge 2$. For every $N \in \mathscr {P}(\mathcal {N})$, let $k_N = \min \{k: \pi _k \in N\}$ and $\mathscr {U}_i(N)$ to be the ultrafilter such that agent $i \in N$ is a principal element of $\mathscr {U}(N)$.

Proposition 1

Suppose $\mathcal {N}= \{1, \ldots , n\}$ for some finite n. Then $\mathscr {U}$ is coherent if and only if $\mathscr {U}(N) = \mathscr {U}_{\pi _{k_N}}(N)$ for every $N \in \mathscr {P}(\mathcal {N})$.

Proof

Suppose that $\mathscr {U}$ is coherent. Fix $N \in \mathscr {P}(\mathcal {N})$. Because $\mathscr {U}(N)$ is principal, it has a principal element $\pi _k$ for some k. On the contrary, suppose that there is some $\pi _i \in N$ such that $i < k$. Then $\pi _i$ is a principal element of $\mathscr {U}(N_i)$. Because $\{\pi _i, \pi _k\} \subset N_i \cap N$ and $\{\pi _i, \pi _k\} \in \mathscr {U}(N_i)$ by the property (b) of ultrafilters, coherence requires that $\{\pi _i\} \in \mathscr {U}(\{\pi _i, \pi _k\})$. By the same argument, coherence requires that $\{\pi _k\} \in \mathscr {U}(\{\pi _i, \pi _k\})$. Because $\mathscr {U}(\{\pi _i, \pi _k\})$ is principal, this is a contradiction. Therefore, $k = k_N$.

Conversely, suppose $\mathscr {U}(N) = \mathscr {U}_{\pi _{k_N}}(N)$ for every $N \in \mathscr {P}(\mathcal {N})$. Consider $N, N' \subset \mathcal {N}$ such that $N \subset N'$ and $N \in \mathscr {U}(N')$. Since $\mathscr {U}(N') = \mathscr {U}_{\pi _{k_{N'}}}(N')$ is principal, $\pi _{k_{N'}} \in N$ and $k_{N'} = \min \{k: \pi _k \in N' \} = \min \{k: \pi _k \in N \subset N' \} = k_N$. For $M \in \mathscr {P}(N')$, $M \in \mathscr {U}(N')$ if and only if $\pi _{k_N'} = \pi _{k_N} \in M$. Meanwhile, $\pi _{k_N} \in M$ if and only if $M \cap N \in \mathscr {U}(N)$. Thus, $\mathscr {U}$ satisfies coherence. $\square$

To see how coherence plays a role, let $\mathcal {N}= \{1,2,3,4\}$. Suppose that each number $i \in \mathcal {N}$ corresponds to their ranking within the veto process. For example, agent 1 is the highest in this ranking. Suppose that a hierarchy of ultrafilters $\mathscr {U}$ assigns the principal ultrafilter $\mathscr {U}(N)$ of the highest ranking element of N to $N \in \mathscr {P}(\mathcal {N})$. On the other hand, suppose that another hierarchy of ultrafilters $\mathscr {U}'$ assigns $\mathscr {U}'(\{2,3,4\}) = \{U' \in \mathscr {P}(\mathcal {N}) | U' \text { contains } 3 \}$ and $\mathscr {U}'(N) = \mathscr {U}(N)$ for all other $N \not = \{2,3,4\}$. Notice that coherence is not satisfied by $\mathscr {U}'$, because $\{3, 4\} \in \mathscr {U}'(\{2,3, 4\})$ but $\{3,4\} \cap \{2,3\} \not \in \mathscr {U}'(\{2,3\})$. On the other hand, coherence is satisfied by $\mathscr {U}$.

Let $\mathcal {X}= \{a, b, c\}$. Suppose that under preference profile $R \in \mathcal {R}^\mathcal {N}$, the following holds:

$$\begin{aligned} \begin{matrix} a I_1 b I_1 c,&\,&a P_2 b P_2 c,&\,&b P_3 c P_3 a,&\,&a I_4 b I_4 c. \end{matrix} \end{aligned}$$

As we will see below, a hierarchy of ultrafilters and a tie-breaking rule can induce an SCC that satisfies the two axioms of unanimity and stability. However, for the SCC to satisfy independence, we need coherence. The following example shows this. Further, suppose that under another profile $R' \in \mathcal {R}^\mathcal {N}$, $R_i = R'_i$ for all $i \not = 4$ and for agent 4, $a I_4 b P_4 c$ holds. Notice that R and $R'$ are the same except for agent 4’s preference over $\{b,c\}$. First, we consider what $\mathscr {U}'$ chooses in the case of $(\mathcal {X}, R')$. We have $\Pi (R')=\{\{1\}, \{2\}, \{3\}, \{4\} \}$. Thus $S_1(R')=\{1\}$, $\succsim _{R',1}=R'_1$. Thus $T_1(\mathcal {X}, R') = \{a,b,c\}$. However, at the next stage, since $C_1(R')=\{2,3,4\}$ under $\mathscr {U}'$, $\mathscr {U}'$ picks up $S_2(R')=\{3\}$ and $\succsim _{R',2}=R'_3$, which implies that $T_2(\mathcal {X}, R')=\{b\}$, that is, $\phi ^{\mathscr {U}'}(\mathcal {X}, R)=\{b\}$. Stability implies $\phi ^{\mathscr {U}'}(\{a,b\}, R')=\{b\}$.

Second consider what $\mathscr {U}'$ chooses in the case of $(\mathcal {X}, R)$. Then $\Pi (R)=\{\{1,4\}, \{2\}, \{3\} \}$. Thus $S_1(R)=\{1,4\}$ and $\succsim _{R,1}=R_1$. It implies that $T_1(\mathcal {X}, R)=\{a,b,c\}$. Now that $C_1(R)=\{2,3\}$ under $\mathscr {U}'$, $\mathscr {U}'$ next picks up $S_2(R)=\{2\}$ and $\succsim _{R, 2} = R_2$. We have $T_2(\mathcal {X}, R)=\{a\}$. Therefore $\phi ^{\mathscr {U}}(\mathcal {X}, R)=\{a\}$. Then stability implies $\phi ^{\mathscr {U}'}(\{a,b\}, R)=\{a\}$. This contradicts independence because $R|_{a,b} = R'|_{a,b}$ but

$$\begin{aligned} \phi ^{\mathscr {U}'}(\{a,b\}, R') = \{b\} \not = \phi ^{\mathscr {U}'}(\{a,b\}, R) = \{a\}. \end{aligned}$$

This contradiction does not arise with $\mathscr {U}$. The problem with $\mathscr {U}'$ is that even if agent 2 has not yet been chosen by the preceding ultrafilter $\mathscr {U}'(C_0(R'))$, the next ultrafilter $\mathscr {U}'(\{2, 3, 4\})$ exclusively chooses a set including agent 3. In this sense, agent 3 is chosen as a dictator before agent 2 in the second dictatorship that $\mathscr {U}'(\{2,3, 4\})$ induces, while with $\mathscr {U}(\{2,3\})$ and $\mathscr {U}(\{2,3, 4\})$, this does not happen, because agent 2 is always chosen before agent 3.

As the proof of Lemma 1 shows, the assumption of finite alternatives is crucial. When the number of alternatives is infinite, there may not be a set in $\Pi (R)$ that belongs to an ultrafilter. To see this, suppose that the set of alternatives is [0, 1] and under a preference profile R, each agent has their most favorite alternative $r \in [0, 1]$. Then $\Pi (R)$ has infinitely many coalitions and none of them belongs to a nonprincipal ultrafilter.

Another difficulty is that even if there is a sequence of coalitions that belongs to an ultrafilter, because the sequence can be infinite, each agent vetoes one point in the set of alternatives, and the final top set can become empty, which leads to an empty SCC. Man and Takayama (2013b) extend their analysis to the case where the number of agents is finite and the set of alternatives is a compact metric space. In their case, the veto process sequence stops at some point and the final top set is not empty, because the cardinality of agents is smaller than the cardinality of alternatives.

5 The proof of the main theorem

5.1 The proof of the “If” part

We start with two lemmas, which will also be used in the proof of the “only if” part. By Lemma 2, $\mathscr {U}$ determines the sequences of subsets $\{S_k, C_{k-1}\}^{K(R)}_{k=1}$ and $\{S'_m, C'_{m-1}\}^{K(R|_X)}_{m=1}$ for R and its restricted preference profile on X, $R|_X$. In Lemma 4, we show that both sequences yield the same final top set for the set X. The next lemma implies Lemma 4.

Lemma 3

For every $m = 1, \ldots , K(R|_X)$, let $k_m$ be the smallest k such that $\succsim _{R, k}$ and $\succsim _{R|_X, m}$ agree on X. Then $k_1< \cdots < k_{K(R|_X)}$.

Proof

We will first show that for every $m \le K(R|_X)$, there is k such that

$$\begin{aligned} C'_{m-1} \subset C_{k-1} \text { and } C'_{m-1} \in \mathscr {U}(C_{k-1}). \end{aligned}$$

(1)

Because $C_0 = C'_0 = \mathcal {N}$ and $C'_0 \in \mathscr {U}(C_0)$, by induction we may suppose that for some $m \le K(R|_X) - 1$, there is k such that (1) holds. By coherence, we must have $S_{k} \cap C'_{m-1} \in \mathscr {U}(C'_{m-1}).$ By Lemma 1, $S_{k} \cap C'_{m-1} \subset S'_{m}.$ Therefore $S_{k} \subset S'_{m}$ because $S_k$’s are finer than $S'_m$’s. Therefore, we conclude that $C'_{m} \subset C_{k}$. By coherence, $S'_{m+1} \in \mathscr {U}(C'_m)$ implies $S'_{m+1} \in \mathscr {U}(C_k)$. Therefore, $C'_m \in \mathscr {U}(C_k)$ and by induction for every m, there is k such that (1) holds and by coherence, $S_{k} \cap C'_{m-1} \subset S'_{m}$ also holds. Then by Lemma 1, for every $m = 1, \ldots , K(R|_X)$, there is some k such that $\succsim _{R, k}$ and $\succsim _{R|_X, m}$ agree on X.

To complete the proof, note that for every n because $S_{k_n} \subset S'_n$, $C'_n \subset C_{k_n}$. Now on the contrary, suppose that there are some m and n such that $m < n$ but $k_m > k_{n}$. Then $C'_{n - 1} \subset C'_{m - 1}$ and $C_{k_m - 1} \subset C_{k_{n} - 1}$ imply

$$\begin{aligned} C'_{n - 1} \subset C'_{m - 1} \subset C_{k_m - 1} \subset C_{k_{n} - 1}. \end{aligned}$$

(2)

Because $S_{k_n} \in \mathscr {U}(C_{k_n - 1})$ and $S_{k_n} \subset S'_{n}$, by (2), $C'_{n-1} \in \mathscr {U}(C_{k_n - 1})$ and $C'_{m-1} \in \mathscr {U}(C_{k_n - 1})$. Because $S'_{m} \in \mathscr {U}(C'_{m - 1})$, coherence requires $S'_m \in \mathscr {U}(C_{k_{n} - 1})$. However, $S'_n \in \mathscr {U}(C_{k_{n} - 1})$ and $S'_m \cap S'_n = \varnothing$. This is a contradiction. $\square$

Lemma 4

For every $X \in \mathscr {P}(\mathcal {X})$,

$$\begin{aligned} T_{K(R)}(X, R) = T_{K(R|_X)}(X, R|_X). \end{aligned}$$

(3)

Proof

If $x \not \in T_{K(R|_X)}(X, R|_X)$, then some $S'_m$ vetoes x and by Lemma 3 its corresponding $S_{k_m}$ vetoes x. Thus $x \not \in T_{K(R|_X)}(X, R|_X)$. Conversely, if $x \not \in T_{K(R|_X)}(X, R|_X)$, there is some $S_{k_m}$ who vetoes x. Then $x \not \in T_{K(R|_X)}(X, R|_X)$, because by the definition of $k_m$, there is $S'_m$ who vetoes x. $\square$

Now we are ready to prove the “if” part of Theorem 1. Let $\mathscr {U}$ be a hierarchy of ultrafilters, and $\rho$ be a tie-breaking rule. Let $\phi ^{\mathscr {U}, \rho }$ be the serial dictatorship induced by $\mathscr {U}$ and $\rho$. We show that $\phi ^{\mathscr {U}, \rho }$ satisfies the three properties.

Lemma 5

The SCC $\phi ^{\mathscr {U}, \rho }$ satisfies unanimity.

Proof

Let $X\in \mathscr {P}(\mathcal {X})$, $x\in X$, and $R \in \mathcal {R}^\mathcal {N}$. Suppose that x is weakly Pareto dominant in X at R. Let $\Pi (R)\equiv \{S_1, \ldots , S_K\}$. For each $k = 1, \ldots , K$, let $R_k\in \mathcal {R}$ be the preference of the agents in $S_k$. Since x is weakly Pareto dominant, for each $k = 1, \ldots , K$, $x\in \mathrm {Top}(X, R_k)$, and there exists $k^* = 1, \ldots , K$ such that $\mathrm {Top}(X, R_{k^*})=\{x\}$. Thus we have $\phi ^{\mathscr {U},\rho }(X, R)=\{x\}$. $\square$

Lemma 6

The SCC $\phi ^{\mathscr {U},\rho }$ satisfies independence.

Proof

Consider $X\in \mathscr {P}(\mathcal {X})$, and $R, R' \in \mathcal {R}^\mathcal {N}$ such that $R|_{X} = R'|_{X}$. Let $\{S_k, C_k\}_{k=0}^{K(R|_X)}$ and $\{S'_k, C'_k\}_{k=0}^{K(R'|_X)}$ be the sequence that $\mathscr {U}$ determines for $R|_X$ and $R'|_X$, respectively. Then $\Pi (R|_X) = \Pi (R'|_X)$, and $K(R|_X) = K(R'|_X)$. By coherence and Lemma 1, $\{S_k\} = \mathscr {U}(C_{k-1}) \cap \Pi (R|_X)$ if and only if $\{S_k \cap C'_{k-1}\} = \mathscr {U}(C'_{k-1}) \cap \Pi (R'|_X)$. Thus, for each $k = 0,\ldots ,K(R|_X)$, $S_k = S'_k$ and $\succsim _{R|_X, k} = \succsim _{R'|_X, k}$. Thus, for each $k = 1,\ldots ,K(R|_X)$,

$$\begin{aligned} T_{k}(X, R|_X) = T_{k}(X, R'|_X). \end{aligned}$$

By Lemma 4,

$$\begin{aligned} T_{K(R)}(X, R) = T_{K(R')}(X, R'). \end{aligned}$$

Therefore, we obtain:

$$\begin{aligned} \phi ^{\mathscr {U}, \rho }(X,R) = \phi ^{\mathscr {U}, \rho }(X,R'). \end{aligned}$$

$\square$

For $X \in \mathscr {P}(\mathcal {X})$ and $R \in \mathcal {R}^\mathcal {N}$, we define $R^X \in \mathcal {R}^\mathcal {N}$ to be the preference profile such that R and $R^X$ agree on X and $\mathcal {X}{\setminus } X$, and $y P^X_i z$ for all i, $y \in X$ and $z \not \in X$. We say $R^X$ takes X to the top from R. Fix $R \in \mathcal {R}^\mathcal {N}$ and take a sequence of preference profiles $\{R^k\}_{k = 0}^{K(R)}$ such that $R^0 = R$ and for each $k > 0$, $R^k$ takes $T_{k-1}(X,R)$ to the top from R. Then by Lemma 4, $x \in T_{k+1}(X, R)$ if and only if $x \in \mathrm {Top}(T_{k}(X,R^{k}), \succsim _{R,{k+1}})$. Thus, we obtain

$$\begin{aligned} \mathrm {Top}(T_{k-1}(X,R^{k-1}), \succsim _{R,k}) = T_{k}(X, R). \end{aligned}$$

(4)

Lemma 7

The SCC $\phi ^{\mathscr {U}, \rho }$ satisfies stability.

Proof

Consider $R \in \mathcal {R}^\mathcal {N}$ and $X', X \in \mathscr {P}(\mathcal {X})$ such that $X' \subset X$. Suppose that $\phi ^{\mathscr {U}, \rho }(X,R)\cap X'\ne \varnothing$. Let $\{\succsim _{R,k}\}_{k=1}^{K(R)}$ be the sequence of preferences derived by $\mathscr {U}$.

Because $\phi ^{\mathscr {U}, \rho }(X,R)\cap X'\ne \varnothing$, $T_{K(R)}(X, R) \cap X' \ne \varnothing$. Let $x \in T_{K(R)}(X, R)$. Then by (4), for every $k = 1, \ldots , K(R)$,

$$\begin{aligned} x \in \mathrm {Top}(T_{k-1}(X,R^{k-1}), \succsim _{R,k}). \end{aligned}$$

(5)

Thus, there is no $y \in X$ such that $y \succ _{R, k} x$ for any k. As $X' \subset X$, there is no $y \in X'$ such that $y \succ _{R, k} x$ for any k. Thus, for every $k = 1, \ldots , K(R)$,

$$\begin{aligned} x \in \mathrm {Top}(T_{k-1}(X', R^{k-1}), \succsim _{R,k}). \end{aligned}$$

(6)

Thus, $\mathrm {Top}(T_{k-1}(X,R^{k-1}), \succsim _{R,k}) \subset \mathrm {Top}(T_{k-1}(X', R^{k-1}), \succsim _{R,k})$ and by (4), $T_{K(R)}(X, R) \cap X' \subset T_{K(R)}(X', R)$. To show the other direction, let $x \in T_{K(R)}(X', R)$. By way of contradiction, suppose $x \not \in T_{K(R)}(X, R)$. Then there must be $y \in X$ such that $y \succ _{R,k} x$ for some k. Then it must be the case that $y \in X {\setminus } X'$ because $x \in T_{K(R)}(X', R)$ implies that there is no $y \in X'$ such that $y \succ _{R,k} x$ for any k. On the other hand, because $T_{K(R)}(X, R) \cap X' \ne \varnothing$, there must be some $z \in X'$ such that $z \in T_{K(R)}(X, R) \cap X'$. Then $z \in T_{K(R)}(X, R)$ implies that for every k, $y \sim _{R, k} z$ and further there is no $w \in X$ such that $w \succ _{R, k} z$. Thus, $z \in T_{K(R)}(X', R)$. This implies that for every k, $z \sim _{R,k} x$. However, this is a contradiction because $y \sim _{R, k} z$ and $y \succ _{R, k} x$ for some k.

Finally, by applying the tie-breaking rule, $\rho$ to both sides, we obtain

$$\begin{aligned} \mathrm {Top}(T_{K(R)}(X,R), \rho )\cap X'= \mathrm {Top}(T_{K(R)}(X',R), \rho ), \end{aligned}$$

which results in $\phi ^{\mathscr {U}, \rho }(X,R)\cap X'= \phi ^{\mathscr {U}, \rho }(X',R)$. $\square$

5.2 The proof of the “Only If” part

Suppose that an SCC $\phi$ satisfies unanimity, independence and stability. We show that there exists a coherent hierarchy of ultrafilters and a tie-breaking rule which induce $\phi$. First, along with Arrow (1959), we show that the implementation of $\phi$ is essentially equivalent to that of a social welfare function (hereafter SWF), where an SWF is defined to be a function from $\mathcal {R}^\mathcal {N}$ to $\mathcal {R}$. To do so, we start with a subset of agents $N \in \mathscr {P}(\mathcal {N})$.

Definition 9

An SWF $\mathbf {R}: \mathcal {R}^N \rightarrow \mathcal {R}$ satisfies

• Unanimity if x is strictly preferred to y according to $\mathbf {R}(R_N)$ whenever x weakly Pareto dominates y under $R_N$;

• Independence if for all $R_N, R'_N \in \mathcal {R}^{N}$ and all $x, y \in X$, $R_N|_{\{x, y\}} = R'_N|_{\{x, y\}}$ implies $\mathbf {R}(R_N)|_{\{x, y\}} = \mathbf {R}(R'_N)|_{\{x, y\}}$.

Lemma 8

Let $\phi ^N: \mathscr {P}(\mathcal {X}) \times \mathcal {R}^N \rightarrow \mathscr {P}(\mathcal {X})$ be an SCC that satisfies unanimity, independence, and stability. There exists an SWF $\mathbf {R}: \mathcal {R}^N \rightarrow \mathcal {R}$ such that for each $R_N \in \mathcal {R}^N$ and each $X\in \mathscr {P}(\mathcal {X})$, $\phi ^N(X, R_N)=\mathrm {Top}(X, \mathbf {R}(R_N))$. Moreover, $\mathbf {R}$ satisfies unanimity and independence.

Proof

For $R_N \in \mathcal {R}^N$, let $\mathbf {R}(R_N)$ be the binary relationship on $\mathcal {X}$ generated by $\phi ^N$, i.e., for each $x, y \in \mathcal {X}$, $x \mathbf {R}(R_N) y$ if $x\in \phi ^N(\{x,y\}, R_N)$. We show that $\mathbf {R}(R_N)$ is a weak preference on $\mathcal {X}$. First, $\mathbf {R}(R_N)$ is complete since, for each $x, y \in \mathcal {X}$, $\phi ^N(\{x,y\}, R_N)\ne \varnothing$. As for transitivity, suppose that $x,y,z \in \mathcal {X}$ are such that $x \mathbf {R}(R_N) y$ and $y \mathbf {R}(R_N) z$. By stability, $x\in \phi ^N(\{x,y,z\}, R_N)$. By stability again, we have $x\in \phi ^N(\{x,z\}, R_N)$, that is, $x \mathbf {R}(R_N) z$. Now that $\mathbf {R}(R_N)$ is a weak preference, Theorem 3 in Arrow (1959) implies that for each $X\in \mathscr {P}(\mathcal {X})$, $\phi ^N(X, R_N)=\mathrm {Top}(X, \mathbf {R}(R_N))$. Unanimity and independence of $\mathbf {R}$ are directly implied by the corresponding properties of $\phi ^N$. $\square$

We respectively denote by p the strict preference profile associated with $R_N$, and by $\mathbf {p}$ the strict preference relation associated with $\mathbf {R}$. Define $\mathcal {U}_N$ to be a family of sets $M \in 2^N$ such that for all $i \in M$, all $x,y \in \mathcal {X}$, and all $R_N \in \mathcal {R}^N$, $x p_i y$ implies $x \ \mathbf {p}(R_N) \ y$. An element of $\mathcal {U}_N$ is a decisive coalition in the population N. Each $M \in \mathcal {U}_N$ dictates the social preference whenever they agree on their strict preferences.

To proceed, we use the following result, which shows that $\mathcal {U}_N$ is an ultrafilter. Campbell and Kelly (2002) show that a domain of an SWF satisfies the chain property (which we define in Appendix I) and the SWF satisfies unanimity and independence, $\mathcal {U}_N$ is an ultrafilter. This result is called the Ultrafilter Lemma. The Ultrafilter Lemma of Campbell and Kelly (2002) is applicable in our environment. The detailed argument showing that the Ultrafilter Lemma is applicable in our case is found in Appendix I after introducing necessary technical terms.

Lemma 9

The collection of decisive coalitions $\mathcal {U}_N$ is an ultrafilter.

We extend this result to the population $\mathcal {N}$. For every $N \in \mathscr {P}(\mathcal {N})$, define $\mathscr {U}(N) \equiv \mathcal {U}_N$ to be the family of decisive coalitions. By Lemma 8, there exists an SWF $\mathbf {R}^{\phi }: \mathcal {R}^\mathcal {N}\rightarrow \mathcal {R}$ such that for each $R \in \mathcal {R}^\mathcal {N}$ and each $X\in \mathscr {P}(\mathcal {X})$, $\phi (X, R)=\mathrm {Top}(X, \mathbf {R}^{\phi }(R))$. We denote by $\mathbf {P}^{\phi }$ the strict preference relation associated with $\mathbf {R}^{\phi }$.

Lemma 10

$\mathscr {U}$ is a coherent hierarchy of ultrafilters.

Proof

By Lemma 9, the family of decisive coalitions $\mathcal {U}_N$ is an ultrafilter. As N is arbitrary in $\mathscr {P}(\mathcal {N})$, $\mathscr {U}$ is a hierarchy of ultrafilters. Now we show that $\mathscr {U}$ is coherent. Let $N, N' \in \mathscr {P}(\mathcal {N})$ be such that $N \in \mathscr {U}(N')$. Let $M \in \mathscr {P}(N')$.

• (i) Suppose that $M \in \mathscr {U}(N')$. Let $R \in \mathcal {R}^\mathcal {N}$ and $x, y \in \mathcal {X}$. Suppose that $x P_i y$ for every $i \in M$, $y P_i x$ for every $N {\setminus } M$ and $x I_i y$ for every $i \in \mathcal {N}{\setminus } (N \cup M)$. Since $N \cap M \in \mathscr {U}(N')$, we have that $x\in \phi (\{x,y\}, R)$ and $y\notin \phi (\{x,y\}, R)$. Thus $N \cap M \in \mathscr {U}(N)$.

• (ii) Next suppose that $N \cap M \in \mathscr {U}(N)$. Since $N \in \mathscr {U}(N')$, we have either $N \cap M \in \mathscr {U}(N')$ or $N \backslash M \in \mathscr {U}(N')$, but not both. Construct another preference profile $R' \in \mathcal {R}^\mathcal {N}$ such that $x P'_i y$ for every $i \in N \cap M$, $y P'_i x$ for every $i \in N \backslash M$ and $x I'_i y$ for every $i \in \mathcal {N}{\setminus } N$. Since $N \cap M \in \mathscr {U}(N)$ and $x P'_i y$ for each $i \in N \cap M$, we have $y \notin \phi (\{x,y\}, R')$. Thus $N \cap M \in \mathscr {U}(N')$, which implies that $M \in \mathscr {U}(N')$.

$\square$

Let $\tilde{R}$ denote the preference profile such that all agents are indifferent between all alternatives. Define a binary relation $\rho$ on $\mathcal {X}$ such that for all $x, y \in \mathcal {X}$,

$$\begin{aligned} x \rho y \quad \text {if and only if} \quad x \in \phi (\{x,y\}, \tilde{R})\text {.} \end{aligned}$$

Lemma 11

The binary relation $\rho$ is complete and transitive.

Proof

• Completeness: For any $x,y \in \mathcal {X}$, $\phi (\{x,y\}, \tilde{R}) \ne \emptyset$. Thus either $x \rho y$ or $y \rho x$ holds.

• Transitivity: Take $x, y, z \in \mathcal {X}$ such that $x \rho y$ and $y \rho z$. Construct $\tilde{R}'$ by taking $\{x,y,z\}$ to the top from $\tilde{R}$. Independence implies $x \in \phi (\{x,y\}, \tilde{R}')$ and $y \in \phi (\{y,z\}, \tilde{R}')$. We claim $x \in \phi (\mathcal {X}, \tilde{R}')$. Suppose not. Since $x \in \phi (\{x,y\}, \tilde{R}')$, if $y \in \phi (\mathcal {X}, \tilde{R}')$, then $\phi (\mathcal {X}, \tilde{R}') \cap \{x, y\} \not = \varnothing$ and thus stability requires $x \in \phi (\mathcal {X}, \tilde{R}')$. This contradicts our assumption and thus we must have $y \notin \phi (\mathcal {X}, \tilde{R}')$. Applying the same logic, we have $z \notin \phi (\mathcal {X}, \tilde{R}')$. Then we must have $w \in \phi (\mathcal {X}, \tilde{R}')$ for some $w \not \in \{x,y,z\}$. Notice that w is strictly Pareto dominated by x, y and z at $\tilde{R}'$. Thus, $\phi (\{x,w\}, \tilde{R}') = \{x\}$ by unanimity. By stability, $\phi (\{x,w\}, \tilde{R}') = \phi (\mathcal {X}, \tilde{R}') \cap \{x,w\} = \{x\}$. However, this contradicts $w \in \phi (\mathcal {X}, \tilde{R}')$. Now by stability and independence, we have $x \in \phi (\{x,z\}, \tilde{R}')=\phi (\{x,z\}, \tilde{R})$. Therefore $x \rho z$. $\square$

The remainder of this section shows that $\mathscr {U}$ and $\rho$ induce $\phi$, that is $\phi ^{\mathscr {U}, \rho } = \phi$. The key step is the following result.

Proposition 2

For every $R \in \mathcal {R}^\mathcal {N}$, $X \in \mathscr {P}(\mathcal {X})$, $\phi (X,R) \subset T_{K(R)}(X,R)$.

Because (4) implies

$$\begin{aligned} \mathrm {Top}(T_{K(R)-1}(X,R^{K(R)-1}), \succsim _{R,K(R)}) = T_{K(R)}(X, R), \end{aligned}$$

Proposition 2 immediately follows from the next result.

Lemma 12

For every $X \in \mathscr {P}(\mathcal {X})$, $R \in \mathcal {R}^\mathcal {N}$, and $k = 1, \ldots , K(R)$,

$$\begin{aligned} \phi (X,R) \subset \mathrm {Top}(T_{k-1}(X,R^{k-1}), \succsim _{R,k}). \end{aligned}$$

Lemma 12 is a consequence of Lemma 13. To state this result, let $N \in \mathscr {P}(\mathcal {N})$. For every $R \in \mathcal {R}^\mathcal {N}$, create a preference profile $\bar{R}^N$ such that all agents in $\mathcal {N}{\setminus } N$ are indifferent between all alternatives, and $\bar{R}^N_i = R_i$ for all agents $i \in N$. Define $\bar{\mathcal {U}}_N$ to be a family of sets $M \in 2^N$ such that for all $i \in M$, all $x,y \in \mathcal {X}$, all $\bar{R}^N \in \mathcal {R}^\mathcal {N}$, $x \bar{P}_i y$ implies $x \ \mathbf {P}^{\phi }(\bar{R}^N) \ y$. For every $R \in \mathcal {R}^\mathcal {N}$, denote a finite partition of N such that $\{i \in N \ | \ R_i = \succsim \text { for some } \succsim \in \mathcal {R}\}$ by $\Pi _{N}(R)$.

In the next lemma, we show that $M \in \mathcal {U}_N$, which dictates the social preference for $R_N \in \mathcal {R}^N$ as shown in Lemma 9, also dictates the social welfare for $\bar{R}^N$ whenever its members agree on their strict preferences.

Lemma 13

$\mathscr {U}(N) = \bar{\mathcal {U}}_N$. For $R \in \mathcal {R}^\mathcal {N}$, let $\bar{R}^N \in \bar{R}^{\mathcal {N}}$. Then

$$\begin{aligned} \mathscr {U}(N) \cap \Pi _N(R_N) = \mathscr {U}(N) \cap \Pi (\bar{R}^N). \end{aligned}$$

Proof

First, we show that $\mathscr {U}(N) = \bar{\mathcal {U}}_N$. Suppose $M \in \bar{\mathcal {U}}_N$. Notice that by unanimity of $\phi$, $N \in \mathscr {U}(\mathcal {N})$. Then $M \in \mathscr {U}(\mathcal {N})$. By coherence, $M \in \mathscr {U}(\mathcal {N})$ if and only if $M \in \mathscr {U}(N)$. Conversely, we can show that if $M \in \mathscr {U}(N)$, then $M \in \bar{\mathcal {U}}_N$.

Second, by Lemma 1, there is a unique set $S \in \mathscr {U}(N) \cap \Pi (R)$. Permutate the sets in $\Pi (R)$ so that $\Pi (R) = \{\pi _1, \ldots , \pi _{K(R)}\}$ and for some $n \le K(R)$, ${\bigcup _{i = 1}^{n}} \pi _i = \mathcal {N}{\setminus } N$ and ${\bigcup _{i = n+1}^{K(R)}} \pi _i = N$ hold. Then notice that $\Pi _N(R_N) = \{\pi _{n+1}, \ldots , \pi _{K(R)}\}$ and $\Pi (\bar{R}^N) = \{\mathcal {N}{\setminus } N, \pi _{n+1}, \ldots , \pi _{K(R)}\}$. Because $S \subset N$, we must have $\{S\} = \mathscr {U}(N) \cap \Pi _N(r)$. Further, because $S \in \Pi (\bar{R}^N)$, we must have $\{S\} = \mathscr {U}(N) \cap \Pi (\bar{R}^N)$. $\square$

Proof of Lemma 12

Let $\{S_k, C_k\}_{k=0}^{K(R)}$ be the sequence that $\mathscr {U}$ induces for R. When $k=0$, $T_0(X,R)=X$, and thus $\phi (X,R) \subset T_0(X,R)$. By induction, for some $k \ge 1$, suppose

$$\begin{aligned} \phi (X,R) \subset \mathrm {Top}(T_{k-1}(X,R^{k-1}), \succsim _{R,k}). \end{aligned}$$

(7)

For notational convenience, let $T = \mathrm {Top}(T_{k-1}(X,R^{k-1}), \succsim _{R,k})$. Suppose $x, y \in T$ are such that $x P_i y$ for every $i \in S_{k+1}$. Take another sequence of preference profiles, $\{\bar{R}^k\}_{k = 0}^{K(R)}$ such that at $\bar{R}^k$, all agents in $\mathcal {N}{\setminus } C_k$ are indifferent between all alternatives, and $R^k_i = \bar{R}^k_i$ for all agents $i \in C_k$. Then notice that $R^k$, $\bar{R}^k$ and R agree on $T_{k-1}(X, R)$ for every k, and that $x \bar{P}^k_i y$ for every $i \in S_{k+1}$.

Since $\{S_{k+1}\} = \mathscr {U}(C_{k}) \cap \Pi (R)$, $\{S_{k+1}\} = \mathscr {U}(C_{k}) \cap \Pi _{C_k}(R)$. Let $r = (R_i)_{i \in C_k}$. Then $\{S_{k+1}\} = \mathscr {U}(C_{k}) \cap \Pi _{C_k}(r)$. By Lemma 13, $\{S_{k+1}\} = \mathscr {U}(C_{k}) \cap \Pi (\bar{R}^{k+1})$ and thus

$$\begin{aligned} y \not \in \mathrm {Top}(T, \mathbf {R}^{\phi }(\bar{R}^{k+1})). \end{aligned}$$

By Lemma 8, $\mathbf {R}^{\phi }$ satisfies independence. Thus, $y \not \in \mathrm {Top}(T, \mathbf {R}^{\phi }(R^{k+1}))$, and hence $y \not \in \phi (T, R^{k+1})$. Because $R^{k+1}$ and R agree on $T_{k}(X, R)$, they also agree on T by (4). By independence,

$$\begin{aligned} \phi (T, R^{k+1}) = \phi (T, R). \end{aligned}$$

Thus, $y \not \in \phi (T, R).$ By stability, $y \not \in \phi (X, R).$ Thus (7) also holds at $k+1$. $\square$

Proposition 3

The coherent hierarchy of ultrafilters $\mathscr {U}$ and the tie-breaking rule $\rho$ induce $\phi$. That is, $\phi = \phi ^{\mathscr {U}, \rho }$.

Proof

Let $X \in \mathscr {P}(\mathcal {X})$. If $T_{K(R)}(X,R) = \{x\}$, then Lemma 2 implies that

$$\begin{aligned} \phi (X,R) \subset \mathrm {Top}(T_{K(R)}(X,R), \rho ) = \{x\}. \end{aligned}$$

(8)

Let $x, y \in T_{K(R)}(X,R)$ and $x \in \mathrm {Top}(T_{K(R)}(X,R), \rho )$. Then $x \in \mathrm {Top}(\{x, y\}, \rho )$, which implies $x \rho y$. By the definition of $\rho$, $x \in \phi (\{x, y\}, \tilde{R})$. Because $x, y \in T_{K(R)}(X,R)$, all agents are indifferent between x and y at R. Thus, $R|_{\{x,y\}} = \tilde{R}|_{\{x,y\}}$. By independence, $x \in \phi (\{x, y\}, R)$. By stability,

$$\begin{aligned} x \in \phi (X,R) \cap \{x, y\} = \phi (\{x, y\}, R). \end{aligned}$$

(9)

Thus, we obtain $\phi (X,R) \subset \mathrm {Top}(T_{K(R)}(X,R), \rho )$.

Next, we show that $\mathrm {Top}(T_{K(R)}(X,R), \rho ) \subset \phi (X,R)$. Let $x \in \mathrm {Top}(T_{K(R)}(X,R), \rho )$ and $x' \in \phi (X,R) \subset T_{K(R)}(X,R)$. Because $x \in \mathrm {Top}(T_{K(R)}(X,R), \rho )$, $x \in \phi (\{x, x'\}, \tilde{R})$. Since both x and $x'$ are in $T_{K(R)}(X,R)$, $\tilde{R}$ and R agree on $\{x, x'\}$. Independence requires $x \in \phi (\{x, x'\}, R) = \phi (\{x, x'\}, \tilde{R})$. Meanwhile, as $x' \in \phi (X, R) \cap \{x, x'\}$, stability requires $x \in \phi (X, R)$. Hence $\mathrm {Top}(T_{K(R)}(X,R), \rho ) \subset \phi (X,R)$.

Thus, we obtain $\phi (X,R) = \mathrm {Top}(T_{K(R)}(X,R), \rho ),$ and thus $\phi = \phi ^{\mathscr {U}, \rho }$. $\square$

6 Discussion of serial dictatorship results in the literature

6.1 Connection with Man and Takayama (2013a)

Theorem 1 is closely related to the theorems in Eraslan and McLennan (2004) and Man and Takayama (2013a). To see this connection, in this subsection we explain the relationship between our result and theirs. We start with the main theorem in Man and Takayama (2013a). First, we discuss the relationship between our stability axiom and the corresponding axiom in their work, which is independence of losing alternatives.

Definition 10

An SCC $\phi$ satisfies independence of losing alternatives (ILA) if for each $X \in \mathscr {P}(\mathcal {X})$ and each $R \in \mathcal {R}^{\mathcal {N}}$, $\phi (X, R)=\phi (\mathcal {X}, R)\cap X$ whenever $\phi (\mathcal {X}, R)\cap X \ne \varnothing$.

Lemma 1 and Lemma 2 of Man and Takayama (2013a) imply Corollary 1 when $\mathcal {N}$ is finite.¹¹ A similar argument works even if $\mathcal {N}$ can be infinite.

Lemma 14

An SCC $\phi$ satisfies stability if it satisfies unanimity, independence and ILA.

Proof

Suppose that $X, X' \in \mathscr {P}(\mathcal {X})$, $X' \subset X$, and $R \in \mathcal {R}^{\mathcal {N}}$. Suppose $\phi (X, R) \cap X' \not = \varnothing$. We obtain $R^{X}$ by taking X to the top of R. Then we claim that $\phi (\mathcal {X}, R^{X}) \subset X$. To show this, let $y \in X$ and suppose that $y R_i x$ for every $i \in \mathcal {N}$ and $y P_j x$ for at least one $j \in \mathcal {N}$. By way of contradiction, suppose that $x \in \phi (X, R)$. Unanimity and ILA imply

$$\begin{aligned} \phi (\{x, y\},R) = \{y\} = \phi (X, R) \cap \{x,y\}. \end{aligned}$$

Hence, we obtain $\{y\} = \phi (X, R) \cap \{x,y\}$, which implies $x \not \in \phi (X, R)$. However this contradicts our initial assumption that $x \in \phi (X, R)$. Thus, $\phi (\mathcal {X}, R^{X}) \subset X$ and together with ILA,

$$\begin{aligned} \phi (\mathcal {X}, R^{X}) = \phi (X, R^{X}). \end{aligned}$$

(10)

Then because $R^{X}|_{X} = R|_{X}$, independence implies

$$\begin{aligned} \phi (X, R^{X}) = \phi (X, R). \end{aligned}$$

(11)

Hence, by (10) and (11),

$$\begin{aligned} \phi (\mathcal {X}, R^{X}) = \phi (X, R). \end{aligned}$$

(12)

By (12) and $\phi (X, R) \cap X' \not = \varnothing$, ILA requires

$$\begin{aligned} \phi (\mathcal {X}, R^{X}) \cap X' = \phi (X, R) \cap X' = \phi (X', R). \end{aligned}$$

(13)

$\square$

Lemma 15

Let $\mathscr {U}$ be a coherent hierarchy of ultrafilters, and let $\rho$ be a tie-breaking rule. Let $\phi ^{\mathscr {U}, \rho }$ be the serial dictatorship induced by $\mathscr {U}$ and $\rho$. If $\phi ^{\mathscr {U}, \rho }$ satisfies stability, then it satisfies ILA.

Proof

This is immediate by noting $X \subset \mathcal {X}$. $\square$

By Theorem 1, Lemma 2 in Man and Takayama (2013a), and Lemma 15, we obtain the following. This corresponds to the result in Man and Takayama (2013a) when the number of agents is not confined to be finite.

Corollary 1

An SCC $\phi$ is a serial dictatorship if and only if it satisfies unanimity, independence and ILA.

6.2 Connection with Eraslan and McLennan (2004)

In this subsection, we discuss the relationship between our result and the work of Eraslan and McLennan (2004). They consider a voting procedure defined on subsets of alternatives with at least $|\mathcal {X}| - 1$ elements. To extend their argument to our framework and state their main theorem, we first lay out the environment in their paper.

The agenda domain $\mathcal {A}$ is the set of all subsets of $\mathcal {X}$ containing all but at most one alternative: $\mathcal {A}=\{A \subset \mathcal {X}: |A| \ge |\mathcal {X}|-1\}$. A voting correspondence is a mapping $V: \mathcal {A}\times \mathcal {R}^{\mathcal {N}} \rightarrow \mathscr {P}(\mathcal {X})$ such that for all $A \in \mathcal {A}$ and $R \in \mathcal {R}^{\mathcal {N}}$, $V(A, R) \subset A$, which is referred to as feasibility. IIA, unanimity, and SCS are defined as follows.

Definition 11

A voting procedure V satisfies independence of irrelevant alternatives (IIA) if for all $A \in \mathcal {A}$ and $R, R' \in \mathcal {R}^{\mathcal {N}}$ with $R|_A=R'|_A$, $V(A,R)=V(A,R')$.

Definition 12

A voting procedure V satisfies unanimity if for all $A \in \mathcal {A}$ and $R \in \mathcal {R}^{\mathcal {N}}$, $V(A,R)=\{x\}$ whenever x is weakly Pareto dominant in A.

Definition 13

A voting procedure V satisfies strong candidate stability (SCS) if for all $x \in \mathcal {X}$ and $R \in \mathcal {R}^{\mathcal {N}}$, either $V(\mathcal {X},R)=\{x\}$, or $V(\mathcal {X}{\setminus } \{x\},R)=V(\mathcal {X},R) \backslash \{x\}$.

To state their result, we first present their definition of a serial dictatorship. For all $A \in \mathcal {A}$ and all preference profiles $R \in \mathcal {R}^{\mathcal {N}}$, define the k-th iteration of the top set operator $\tau$ by the following:

$$\begin{aligned} \tau _k(A,R)= \mathrm {Top}(\tau _{k-1}(A,R), R_{\pi _k}). \end{aligned}$$

Then Eraslan and McLennan (2004) define a voting procedure V to be serially dictatorial if there exists a permutation of individuals $\pi$ and a tie-breaking rule $\rho$ such that for all $A \in \mathcal {A}$ and $R \in \mathcal {R}^{\mathcal {N}}$,

$$\begin{aligned} V(A, R)=\mathrm {Top}(\tau _{|\mathcal {N}|}(A,R), \rho ). \end{aligned}$$

Suppose $\mathcal {N}$ is finite. The difference between our definition and their definition is that in our definition, all the agents who have the same preference with $\pi _k$ are grouped into the same decisive coalition, while in the definition of Eraslan and McLennan (2004), only $\pi _k$’s preference is consulted at round k, and other succeeding serial dictators stay in the remaining population even if their preference is the same with $R_{\pi _k}$. When a hierarchy of ultrafilters satisfies coherence, a coherent hierarchy is associated with the unique permutation $\{\pi _1, \ldots , \pi _n\}$ shown in Proposition 1, and the two definitions lead to the same set of outcomes, because even if some succeeding dictator is grouped with a precedent dictator in our definition, the succeeding dictator’s preference is already consulted when his individual turn comes up in the definition of Eraslan and McLennan (2004), and this dictator’s opinion does not make a difference to the veto process.

In addition to the assumption that $\mathcal {N}$ is finite, there are two additional differences between our setting and the one in Eraslan and McLennan (2004). First, in Eraslan and McLennan (2004), there are two kinds of voters: in one set, voters are allowed to have weak preferences and in the other set, voters only have strict preferences. To keep the argument simple, we keep our setting such that all the voters may have weak preferences. Second, Eraslan and McLennan (2004) allow for candidate voters (alternatives which are also agents), although Man and Takayama (2013a) do not allow this possibility. In this paper, we follow Man and Takayama (2013a) and do not consider the possibility of candidate voters.

The next proposition corresponds to the theorem in Eraslan and McLennan (2004) (see page 38 in Eraslan and McLennan 2004) when all the voters may have weak preferences, the number of agents is not confined to be finite and candidate voters are not allowed. We first define a serial dictatorship for a voting procedure.

Definition 14

A hierarchy of ultrafilters $\mathscr {U}$ and a tie-breaking rule $\rho \in \mathcal {R}$ induce a voting procedure $V^{\mathscr {U}, \rho }$ if for all $A \in \mathcal {A}$ and all $R \in \mathcal {R}^{\mathcal {N}}$, $\mathscr {U}$ determines a sequence of preferences $\{\succsim _{R, k}\}_{k=1}^{K(R)}$ and for each $k = \{1, \ldots , K(R)\}$,

• (i) $T_0(A, R) = A$,

• (ii) $T_k(A,R)= \mathrm {Top}(T_{k-1}(A,R), \succsim _{R,k})$,

• (iii) $V^{\mathscr {U}, \rho }(A, R)=\mathrm {Top}(T_{K(R)}(A, R), \rho )$.

Definition 15

A voting procedure V is a serial dictatorship if $V = V^{\mathscr {U}, \rho }$ for some coherent hierarchy of ultrafilters $\mathscr {U}$ and a tie-breaking rule $\rho$.

Proposition 4

A voting procedure V satisfies feasibility, unanimity, independence and SCS if and only if it is a serial dictatorship.

We keep the proof of Proposition 4 in Appendix II together with the required lemmas.

7 A coherent hierarchy of non-principal ultrafilters

In the previous sections, we defined a serial dictatorship when the number of agents can be infinite, and showed that the serial dictatorship is the unique mechanism that satisfies unanimity, independence, and stability. However, one question arises: How rich is the space of coherence hierarchies of ultrafilters?Fishburn (1970) and Kirman and Sondermann (1972) showed that the family of decisive coalitions can be a non-principal ultrafilter. The existence of non-principal ultrafilters was previously known to be a consequence of the axiom of choice, but this does not settle whether the families of decisive coalitions can be serially non-principal in our framework. To answer this question, we show that there exists a coherent hierarchy of ultrafilters that assigns non-principal ultrafilters to all infinite sets. The following theorem guarantees that when $\mathcal {N}$ is infinite, the statement of Theorem 1 is not vacuous.

Theorem 2

There exists a coherent hierarchy of ultrafilters $\mathscr {U}$ on $\mathscr {P}(\mathcal {N})$, that assigns non-principal ultrafilters to all infinite sets.

To prove Theorem 2, we define an ultrafilter mapping.

Definition 16

Let $\mathcal {M}\subset \mathscr {P}(\mathcal {N})$. A correspondence $\mathscr {F}: \mathcal {M} \rightarrow \mathscr {P}(\mathcal {N})$ is an ultrafilter mapping with domain $\mathcal {M}$ if for each $N \in \mathcal {M}$, $\mathscr {F}(N)$ is an ultrafilter on N. An ultrafilter mapping $\mathscr {F}$ with domain $\mathcal {M}$ is non-principal if it assigns a non-principal ultrafilter $\mathscr {F}(N)$ to every infinite set $N \in \mathcal {M}$. An ultrafilter mapping $\mathscr {F}$ with domain $\mathcal {M}$ is coherent if for each $N, N' \in \mathcal {M}$ with $N \in \mathscr {F}(N')$,

$$\begin{aligned} \mathscr {F}(N') = \{Z \subset N': Z \cap N \in \mathscr {F}(N)\}. \end{aligned}$$

Similarly to a hierarchy of ultrafilters, $\mathscr {F}$ assigns an ultrafilter $\mathscr {F}(N)$ over N to each $N \in \mathcal {M}$. The only difference is that the domains of the mappings do not have to be $\mathscr {P}(\mathcal {N})$. In this sense, an ultrafilter mapping is a more general concept than a hierarchy of ultrafilters.

Our strategy of proving Theorem 2 is as follows. Let $\mathcal {M}^{F} \equiv \{N \in \mathscr {P}(\mathcal {N}): N \text { is finite}\}$ and $\mathcal {M}^{I} \equiv \{N \in \mathscr {P}(\mathcal {N}): N \text { is infinite}\}$. Notice that we can separately study each of the two cases where $\mathscr {F}$’s domain is $\mathcal {M}^{F}$ and $\mathcal {M}^I$. To see this, let $\mathscr {F}$ be an ultrafilter mapping that assigns non-principal ultrafilters to all the infinite sets. Let $N_0 \in \mathcal {M}^{F}$, $N_1 \in \mathcal {M}^I$, and $N_0 \subset N_1$. Then $\mathscr {F}(N_1)$ only includes infinite sets because $N_1$ is infinite. Then the finite set $N_0 \not \in \mathscr {F}(N_1)$. Therefore, we can see that coherence is not required between $\mathscr {F}(N_0)$ and $\mathscr {F}(N_1)$. We will prove Theorem 2 by showing that $\mathscr {U}(N) = \mathscr {F}(N)$ for some coherent non-principal ultrafilter mapping $\mathscr {F}$ with domain $\mathcal {M}^{F} \cup \mathcal {M}^{I}$, individually in two cases; in the first case, for every $N \in \mathcal {M}^{F}$, $\mathscr {F}(N)$ is a principal ultrafilter, and in the second case, for every $N \in \mathcal {M}^{I}$, $\mathscr {F}(N)$ is a non-principal ultrafilter.

Proposition 5

There exists a coherent ultrafilter mapping $\mathscr {F}^* : \mathcal {M}^F \rightarrow \mathscr {P}(\mathcal {N})$.

Proof

A well-ordering is a complete strict ordering such that each $N \subset \mathcal {N}$ has a minimal element. The well-ordering principle¹² asserts that there is a complete strict ordering for $\mathcal {N}$ and there is a minimal element in this ordering for any finite set $N \subset \mathcal {N}$. Let $\underline{i}_N\in N$ be this minimal element. We can define $\mathscr {F}^* : \mathcal {M}^F \rightarrow \mathscr {P}(\mathcal {N})$ such that $\mathscr {F}^*(N)\equiv \{E \subset N \ | \ \underline{i}_N \in E \}$. Let $\tilde{N}\in \mathscr {F}^*(N)$. Then $\underline{i}_N\in \tilde{N}$. Since $\underline{i}_N$ is also the minimal element in $\tilde{N}$, $\mathscr {F}^*(\tilde{N})= \{E \subset \tilde{N} \ | \ \underline{i}_N \in E \}$. Thus, for each $Z\subset N$, $Z\in \mathscr {F}^*(N)$ is equivalent to $\underline{i}_N \in Z$. Meanwhile, $\underline{i}_N \in Z \cap \tilde{N}$ is equivalent to $Z\cap \tilde{N} \in \mathscr {F}^*(\tilde{N})$. Thus, $Z\in \mathscr {F}^*(N)$ if and only if $Z\cap \tilde{N} \in \mathscr {F}^*(\tilde{N})$, which implies that $\mathscr {F}^*$ is coherent. $\square$

Next, we would like to show that there is a coherent ultrafilter mapping with the domain $\mathcal {M}^I$. The proof takes the three steps. First, we define the set of non-principal coherent ultrafilter mappings and its domains such that coherence also holds in the domain, and show that the set is not empty. Second, we show that there exists a maximal element in this set with respect to the binary relation $\ge$, which we define below. Finally, we show that the domain in a maximal element is $\mathcal {M}^I$.

Let $\mathfrak {F}$ be the set of $(\mathcal {M}, \mathscr {F})$ such that $\varnothing \ne \mathcal {M}\subset \mathcal {M}^I$ and $\mathscr {F}:\mathcal {M}\rightarrow \mathscr {P}(\mathcal {N})$ is a non-principal coherent ultrafilter mapping with domain $\mathcal {M}$. To define a maximal element in the set $\mathfrak {F}$, we define a binary relation $\le$ on $\mathfrak {F}$ as follows:

$$\begin{aligned} (\mathcal {M},\mathscr {F})\le (\mathcal {M}',\mathscr {F}') \ \ \text {if} \ \ \left\{ \begin{array}{ll} (1) &{} \mathcal {M}\subset \mathcal {M}', \ \text {and}\\ (2) &{} \text {for each} \ M\in \mathcal {M}, \ \mathscr {F}(M)=\mathscr {F}'(M). \end{array}\right. \end{aligned}$$

Let $(\mathcal {M}, \mathscr {F}), (\mathcal {M}', \mathscr {F}') \in \mathfrak {F}$. Then the binary relation $\ge$ is

• reflexive, i.e., $(\mathcal {M}, \mathscr {F}) \le (\mathcal {M}, \mathscr {F})$;

• antisymmetric, i.e., $(\mathcal {M}, \mathscr {F}) \le (\mathcal {M}', \mathscr {F}')$ and $(\mathcal {M}', \mathscr {F}') \le (\mathcal {M}, \mathscr {F})$ imply $(\mathcal {M}, \mathscr {F}) = (\mathcal {M}', \mathscr {F}')$;

• transitive, i.e., if $(\mathcal {M}, \mathscr {F}) \le (\mathcal {M}', \mathscr {F}')$ and $(\mathcal {M}', \mathscr {F}') \le (\mathcal {M}'', \mathscr {F}'')$, then we have $(\mathcal {M}, \mathscr {F}) \le (\mathcal {M}'', \mathscr {F}'')$.

The relation > is defined by $(\mathcal {M}, \mathscr {F}) < (\mathcal {M}', \mathscr {F}')$ if and only if $(\mathcal {M}, \mathscr {F}) \le (\mathcal {M}', \mathscr {F}')$ but not $(\mathcal {M}, \mathscr {F}) \ge (\mathcal {M}', \mathscr {F}')$.

Proposition 6

There exists a coherent non-principal ultrafilter mapping $\mathscr {F}^*: \mathcal {M}^I \rightarrow \mathscr {P}(\mathcal {N})$.

Proof

Step 1. :

First we show that $\mathfrak {F}$ is non-empty. Since $\mathcal {N}$ is an infinite set, the ultrafilter theorem of Ulam (1929)¹³ implies that there exists a non-principal ultrafilter $\mathcal {U}_\mathcal {N}$ on $\mathcal {N}$. Let $\mathcal {M}\equiv \{\mathcal {N}\}$ and $\mathscr {F}(\mathcal {N})\equiv \mathcal {U}_\mathcal {N}$. By the definition of ultrafilters, $(\mathcal {M}, \mathscr {F}) \in \mathfrak {F}$.

Step 2. :

Next, we show the existence of a maximal element $(\mathcal {M}^*, \mathscr {F}^*)$ in $\mathfrak {F}$. Let $\mathscr {C}\subset \mathfrak {F}$ be a chain, which is a totally ordered subset, so that for every two elements $(\mathcal {M}, \mathscr {F}), (\mathcal {M}', \mathscr {F}')$ in $\mathscr {C}$, either $(\mathcal {M}, \mathscr {F}) \le (\mathcal {M}', \mathscr {F}')$ or $(\mathcal {M}, \mathscr {F}) \ge (\mathcal {M}', \mathscr {F}')$ holds. First we show that $\mathscr {C}$ has an upper bound in $\mathfrak {F}$. Let $\mathscr {C}_1$ be the projection of $\mathscr {C}$ on the first argument, and $\bar{\mathcal {M}}\equiv \bigcup _{\mathcal {M}\in \mathscr {C}_1}\mathcal {M}$. Then for each $M\in \bar{\mathcal {M}}$, there exists $(\mathcal {M}^M,\mathscr {F}^M)\in \mathscr {C}$ such that $M\in \mathcal {M}^M$. For each $M\in \bar{\mathcal {M}}$, let $\bar{\mathscr {F}}(M)\equiv \mathscr {F}^M(M)$. It gives us a well defined correspondence $\bar{\mathscr {F}}:\bar{\mathcal {M}} \rightarrow \mathscr {P}(\mathcal {N})$ because, for each $M\in \bar{\mathcal {M}}$, $\bar{\mathscr {F}}(M)$ is uniquely defined. Suppose that $(\mathcal {M}, \mathscr {F}), (\mathcal {M}', \mathscr {F}')\in \mathscr {C}$ and $M\in \mathcal {M}\cap \mathcal {M}'$. Then $(\mathcal {M}, \mathscr {F}) \le (\mathcal {M}', \mathscr {F}')$ or $(\mathcal {M}, \mathscr {F}) \ge (\mathcal {M}', \mathscr {F}')$ because $\mathscr {C}$ is totally ordered. In both cases, the definition of the order implies that $\mathscr {F}(M)=\mathscr {F}'(M)$. Thus $\bar{\mathscr {F}}$ is uniquely determined.

We show that $(\bar{\mathcal {M}}, \bar{\mathscr {F}})\in \mathfrak {F}$ below. By construction, it is clear that $(\bar{\mathcal {M}}, \bar{\mathscr {F}})\in \mathfrak {F}$. By construction, $(\bar{\mathcal {M}}, \bar{\mathscr {F}})$ is an upper bound of $\mathscr {C}$. By Zorn’s lemma, there exists a maximal element $(\mathcal {M}^*, \mathscr {F}^*)$ in $\mathfrak {F}$.

Step 3. :

We conclude our proof by showing that $\mathcal {M}^* = \mathcal {M}^I$. By way of contradiction, suppose that there exists $N\in \mathcal {M}^I \backslash \mathcal {M}^*$. By the ultrafilter theorem (see Footnote 13), there exists a non-principal ultrafilter $\mathcal {U}_N$ on N. Let $\hat{\mathcal {M}} = \mathcal {M}^* \cup N$. We extend the ultrafilter mapping $\mathscr {F}^{*}$ to $\hat{\mathcal {M}}$ by defining $\mathscr {F}^{*}(N)$ as follows:

$$\begin{aligned} \mathscr {F}^{*}(N)=\left\{ \begin{array}{ll} \{Z \subset N \ | \ Z \in \mathscr {F}^{*}(M)\} &{} \text { if there is }M\text { with} \ N \in \mathscr {F}^*(M),\\ \mathcal {U}_N &{} \text { otherwise}. \end{array}\right. \end{aligned}$$

We show that $(\hat{\mathcal {M}},\mathscr {F}^{*})\in \mathfrak {F}$ by showing that $\mathscr {F}^{*}$ is still coherent. For any two sets $M, M' \in \mathcal {M}^{*}$, $\mathscr {F}^{*}(M)$ and $\mathscr {F}^{*}(M')$ satisfy coherence by construction. So take $M \in \mathcal {M}^{*}$ and we show $\mathscr {F}^{*}(M)$ and $\mathscr {F}^{*}(N)$ satisfy coherence.

If $N \not \in \mathscr {F}^{*}(M)$, coherence is not required between $\mathscr {F}^{*}(N)$ and $\mathscr {F}^{*}(M)$. Now, suppose $N \in \mathscr {F}^{*}(M)$. Then $\mathscr {F}^{*}(N)=\{Z\subset N \ | \ Z \cap M \in \mathscr {F}^{*}(M)\}$. Then $Z \in \mathscr {F}^{*}(N)$ if and only if $Z \cap M \in \mathscr {F}^{*}(M)$. Thus, $\mathscr {F}^{*}(M)$ and $\mathscr {F}^{*}(N)$ satisfy coherence.

Thus, $(\hat{\mathcal {M}},\hat{\mathscr {F}})\in \mathfrak {F}$, but $(\hat{\mathcal {M}}, \mathscr {F}^*)> (\mathcal {M}^*, \mathscr {F}^*)$. Since $(\mathcal {M}^*, \mathscr {F}^*)$ is a maximal element, it is a contradiction. Thus $\mathcal {M}^* = \mathcal {M}^I$. $\square$

Appendices

Appendix I

The chain property is formally defined as follows. Denote the set of weak orderings on Y by f(Y), and the set of linear orderings on Y by l(Y). A social welfare function for outcome set X and domain $\mathcal {P}$ is a function from $\mathcal {P}$ into the set of complete binary relations on $\mathcal {X}$. Let $\mathcal {P}(Y)$ denote the set of profiles $r \in f(Y)^N$ such that there is some $R \in \mathcal {P}$ for which $r = R|_{Y}$. Given the domain $\mathcal {P}$, we say that a triple $\{x, y, z\}$ of alternatives is free if either

$$\begin{aligned} \mathcal {P}(\{x, y, z\}) = f(\{x, y, z\})^N \text { or } l(\{x, y, z\})^N. \end{aligned}$$

We say that the domain $\mathcal {P}$ has the chain property if $|\mathcal {X}| \ge 3$ and for every two ordered pairs (x, y) and (w, z) of alternatives in $\mathcal {X}$, there exists an integer k and a sequence $v_1, \ldots , v_k$ such that all of the triples $\{x, y, v_1\}, \{y, v_1, v_2\}, \{v_1, v_2, v_3\}, \ldots , \{v_k, w, z\}$ are free.

Proof of Lemma 9

The Ultrafilter Lemma of Campbell and Kelly (2002) shows that a domain of an SWF satisfies the chain property and the SWF satisfies unanimity and independence, $\mathcal {U}_N$ is an ultrafilter. In our environment, because there are finitely many alternatives in $\mathcal {X}$ and the domain is a full domain, $\mathcal {R}^{N}$ has the chain property, and by Lemma 8, $\mathbf {R}$ satisfies the two properties. Thus the Ultrafilter Lemma holds. $\square$

Appendix II

The “if” Part Proof of Proposition 4

Suppose that a coherent hierarchy of ultrafilters $\mathscr {U}$ and a tie-breaking rule $\rho$ induce a voting procedure V. Let $R \in \mathcal {R}^{\mathcal {N}}$. For all $A \in \mathcal {A}$, $T_{K(R)}(A, R) \subset A$ and thus V satisfies feasibility. Further, the unanimity and independence of V follow from the proofs of Lemma 5 and Lemma 6 by replacing X with $A \in \mathcal {A}$, and $\phi ^{\mathscr {U}, \rho }$ with V. To show that V is SCS, take $x \in \mathcal {X}$ and suppose $V(\mathcal {X},R) \not = \{x\}$. Then there is some $y \not = x$ such that $y \in V(\mathcal {X},R) {\setminus } \{x\}$. Then $y \in T_{K(R)}(\mathcal {X}, R)$, which implies that there is no $k = 1, \ldots , K(R)$ and $z \in \mathcal {X}{\setminus } \{x, y\}$ such that $z \succ _{R, k} y$. Thus, $y \in T_{K(R)}(\mathcal {X}{\setminus } \{x\}, R)$, and $y \in V(\mathcal {X}{\setminus } \{x\},R)$.

Conversely, suppose $y \in V(\mathcal {X}{\setminus } \{x\},R)$. Then $y \in T_{K(R)}(\mathcal {X}{\setminus } \{x\}, R)$, which implies that there is no $k = 1, \ldots , K(R)$ and $z \in \mathcal {X}{\setminus } \{x\}$ such that $z \succ _{R, k} y$. Then $y \in T_{K(R)}(\mathcal {X}, R) {\setminus } \{x\}$ or $\{x\} = T_{K(R)}(\mathcal {X}, R)$. Thus $y \in V(\mathcal {X},R) {\setminus } \{x\}$ or otherwise, $\{x\} = V(\mathcal {X},R)$. By the initial assumption, $V(\mathcal {X},R) \not = \{x\}$ and thus we conclude that $y \in V(\mathcal {X},R) {\setminus } \{x\}$. Thus, we obtain $V(\mathcal {X}{\setminus } \{x\},R) = V(\mathcal {X},R) {\setminus } \{x\}$. $\square$

Now suppose that a voting procedure V satisfies feasibility, unanimity, IIA and SCS. Our strategy for proving the “only-if” part of Proposition 4 is as follows. For all $X \in \mathscr {P}(\mathcal {X})$ and all $R \in \mathcal {R}^{\mathcal {N}}$, we define $\phi$ to be:

$$\begin{aligned} \phi (X, R) = V(\mathcal {X}, R^X), \end{aligned}$$

(14)

where $R^X$ is the preference profile that takes X to the top from R. We will show that $\phi$ satisfies unanimity, independence and stability. Then by Theorem 1, a coherent hierarchy of ultrafilters and a tie-breaking rule induce $\phi$, and $\phi$ is a serial dictatorship. Then we show that the coherent hierarchy of ultrafilters and tie-breaking rule which induce $\phi$ also induce V defined in (14).

Fix $R \in \mathcal {R}^{\mathcal {N}}$. The proof of the following lemma, which guarantees that $V(\mathcal {X}, R^X) \subset X$ occupies the rest of the subsection. Eraslan and McLennan (2004) prove a similar result for the case of finite $\mathcal {N}$ as their Lemma 1 (in pages 41 – 42). A similar logic works in our case, even when the case of infinitely many agents is included.

Lemma 16

If $x \in V(\mathcal {X},R)$, then x is not strongly Pareto dominated at R.

Lemma 16 implies that $V(\mathcal {X}, R^X) \subset X$ for every $X \in \mathscr {P}(\mathcal {X})$. Let $x \in \mathscr {P}(\mathcal {X})$. We say that $R'$ is an x -modification of $R$ if $R|_{\mathcal {X}\backslash \{x\}}=R'|_{\mathcal {X}\backslash \{x\}}$ holds. Several results prepare the proof of Lemma 16.

Lemma 17

Suppose that $R'$ is an x-modification of $R$, and $V(\mathcal {X}, R') \not = \{x\} \not = V(\mathcal {X}, R)$. Then $V(\mathcal {X}, R) \backslash \{x\} = V(\mathcal {X}, R') \backslash \{x\}$.

Proof

We have

$$\begin{aligned} \begin{array} {r c l l} V(\mathcal {X}, R) \backslash \{x\} &{} = &{} V(\mathcal {X}\backslash \{x\}, R) &{} \quad \text {(SCS and }V(\mathcal {X}, R) \not = \{x\}) \\ &{} = &{} V(\mathcal {X}\backslash \{x\}, R') &{} \quad \text {(IIA)} \\ &{} = &{} V(\mathcal {X}, R') \backslash \{x\} \text {.} &{} \quad \text {(SCS and }V(\mathcal {X}, R') \not = \{x\}) \end{array} \end{aligned}$$

$\square$

Let $X = \{x_1, \ldots , x_K\}$ denote a set of K alternatives. Take a sequence of preference profiles $\{R^k\}_{k=0}^{K}$ such that each $R^k$ is an $x_{k}$-modification of $R^{k-1}$.

Lemma 18

For all $k \ge 1$, $V(\mathcal {X}, R^k) \subset V(\mathcal {X}, R^{0}) \cup \{x_{1}, \ldots , x_{k}\}$.

Proof

By induction suppose that $V(\mathcal {X}, R^{k-1}) \subset V(\mathcal {X}, R^{0}) \cup \{x_1, \ldots , x_{k-1}\}$ for some $k \ge 1$. Then by Lemma 17, $V(\mathcal {X}, R^{k}) = \{x_{k}\}$ or $V(\mathcal {X}, R^{k}) \backslash \{x_{k}\} = V(\mathcal {X}, R^{k-1}) \backslash \{x_{k}\}$. $\square$

Lemma 19

Suppose that $V(\mathcal {X}, R^0) \not \subset X$. Then for every k, $V(\mathcal {X}, R^k) \backslash X = V(\mathcal {X}, R^0) \backslash X$.

Proof

This follows from repeated applications of Lemma 17 unless $V(\mathcal {X}, R^k) = \{x_k\}$ for some k. In this case applying Lemma 18 to the sequence from $R^k$ to $R^0$ implies that $V(\mathcal {X}, R^0) \subset \{x_{k}, \ldots , x_{1}\} \subset X$. $\square$

Proof of Lemma 16

Let $x \in V(\mathcal {X},R)$. On the contrary suppose that there exists a $y \in \mathcal {X}$ such that $y P_i x$ for all $i \in \mathcal {N}$. Consider $R'$ such that at $R'$, $y P'_i z$ for all $z \in \mathcal {X}$ and all $i \in \mathcal {N}$, and $R'|_{\mathcal {X}{\setminus } \{y\}}=R|_{\mathcal {X}{\setminus } \{y\}}$. Then y is strongly Pareto dominant at $R'$ and so unanimity implies that $V(\mathcal {X},R')=\{y\}$. Since R is a y-modification of $R'$, by Lemma 18, $\{x, y\} \subset V(\mathcal {X},R) \subset V(\mathcal {X},R') = \{y\}$, which is a contradiction. $\square$

Lemma 20

The SCC $\phi$ defined in (14) satisfies unanimity, independence and stability.

Proof

• Unanimity: If y is weakly Pareto dominant in $Y \in \mathscr {P}(\mathcal {X})$ at some $R \in \mathcal {R}^{\mathcal {N}}$, then y is weakly Pareto dominant in $\mathcal {X}$ at $R^Y$. By the unanimity of V and (14), $\phi (Y, R) = V(\mathcal {X}, R^Y) = \{y\}$.

• Independence: Let $Y \in \mathscr {P}(\mathcal {X})$, $R, R' \in \mathcal {R}^{\mathcal {N}}$ and $R|_Y = R'|_Y$. By the definition of $\phi$ in (14), $\phi (Y, R) = V(\mathcal {X}, R^Y)$ and $\phi (Y, R') = V(\mathcal {X}, {R'}^Y)$. We can construct ${R'}^Y$ from $R^Y$ through finitely many interim preference profiles $\{R^k\}$ by repeatedly moving each element $x^k$ so that for each $x^k \not \in Y$ and $y \in Y$ with $R^Y|_{\{x^k, y\}} \not = {R'}^Y|_{\{x^k, y\}}$, $R^k|_{\{x^k, y\}} = {R'}^Y|_{\{x^k, y\}}$ holds. By Lemma 16 and Lemma 19, we obtain $V(\mathcal {X}, R^Y) = V(\mathcal {X}, {R'}^Y)$. Thus, $\phi (Y, R) = \phi (Y, R')$.

• Stability: Fix $X, Y \in \mathscr {P}(\mathcal {X})$ where $Y \subset X$, and $R \in \mathcal {R}^{\mathcal {N}}$ such that $V(\mathcal {X}, R^X) \cap Y \ne \varnothing$. Let $Z = X {\setminus } Y = \{z_1, \ldots , z_K\}$. Define $Z_0 = \varnothing$ and $Z_k = \{z_1, \ldots , z_k \}$. Construct $R^0 = R^X$ and for all $k>0$, a preference profile $R^k$ such that $R^k$ is the $z_k$-modification of $R^{k-1}$ such that $z_k$ is strongly Pareto dominated by alternatives in $X {\setminus } \{z_k\}$ at $R^k$.

Because $V(\mathcal {X}, R^X) \cap Y \ne \varnothing$, $V(\mathcal {X}, R^X) \not \subset Z$. By Lemma 19, $V(\mathcal {X}, R^0) {\setminus } Z = V(\mathcal {X}, R^K) {\setminus } Z$. At the same time, at $R^K$, alternatives in Z are strongly Pareto dominated by alternatives in Y. Thus, by Lemma 16, $V(\mathcal {X}, R^K) {\setminus } Z = V(\mathcal {X}, R^K)$. Because $R^K|_Y = R^Y|_Y$, by the same argument as in the proof of independence, we obtain $V(\mathcal {X}, R^K) = V(\mathcal {X}, R^Y)$ and hence

$$\begin{aligned} V(\mathcal {X}, R^Y) = V(\mathcal {X}, R^X) {\setminus } Z \text {.} \end{aligned}$$

(15)

Then by the definition of $\phi$ in (14), $V(\mathcal {X}, R^X) \cap Y \ne \varnothing$ implies $\phi (X, R) \cap Y \ne \varnothing$ and at the same time,

$$\begin{aligned} \phi (Y, R) = \phi (X, R) {\setminus } Z, \end{aligned}$$

(16)

which implies $\phi (Y, R) = \phi (X, R) \cap Y$. Thus, stability follows. $\square$

The “only-if” part proof of Proposition 4

By Lemma 20, the SCC $\phi$ defined in (14) satisfies unanimity, independence and stability. Then by Theorem 1, $\phi$ is a serial dictatorship. Thus, a coherent hierarchy of ultrafilters $\mathscr {U}$ and a tie-breaking rule $\rho$ induce $\phi$. Then by Definition 6, for all $R \in \mathcal {R}^{\mathcal {N}}$,

$$\begin{aligned} \phi (\mathcal {X}, R)=\mathrm {Top}(T_{K(R)}(\mathcal {X}, R), \rho ). \end{aligned}$$

(17)

By replacing X with $\mathcal {X}$ in (14), for all $R \in \mathcal {R}^{\mathcal {N}}$,

$$\begin{aligned} V(\mathcal {X}, R)=\mathrm {Top}(T_{K(R)}(\mathcal {X}, R), \rho ). \end{aligned}$$

Therefore, a coherent hierarchy of ultrafilters $\mathscr {U}$ and a tie-breaking rule $\rho$ also induce V for $\mathcal {X}$. To show the result for any agenda domain, fix $x \in \mathcal {X}$. Let $A = \mathcal {X}{\setminus } \{x\}$. Then similarly to (17), for all $R \in \mathcal {R}^{\mathcal {N}}$,

$$\begin{aligned} \phi (A, R)=\mathrm {Top}(T_{K(R)}(A, R), \rho ). \end{aligned}$$

By replacing X with A in (14), for all $R \in \mathcal {R}^{\mathcal {N}}$,

$$\begin{aligned} V(A, R^{A})=\mathrm {Top}(T_{K(R)}(A, R), \rho ). \end{aligned}$$

By SCS, for all $R \in \mathcal {R}^{\mathcal {N}}$, $V(A, R) = V(\mathcal {X}, R) {\setminus } \{x\}$ and $V(A, R^A) = V(\mathcal {X}, R^A) {\setminus } \{x\}$. By IIA, $V(A, R) = V(A, R^A)$ for all $R \in \mathcal {R}^{\mathcal {N}}$. Finally, for all $R \in \mathcal {R}^{\mathcal {N}}$, $V(A, R^A) = V(A, R)$, and thus

$$\begin{aligned} V(A, R)=\mathrm {Top}(T_{K(R)}(A, R), \rho ). \end{aligned}$$

Therefore, a coherent hierarchy of ultrafilters $\mathscr {U}$ and a tie-breaking rule $\rho$ also induce V. $\square$