Self-implementation of Social Choice Correspondences in Strong Equilibrium

Abstract

A social choice correspondence is self-implementable in strong equilibrium if it is implementable in strong equilibrium by a social choice function selecting from the correspondence itself as a game form. We characterize all social choice correspondences implementable this way by an anonymous social choice function satisfying no veto power, given that the number of agents is large relative to the number of alternatives. It turns out that these are exactly the social choice correspondences resulting from feasible elimination procedures as introduced in Peleg (Econometrica 46:153–161, 1978).

1 Introduction

A social choice correspondence chooses alternatives based on the preferences of the agents. Generally speaking, one looks for social choice correspondences with desirable properties, such as anonymity, Pareto optimality, and many more. The problem, as already studied in Hurwicz (1972), is that preferences may be private knowledge or, more generally, agents are entitled to report any preferences they wish, resulting in alternatives chosen on the basis of the wrong information, and thus in the desired properties of the social choice correspondence being violated. Requiring strategy-proofness of a social choice function, meaning that no agent can ever benefit from not reporting truthfully, is in general too strong and results in dictatorship (Gibbard, 1973; Satterthwaite, 1975).

Implementation theory is concerned with finding game forms (mechanisms, decentralized systems) of which the equilibrium (Nash, strong, etc.) alternatives in the game with the true preferences coincide with the alternatives assigned to those preferences by the social choice correspondence under consideration. In particular since the work of Hurwicz (1972) there is a large literature on necessary and/or sufficient conditions for implementation of social choice correspondences under various equilibrium concepts, with Maskin (1999) as one of the basic contributions. For an overview of this literature up to the current millennium, see Jackson (2001).

A well-recognized drawback of many of the game forms or mechanisms employed in implementation theory is that they tend to be fairly complicated and not easy to use in practice. For instance, they may require agents to report not just preferences but complete preference profiles, to report integer numbers, etc. In the present paper, we therefore ask what is still feasible by using what we call ‘self-implementation’: this means implementation by a game form that is simply a selection (social choice function) from the correspondence under consideration and, thus, requires the agents just to report their own preferences and nothing else. Apart from the simplicity of such a mechanism its use is also defendable in the sense that it is close to the social choice correspondence that is deemed desirable. Specifically, we ask the following question: which social choice correspondences are self-implementable in strong equilibrium (that is, strategy-profiles such that no coalition can gain by deviating, as introduced in Aumann, 1959)?

It turns out that under some natural additional conditions we are able to give a precise answer to this question: if the number of agents is not too small and the social choice function that selects from the correspondence and implements it is anonymous and satisfies ‘no veto power’, then the correspondence must result from so-called feasible elimination, as already introduced in Peleg (1978). The number of agents being not too small will be made precise and, together with the no veto power property boils down to this number being at least as large as twice the number of alternatives minus one—a condition satisfied in most (political) elections. No veto power means that no agent on its own is able to exclude any alternative from being chosen—again a natural condition in larger elections. This result is quite involved: its proof can be based on a selection from existing results in the literature, as we will indicate; nevertheless, for the convenience of the reader and in order to avoid having to introduce many additional concepts, we present a completely self-contained proof.

As already mentioned, the concept of feasible elimination was introduced by Peleg (1978), in order to construct the so-called exactly and strongly consistent social choice functions: for such social choice functions there is for every profile of (true) preferences a strong equilibrium profile resulting in the truthful alternative. What we explicitly add in the present paper is not only that social choice functions that select from a feasible elimination social choice correspondence implement this correspondence in strong equilibrium, but also that under the additional conditions mentioned above, the feasible elimination correspondence is the unique correspondence for which this can be done.

Section 2 introduces the main concepts and Sect. 3 presents the main result. Most parts of the proof are shifted to the Appendix. Section 4 concludes.

Notations

The following basic notations are used throughout. For a set D, |D| denotes the cardinality of D, P(D) the power set, i.e., the set of all subsets of D, and P ₀(D) the set of all nonempty subsets of D.

2 Self-implementation in Strong Equilibrium

Let A be the set of m alternatives, m ≥ 2, and let N = {1, …, n}, n ≥ 2, be the set of voters. Subsets of N are called coalitions. Let L be the set of all preferences, i.e., complete, antisymmetric and transitive binary relations, on A. Then L ^N is the set of all (preference) profiles. A social choice correspondence (SCC) is a function H : L ^N → P ₀(A). A social choice function (SCF) is a function F : L ^N → A. A social choice function F is a selection from a social choice correspondence H if F(R ^N) ∈ H(R ^N) for every R ^N ∈ L ^N.

A game form is an (n + 1)-tuple g = ( Σ¹, …, Σⁿ, π), where Σⁱ is the strategy set of player (voter) i ∈ N, and $\pi : \Pi _{i=1}^n \Sigma ^i \rightarrow A$ is the outcome function. For every R ^N ∈ L ^N the pair (g, R ^N) is a(n ordinal) game. A strategy profile $\sigma \in \Pi _{i=1}^n \Sigma ^i$ is a strong equilibrium (Aumann, 1959) in the game (g, R ^N) if there are no S ∈ P ₀(N) and $\widetilde {\sigma }^S \in \Pi _{i\in S} \Sigma ^i$ such that $\pi (\widetilde {\sigma }^S,\sigma ^{N \setminus S}) \neq \pi (\sigma )$ and $\pi (\widetilde {\sigma }^S,\sigma ^{N \setminus S}) R^i \pi (\sigma )$ for all i ∈ S.¹

A social choice correspondence H is strong equilibrium implementable if there is a game form g = ( Σ¹, …, Σⁿ, π) such that for every R ^N ∈ L ^N we have

$$\displaystyle \begin{aligned} H(R^N) = \{\pi(\sigma) : \sigma\mbox{ is a strong equilibrium in }(g,R^N) \}\;. \end{aligned}$$

In this case we also say that the game form g implements the SCC H in strong equilibrium.

A social choice function F can be identified with the game form in which the strategy set of each voter is the set L and the outcome function is F, i.e., to each strategy profile (preference profile) Q ^N ∈ L ^N the outcome (alternative) F(Q ^N) is assigned. We denote this game form simply by F. Then (F, R ^N) is a game for every R ^N ∈ L ^N.

Let H be a social choice correspondence. We call H strong self-implementable if there is a social choice function F such that

• (i) F(R ^N) ∈ H(R ^N) for every R ^N ∈ L ^N, and

• (ii) H(R ^N) = {F(Q ^N) : Q ^N is a strong equilibrium in (F, R ^N)}.

In words, the selection F from H implements H in strong equilibrium.

We assume that every SCC H (including every SCF, since this can be viewed as a single-valued SCC) occurring in the rest of the paper is non-imposed, i.e., for every x ∈ A there is an R ^N ∈ L ^N such that H(R ^N) = {x}.

A well-known necessary condition (Maskin, 1999; see also Jackson, 2001) for H to be (self-)implementable is the following.

Maskin Monotonicity

For all R ^N = (R ¹, …, R ⁿ), Q ^N = (Q ¹, …, Q ⁿ) ∈ L ^N, and x ∈ H(Q ^N), if xQ ⁱ y implies xR ⁱ y for all y ∈ A and i ∈ N, then x ∈ H(R ^N).

3 Main Result

The purpose of this section is to characterize all social choice correspondences H that are self-implementable in strong equilibrium if the number of voters is relatively large and the selection that implements H satisfies two natural properties, namely anonymity and no-veto power. The latter means that no voter on his own is able to exclude any alternative from being chosen. We arrive at this theorem by combining a number of existing results in the literature, but our proof will be self-contained.

We start with the following concept, introduced by Peleg (1978). A social choice function F is exactly and strongly consistent (ESC) if for every R ^N ∈ L ^N the game (F, R ^N) has a strong equilibrium Q ^N ∈ L ^N such that F(Q ^N) = F(R ^N). We now immediately have the following result.

Lemma 3.1

Let the selection F from the social choice correspondence H implement H in strong equilibrium. Then F is ESC.

Proof

Let R ^N ∈ L ^N and x = F(R ^N). Then x ∈ H(R ^N) and therefore there is a strong equilibrium Q ^N of the game (F, R ^N) such that F(Q ^N) = x. Hence, F(Q ^N) = F(R ^N). □

The SCCs of interest in this section are based on the so-called feasible elimination procedures, defined for the case where n + 1 ≥ m. Informally, first, assign weights $\beta (x)\in \mathbb {N}$ to the alternatives x ∈ A such that the sum of these weights is equal to n + 1. Consider a preference profile and take an alternative x that is bottom ranked at least β(x) times. Eliminate β(x) preferences where x is bottom ranked, and next eliminate x everywhere in the remaining profile. Repeat this procedure until one alternative remains.

Formally, we have the following definition. Let n + 1 ≥ m. A function $\beta : A \rightarrow \mathbb {N}$ such that ∑_{x ∈ A} β(x) = n + 1 is called a weight function.

Definition 3.2

Let β be a weight function. Let R ^N ∈ L ^N. A (β-)feasible elimination procedure ((β-)f.e.p.) for R ^N is a sequence (x ₁, C ₁;…;x _m−1, C _m−1;x _m) such that

• (a) A = {x ₁, …, x _m},

• (b) C ₁, …, C _m−1 are pairwise disjoint subsets of N and |C _j| = β(x _j) for all j = 1, …, m − 1,

• (c) x _k R ⁱ x _j for all j = 1, …, m − 1, k = j + 1, …, m, and i ∈ C _j.

Thus, in a feasible elimination procedure² (x ₁, C ₁;…;x _m−1, C _m−1;x _m), by condition (c) alternative x ₁ is bottom ranked for all voters in C ₁ and by condition (b), |C ₁| = β(x ₁). Now eliminate the preferences of the voters in C ₁, and eliminate x ₁ from the preferences of the remaining voters. In the remaining profile, x ₂ is bottom ranked for all voters in C ₂ by condition (c), and by condition (b), |C ₂| = β(x ₂), so that the preferences of the voters in C ₂ can be eliminated and x ₂ can be eliminated from the remaining profile. And so on and so forth. Observe that after eliminating x ₁ there are n − β(x ₁) voters left, after eliminating x ₂ there are n − β(x ₁) − β(x ₂) voters left, and after eliminating x _m−1 there are n − β(x ₁) −… − β(x _m−1) = β(x _m) − 1 ≥ 0 voters left.

An important observation about f.e.p.s. is the following. Suppose an alternative x is bottom ranked by (at least) the voters in some coalition S with |S| = β(x), in a profile R ^N ∈ L ^N. Then x must be eliminated in every f.e.p. for R ^N. To see this suppose there is an f.e.p. in which x is not eliminated and let y be the alternative eliminated last, say via coalition T. Then the finally left voters form a coalition S′ containing S. We have β(y) + β(x) = |T| + |S′| + 1 by the foregoing, but also |T| + |S′|≥ β(y) + β(x), a contradiction.

It is not difficult to see that there exists always at least one f.e.p. under the assumptions in the definition. If every alternative x _j is bottom ranked less than β(x _j) times, then the total number of voters is at most $\sum _{j=1}^m \beta (x_j) - m$, which is equal to n + 1 − m and therefore strictly smaller than n. A similar argument can be made after elimination of each alternative x ₁, …, x _m−2.

Let β be a weight function. An alternative x is R ^N-maximal for β if there exists a β-f.e.p. (x ₁, C ₁;…;x _m−1, C _m−1;x). We denote

$$\displaystyle \begin{aligned} M_\beta(R^N) = \{x \in A : x \mbox{ is }R^N\mbox{-maximal for }\beta\}.\end{aligned}$$

The following lemma repeats the known result that M _β is Maskin monotonic. For completeness, a proof can be found in the appendix, where also references to the literature are provided. For a weight function β as in Definition 3.2 we use the notation β(B) =∑_{x ∈ B} β(x) for B ⊆ A.

Lemma 3.3

Let β be a weight function. Then M _β is Maskin monotonic.

Next, we provide a characterization of maximal alternatives. Again, see the appendix for references and a proof.

Lemma 3.4

Let β be a weight function. Let x ∈ A and R ^N ∈ L ^N . The following statements are equivalent.

• (i) x ∈ M _β(R ^N).

• (ii) There are no S ∈ P ₀(N) and B ∈ P ₀(A) such that |S|≥ β(A ∖ B), x ∈ A ∖ B, and y R ⁱ x for all i ∈ S and y ∈ B.

The following result says that M _β is self-implementable in strong equilibrium by any selection from it.

Proposition 3.5

Let β be a weight function and let F be a selection from M _β . Then F implements M _β in strong equilibrium.

Proof

• (a) Let R ^N ∈ L ^N and x ∈ M _β(R ^N). We show that there is a strong equilibrium Q ^N of (F, R ^N) such that F(Q ^N) = x. Let (x ₁, C ₁;…;x _m−1, C _m−1;x) be an f.e.p. for R ^N and consider the profile Q ^N ∈ L ^N obtained from R ^N by lowering x _j to the last position in the preferences of the voters in C _j, j = 1, …, m − 1, leaving everything else in tact. Then M _β(Q ^N) = {x}, hence F(Q ^N) = x. Also, Q ^N is a strong equilibrium of (F, R ^N). Indeed assume on the contrary that there exist S ∈ P ₀(N) and P ^S ∈ L ^S such that F(P ^S, Q ^N∖S) = z ≠ x and zR ⁱ x for all i ∈ S. Then z = x _j for some 1 ≤ j ≤ m − 1. By the definition of an f.e.p., xR ⁱ z for all i ∈ C _j, hence S ∩ C _j = ∅. Since |C _j| = β(z) and z is the last ranked alternative of Q ^ℓ for all ℓ ∈ C _j, we have that z∉M _β(P ^S, Q ^N∖S), contradicting F(P ^S, Q ^N∖S) = z.

• (b) Let Q ^N be strong equilibrium of (F, R ^N) with F(Q ^N) = x. We show that x ∈ M _β(R ^N). It is sufficient to show that (ii) of Lemma 3.4 holds for x. Suppose not. Then there is an S ∈ P ₀(N) and B ∈ P ₀(A), x∉B, such that yR ⁱ x for all y ∈ B and i ∈ S, and |S|≥ β(A ∖ B). Consider a profile P ^S ∈ L ^S with A ∖ B at bottom for all voters in S. Then by the remarks following Definition 3.2, all elements of A ∖ B will be eliminated in any f.e.p. for (P ^S, Q ^N∖S), so that M _β(P ^S, Q ^N∖S) ⊆ B, hence S has an improvement, a contradiction to the assumption that Q ^N is strong equilibrium of (F, R ^N). □

Before turning to a converse of Proposition 3.5 we introduce two additional possible properties of a social choice correspondence H. Of course, these properties also apply for a social choice function F, since a social choice function can be identified with a single-valued social choice correspondence.

Anonymity

For all R ^N ∈ L ^N and for all permutations π of N, H(R ¹, …, R ⁿ) = H(R ^π(1), …, R ^π(n)).

No Veto Power

For all x ∈ A and i ∈ N, there is no R ⁱ ∈ L such that x∉H(R ⁱ, R ^N∖{i}) for all R ^N∖{i}∈ L ^N∖{i}.

Proposition 3.6

Let social choice function F be ESC, anonymous, and satisfy No Veto Power, and let n + 1 ≥ m. Then there is a weight function β such that F is a selection from M _β.

Also this proposition can be deduced from earlier results in the literature, but for completeness we provide a self-contained proof in the appendix. The following theorem is a corollary to Propositions 3.5 and 3.6 and the main result of this section.

Theorem 3.7

Let n + 1 ≥ m and let the social choice function H be implementable in strong equilibrium by a selection F which is anonymous and satisfies No Veto Power. Then H = M _β for some weight function β.

Proof

By Lemma 3.1 and Proposition 3.6 it follows that there is a weight function β such that F(R ^N) ∈ M _β(R ^N) for all R ^N ∈ L ^N. By Proposition 3.5, F implements M _β in strong equilibrium. Hence,

$$\displaystyle \begin{aligned} H(R^N) = \{ F(Q^N) : Q^N\mbox{ is a strong equilibrium in }(F,R^N) \} = M_\beta(R^N) \end{aligned}$$

for all R ^N ∈ L ^N, which completes the proof. □

Theorem 3.7 says, roughly, that if the number of voters is relatively large, then the only social choice correspondences which are self-implementable in a reasonable way in strong equilibrium are the correspondences M _β. Typically, in political elections the constraint n + 1 ≥ m is satisfied and the conditions of Anonymity and No Veto Power for a final selection of a candidate are natural if not compelling.

The conditions of Anonymity and No Veto Power in the theorem are on the selection F. In general we can make the following observations. It is possible that H is anonymous but F is not: let H assign to every profile the set of all top-ranked alternatives, and let F select from that set the top-ranked alternative of agent 1. Also, F can be anonymous but H not: fix an alternative a ∈ A and let H assign all top-ranked alternatives, but leave out a if this is top-ranked by agent 1 alone, and let F select from H the alternative that is ranked maximally according to a fixed preference Q which has a last. Further, if F satisfies No Veto Power, then also H does, but the converse is not necessarily true: fix an alternative a, let H assign all top-ranked alternatives, and let F select from that according to a fixed ordering Q, but leave out a as a possible choice if it is last ranked by agent 1. Then H satisfies No Veto Power but F does not.

Since, by the preceding remarks, M _β in the theorem satisfies No Veto Power, it follows by the definition of a β-f.e.p. that β(x) ≥ 2 for all x ∈ A and, thus, that the number of agents is at least as large as twice the number of alternatives minus one.

4 Concluding Remarks

Clearly, the approach in this paper leaves many open questions. We mention two of these. First, which social choice correspondences are self-implementable in strong equilibrium if the number of agents is relatively small—for instance, a small group of people in a restaurant has to make some common choices from a large menu of dishes? Second, what can be said about self-implementation in Nash equilibrium?

Appendix: Remaining Proofs

Proofs of Lemmas 3.3 and 3.4

Proof of Lemma 3.3

³ Let Q ^N and R ^N be as in the definition of Maskin monotonicity, and x ∈ M _β(Q ^N). Without loss of generality we assume that there is a voter v such that Q ^N∖{v} = R ^N∖{v}. Let f ^∗ = (x ₁, C ₁;…;x _m−1, C _m−1;x) be an f.e.p. for Q ^N, where A = {x ₁, …, x _m−1, x}. If v∉C ₁ ∪… ∪ C _m−1, then it is easy to see that f ^∗ is still an f.e.p. for R ^N, so that x ∈ M _β(R ^N). Now assume v ∈ C ₁ ∪… ∪ C _m−1. If v ∈ C _j with j > 1, then we may eliminate x ₁, …, x _j−1 and all voters in C ₁ ∪… ∪ C _j−1 first, and next continue the argument with the remaining profile, where now all voters in C _j have x _j bottom ranked according to $Q^{C_j}$. So, without loss of generality, let v ∈ C ₁.

The rest of the proof is based on a three-step algorithm.

• If the bottom alternative of R ^v is equal to x ₁, then f ^∗ is still an f.e.p. for R ^N and we are done. Otherwise, go to Step 2.

• Let the bottom alternative of R ^v be x _ℓ ≠ x ₁, so ℓ ∈{2, …, m − 1}. If all voters in C _ℓ have x _ℓ as bottom alternative in R ^N, then we can first eliminate x _ℓ via C _ℓ and go back to Step 1 for the reduced profile. Otherwise, go to Step 3.

• Take $\hat {v} \in C_\ell$ with x _ℓ not as bottom alternative and note that the bottom alternative of $R^{\hat {v}}=Q^{\hat {v}}$ is some x _j with j < ℓ (since x _j must be eliminated before x _ℓ in f ^∗). Then modify C _ℓ to $\hat {C}_\ell = (C_\ell \cup \{v\}) \setminus \{\hat {v}\}$ and modify C ₁ to $\hat {C}_1 = (C_1 \cup \{\hat {v}\}) \setminus \{v\}$. (In words, we switch v and $\hat {v}$.) Go back to Step 1.

Repeat this procedure until the final substitute of v in the modified C ₁ has x ₁ at bottom. Then we can apply an f.e.p. resulting in x, so that x ∈ M _β(R ^N). □

Proof of Lemma 3.4

⁴ For the implication (i) ⇒ (ii), let x ∈ M _β(R ^N) and let (x ₁, C ₁;…; x _m−1, C _m−1;x) be an f.e.p. for R ^N. Suppose there were S and B as in (ii). Write $B = \{x_{i_1},\ldots ,x_{i_{|B|}}\} \subseteq \{x_1,\ldots ,x_{m-1}\}$, then $\left (\cup _{j=1}^{|B|} C_{i_j}\right ) \cap S = \emptyset$ by definition of an f.e.p., and $|\cup _{j=1}^{|B|} C_{i_j}| = \beta (B)$. Hence $|S| + |\cup _{j=1}^{|B|} C_{i_j}| \geq \beta (A\setminus B) + \beta (B) = n+1$, a contradiction.

We prove the implication (ii) ⇒ (i) by induction on the number of alternatives m. Let x ∈ A and assume that (ii) holds.

If m = 2, say A = {x, y}, then there is no S ∈ P ₀(N) such that |S|≥ β(x) and yR ⁱ x for all i ∈ S, so that M _β(R ^N) = {x}.

Now suppose that m > 2 and that the implication (ii) ⇒ (i) holds if there are less than m alternatives. For every B ∈ P ₀(A ∖{x}) denote S _B = {i ∈ N : yR ⁱ x for all y ∈ B}. Then (ii) is equivalent to

$$\displaystyle \begin{aligned} |S_B| < \beta(A\setminus B) \mbox{ for all } B\in P_0(A\setminus\{x\}) \end{aligned} $$

(1)

hence to

$$\displaystyle \begin{aligned} |N\setminus S_B| \geq \beta(B) \mbox{ for all } B\in P_0(A\setminus\{x\}). \end{aligned} $$

(2)

We consider two cases.

Case 1 There exists $\widetilde {B} \in P_0(A \setminus \{x\})$ with $|\widetilde {B}| \leq m-2$ and $|N\setminus S_{\widetilde {B}}| = \beta (\widetilde {B})$.

For this case we consider the two following subproblems:

• $N_1=N\setminus S_{\widetilde {B}}$, $A_1 = \widetilde {B} \cup \{x\}$, β ₁(y) = β(y) for all $y \in \widetilde {B}$, β ₁(x) = 1, and $R_1^i = R^i_{|A_1}$ for all i ∈ N ₁.⁵

• $N_2=S_{\widetilde {B}}$, $A_2=A\setminus \widetilde {B}$, β ₂(y) = β(y) for all y ∈ A ₂, and $R_2^i = R^i_{|A_2}$ for all i ∈ N ₂.

We next show that (1) holds for the first subproblem. If not, then there is a $B \in P_0(\widetilde {B})$ such that |T|≥ β ₁(A ₁ ∖ B), where $T = \{ i\in N_1 : y R_1^i x \mbox{ for all } y\in B\}$. Then , hence |S _B|≥ β(A ∖ B), which is a violation of (1) for the original problem. Therefore, (1) must hold for the first subproblem, implying that $x \in M_{\beta _1}(R^{N_1}_1)$ by induction.

Similarly, suppose that (1) does not hold for the second subproblem. Then there is a $B \in P_0(A \setminus (\widetilde {B} \cup \{x\}))$ such that |T|≥ β ₂(A ₂ ∖ B), where now $T=\{ i\in S_{\widetilde {B}} : y R^i_2 x \mbox{ for all } y \in B\}$. Then $|T \cup (N\setminus S_{\widetilde {B}})| = |T| + |N\setminus S_{\widetilde {B}}| \geq [\beta (A) -\beta (B) -\beta (\widetilde {B})] + \beta (\widetilde {B}) = \beta (A \setminus B)$, which is a violation of (1) for the original problem. We conclude that (1) must hold for the second subproblem as well, so that $x \in M_{\beta _2}(R^{N_2}_2)$ by induction.

Now let $(z_1,C_1;\ldots ;z_{|\widetilde {B}|},C_{|\widetilde {B}|};x)$ be an f.e.p. for the first subproblem and let $(u_1,D_1;\ldots ;u_{m-1-|\widetilde {B}|},D_{m-1-|\widetilde {B}|};x)$ be an f.e.p. for the second subproblem. Since, in particular, yR ⁱ x for all $y \in \widetilde {B}$ and $i\in N_2 = S_{\widetilde {B}}$, it follows that

$$\displaystyle \begin{aligned} (u_1,D_1;\ldots;u_{m-1-|\widetilde{B}|},D_{m-1-|\widetilde{B}|}; z_1,C_1;\ldots;z_{|\widetilde{B}|},C_{|\widetilde{B}|};x) \end{aligned}$$

is an f.e.p. for the original problem, implying that in this case we have x ∈ M _β(R ^N).

Case 2 For all $\widetilde {B} \in P_0(A \setminus \{x\})$ with $|\widetilde {B}| \leq m-2$ we have $|N\setminus S_{\widetilde {B}}| > \beta (\widetilde {B})$.

Suppose there is an ℓ ∈ N such that x is not ranked at the last or second last position in R ^ℓ, and let $\widehat {y}$ be the alternative ranked right below x. We switch x and $\widehat {y}$ in voter ℓ’s preference to obtain a new preference $\widehat {R}^\ell$ and a new preference profile $\widehat {R}^N=(R^1,\ldots ,R^{\ell -1},\widehat {R}^\ell , R^{\ell +1},\ldots ,R^N)$ that still satisfies (2): for any set B with |B|≤ m − 2 this holds because of the strict inequality in Case 2, and for B = A ∖{x} this holds since x is not ranked last in $\widehat {R}^\ell$.

If Case 1 applies to $\widehat {R}^N$, then $x\in M_\beta (\widehat {R}^N)$. Thus, by Lemma 3.3, x ∈ M _β(R ^N). If Case 1 does not apply to $\widehat {R}^N$, then we repeat this step for some voter ℓ′∈ N with x not ranked last or second last at $\widehat {R}^{\ell '}$, and so on, until either Case 1 applies or there is no voter left with x not ranked at the last or second last position.

In the latter case, we have a profile, say ${\widetilde{R}}^N$, for which still (2) holds and with x ranked last or second last for each voter i ∈ N. Observe that y is last ranked for all voters in N ∖ S _{y} for all y ∈ A ∖{x}. Also, by (2), |N ∖ S _{y}|≥ β(y) for all y ∈ A ∖{x}. It follows that in any f.e.p. for ${\widetilde{R}}^N$ every y ∈ A ∖{x} is bottom ranked by at least β(y) voters and therefore eliminated, so that $M_\beta (\widetilde {R}^N)=\{x\}$. By Lemma 3.3 again, x ∈ M(R ^N).

By (2), Cases 1 and 2 are exhaustive, which completes the proof of the lemma. □

Proof of Proposition 3.6

We now turn to the proof of Proposition 3.6.⁶ It will be convenient to introduce some terminology related to effectivity functions.⁷ Let F be a social choice function and let S ⊆ N and B ⊆ A. Then S is (F-)effective for B is there is R ^S ∈ L ^S such that F(R ^S, Q ^N∖S) ∈ B for all Q ^N∖S ∈ L ^N∖S. For every x ∈ A define the integer b(x) (the ‘blocking coefficient’ of x) by

$$\displaystyle \begin{aligned} b(x) = \min \{ |S| : S \subseteq N\mbox{ is effective for }A \setminus \{x\}\} \;. \end{aligned}$$

By non-imposition of F, we have 1 ≤ b(x) ≤ n for all x ∈ A. We write b(B) for ∑_{x ∈ B} b(x), B ⊆ A. Of course, b(⋅) depends on F but this will be suppressed from notation if confusion is unlikely.

We start with three useful observations.⁸

Lemma A.1

Let the SCF F be anonymous. Let S ⊆ N and B ⊆ A such that |S|≥ b(A ∖ B). Then S is effective for B.

Proof

Write A ∖ B = {x ₁, …, x _k}, where k ≥ 0. Let S ₁, …, S _k be a partition of S such that |S _j|≥ b(x _j) for each j = 1, …, k, and let $R^{S_j} \in L^{S_j}$ such that $F(R^{S_j},Q^{N \setminus S_j}) \in A\setminus \{x_j\}$ for each j = 1, …, k and $Q^{N \setminus S_j} \in L^{N \setminus S_j}$. Then F(R ^S, Q ^N∖S) ∈ B for all Q ^N∖S ∈ L ^N∖S. So S is effective for B. □

Lemma A.2

Let the SCF F be ESC and let S ⊆ N be effective for B ⊆ A. Let R ^N ∈ L ^N and x ∈ A ∖ B such that yR ⁱ x for all y ∈ B and i ∈ S. Then F(R ^N) ≠ x.

Proof

Suppose on the contrary that F(R ^N) = x and let Q ^N be a strong equilibrium in (F, R ^N) with F(Q ^N) = x. Since S is effective for B, there is P ^S ∈ L ^S such that F(P ^S, Q ^N∖S) ∈ B, contradicting that Q ^N is a strong equilibrium in (F, R ^N). □

Lemma A.3

Let the SCF F be ESC and anonymous, and assume that b(A) = n + 1. Then F is a selection from M _b.

Proof

Let R ^N ∈ L ^N and x = F(R ^N). Let B ⊆ A, S ⊆ N, |S|≥ b(A ∖ B), and x ∈ A ∖ B. In order to prove that x ∈ M _b(R ^N), it is by Lemma 3.4 sufficient to prove that we do not have yR ⁱ x for all y ∈ B and i ∈ S.

On the contrary, suppose that yR ⁱ x for all y ∈ B and i ∈ S. Since |S|≥ b(A ∖ B), Lemma A.1 implies that S is effective for B. Then Lemma A.2 implies that F(R ^N) ≠ x, a contradiction. □

Notice that in order to obtain Proposition 3.6 we may try and derive the condition b(A) = n + 1 in Lemma A.3. This is, essentially, what is done in the remainder of the proof.

Lemma A.4

Let the SCF F be ESC, S ⊆ N, B ⊆ A, and suppose that for every Q ^N∖S ∈ L ^N∖S there is P ^S ∈ L ^S such that F(P ^S, Q ^N∖S) ∈ B. Then S is effective for B. ⁹

Proof

On the contrary, suppose that for every Q ^S ∈ L ^S there is P ^N∖S ∈ L ^N∖S such that F(Q ^S, P ^N∖S) ∈ A ∖ B. Consider a profile R ^N ∈ L ^N such that xR ⁱ y and yR ^j x for every i ∈ S, j ∈ N ∖ S, x ∈ B, and y ∈ A ∖ B. Let z = F(R ^N) and let Q ^N be a strong equilibrium of (F, R ^N) with F(Q ^N) = z. If z ∈ A ∖ B, then S can improve by a profile P ^S as in the statement of the lemma. If z ∈ B, then N ∖ S can improve by a profile P ^N∖S as above. □

In what follows we will use the notion of a generalized partition or g-partition of a set, which is a partition in which some elements may be empty.

Lemma A.5

Let the SCF F be ESC. Then there are no p ≥ 2, partition B ₁, …, B _p of A and g-partition S ₁, …, S _p of N such that N ∖ S _i is effective for B _i , for every i = 1, …, p.

Proof

Suppose not, so (g-)partitions as in the lemma exist. Consider a profile R ^N as in the following table:

(meaning that every member of coalition S ₁ prefers all alternatives of B ₂ over all alternatives of B ₃, all alternatives of B ₃ over all alternatives of B ₄, and so on and so forth). Now by Lemma A.2, F(R ^N)∉B _i for every i = 1, …, p. Since $\cup _{i=1}^p B_i = A$, this is a contradiction. □

Lemma A.6

Let the SCF F be ESC and satisfy NVP. Then there are no partition {x}, B ₁, B ₂ of A and g-partition S, T ₁, T ₂ of N such that |S| = b(x) and N ∖ T _j is effective for B _j for j = 1, 2.

Proof

Suppose not, so (g-)partitions as in the lemma exist.

First, suppose S = N. Then for every i ∈ N, |N ∖{i}| < |S| = b(x). Therefore, for every Q ^N∖{i}∈ L ^N∖{i} there is P ⁱ ∈ L such that F(P ⁱ, Q ^N∖{i}) = x, so that by Lemma A.4, {i} is effective for x. Since |A|≥ 2 this violates NVP of F. Thus, S ≠ N and b(x) < n. By NVP, also b(x) > 1. So |S|≥ 2 and T ₁ ∪ T ₂ ≠ ∅.

Let now S ₁, S ₂ be a partition of S and consider a profile R ^N as in the following table:

Since S = S ₁ ∪ S ₂ is effective for A ∖{x} = B ₁ ∪ B ₂ we have by Lemma A.2 that F(R ^N) ≠ x. Without loss of generality we assume that F(R ^N) ∈ B ₁. Let Q ^N be a strong equilibrium in (F, R ^N) with F(Q ^N) = F(R ^N), hence F(Q ^N) ≠ x.

Case 1 xQ ⁱ y for some i ∈ S, without loss of generality i ∈ S ₁, and y ∈ A ∖{x}.

In this case consider the partition {x}, {y}, A ∖{x, y} of A and the g-partition S ∖{i}, {i}, T ₁ ∪ T ₂ of N. Since |S ∖{i}| < b(x) we have that N ∖ (S ∖{i}) is effective for {x} by Lemma A.4. By NVP and Lemma A.4, N ∖{i} is effective for {y}. Hence, by Lemma A.5, N ∖ (T ₁ ∪ T ₂) is not effective for A ∖{x, y}. In turn, again by Lemma A.4, this implies that T ₁ ∪ T ₂ is effective for {x, y}. Consider a profile $P^{T_1 \cup T_2} \in L^{T_1 \cup T_2}$ such that xP ^j yP ^j z for all j ∈ T ₁ ∪ T ₂ and z ∈ A ∖{x, y}. Then by Lemma A.2, $F(P^{T_1 \cup T_2},Q^S) \in \{x,y\}$. Since xQ ⁱ y and since T ₁ ∪ T ₂ ∪{i} = N ∖ (S ∖{i}) is effective for {x}, again by Lemma A.2, $F(P^{T_1 \cup T_2},Q^S) \neq y$. Hence, $F(P^{T_1 \cup T_2},Q^S) =x$. This contradicts that Q ^N is a strong equilibrium in (F, R ^N).

Case 2 yQ ⁱ x for all i ∈ S and y ∈ A ∖{x}.

In this case, consider the partition {x}, B ₁, B ₂ of A and the g-partition S ₂, S ₁ ∪ T ₁, T ₂ of N. Since |S ₂| < b(x) we have by Lemma A.4 that N ∖ S ₂ is effective for {x}. By assumption, N ∖ T ₂ is effective for B ₂. Hence by Lemma A.5, N ∖ (S ₁ ∪ T ₁) is not effective for B ₁, which in turn by Lemma A.4 implies that S ₁ ∪ T ₁ is effective for A ∖ B ₁. Consider a profile $P^{S_1 \cup T_1} \in L^{S_1 \cup T_1}$ such that yP ^j xP ^j z for all j ∈ S ₁ ∪ T ₁, y ∈ B ₂, and z ∈ B ₁. By Lemma A.2, $F(P^{S_1 \cup T_1},Q^{S_2 \cup T_2}) \notin B_1$. Since by assumption S ₁ ∪ S ₂ ∪ T ₁ is effective for B ₂, by Case 2 yQ ⁱ x for all y ∈ B ₂ and i ∈ S, and N ∖ T ₂ is effective for B ₂, we have by Lemma A.2 that $F(P^{S_1 \cup T_1},Q^{S_2 \cup T_2}) \neq x$. Hence $F(P^{S_1 \cup T_1},Q^{S_2 \cup T_2}) \in B_2$. Since F(Q ^N) = F(R ^N) ∈ B ₁, S ₁ ∪ T ₁ has an improvement, contradicting that Q ^N is a strong equilibrium of (F, R ^N). □

Lemma A.7

Let the SCF F be ESC and satisfy NVP, and 1 ≤ k ≤ m − 2. Then there are no partition {x ₁}, …, {x _k}, B ₁, B ₂ of A and g-partition S ₁, …, S _k, T ₁, T ₂ of N such that |S _i| = b(x _i) for each i = 1, …, k, N ∖ T ₁ is effective for B ₁ , and N ∖ T ₂ is effective for B ₂.

Proof

The proof is by induction on k. For k = 1 this is Lemma A.6. Let 2 ≤ k ≤ m − 2 and suppose that the statement in the lemma holds for k − 1. Suppose, on the contrary, that the statement does not hold for k, and let {x ₁}, …, {x _k}, B ₁, B ₂ and S ₁, …, S _k, T ₁, T ₂ be as in the lemma. Since S _i ≠ ∅ for every i = 1, …, k, we have ∅ ≠ S _k ∪ T ₁ ≠ N. By Lemma A.4, either S _k ∪ T ₁ is effective for A ∖ ({x _k}∪ B ₁) or N ∖ (S _k ∪ T ₁) is effective for {x _k}∪ B ₁. In the first case, Lemma A.6 is violated for the partition {x _k}, B ₁, A ∖ ({x _k}∪ B ₁) of A and the g-partition S _k, T ₁, N ∖ (S _k ∪ T ₁) of N. In the second case, the induction hypothesis is violated for the partition {x ₁}, …, {x _k−1}, {x _k}∪ B ₁, B ₂ of A and the g-partition S ₁, …, S _k−1, S _k ∪ T ₁, T ₂ of N. □

The next lemma says that an ESC social choice function is ‘subadditive’.¹⁰

Lemma A.8

Let the SCF F be ESC, let S ₁ ⊆ N be effective for B ₁ ⊆ A and let S ₂ ⊆ N be effective for B ₂ ⊆ A, such that B ₁ ∩ B ₂ = ∅. Then S ₁ ∩ S ₂ is effective for B ₁ ∪ B ₂.

Proof

• (a) Say that coalition S is s-effective for a set of alternatives B if there is a partition B ₁, …, B _k of B and there are coalitions S ₁, …, S _k such that S _j is effective for B _j, j = 1, …, k, and $S = \cap _{j=1}^k S_j$. Clearly, if S is effective for B, then S is also s-effective for B by taking k = 1, S ₁ = S, B ₁ = B. We will prove the converse, which will imply the lemma.

• (b) We first prove that if S is s-effective for B, then N ∖ S is not s-effective for A ∖ B. Suppose the latter were not the case, i.e., both S is s-effective for B and N ∖ S is s-effective for A ∖ B. Let B ₁, …, B _k and C ₁, …, C _ℓ be the associated partitions of B and A ∖ B, and let S ₁, …, S _k and T ₁, …, T _ℓ be the associated coalitions, hence $S = \cap _{j=1}^k S_j$ and $N \setminus S = \cap _{h=1}^\ell T_h$. List S ₁, …, S _k, T ₁, …, T _ℓ as V ₁, …, V _p and list the associated sets of alternatives as D ₁, …, D _p (where p = k + ℓ). Then for every i ∈ N there is q ∈{1, …, p} such that i∉V _q. Consider a preference profile R ^N such that for every i ∈ N, D _q+1 R ⁱ D _q+2 R ⁱ…R ⁱ D _p R ⁱ D ₁ R ⁱ…R ⁱ D _q. Let x ∈ A. If x ∈ D _q for some q > 1, then D _q−1 R ⁱ x for all i ∈ V _q−1, so that by Lemma A.2 we have F(R ^N) ≠ x. If x ∈ D ₁, then D _p R ⁱ x for all i ∈ V _p, so that again by Lemma A.2 we have F(R ^N) ≠ x. This is not possible, hence we have that if S is s-effective for B, then N ∖ S is not s-effective for A ∖ B.

• (c) Now, finally, assume that S is s-effective for B. Then by part (b), N ∖ S is not s-effective for A ∖ B, hence by part (a), N ∖ S is not effective for A ∖ B. By Lemma A.4, S is effective for B. This concludes the proof of the lemma. □

The final lemma we need is the following.

Lemma A.9

Let the SCF F be ESC and satisfy NVP. Let 0 ≤ k ≤ m − 2. Then there are no partition {x ₁}, …, {x _m} of A and g-partition S ₁, …, S _m of N such that |S _j| = b(x _j) for j = 1, …, k and |N ∖ S _j| is effective for {x _j} for j = k + 1, …, m.

Proof

For k = 0 this follows from Lemma A.5. Now let k > 0. Suppose on the contrary that we had {x ₁}, …, {x _m} and S ₁, …, S _m as in the lemma. By repeated application of Lemma A.8 we have that N ∖ (S _k+1 ∪… ∪ S _m−1) is effective for {x _k+1, …, x _m−1}. Now the partition {x ₁}, …, {x _k}, {x _k+1, …, x _m−1}, {x _m} and g-partition S ₁, …, S _k, T ₁, T ₂ with T ₁ = S _k+1 ∪… ∪ S _m−1 and T ₂ = S _m violate Lemma A.7. □

Proof of Proposition 3.6

In view of Lemma A.3, it is sufficient to prove that b(A) = n + 1. Clearly, b(A) ≥ n + 1, otherwise N would have some profile R ^N such that F(R ^N)∉A, which is clearly impossible. Write A = {x ₁, …, x _m}. We distinguish two cases.

Case 1 b(A) ≥ n + m. Then $n \leq b(A) - m = \sum _{j=1}^m (b(x_j)-1)$, so that there is a g-partition S ₁, …, S _m of N with |S _j|≤ b(x _j) − 1 for every j = 1, …, m, which by using Lemma A.4 violates Lemma A.9 for k = 0.

Case 2 b(A) = n + (m − k) for some k ∈{1, …, m − 2}. In this case, let S _j, j = 1, …, k, be coalitions with |S _j| = b(x _j). Since

$$\displaystyle \begin{aligned} \begin{array}{rcl} \sum_{j=1}^k |S_j| &\displaystyle = &\displaystyle b(A) - (b(x_{k+1}+ \ldots +b(x_m)) \\ &\displaystyle = &\displaystyle n + (m-k) - (b(x_{k+1}+ \ldots +b(x_m)) \\ &\displaystyle \leq &\displaystyle n + (m-k) - (m-k) \\ &\displaystyle = &\displaystyle n \end{array} \end{aligned} $$

the S _j can be chosen disjoint. Also,

$$\displaystyle \begin{aligned} \begin{array}{rcl} n - \sum_{j=1}^k |S_j| &\displaystyle = &\displaystyle n - (b(A) - \sum_{j=k+1}^m b(x_j)) \\ &\displaystyle = &\displaystyle n - n - (m-k) + \sum_{j=k+1}^m b(x_j)) \\ &\displaystyle = &\displaystyle \sum_{j=k+1}^m (b(x_j)-1) \vspace{-3pt}\end{array} \end{aligned} $$

so that we can find disjoint S _k+1, …, S _m with |S _j| = b(x _j) − 1 for all j = k + 1, …, m, hence, by Lemma A.4, N ∖ S _j is effective for {x _j}. This is again a violation of Lemma A.9.

Thus, b(A) = n + 1, which concludes the proof. □