On strategy-proof social choice between two alternatives

Abstract

We study strategy-proof rules for choosing between two alternatives. We consider the full preference domain which allows for indifference. In this framework, for strategy-proof rules, ontoness does not imply efficiency. We weaken the requirement of efficiency to ontoness and characterize the class of strategy-proof rules. We argue that the notion of efficiency is not desirable always. Further, we provide a simple description of the class of onto, anonymous and strategy-proof rules in this framework. The key feature of our characterization results brings out the role played by indifferent agents.

1 Introduction

In this paper, we study social choice problems where a finite set of individuals/agents have to choose one between two alternatives. Let a and b be two alternatives. We assume that individuals can report one among the following three preferences over these two alternatives: (1) a is strictly preferred to b, (2) b is strictly preferred to a and (3) a is indifferent to b. Based on individuals’ reported preferences, a Social Choice Function (or simply a rule) selects an alternative. Choosing between two alternatives has many important applications - such as, two candidate elections, up-down votes on legislation, choosing one out of two locations for locating a public facility, yes-no decisions about building a new public facility or any situation with a status-quo alternative and a new alternative.

Throughout this paper we consider non-constant rules i.e. onto rules. Ontoness implies efficiency (or unanimity) for strategy-proof rules defined over a suitably rich domain of strict preferences¹. However, ontoness does not imply efficiency if preference domain includes indifference (see Examples in Sect. 3)². We do not impose efficiency criteria on rules and characterize the class of onto and strategy-proof rules in this framework. Further, we provide a simple description of the class of anonymous, onto and strategy-proof rules.

A natural objection could be why one might compromise efficiency. In election, it is quite often that a significant proportion of voters express their opinion as indifference. For instance, abstaining from voting can be interpreted as indifference³. Our objective in this paper is to examine the role played by the agents who are indifferent among the two alternatives. In this scenario, if we only look at efficient and strategy-proof voting rules, the outcome is simply based on voters who do not express their opinion as indifference. We believe that this is not desirable in particular when the number of indifferent voters is very large. However if we relax the requirement of efficiency, the outcome depends on both the voters who are indifferent and who are not. Of course, the class of efficient and strategy-proof rules is contained in the class of onto and strategy-proof rules.

In this paper, we introduce two classes of rules, one contained in the other. The larger one, named Generalized Voting by Committee (GVC) contains all onto and strategy-proof rules in our setting. In rough words, any GVC rule first considers the coalition of agents who are indifferent. If they are not winning, then the rule looks at the set of remaining agents (agents with strict preference) and selects the outcome for which there is a winning coalition. The technical details are purposefully not presented in this section in order to improve readability. The smaller class, named quota rule with indifference default contains those GVC rules which are also anonymous. Roughly, these are those GVC rules which cares about only the size of the coalitions and not the members of the coalitions. Further, we study a solidarity property in this framework. We consider the following solidarity property: “Welfare dominance under preference replacement (WDPR)”, which says that when the preferences of one agent change, the other agents all weakly gain or all weakly lose. We characterize the class of rules satisfying WDPR among the class of quota rules.

Larsson and Svensson (2006) characterizes the class of efficient and strategy-proof rules in this framework. These rules are known as voting by extended committees (see Sect. 3 for details). These rules are contained in the class of GVC rules - in fact, efficient GVC rules are voting by extended committees rules. A point of difference between Larsson and Svensson (2006) and this work is the presentation of the class of rules. Here our objective is to examine the role played by the indifferent agents. The winning coalitions in any voting by extended committees consists of agents with strict preferences. In such description, the role of the indifferent agent is not obvious. That is why, our presentation centers around agents with indifferences. It is worth mentioning at this point that our results in Theorems 1 and 2 can also be obtained as corollaries of Ju (2003) (see Conclusions for a detailed explanation). In our paper, however, apart from other results not included in Ju (2003), we propose alternative proofs and definitions of the characterized rules which we believe are useful for the literature.

This paper is organized as follows. Section 2 describes the basic notation and definitions. Section 3 discusses the relationship between ontoness and unanimity (or efficiency) and provides some rules which are onto and strategy-proof but not efficient. The main results are presented in Sect. 4. Proofs are relegated to the Appendix. We conclude the paper in Sect. 5.

2 Basic notation and definitions

Let $A = \{a, b\}$ denote the set of two alternatives and $N=\{1,\ldots ,n \}$, $n\ge 2$, a finite set of agents/individuals. Each individual in N has a preference relation over A: she either prefers a, prefers b, or is indifferent between them. Let ${\mathcal {R}}$ be the set of these three preference relations. For each $i\in N$, let $R_i \in {\mathcal {R}}$ denote individual i’s preference relation. If a is at least as good asb according to individual i, we write $aR_ib$. If she prefers a to b, we write $aP_ib$ and if she is indifferent between the two, $aI_ib$. Let ${\mathcal {P}}$ be the set of two strict preference relations defined over A.

A preference profile is a list $R=(R_1,\ldots ,R_n)\in {\mathcal {R}}^n$ of individuals preferences. For any coalition $S \subseteq N$ and any profile $R \in {\mathcal {R}}$, $R_S$ denotes the restriction of the profile R to the coalition Si.e.$R_S = (R_i)_{i \in S}$. A profile $R^\prime \in {\mathcal {R}}^n$ is defined to be a $i-$deviation from another profile $R \in {\mathcal {R}}^n$ if $R_{N {\setminus } \{i\}} = R^{\prime }_{N {\setminus } \{i\}}$.

For each $R\in {\mathcal {R}}^n$ , let $N_{a}(R)$ be the set of individuals who prefer a to b at R. Similarly, let $N_{b}(R)$ be the set of individuals who prefer b to a, and let $N_{A}(R)$ be the set of individuals who are indifferent between a and b at R. Finally, let $\varsigma$ be the set of permutations of N. For each $R\in {\mathcal {R}}^n$ and each $\sigma \in \varsigma$, let $\sigma (R)= (R_{\sigma (i)})_{i\in N}$.

Definition 1

A SCF f is a mapping from ${\mathcal {R}}^n$ to Ai.e.$f: {\mathcal {R}}^n\longrightarrow A$.

A SCF is sometimes called a voting rule (or simply a rule).

Definition 2

A SCF f is onto if for every alternative $x \in A$ there exists a profile $R \in {\mathcal {R}}^n$ such that $f(R)=x$.

Note that, as $|A| = 2$, if f is not onto, then it must be a constant rule i.e. a rule that selects the same alternative at each profile.

We list some well-known properties of SCFs below.

Definition 3

A SCF f satisfies unanimity, if for all profile $R\in {\mathcal {R}}^n$, $f(R) = a$ whenever $N_a(R) \ne \emptyset$ and $N_b(R) = \emptyset$, and $f(R) = b$ whenever $N_a(R) = \emptyset$ and $N_b(R) \ne \emptyset$.

If $x\in A$ is at least as good as $A{\setminus } \{x\}$ by all individuals and at least one individual prefers x, then by unanimity, the SCF must select x. Unanimity is also known as efficiency in this model.

The next property imposes a weaker requirement than unanimity. If all individuals prefer $x\in A$, then the SCF must select x.

Definition 4

A SCF f satisfies weak unanimity, if for all profile $R \in {\mathcal {R}}^n$, $f(R) = a$ whenever $N_a(R) = N$, and $f(R) = b$ whenever $N_b(R) = N$.

Anonymity requires that the names of the agents should not matter. In particular, when the identities of the agents are shuffled, the rule must select the same alternative.

Definition 5

A SCF f is anonymous if for any $R \in {\mathcal {R}}^n$ and for any $\sigma \in \varsigma$, we have $f(R)=f(\sigma (R))$.

Definition 6

A SCF f is strategy-proof if, for any $i\in N$, for any $R \in {\mathcal {R}}^n$ and for any $i-$deviation $R^\prime \in {\mathcal {R}}^n$ of R, we have $f(R) R_i f(R^\prime )$.

A SCF is strategy-proof if no individual can obtain a preferred alternative by misrepresenting her preferences for any announcement of the preferences of the other individuals. Strategy-proofness ensures that for every agent truth-telling is a weakly dominant strategy in the direct revelation game induced by the SCF.

Next we introduce a weaker notion of strategy-proofness as follows.

Definition 7

A SCF f is weakly strategy-proof if, for any $i\in N$, for any $R \in {\mathcal {R}}^n$ and for any $i-$deviation $R^\prime \in {\mathcal {R}}^n$ of R such that $R_i \in {\mathcal {P}}$ and $a I^\prime _i b$, we have $f(R) R_i f(R^\prime )$.

Next we show that in our model, strategy-proofness and weak strategy-proofness are equivalent.

Lemma 1

Let $f : {\mathcal {R}}^n \longrightarrow A$ be a SCF. f is strategy-proof if and only if f is weakly strategy-proof.

The proof of Lemma 1 is in the Appendix. Weak strategy-proofness can be seen as participation property of a SCF for the case of two alternatives [for instance, see Section 3 in Núñez and Sanver (2017)]⁴. Therefore, with two alternatives, participation property and strategy-proofness are logically equivalent.

3 Unanimity versus weak unanimity

It is important to mention that unanimity implies weak unanimity and weak unanimity implies ontoness. However, ontoness does not imply weak unanimity and weak unanimity does not imply unanimity. If we restrict our attention to strategy-proof SCFs, then ontoness implies weak unanimity. In the following, we show this.

Proposition 1

Let $f:{\mathcal {R}}^n\rightarrow A$ be a strategy-proof SCF. If f is onto, then it satisfies weak unanimity.

Proof

Suppose not. We assume that $f(R)=b$ where $aP_ib$ for all $i\in N$. Since f is onto, there exists $R^\prime \in {\mathcal {R}}^n$ such that $f(R^\prime )=a$. Applying strategy-proofness repeatedly, it follows that

$$\begin{aligned} f(R^\prime )&= f(R_1,R^\prime _2,\ldots ,R^\prime _n) \\&= f(R_1,R_2,R^\prime _3,\ldots ,R^\prime _n) \\&\ \vdots \\&= f(R_1,\ldots ,R_n)\\&= a \end{aligned}$$

This contradicts the assumption $f(R)=b$. A similar argument will lead to a contradiction if we assume that $f(R)=a$ where $bP_ia$ for all $i\in N$. Therefore f satisfies weak unanimity. $\square$

We first introduce the class of unanimous and strategy-proof rules known in the literature as $VEC^{a,t}$ which were characterized by Larsson and Svensson (2006). To introduce the class of unanimous and strategy-proof rules on ${\mathcal {R}}^n$, we need the following notations and definitions. For each $M\subseteq N$, a committee for alternative a at M, ${\mathcal {F}}_M$, is a set of subsets of M, satisfying the following two properties:

• 1. Non-emptyness: If $M\ne \emptyset$, then ${\mathcal {F}}_M\ne \emptyset$ and $\emptyset \notin {\mathcal {F}}_M$. If $M=\emptyset$, then ${\mathcal {F}}_M=\emptyset$.

• 2. Monotonicity: For each $S\in {\mathcal {F}}_M$ and $T\subseteq M$, if $S\subseteq T$, then $T\in {\mathcal {F}}_M$.

A collection of committees for a, ${\mathcal {F}}\equiv \{{\mathcal {F}}_M\}_{M\subseteq N}$, is a set containing for each $M\subseteq N$ a committee for a at M, ${\mathcal {F}}_M$, satisfying the following properties:

For each $M\subseteq N$ and each $i\in M$

• 1. If $S\in {\mathcal {F}}_M$ and $i\notin S$, then $S\in {\mathcal {F}}_{M{\setminus }\{i\}}$.

• 2. If $S\cup \{i\}\notin {\mathcal {F}}_M$, then $S\notin {\mathcal {F}}_{M{\setminus }\{i\}}$.

Definition 8

A SCF is voting by extended committees, denoted by $VEC^{a,t}$, if there exists a collection of committees for a (i.e. ${\mathcal {F}}$) and a tie-breaker $t\in A$ such that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} VEC^{a, t}(R) = \left\{ \begin{array}{l l} t &{} \quad if N_A(R) = N\\ a &{} \quad if N_{a}(R) \in {\mathcal {F}}_{N{\setminus } N_{A}(R)}\\ b &{} \quad otherwise \\ \end{array} \right. \end{aligned}$$

A natural question arises - if a SCF satisfies ontoness and strategy-proofness, does it satisfy unanimity? In the following, we provide rules which are strategy-proof and onto but not unanimous.

Example 1

Consider the following SCF $f:{\mathcal {R}}^n\longrightarrow A$:

$$\begin{aligned} f(R) = \left\{ \begin{array}{l l} a &{} \quad \text {if } aR_1b\\ b &{} \quad \text {if } bP_1a\\ \end{array} \right. \end{aligned}$$

Note that f satisfies strategy-proofness and ontoness (see Sect. 4.1). However, it does not satisfy unanimity. To see this, consider a preference profile $R^\prime$ where $aI^\prime _1b$ and for all $j\in N {\setminus } \{1\}$, $b P^\prime _j a$. Unanimity implies that f must select b at $R^\prime$. However, $f(R^\prime )=a$. Therefore f is not unanimous. $\square$

Note that the rule in Example 1 is not anonymous. However, there are anonymous, onto and strategy-proof rules which are not unanimous.

Example 2

Consider the status-quo rule with respect to the status-quo alternative a, $f^a:{\mathcal {R}}^n\longrightarrow A$:

$$\begin{aligned} f^a(R) = \left\{ \begin{array}{l l} b &{} \quad \text {if } b \text { is preferred by all agents} \\ a &{} \quad \text {otherwise }\\ \end{array} \right. \end{aligned}$$

It is straightforward that $f^a$ is strategy-proof, anonymous and onto (see Sect. 4.2). However, $f^a$ is not unanimous. Consider a preference profile R where $aI_ib$ for some $i \in N$ and for all $j \in N {\setminus } \{i\}$, $bP_ja$. Unanimity implies that $f^a$ must select b at R. However, $f^a(R)=a$. Therefore $f^a$ is not unanimous.

The status-quo rule with respect to the status-quo alternative b, is defined as follows:

$$\begin{aligned} f^b(R) = \left\{ \begin{array}{l l} a &{} \quad \text {if } a \text { is preferred by all agents} \\ b &{} \quad \text {otherwise }\\ \end{array} \right. \end{aligned}$$

It can be seen that $f^b$ is strategy-proof, anonymous and onto but not unanimous. $\square$

The following class of rules can be found in Chapter 2 of Fishburn (1973).

Example 3

Let $s:{\mathcal {R}}\longmapsto \{1,0,-1\}$ such that

$$\begin{aligned} s(R_i) = \left\{ \begin{array}{l l} 1 &{} \quad \text { if } aP_ib\\ 0 &{} \quad \text { if } aI_ib\\ -1 &{} \quad \text { if } bP_ia \end{array} \right. \end{aligned}$$

For each $R\in {\mathcal {R}}^n$, we denote $s(R)=\sum ^n_{i=1} s(R_i)$.

We fix an integer $h\in (-n,n] \cap {\mathbb {Z}}$ and define the SCF $f^h$, as follows: For all $R\in {\mathcal {R}}^n$

$$\begin{aligned} f^h(R) = \left\{ \begin{array}{l l} a &{} \quad if s(R)\ge h\\ b &{} \quad otherwise \end{array} \right. \end{aligned}$$

First, we make following remarks on these rules.

• 1. If $h = 1$, we get the simple majority rule i.e.a beats b whenever more individuals that prefer a to b than prefer b to a and b beats a whenever the converse holds.

• 2. The case where a wins if the number of individuals that prefer a to b exceeds the number of individuals that prefer b to a by at least a positive integer r, and b wins otherwise, is described by $h = r$.

• 3. If $h = n$, then we get the status-quo rule with respect to status quo alternative b. Similarly, if $h = -(n-1)$, then we get the status-quo rule with respect to status-quo alternative a.

• 4. If $h = -n$, then $f^{-n}(R) = a$ for all profiles, a constant rule. That is why we exclude this case.

In Sect. 4.2, we show that $f^h$ is strategy-proof, anonymous and onto. Whether $f^h$ is unanimous or not, that depends on the value of h. In particular, it can be seen that $f^h$ is unanimous if $h\in \{0, 1\}$. However if $h>1$ or $h\le -1$, then $f^h$ is not unanimous. To see this, we first assume that $h>1$. Let $R\in {\mathcal {R}}^n$ be a preference profile where $aP_ib$ and $aI_jb$ for all $j\in N{\setminus } i$. By unanimity, we should select a at R. However $f^h(R)=b$, because $s(R)=1<h$. Similarly, if $h\le -1$, at $R\in {\mathcal {R}}^n$ where $bP_ia$ and $aI_jb$ for all $j\in N{\setminus } i$, $f^h(R)=a$, because $s(R)=-1\ge h$ - violates unanimity. $\square$

We can think of a rule where the number of individuals who are indifferent between two alternatives, can determine the outcome. For instance, consider a rule which selects an alternative $x\in A$ if the number of indifferent individuals is at least a positive integer $r\in \{1,2,\ldots ,n\}$. Otherwise if the number is less than r, then based upon the preferences of strict individuals, the rule selects x or the other alternative $A{\setminus } \{x\}$. Below, we introduce a class of such rules.

Example 4

We fix a positive integer $r \in \{1,2,\ldots ,n\}$ and define the SCF $f^r$ as follows: For all $R\in {\mathcal {R}}^n$

$$\begin{aligned} f^r(R) = \left\{ \begin{array}{l l} b &{} \quad \text { if }|N_{A}(R)|\ge r \\ b &{} \quad \text { if }|N_{A}(R)|< r\text { and }|N_{b}(R)|\ne 0\\ a &{} \quad \text { if }|N_{A}(R)|< r\text { and }|N_{b}(R)|= 0 \end{array} \right. \end{aligned}$$

We make the following remarks on these rules.

• 1. If $r=1$, then we get the status-quo rule with respect to status quo alternative b.

• 2. If $r=n$, then we get the consensus rule with disagreement-default b and indifference-default b ( Manjunath (2012)).

In Sect. 4.2, we show that $f^r$ is strategy-proof, anonymous and onto. However, whether $f^r$ is unanimous or not depends on r. In particular, if $r=n$, then it is straightforward to show that $f^r$ is unanimous. However, if $r<n$, $f^r$ is not unanimous. To see this, consider $R\in {\mathcal {R}}^n$ where $aP_ib$ and $aI_jb$ for all $j\in N{\setminus } i$. By unanimity, we should select a at R. However $f^r(R)=b$, because $|N_{A}(R)|=n-1\ge r$. $\square$

4 Results

4.1 Generalized voting by committees

In this section, we characterize onto and strategy-proof rules. For this, we need to introduce additional notation and definitions.

A committee for indifference default$d\in \{a,b\}$, denoted by${\mathcal {I}}^d$, is a set of subsets of N, satisfying the following two properties:

• 1. Non-emptyness${\mathcal {I}}^d\ne \emptyset$ and $\emptyset \notin {\mathcal {I}}^d$.

• 2. Monotonicity For each $S\in {\mathcal {I}}^d$ and $T\subseteq N$, if $S\subseteq T$, then $T\in {\mathcal {I}}^d$.

Since $d\in \{a,b\}$, ${\mathcal {I}}^a$ denotes a committee for indifference default a. Similarly, a committee for indifference default b is denoted by ${\mathcal {I}}^b$.

Let $M\subseteq N$ and ${\mathcal {I}}^d$ be a committee for indifference default d. A committee foraatMwith respect to${\mathcal {I}}^d$, denoted by ${\mathcal {F}}_{M,{\mathcal {I}}^d}$, is a set of subsets of M, satisfying the following two properties:

• 1. Non-emptiness with respect to${\mathcal {I}}^d$: If $N{\setminus } M\notin {\mathcal {I}}^d$, then ${\mathcal {F}}_{M,{\mathcal {I}}^d}\ne \emptyset$ and $\emptyset \notin {\mathcal {F}}_{M,{\mathcal {I}}^d}$. If $N{\setminus } M\in {\mathcal {I}}^d$, then ${\mathcal {F}}_{M,{\mathcal {I}}^d}=\emptyset$.

• 2. Monotonicity For each $S\in {\mathcal {F}}_{M,{\mathcal {I}}^d}$ and $T\subseteq M$, if $S\subseteq T$, then $T\in {\mathcal {F}}_{M,{\mathcal {I}}^d}$.

A collection of committees forawith respect to${\mathcal {I}}^a$, denoted by ${\mathcal {F}}_{{\mathcal {I}}^a}\equiv \{{\mathcal {F}}_{M,{\mathcal {I}}^a}\}_{M\subseteq N}$, is a set containing for each $M\subseteq N$ a committee for a with respect to ${\mathcal {I}}^a$ i.e. ${\mathcal {F}}_{M,{\mathcal {I}}^a}$, satisfying the following properties:

For each $M\subseteq N$ and each $i\in M$

• 1. If $N{\setminus } M\notin {\mathcal {I}}^a$ and $\{N{\setminus } M\}\cup \{i\}\in {\mathcal {I}}^a$, then for all $S \subseteq M$ such that $i\in S$, $S\in {\mathcal {F}}_{M,{\mathcal {I}}^a}$.

• 2. If $S\in {\mathcal {F}}_{M,{\mathcal {I}}^a}$, $i\notin S$ and $\{N{\setminus } M\}\cup \{i\}\notin {\mathcal {I}}^a$, then $S\in {\mathcal {F}}_{M{\setminus }\{i\},{\mathcal {I}}^a}$.

• 3. If $N{\setminus } M\notin {\mathcal {I}}^a$, $S\cup \{i\}\notin {\mathcal {F}}_{M,{\mathcal {I}}^a}$ and $\{N{\setminus } M\}\cup \{i\}\notin {\mathcal {I}}^a$, then $S\notin {\mathcal {F}}_{M{\setminus }\{i\},{\mathcal {I}}^a}$.

Similarly, a collection of committees forawith respect to${\mathcal {I}}^b$, ${\mathcal {F}}_{{\mathcal {I}}^b}\equiv \{{\mathcal {F}}_{M,{\mathcal {I}}^b}\}_{M\subseteq N}$, is a set containing for each $M\subseteq N$ a committee for a with respect to ${\mathcal {I}}^b$ i.e. ${\mathcal {F}}_{M,{\mathcal {I}}^b}$, satisfying the following properties:

For each $M\subseteq N$ and each $i\in M$

• 1. If $N{\setminus } M\notin {\mathcal {I}}^b$ and $\{N{\setminus } M\}\cup \{i\}\in {\mathcal {I}}^b$, then for all $S\in {\mathcal {F}}_{M,{\mathcal {I}}^b}$, $i\in S$.

• 2. If $S\in {\mathcal {F}}_{M,{\mathcal {I}}^b}$, $i\notin S$ and $\{N{\setminus } M\}\cup \{i\}\notin {\mathcal {I}}^b$, then $S\in {\mathcal {F}}_{M{\setminus }\{i\},{\mathcal {I}}^b}$.

• 3. If $N{\setminus } M\notin {\mathcal {I}}^b$, $S\cup \{i\}\notin {\mathcal {F}}_{M,{\mathcal {I}}^b}$ and $\{N{\setminus } M\}\cup \{i\}\notin {\mathcal {I}}^b$, then $S\notin {\mathcal {F}}_{M{\setminus }\{i\},{\mathcal {I}}^b}$.

Given a committee for indifference default d, ${\mathcal {I}}^d$ and a collection of committees for a with respect to ${\mathcal {I}}^d$, we define generalized voting by committees (GVC) as follows.

Definition 9

A SCF is a GVC, denoted by $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}$, if there exist a committee for indifference default d, ${\mathcal {I}}^d$ where $d\in A$ and a collection of committees for a with respect to ${\mathcal {I}}^d$, ${\mathcal {F}}_{{\mathcal {I}}^d}$, such that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R) = \left\{ \begin{array}{l l} \text {d} &{} \quad \text { if } N_{A}(R)\in {\mathcal {I}}^d\\ \text {a} &{} \quad \text { if } N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^d} \text { and } N_{A}(R)\notin {\mathcal {I}}^d\\ \text {b} &{} \quad \text { otherwise}\\ \end{array} \right. \end{aligned}$$

A generalized voting by committees (GVC) rule is described by two sets. The first one is a nonempty set of subsets of N satisfying a monotonicity condition and we say it as a committee for indifference default $d\in \{a,b\}$. The second one is a set containing for each $M\subseteq N$, a committee for the alternative a at M. Moreover, the second set, not only depends on the first set, but also satisfies further properties. For any preference profile, if the set of agents who are indifferent between two alternatives, belongs to the committee for indifference default d, then the rule selects d at that profile. Otherwise, consider the committee for a at the set of agents with strict preferences over a and b - if the set of agents who prefers a to b, belongs the that committee, then the outcome is a or if it does not belong the that committee, then the outcome is b.

Now we state the main result of the paper.

Theorem 1

Let $f : {\mathcal {R}}^n \longrightarrow A$ be a SCF. Then, f is onto and strategy-proof if and only if f is a GVC.

The proof of Theorem 1 is in the Appendix. However, we make several remarks on Theorem 1 in the following:

• 1. Larsson and Svensson (2006) characterizes unanimous (or efficient) and strategy-proof rules in this framework. In particular, they show that the only unanimous and strategy-proof rules are $VEC^{a, t}$ (see Sect. 3). We consider the much weaker requirement of ontoness and characterize strategy-proof rules in this framework. The class of $VEC^{a, t}$ rules belongs to the the class of GVC rules. In particular, a GVC rule, $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}$ is unanimous if and only if ${\mathcal {I}}^d=\{N\}$.

• 2. It can be seen that the rule in Example 1 is a GVC rule where ${\mathcal {I}}^a= \{S\subseteq N: 1\in S\}$ and ${\mathcal {F}}_{{\mathcal {I}}^a}\equiv \{{\mathcal {F}}_{M,{\mathcal {I}}^a}\}_{M\subseteq N}$ is as described below:

  $$\begin{aligned} {\mathcal {F}}_{M,{\mathcal {I}}^a} = \left\{ \begin{array}{cl} \left\{ S \subseteq M : \begin{array}{c} 1\in S \\ \end{array}\right\} &{} \quad \text { if } \begin{array}{l} 1\in M \\ \end{array} \\ \\ \emptyset &{} \quad \text { if } \begin{array}{l} 1\notin M \end{array} \end{array}\right. \end{aligned}$$

• 3. Using Lemma 1, it follows that Theorem 1 would still hold if we replace strategy-proofness with weak strategy-proofness.

4.2 Quota rules

Theorem 1 provides a characterization of onto and strategy-proof rules in our model. However, we must confess that GVC rules are not simple to describe. The rules that are anonymous, can be described in much simpler way. First we define the following class of rules.

Definition 10

A SCF is a quota rule with indifference defaulta, denoted by $f_a^{k, x}$, if there exists a vector of natural numbers of length k, $x=(x_1,x_2,\ldots ,x_k) \in \{1\} \times \{1, 2\} \times \ldots \times \{1, 2, \ldots , k\}$, where $k \in \{1, 2, \ldots , n\}$ and $x_{i + 1} - 1 \le x_i \le x_{i + 1}$ for all $i \in \{1, 2, \ldots , k-1\}$ such that for all $R\in {\mathcal {R}}^n$

$$\begin{aligned} f_a^{k, x}(R) = \left\{ \begin{array}{cl} a &{} \quad \text { if } |N_A(R)| \ge k \\ \\ a &{} \quad \text { if } |N_A(R)| < k \\ &{} \quad \quad \text { and } |N_a(R) \cup N_b(R)| = n - k + l \text { for some } l \in \{1, 2, \ldots , k\} \\ &{} \quad \quad \text { and } |N_a(R)| \ge x_l \\ \\ b &{} \quad \text { otherwise } \end{array}\right. \end{aligned}$$

Next we define another class of rules as follows.

Definition 11

A SCF is a quota rule with indifference defaultb, denoted by $f_b^{k, y}$, if there exists a vector of natural numbers of length k, $y=(y_1,y_2,\ldots ,y_k) \in \{n - k + 1\} \times \{n - k + 1, n - k + 2\} \times \ldots \times \{n - k + 1, n - k + 2, \ldots , n\}$, where $k \in \{1, 2, \ldots , n\}$ and $y_{i + 1} - 1 \le y_i \le y_{i + 1}$ for all $i \in \{1, 2, \ldots , k-1\}$ such that for all $R\in {\mathcal {R}}^n$

$$\begin{aligned} f_b^{k, y}(R) = \left\{ \begin{array}{cl} b &{} \quad if |N_A(R)| \ge k \\ \\ a &{} \quad if |N_A(R)| < k \\ &{} \quad \quad and |N_a(R) \cup N_b(R)| = n - k + l for some l \in \{1, 2, \ldots , k\} \\ &{} \quad \quad and |N_a(R)| \ge y_l \\ \\ b &{} \quad otherwise \end{array}\right. \end{aligned}$$

A quota rule with indifference default a is described simply by a vector of integers of length k, $k \in \{1, 2, \ldots , n\}$, $x=(x_1,x_2,\ldots ,x_k) \in \{1\} \times \{1, 2\} \times \ldots \times \{1, 2, \ldots , k\}$, where $x_{i+1}-1 \le x_i \le x_{i + 1}$ for all $i \in \{1, 2, \ldots , k-1\}$. Note that $x_i$ is the $i^{th}$ component of the vector x, where $i\in \{1, 2, \ldots , k\}$. The rule works as follows. For any preference profile, if the number of agents who are indifferent between the two alternatives, is at least k, then the rule selects the indifference default a at that profile. Suppose that the number is less than k, i.e. the number of agents with strict preferences belongs to $\{n-k+1,\ldots ,n\}$. In particular, we assume that the number of agents with strict preferences is $n-k+l$ where $l\in \{1,2,\ldots ,k\}$. Then the outcome is a if the number of agents who prefers a to b is at least $x_l$ and the outcome is b if the number is less than $x_l$. Here, k is the quota for indifference default a i.e. whenever the number of indifferent agents is at least k, the outcome is a. Also, $x_l$ is the quota for a when the number of strict agents is $n-k+l$, $l\in \{1,2,\ldots ,k\}$ i.e when $n-k+l$ is the number of strict agents, the outcome is a if the number of agents who prefers a to b is at least $x_l$ and the outcome is b if the number is less than $x_l$. Quota rule for a with indifference default b can also be described in similar fashion. Theorem 2 characterizes the class of anonymous, onto and strategy-proof rules in terms of quota rules in this framework.

Theorem 2

Let $f : {\mathcal {R}}^n \longrightarrow A$ be a SCF. Then, f is anonymous, onto and strategy-proof if and only if it is either a quota rule with indifference default a or a quota rule with indifference default b.

The proof of Theorem 2 is in the Appendix. In the following, we make several remarks on Theorem 2:

• 1. An anonymous, onto and strategy-proof rule can be described simply by a vector of natural numbers of length k, where $k\in \{1,2,\ldots ,n\}$. In particular, a quota rule with indifference default a, $f_a^{k, x}$, is described by a vector of natural numbers of length k, $x=(x_1,x_2,\ldots ,x_k) \in \{1\} \times \{1, 2\} \times \ldots \times \{1, 2, \ldots , k\}$, where $k \in \{1, 2, \ldots , n\}$ and $x_{i + 1} - 1 \le x_i \le x_{i + 1}$ for all $i \in \{1, 2, \ldots , k-1\}$. For any $R\in {\mathcal {R}}^n$, $f_a^{k, x}$ works as follows.

  • If the number of individuals who are indifferent between two alternatives at R, is atleast k, i.e. $|N_A(R)|\ge k$, then the rule selects the indifference default a i.e. $f_a^{k, x}(R)=a$. Here, k is the quota for indifference default a.

  • If $|N_A(R)|<k$, then note that $|N_a(R) \cup N_b(R)|= n - k + l$ for some $l \in \{1, 2, \ldots , k\}$ and we consider $x_l$ which represents the quota for alternative a. If the number of individuals who vote for a is atleast $x_l$, i.e. $|N_a(R)| \ge x_l$, then $f_a^{k, x}(R)=a$; otherwise $f_a^{k, x}(R)=b$.

  A quota rule with indifference default b, can be described in a similar way as well.

• 2. Note that $f_a^{k, x}$ is unanimous if and only if $k=n$. Similarly, $f_b^{k, y}$ is unanimous if and only if $k=n$.

• 3. Rules in Example 2: The status-quo rule with respect to the status-quo alternative a, $f^a$ is a quota rule with indifference default a, $f^{k,x}_a$, where x is a vector of natural numbers of length 1 i.e. $k=1$ and $x\equiv (x_1)=(1)$. The status-quo rule with respect to the status-quo alternative b, $f^b$ is a quota rule with indifference default b, $f^{k,y}_b$ where y is a vector of natural numbers of length 1 i.e. $k=1$ and $y\equiv (y_1)=(n)$.

• 4. Rules in Example 3: If $h>0$, the $f^h$ is a quota rule with indifference default b, $f^{k,y}_b$ where y is a vector of natural numbers of length $n-h+1$ i.e. $k=n-h+1$ and $y\equiv (y_1,\ldots ,y_{n-h+1})=(h,h+1,h+1,h+2,h+2,h+3,\ldots )$.

  If $h\le 0$, the $f^h$ is a quota rule with indifference default a, $f^{k,x}_a$, where x is a vector of natural numbers of length $n+h$ i.e. $k=n+h$ and $x\equiv (x_1,\ldots ,x_{n+h})=(1,1,2,2,3,3,\ldots )$.

• 5. The rule in Example 4: It can be seen that the rule $f^r$ in Example 4 is a quota rule with indifference default b, $f^{k,y}_b$ where y is a vector of natural numbers of length r i.e. $k=r$ and $y\equiv (y_1,\ldots ,y_r)=(n-r+1,n-r+2,\ldots ,n)$.

• 6. Using Lemma 1, it follows that Theorem 1 would still hold if we replace strategy-proofness with weak strategy-proofness.

4.3 Solidarity and quota rules

Among the class of anonymous, onto and strategy-proof rules, those that satisfy solidarity property, are studied in this section. We consider the following solidarity property: “welfare dominance under preference replacement”, which says that when the preferences of one agent change, the other agents all weakly gain or all weakly lose.

Definition 12

A SCF f satisfies welfare dominance under preference replacement (WDPR) if for any $R \in {\mathcal {R}}^n$, for any $i\in N$ and for any $R'_i\in {\mathcal {R}}$, either (i) for each $j\in N{\setminus } \{i\}$, we have $f(R)R_jf(R'_i,R_{-i})$ or (ii) for each $j\in N{\setminus } \{i\}$, we have $f(R'_i,R_{-i})R_jf(R)$.

Harless (2015) characterizes the class of WDPR rules. Among the class of WDPR rules, the rules that satisfy anonymity, ontoness and strategy-proofness, are discussed in this section. Before presenting the main results of this section, we state the following lemma.

Lemma 2

Let $f:{\mathcal {R}}^n\longrightarrow A$ satisfy WDPR. Then, for all $R,R'\in {\mathcal {R}}^n$ such that $N_a(R)$, $N_b(R)$, $N_a(R')$, $N_b(R')$$\ne$$\emptyset$, we have $f(R)=f(R')$.

Proof

The proof can be found in Lemma 1 of Harless (2015). Hence, it is omitted. $\square$

According to Lemma 2, if a rule satisfies WDPR, then, it selects the same alternative in each disagreement profile⁵.

Now we are ready to state our results. The following proposition characterizes the class of rules satisfying WDPR among the class of quota rules with indifference default a.

Proposition 2

Let $n\ge 3$ and $f_a^{k, x}:{\mathcal {R}}^n\longrightarrow A$ be a quota rule with indifference default a. Then, $f_a^{k, x}$ satisfies WDPR if and only if x is a vector of natural numbers of length n, where $x=(x_1,\ldots ,x_n)\in \{(1,1,\ldots ,1), (1,2,\ldots ,n)\}$ or x is a vector of natural numbers of length k, $k\in \{1,2,\ldots ,n-1\}$, where $x=(x_1,\ldots ,x_k)=(1,1,\ldots ,1)$.

The proof of Proposition 2 is in the Appendix. Next we characterize the class of rules satisfying WDPR among the class of quota rules with indifference default b.

Proposition 3

Let $n\ge 3$ and $f_b^{k, y}:{\mathcal {R}}^n\longrightarrow A$ be a quota rule with indifference default b. Then, $f_b^{k, y}$ satisfies WDPR if and only if y is a vector of natural numbers of length n, where $y=(y_1,\ldots ,y_n)\in \{(1,1,\ldots ,1), (1,2,\ldots ,n)\}$ or y is a vector of natural numbers of length k, $k\in \{1,2,\ldots ,n-1\}$, where $y=(y_1,\ldots ,y_k)=(n-k+1,n-k+2,\ldots ,n)$.

The proof of Proposition 2 is in the Appendix. In the following, we make remarks on Propositions 2 and 3.

• 1. If $n=2$, then quota rules with indifference default a and quota rules with indifference default b, satisfy WDPR. For $n>2$, this is not true.

• 2. For unanimous rules, WDPR implies strategy-proofness and anonymity [see Theorem 2(b) in Harless (2015)]. However, for onto rules, WDPR does not imply strategy-proofness and anonymity [see Theorem 2(a) in Harless (2015)]. By Propositions 2 and 3, the combination of anonymity, ontoness and strategy-proofness does not imply WDPR for $n>2$. In particular, Proposition 2 and 3 together characterize the class of rules satisfying WDPR among the class of anonymous, onto and strategy-proof rules.

5 Conclusion

We study social choice problems where a finite set of individuals have to choose one between two alternatives. We consider the full preference domain which allows for indifference. We weaken the requirement of efficiency to ontoness and analyse strategy-proof rules in this framework. Firstly, we characterize the class of onto and strategy-proof rules. Further, we provide a simple description of the class of anonymous, onto and strategy-proof rules in this framework. It is important to mention that such characterizations can be obtained from Theorem 1 and Corollary 2 in Ju (2003). In particular, in Ju (2003), if one assumes that the set of indivisible objects contain only one item and the set of alternatives is all possible subsets of that set of indivisible object, then it boils down to our model. Ju (2003) characterizes the class of rules satisfying strategy-proofness and null-independence by describing the class of rules through profile of power structures. Null-independence is trivially satisfied in our setting. But, the main difference between Ju (2003) and this work lies in the description of the rules. The profile of power structure is a tuple of coalitions for every object (for one coalition, the object is good and for the other, it is bad), satisfying a monotonicity condition. Ju (2003) does not describe the profile of power structure in terms of those agents for whom an object is a null which is what we do in this paper. Note that agents for whom an object is a null in Ju (2003) would correspond to indifferent agents in our framework and the main focus of this paper has been to point out the roles played by the agents who are indifferent. Moreover, the description of the rules in this paper are easier than Ju (2003) (in particular, quota rules). At the same time, analysis with respect to solidarity properties is absent in Ju (2003), whereas our Propositions 2 and 3 together characterize the class of rules satisfying WDPR among the class of anonymous, onto and strategy-proof rules. Also note that from Lemma 1, we have equivalence between participation property (as introduced in Moulin (1991)) and strategy-proofness. Such a result is not attainable in Ju (2003).

Appendices

Appendix

The Proof of Lemma 1

Proof

Note that if f is strategy-proof then it is weakly strategy-proof. So suppose that f is weakly strategy-proof, but to the contrary f is not strategy-proof. Then there exist an agent $i \in N$ and a profile $R \in {\mathcal {R}}^n$ and an $i-$deviation $R^\prime \in {\mathcal {R}}$ of R such that $R_i, R^\prime _i \in {\mathcal {P}}$ and $f(R^\prime ) P_i f(R)$. So it follows that $R_i \ne R^\prime _i$. Without loss of generality, assume that $a P_i b$ and $b P^\prime _i a$. So it follows that $f(R) = b$ and $f(R^\prime ) = a$. Now consider the profile $R^\star \in {\mathcal {R}}^n$ such that $R^\star _{N {\setminus } \{i\}} = R^\prime _{N {\setminus } \{i\}} = R_{N {\setminus } \{i\}}$, and $a I^\star _i b$. Now weak strategy-proofness for the deviation from R to $R^\star$ implies that $f(R^\star ) = b$. On the other hand weak strategy-proofness for the deviation from $R^\prime$ to $R^\star$ implies that $f(R^\star ) = a$, which contradicts the fact that $f(R^\star ) = b$ and concludes the proof. $\square$

The Proof of Theorem 1

Proof

If part. Let $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}$ be a GVC rule. Let ${\mathcal {I}}^d$ be the committee for indifference default $d\in \{a,b\}$ and ${\mathcal {F}}_{{\mathcal {I}}^d}$, the collection of committees for a with respect to ${\mathcal {I}}^d$. We show that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}$ is onto and strategy-proof.

To prove that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}$ is onto, we show that there exist $R',R''\in {\mathcal {R}}^n$ such that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R')=a$ and $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R'')=b$. Let $R'$ and $R''$ be such that $N_a(R')=N$ and $N_b(R'')=N$ respectively. Note that $N_{A}(R')=N_b(R')=\emptyset$, $N_a(R')\in {\mathcal {F}}_{N{\setminus } N_{ab}(R'),{\mathcal {I}}^d}$ and $N_{A}(R')\notin {\mathcal {I}}^d$. Therefore, $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R')=a$. Again, since $N_{A}(R'')=N_a(R'')=\emptyset$, $N_a(R'')\notin {\mathcal {F}}_{N{\setminus } N_{ab}(R''),{\mathcal {I}}^d}$ and $N_{A}(R'')\notin {\mathcal {I}}^d$, we have $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R'')=b$.

Next we show that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}$ satisfies strategy-proofness. We consider $R\in {\mathcal {R}}^n$ and $R'_i\in {\mathcal {R}}$.

First we assume that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R)=a$. If $aR_ib$, then i can not manipulate at R via $R'_i$. If $bP_ia$ then we show that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R'_i,R_{N {\setminus } \{i\}})=a$. The following two cases arise : (i) $aI'_ib$ and (ii) $aP'_ib$.

(i) Suppose $aI'_ib$. Let $d=a$. If $N_{A}(R)\in {\mathcal {I}}^a$, then $N_{A}(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {I}}^a$. Therefore, $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R'_i,R_{N {\setminus } \{i\}})=a$. If $N_{A}(R)\notin {\mathcal {I}}^a$, then $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R)=a$ implies that $N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a}$. Now we consider the set $N_{A}(R'_i,R_{N {\setminus } \{i\}})$. If $N_{A}(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {I}}^a$, then $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R'_i,R_{N {\setminus } \{i\}})=a$. If $N_{A}(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {I}}^a$, then the property 2 of ${\mathcal {F}}_{{\mathcal {I}}^a}$ would imply that $N_a(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$. Therefore, $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R'_i,R_{N {\setminus } \{i\}})=a$.

Let $d=b$. Since $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R)=a$, $N_{A}(R)\notin {\mathcal {I}}^b$ and $N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^b}$. Now we consider the set $N_{A}(R'_i,R_{N {\setminus } \{i\}})$. If $N_{A}(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {I}}^b$, then by property 1 of ${\mathcal {F}}_{{\mathcal {I}}^b}$, $i\in N_a(R)$ which is not possible. Therefore, $N_{A}(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {I}}^b$. Since $N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^b}$ and $N_a(R'_i,R_{N {\setminus } \{i\}})=N_a(R)$, by the property 2 of ${\mathcal {F}}_{{\mathcal {I}}^b}$ we have $N_a(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^b}$. Therefore, $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R'_i,R_{N {\setminus } \{i\}})=a$.

(ii) Suppose $aP'_ib$. Let $d=a$. Note that $N_{A}(R'_i,R_{N {\setminus } \{i\}})=N_{A}(R)$. If $N_{A}(R)\in {\mathcal {I}}^a$, then $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R'_i,R_{N {\setminus } \{i\}})=a$. If $N_{A}(R)\notin {\mathcal {I}}^a$, then $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R)=a$ implies that $N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a}$. By monotonicity property of ${\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a}$, $N_a(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a}$. Since $N_{A}(R'_i,R_{N {\setminus } \{i\}})=N_{A}(R)$, $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R'_i,R_{N {\setminus } \{i\}})=a$.

Let $d=b$. Since $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R)=a$, $N_{A}(R)\notin {\mathcal {I}}^b$ and $N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^b}$. Also, since $N_{A}(R'_i,R_{N {\setminus } \{i\}})=N_{A}(R)$, $N_{A}(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {I}}^b$. By monotonicity property of ${\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^b}$, $N_a(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^b}$. Therefore, $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R'_i,R_{N {\setminus } \{i\}})=a$.

Now we assume that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R)=b$. If $bR_ia$, then i can not manipulate. If $aP_ib$ then we show that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R'_i,R_{N {\setminus } \{i\}})=b$. The following two cases arise : (i) $aI'_ib$ and (ii) $bP'_ia$.

(i) Suppose $aI'_ib$. Let $d=a$. Since $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R)=b$, $N_{A}(R)\notin {\mathcal {I}}^a$ and $N_a(R)\notin {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a}$. Now we consider the set $N_{A}(R'_i,R_{N {\setminus } \{i\}})$. If $N_{A}(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {I}}^a$, then by property 1 of ${\mathcal {F}}_{{\mathcal {I}}^a}$, $N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a}$ which is not possible. Therefore, $N_{A}(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {I}}^a$. Since $N_a(R)\notin {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a}$ and $N_{A}(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {I}}^a$, property 3 of ${\mathcal {F}}_{{\mathcal {I}}^a}$ would imply that $N_a(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$. Therefore, $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R'_i,R_{N {\setminus } \{i\}})=b$.

Let $d=b$. If $N_{A}(R)\in {\mathcal {I}}^b$, then (by monotonicity property of ${\mathcal {I}}^b$) $N_{A}(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {I}}^b$. Therefore, $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R'_i,R_{N {\setminus } \{i\}})=b$. If $N_{A}(R)\notin {\mathcal {I}}^b$, then $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R)=b$ implies that $N_a(R)\notin {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^b}$. Now we consider the set $N_{A}(R'_i,R_{N {\setminus } \{i\}})$. If $N_{A}(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {I}}^b$, then $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R'_i,R_{N {\setminus } \{i\}})=b$. If $N_{A}(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {I}}^b$, then property 3 of ${\mathcal {F}}_{{\mathcal {I}}^b}$ would imply that $N_a(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$. Therefore, $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R'_i,R_{N {\setminus } \{i\}})=b$.

(ii) Suppose $bP'_ia$. Note that $N_{A}(R'_i,R_{N {\setminus } \{i\}})=N_{A}(R)$. Let $d=a$. Since $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R)=b$, $N_{A}(R)\notin {\mathcal {I}}^a$ and $N_a(R)\notin {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a}$. Since $N_{A}(R'_i,R_{N {\setminus } \{i\}})=N_{A}(R)$, we have $N_{A}(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {I}}^a$ and $N_a(R)\notin {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$. Note that $N_a(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$, otherwise by monotonicity property of ${\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$, $N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$ which is not possible. Therefore, $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R'_i,R_{N {\setminus } \{i\}})=b$.

Let $d=b$. If $N_{A}(R)\in {\mathcal {I}}^b$, then $N_{A}(R'_i,R_{N {\setminus } \{i\}})\in {\mathcal {I}}^b$. Therefore, $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R'_i,R_{N {\setminus } \{i\}})=b$. So, we consider that $N_{A}(R)\notin {\mathcal {I}}^b$. since $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R)=b$, $N_a(R)\notin {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^b}$. Note that since $N_{A}(R'_i,R_{N {\setminus } \{i\}})=N_{A}(R)$, we have $N_a(R'_i,R_{N {\setminus } \{i\}})\notin {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$, otherwise by monotonicity property of ${\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$, $N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R'_i,R_{N {\setminus } \{i\}}),{\mathcal {I}}^a}$ which is not possible. Therefore, $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R'_i,R_{N {\setminus } \{i\}})=b$.

Only if part. Let f be an onto and strategy-proof SCF. Let ${\bar{R}}\in {\mathcal {R}}^n$ denotes the preference profile where all agents are indifferent between a and b. We show that if $f({\bar{R}})=a$, then there exists a committee for indifference default a, ${\mathcal {I}}^a$ and a collection of committees for a with respect to ${\mathcal {I}}^a$, ${\mathcal {F}}_{{\mathcal {I}}^a}$, such that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} f(R) = f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R). \end{aligned}$$

Similarly, if $f({\bar{R}})=b$, then there exists a committee for indifference default b, ${\mathcal {I}}^b$ and a collection of committees for a with respect to ${\mathcal {I}}^b$, ${\mathcal {F}}_{{\mathcal {I}}^b}$, such that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} f(R) = f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R). \end{aligned}$$

In the following, we consider these two cases.

Case 1: $f({\bar{R}})=a$. For each $M\subseteq N$, let $g^M_f$ be the restriction of f to $\{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M \}$. In other words, let $g^M_f : \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M \} \longrightarrow A$ be a function defined as $g^M_f(R) = f(R)$ for all $R \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M \}$. First we show the following claim.

Claim 1

For each $M\subseteq N$, either $g^{M}_f$ is a constant rule that picks a or $g^{M}_f$ is onto.

Proof

If $M=\emptyset$, then it is trivial that $g^{M}_f$ is a constant rule that picks a. Therefore, for contradiction, we assume that there exists $\emptyset \ne M'\subseteq N$ such that $g^{M'}_f$ is a constant rule that picks b. W.o.l.g. let $M'=\{1,2,\ldots ,k\}$, $k\le n$. Let $R'$ be such that $aI'_ib$ if $i\in \{k+1,\ldots ,n\}$ and $aP'_ib$ if $i\in \{1,\ldots ,k\}$. Since $g^{M'}_f$ is a constant rule that picks b, $f(R')=b$. Applying strategy-proofness, we have

$$\begin{aligned} f(R'_1,R'_2,\ldots ,R'_n)&= f(R_1,\ldots ,R_{k-1},{\bar{R}}_k,R'_{k+1},\ldots ,R'_n) \\&= f(R_1,\ldots ,R_{k-2},{\bar{R}}_{k-1},{\bar{R}}_k,R'_{k+1},\ldots ,R'_n) \\&\ \vdots \\&= f({\bar{R}}_1,\ldots ,{\bar{R}}_k,R'_{k+1},\ldots ,R'_n) \\&= f({\bar{R}})\\&= b \end{aligned}$$

This contradicts $f({\bar{R}})=a$. $\square$

Let ${\mathcal {I}}^a(f) = \{S\subseteq N: g^{N{\setminus } S}_f \textit{ is constant rule that picks a }\}$. Next we show the following fact.

Fact 1

${\mathcal {I}}^a(f)$ is a committee for indifference default a.

Proof

We show that ${\mathcal {I}}^a(f)$ satisfies following two properties.

• 1. Non-emptiness Since $N\in {\mathcal {I}}^a(f)$, ${\mathcal {I}}^a(f)\ne \emptyset$. Since f is onto and strategy-proof, $g^N_f$ is onto. Therefore, $\emptyset \notin {\mathcal {I}}^a(f)$.

• 2. Monotonicity Let $S\in {\mathcal {I}}^a(f)$ , $T\subseteq N$ and $S\subseteq T$. We show that $T\in {\mathcal {I}}^a(f)$. Since $g^{N{\setminus } S}_f$ is a constant rule that picks a, $g^{N{\setminus } T}_f$ is a constant rule that picks a. Therefore, $T\in {\mathcal {I}}^a(f)$.

$\square$

The following claim is a direct implication of Theorem 1 of Barberà et al. (1991). Hence, we omit the proof.

Claim 2

For each $M\subseteq N$, if $g^{M}_f$ is onto, then it is a voting by committee for a at M.

For each $M\subseteq N$ such that $g^{M}_f$ is onto, Claim 2 implies that $g^{M}_f$ is a voting by committee for a at M. Let ${\mathcal {F}}^{g^{M}_f}_M$ be the committee for a at M associated with $g^{M}_f$. Now, for each $M\subseteq N$, we define the set ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$ as follows. If $g^{M}_f$ is onto, then ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}= {\mathcal {F}}^{g^{M}_f}_M$. If $g^{M}_f$ is not onto i.e. $g^{M}_f$ is a constant rule that picks a, then ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}= \emptyset$.

First we show the following fact.

Fact 2

For each $M\subseteq N$, ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$ is a committee for a at M with respect to ${\mathcal {I}}^a(f)$.

Proof

We show that for each $M\subseteq N$, ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$ satisfies following two properties.

• 1. Non-emptiness with respect to${\mathcal {I}}^a(f)$: If $N{\setminus } M\notin {\mathcal {I}}^a(f)$, then $g^{M}_f$ is onto. Therefore, ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}={\mathcal {F}}^{g^{M}_f}_M$. Since ${\mathcal {F}}^{g^{M}_f}_M\ne \emptyset$ and $\emptyset \notin {\mathcal {F}}^{g^{M}_f}_M$, we have ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}\ne \emptyset$ and $\emptyset \notin {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$. This follows from Claim 2 and Barberà et al. (1991). If $N{\setminus } M\in {\mathcal {I}}^a(f)$, then $g^{M}_f$ is a constant rule that picks a. Therefore, ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}=\emptyset$ by definition.

• 2. Monotonicity W.o.l.o.g. we assume that ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}\ne \emptyset$. Therefore ${\mathcal {F}}_{M,{\mathcal {I}}^a(f)}={\mathcal {F}}^{g^{M}_f}_M$. Since ${\mathcal {F}}^{g^{M}_f}_M$ satisfies monotonicity (from Claim 2 and Barberà et al. (1991)), we have that for each $S\in {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$ and $T\subseteq M$, if $S\subseteq T$, then $T\in {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$.

$\square$

Next we show that ${\mathcal {F}}_{{\mathcal {I}}^a(f)} \equiv \{{\mathcal {F}}_{M,{\mathcal {I}}^a(f)}\}_{M\subseteq N}$ satisfies the properties of a collection of committees for a with respect to ${\mathcal {I}}^a(f)$.

Fact 3

${\mathcal {F}}_{{\mathcal {I}}^a(f)} \equiv \{{\mathcal {F}}_{M,{\mathcal {I}}^a(f)}\}_{M\subseteq N}$ satisfies the properties of a collection of committees for a with respect to ${\mathcal {I}}^a(f)$.

Proof

We show that for each $M\subseteq N$ and each $i\in M$:

• 1. If $N{\setminus } M\notin {\mathcal {I}}^a(f)$ and $\{N{\setminus } M\}\cup \{i\}\in {\mathcal {I}}^a(f)$, then for all $S \subseteq M$ such that $i\in S$, $S\in {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$. Suppose not. There exist $M\subseteq N$ and $S\subseteq M$ such that $N{\setminus } M\notin {\mathcal {I}}^a(f)$, $\{N{\setminus } M\}\cup \{i\}\in {\mathcal {I}}^a(f)$ and $i\in S\notin {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$. Let $R\in {\mathcal {R}}^n$ be a preference profile such that $aI_kb$ for all $k\in \{N{\setminus } M\}$, $aP_kb$ for all $k\in S$ and $bP_ka$ for all $k\in M{\setminus } S$. Note that $g^M_f(R)=b$. Therefore $f(R)=b$. Since f is strategy-proof, $f(R'_i,R_{N {\setminus } \{i\}})=b$ where $R'_i= aI'_ib$. This contradicts with the fact that $\{N{\setminus } M\}\cup \{i\}\in {\mathcal {I}}^a(f)$.

• 2. If $S\in {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$, $i\notin S$ and $\{N{\setminus } M\}\cup \{i\}\notin {\mathcal {I}}^a(f)$, then $S\in {\mathcal {F}}_{M{\setminus }\{i\},{\mathcal {I}}^a(f)}$. Let $R\in {\mathcal {R}}^n$ be a preference profile such that $aI_kb$ for all $k\in \{N{\setminus } M\}\cup \{i\}$, $aP_kb$ for all $k\in S$ and $bP_ka$ for all $k\in M{\setminus }\{S\cup i\}$. Let $R'=(R'_i,R_{N {\setminus } \{i\}})$ where $R'_i=bP'_ia$. Since $S\in {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$, $g^M_f(R')=a$. Therefore $f(R')=a$. Then by strategy-proofness, $f(R)=a$, i.e $g^{M{\setminus } i}_f(R)=a$. Since $\{N{\setminus } M\}\cup i\notin {\mathcal {I}}^a(f)$, $S\in {\mathcal {F}}_{M{\setminus } i,{\mathcal {I}}^a(f)}$.

• 3. If $N{\setminus } M\notin {\mathcal {I}}^a(f)$, $S\cup \{i\}\notin {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$ and $\{N{\setminus } M\}\cup \{i\}\notin {\mathcal {I}}^a(f)$, then $S\notin {\mathcal {F}}_{M{\setminus }\{i\},{\mathcal {I}}^a(f)}$. Let $R\in {\mathcal {R}}^n$ be be a preference profile such that $aI_kb$ for all $k\in N{\setminus } M$, $aP_kb$ for all $k\in S\cup i$ and $bP_ka$ for all $k\in M{\setminus }\{S\cup i\}$. Let $R'=(R'_i,R_{N {\setminus } \{i\}})$ where $R'_i=bI'_ia$. Since $S \cup i\notin {\mathcal {F}}_{M,{\mathcal {I}}^a(f)}$, $g^M_f(R)=b$. Therefore $f(R)=b$. Then by strategy-proofness, $f(R')=b$, i.e $g^{M{\setminus } i}_f(R')=b$. Since $\{N{\setminus } M\}\cup i\notin {\mathcal {I}}^a(f)$, $S\notin {\mathcal {F}}_{M{\setminus } i,{\mathcal {I}}^a(f)}$.

$\square$

We complete this case by showing that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} f(R) = h^{{\mathcal {I}}^a(f)}_{{\mathcal {F}}_{{\mathcal {I}}^a(f)}}(R). \end{aligned}$$

Consider any profile R. By Claim 1, $g^{N{\setminus } N_A(R)}_f$ is either a constant rule that picks a or it is an onto rule. Let $g^{N{\setminus } N_A(R)}_f$ be a constant rule that picks a. Therefore, $g^{N{\setminus } N_A(R)}_f(R)=a$ implies that $f(R)=a$. Which, in turn, implies that $N_{A}(R)\in {\mathcal {I}}^a(f)$; i.e.; $h^{{\mathcal {I}}^a(f)}_{{\mathcal {F}}_{{\mathcal {I}}^a(f)}}(R) = a$.

Now we assume that $g^{N{\setminus } N_A(R)}_f$ is an onto rule. Therefore, $N_{A}(R)\notin {\mathcal {I}}^a(f)$. By Claim 2, $g^{N{\setminus } N_A(R)}_f$ is a voting by committee for a at $N{\setminus } N_A(R)$. Let ${\mathcal {F}}^{g^{N{\setminus } N_A(R)}_f}_{N{\setminus } N_A(R)}$ be the committee for a at $N{\setminus } N_A(R)$ associated with $g^{N{\setminus } N_A(R)}_f$. Therefore, $g^{N{\setminus } N_A(R)}_f(R)=a$ if $N_a(R)\in {\mathcal {F}}^{g^{N{\setminus } N_A(R)}_f}_{N{\setminus } N_A(R)}$ and $g^{N{\setminus } N_A(R)}_f(R)=b$ if $N_a(R)\notin {\mathcal {F}}^{g^{N{\setminus } N_A(R)}_f}_{N{\setminus } N_A(R)}$. Since $g^{N{\setminus } N_A(R)}_f(R)=f(R)$ and

${\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^a(f)} = {\mathcal {F}}^{g^{N{\setminus } N_A(R)}_f}_{N{\setminus } N_A(R)}$, we are done.

Case 2: $f({\bar{R}})=b$. A similar argument (as in case 1) shows that there exists a committee for indifference default b, ${\mathcal {I}}^b$ and a collection of committees for a with respect to ${\mathcal {I}}^b$, ${\mathcal {F}}_{{\mathcal {I}}^b}$, such that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} f(R) = f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R). \end{aligned}$$

$\square$

The Proof of Theorem 2

We prove this theorem with the help of the following propositions. The first proposition is a direct implication of adding anonymity on Theorem 1. For this purpose, we introduce the following definitions. A committee for indifference default $d\in \{a,b\}$, ${\mathcal {I}}^d$, is anonymous, if $S \in {\mathcal {I}}^d$ implies $S^\prime \in {\mathcal {I}}^d$ for any $S^\prime \subseteq N$ such that $|S| = |S^\prime |$. If a committee for indifference default d is anonymous, then we refer it as anonymous committee for indifference defaultd.

Let $M\subseteq N$ and ${\mathcal {I}}^d$ be a committee for indifference default d. A committee for a at M with respect to ${\mathcal {I}}^d$, ${\mathcal {F}}_{M,{\mathcal {I}}^d}$, is anonymous, if $S \in {\mathcal {F}}_{M,{\mathcal {I}}^d}$ implies $S^\prime \in {\mathcal {F}}_{M,{\mathcal {I}}^d}$ for any $S^\prime \subseteq M$ such that $|S| = |S^\prime |$. If a committee for a at M with respect to ${\mathcal {I}}^d$ is anonymous, we refer it as anonymous committee foraatMwith respect to${\mathcal {I}}^d$.

A collection of anonymous committees forawith respect to${\mathcal {I}}^d$, is a collection of committees for a with respect to ${\mathcal {I}}^d$, satisfying following properties

• 1. For any $M\subseteq N$, ${\mathcal {F}}_{M,{\mathcal {I}}^d}$ is a anonymous committees for a at M with respect to ${\mathcal {I}}^d$.

• 2. For any $M,M'\subseteq N$, $S\subseteq M$ and $S'\subseteq M'$ where $|M|=|M'|$ and $|S|=|S'|$, if $S\in {\mathcal {F}}_{M,{\mathcal {I}}^d}$ then $S'\in {\mathcal {F}}_{M',{\mathcal {I}}^d}$.

We define generalized voting by anonymous committees (GVAC), as follows.

Definition 13

A SCF is GVAC, denoted by $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}$, if there exists a anonymous committee for indifference default d, ${\mathcal {I}}^d$ where $d\in A$ and a collection of anonymous committees for a with respect to ${\mathcal {I}}^d$, ${\mathcal {F}}_{{\mathcal {I}}^d}$, such that for all $R\in {\mathbb {R}}^n$;

$$\begin{aligned} f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}(R) = \left\{ \begin{array}{l l} d &{} \quad \text { if } N_{A}(R)\in {\mathcal {I}}^d\\ a &{} \quad \text { if } N_a(R)\in {\mathcal {F}}_{N{\setminus } N_{A}(R),{\mathcal {I}}^d} \text { and }N_{A}(R)\notin {\mathcal {I}}^d\\ b &{} \quad \text { otherwise }\\ \end{array} \right. \end{aligned}$$

This brings us to the following proposition.

Proposition 4

Let $f : {\mathcal {R}}^n \longrightarrow A$ be an onto SCF. If f is anonymous and strategy-proof, then f is GVAC.

Proof

Let f be an onto, anonymous and strategy-proof SCF. Let ${\bar{R}}\in {\mathcal {R}}^n$ denotes the preference profile where all agents are indifferent between a and b. We show that if $f({\bar{R}})=a$, then there exists a anonymous committee for indifference default a, ${\mathcal {I}}^a$ and a collection of anonymous committees for a with respect to ${\mathcal {I}}^a$, ${\mathcal {F}}_{{\mathcal {I}}^a}$, such that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} f(R) = f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R). \end{aligned}$$

Similarly, if $f({\bar{R}})=b$, then there exists a anonymous committee for indifference default b, ${\mathcal {I}}^b$ and a collection of anonymous committees for a with respect to ${\mathcal {I}}^b$, ${\mathcal {F}}_{{\mathcal {I}}^b}$, such that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} f(R) = f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R). \end{aligned}$$

In the following, we consider these two cases.

Case 1: $f({\bar{R}})=a$ : As f is strategy-proof and onto, we have the following.

• For any $M \subseteq N$, let $g^M_f : \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M \} \longrightarrow A$ be a function defined as $g^M_f(R) = f(R)$ for all $R \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M \}$. Then either $g^{M}_f$ is a constant rule that picks a or $g^{M}_f$ is onto. This follows from Claim 1 in the proof of Theorem 1.

• ${\mathcal {I}}^a(f) = \{S\subseteq N: g^{N {\setminus } S}_f \text { is constant rule that picks } a\}$ is a committee for indifference default a. This follows from Fact 1 in the proof of Theorem 1.

• ${\mathcal {F}}_{{\mathcal {I}}^a(f)} \equiv \{{\mathcal {F}}_{M,{\mathcal {I}}^a(f)}\}_{M\subseteq N}$, where

  $$\begin{aligned} {\mathcal {F}}_{M,{\mathcal {I}}^a(f)} = \left\{ \begin{array}{cl} \left\{ S \subseteq M : \begin{array}{c} \exists \text { } R \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M \} \\ \text { with } S = N_a(R) \subseteq M \text { and } g^{M}_f(R) = a \end{array}\right\} &{} \quad \text { if } \begin{array}{l} g^{M}_f \text { is an }\\ \text { onto function } \end{array} \\ \\ \emptyset &{} \quad \text { if } \begin{array}{l} g^{M}_f \text { is a }\\ \text { constant rule }\\ \text { that picks a} \end{array} \end{array}\right. \end{aligned}$$

  is a collection of committees for a with respect to ${\mathcal {I}}^a(f)$. This follows from Claim 2 and Facts 2 and 3 in the proof of Theorem 1.

Next we are going to show that ${\mathcal {I}}^a(f)$ is an anonymous committee for indifference default a.

Claim 3

${\mathcal {I}}^a(f)$ is an anonymous committee for indifference default a.

Proof

Consider $S, S^\prime \subseteq N$ such that $|S| = |S^\prime |$. Suppose $S \in {\mathcal {I}}^a(f)$, but to the contrary $S^\prime \notin {\mathcal {I}}^a(f)$. This implies that $g^{N {\setminus } S}_f$ is a constant rule that selects a, but $g^{N {\setminus } S^\prime }_f$ is onto. So there exists a $R \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin N {\setminus } S^\prime \}$ such that $g^{N {\setminus } S^\prime }_f(R) = b$. As $|S| = |S^\prime |$, we have $|N {\setminus } S| = |N {\setminus } S^\prime |$. As $N_a(R) \subseteq N {\setminus } S^\prime$, there exists $T \subseteq N {\setminus } S$ such that $|N_a(R)| = |T|$ and $|(N {\setminus } S^\prime ) {\setminus } N_a(R)| = |(N {\setminus } S) \setminus T|$. So we can define the following functions; $\sigma _1 : S^\prime \longrightarrow S$, $\sigma _2 : N_a(R) \longrightarrow T$ and $\sigma _3 : (N {\setminus } S^\prime ) {\setminus } N_a(R) \longrightarrow (N {\setminus } S) \setminus T$; which are all one-to-one and onto. Next, we define a permutation $\sigma : N \longrightarrow N$ as follows.

$$\begin{aligned} \sigma (i) = \left\{ \begin{array}{cl} \sigma _1(i) &{} \quad if i \in S^\prime \\ \sigma _2(i) &{} \quad if i \in N_a(R) \\ \sigma _3(i) &{} \quad if i \in (N {\setminus } S^\prime ) {\setminus } N_a(R) \\ \end{array}\right. \end{aligned}$$

Note that $\sigma$ is a well-defined permutation and $\sigma (R) \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin N {\setminus } S\}$. This implies that $g^{N {\setminus } S}_f(\sigma (R)) = a$; i.e.; $f(\sigma (R)) = a$. But this contradicts anonymity of f as $g^{N {\setminus } S^\prime }_f(R) = b$ implies $f(R) = b$. This concludes the proof of Claim 3. $\square$

Next we show that ${\mathcal {F}}_{{\mathcal {I}}^a(f)}$ is a collection of anonymous committees for a with respect to ${\mathcal {I}}^a(f)$.

Claim 4

${\mathcal {F}}_{{\mathcal {I}}^a(f)}$ is a collection of anonymous committees for a with respect to ${\mathcal {I}}^a(f)$.

Proof

First we show that for every $M \subseteq N$, ${\mathcal {F}}_{M, {\mathcal {I}}^a(f)}$ is a anonymous committees for a at M with respect to ${\mathcal {I}}^a(f)$. First note that as f is anonymous, so for any $M \subseteq N$, it follows that $g^{M}_f$ is also anonymous. Now for any $M \subseteq N$, consider $S, S^\prime \subseteq M$ such that $|S| = |S^\prime |$. Suppose for contradiction that $S \in {\mathcal {F}}_{M, {\mathcal {I}}^a(f)}$, but $S^\prime \notin {\mathcal {F}}_{M, {\mathcal {I}}^a(f)}$. This implies that there exists a profile $R \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M\}$ such that $N_a(R) = S$ and $g^{M}_f(R) = a$. As $|S| = |S^\prime |$, we have $|M {\setminus } S| = |M {\setminus } S^\prime |$. So we can define the following functions; $\sigma _1 : S \longrightarrow S^\prime$ and $\sigma _2 : M {\setminus } S \longrightarrow M {\setminus } S^\prime$; which are all one-to-one and onto. Next, we define a permutation $\sigma : N \longrightarrow N$ as follows.

$$\begin{aligned} \sigma (i) = \left\{ \begin{array}{cl} i &{} \quad if i \in N {\setminus } M \\ \sigma _1(i) &{} \quad if i \in S \\ \sigma _2(i) &{} \quad if i \in M {\setminus } S \\ \end{array}\right. \end{aligned}$$

Note that $\sigma$ is a well-defined permutation and $\sigma (R) \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M\}$ and $N_a(R) = S^\prime$. Now $S^\prime \notin {\mathcal {F}}_{M, {\mathcal {I}}^a(f)}$ implies that $g^{M}_f(\sigma (R)) = b$ because $g^{M}_f$ is onto. But this contradicts anonymity of $g^{M}_f$, as $g^{M}_f(R) = a$. This shows that for every $M \subseteq N$, ${\mathcal {F}}_{M, {\mathcal {I}}^a(f)}$ is a anonymous committee for a at M with respect to ${\mathcal {I}}^a(f)$. Next, consider any $M, M^\prime \subseteq N$ and $S \subseteq M$ and $S^\prime \subseteq M^\prime$ such that $|M| = |M^\prime |$ and $|S| = |S^\prime |$. We are going to show that if $S \in {\mathcal {F}}_{M, {\mathcal {I}}^a(f)}$, then $S^\prime \in {\mathcal {F}}_{M^\prime , {\mathcal {I}}^a(f)}$. So suppose for contradiction that $S \in {\mathcal {F}}_{M, {\mathcal {I}}^a(f)}$, but $S^\prime \notin {\mathcal {F}}_{M^\prime , {\mathcal {I}}^a(f)}$. As $S \in {\mathcal {F}}_{M, {\mathcal {I}}^a(f)}$, there exists a profile $R \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M\}$ such that $N_a(R) = S$ and $g^{M}_f(R) = a$. As $|M| = |M^\prime |$ and $|S| = |S^\prime |$, so it follows that $|M {\setminus } S| = |M^\prime {\setminus } S^\prime |$ and $|N {\setminus } M| = |N {\setminus } M^\prime |$. So we can define the following functions; $\sigma _4 : N {\setminus } M \longrightarrow N {\setminus } M^\prime$, $\sigma _5 : S \longrightarrow S^\prime$ and $\sigma _6 : M {\setminus } S \longrightarrow M^\prime {\setminus } S^\prime$; which are all one-to-one and onto. Next, we define a permutation $\sigma ^\star : N \longrightarrow N$ as follows.

$$\begin{aligned} \sigma ^\star (i) = \left\{ \begin{array}{cl} \sigma _4(i) &{} \quad if i \in N {\setminus } M \\ \sigma _5(i) &{} \quad if i \in S \\ \sigma _6(i) &{} \quad if i \in M {\setminus } S \\ \end{array}\right. \end{aligned}$$

Note that $\sigma ^\star$ is a well-defined permutation and $\sigma ^\star (R) \in \{R\in {\mathcal {R}}^n: aI_ib \textit{ iff } i\notin M^\prime \}$ and $N_a(R) = S^\prime$. As $g^{M}_f$ is onto, so it follows that $g^{M^\prime }_f$ is also onto. Otherwise there would be a violation of Claim 3 as $|N {\setminus } M| = |N {\setminus } M^\prime |$. Then $S^\prime \notin {\mathcal {F}}_{M^\prime , {\mathcal {I}}^a(f)}$ implies that $g^{M^\prime }_f(\sigma ^\star (R)) = b$; i.e.; $f(\sigma ^\star (R)) = b$. This contradicts anonymity of f as $g^{M}_f(R) = a$ implies that $f(R) = a$. This concludes the proof of Claim 4. $\square$

We complete this case by showing that for all $R\in {\mathcal {R}}^n$;

$$\begin{aligned} f(R) = f^{{\mathcal {I}}^a(f)}_{{\mathcal {F}}_{{\mathcal {I}}^a(f)}}(R). \end{aligned}$$

This follows from the definition of ${\mathcal {I}}^a(f)$ and ${\mathcal {F}}_{{\mathcal {I}}^a(f)}$ as shown at the end of case 1 in the proof of the only if part of Theorem 1.

Case 2: $f({\bar{R}})=b$ : A similar argument (as in case 1) shows that there exists a anonymous committee for indifference default b, ${\mathcal {I}}^b$ and a collection of anonymous committees for a with respect to ${\mathcal {I}}^b$, ${\mathcal {F}}_{{\mathcal {I}}^b}$, such that for all $R\in {\mathcal {R}}^n$; $f(R) = f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R).$$\square$

In the following proposition, we show that any GVAC rule can be described as either a quota rule with indifference default a or a quota rule with indifference default b.

Proposition 5

Let $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}}$ be a GVAC rule. Then either there exists a quota rule with indifference default a ($f^{k, x}_a$) such that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}} \equiv f^{k, x}_a$ or a quota rule with indifference default b ($f^{k, y}_b$) such that $f^{{\mathcal {I}}^d}_{{\mathcal {F}}_{{\mathcal {I}}^d}} \equiv f^{k, y}_b$.

Proof

Let ${\mathcal {W}}$ be any collection of subsets of N. We denote $Q({\mathcal {W}})$ as the cardinality of $S \in {\mathcal {W}}$ such that S contains the least number of agents among all sets in ${\mathcal {W}}$; i.e;

$$\begin{aligned} Q({\mathcal {W}}) = \displaystyle \min _{S \in {\mathcal {W}}} |S|, \text { where } {\mathcal {W}} \subseteq 2^N. \end{aligned}$$

We prove Proposition 5 with the help of the following lemmas. $\square$

Lemma 3

For the GVAC rule $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}$, we have the following.

• 1. $1 \le Q({\mathcal {I}}^a)=k\le n$.

• 2. ${\mathcal {F}}_{M,{\mathcal {I}}^a}$ satisfies following conditions:

  • 2.1 For all $M\subseteq N$, if $|M|\le n-k$ then ${\mathcal {F}}_{M,{\mathcal {I}}^a}=\emptyset$.

  • 2.2 For all $M,M'\subseteq N$ such that $|M|=|M'|> n-k$, $Q({\mathcal {F}}_{M,{\mathcal {I}}^a})=Q({\mathcal {F}}_{M',{\mathcal {I}}^a})$ and ${\mathcal {F}}_{M,{\mathcal {I}}^a}\ne \emptyset$ and ${\mathcal {F}}_{M',{\mathcal {I}}^a}\ne \emptyset$.

  • 2.3 For all $M\subseteq N$ such that $|M|=n-k+l$ where $l\in \{1,\ldots ,k\}$, we have $Q({\mathcal {F}}_{M,{\mathcal {I}}^a})\in \{1,\ldots ,l\}$.

  • 2.4 For all $M,M'\subseteq N$ such that $|M'|=|M|-1> n-k$, $Q({\mathcal {F}}_{M,{\mathcal {I}}^a})\ge Q({\mathcal {F}}_{M',{\mathcal {I}}^a}) \ge Q({\mathcal {F}}_{M,{\mathcal {I}}^a}) - 1$.

Proof

As ${\mathcal {I}}^a$ is an anonymous committee for indifference default a, it follows that $N \in {\mathcal {I}}^a$ and $\emptyset \notin {\mathcal {I}}^a$ (Non-emptyness condition of ${\mathcal {I}}^a$). This implies that $1 \le Q({\mathcal {I}}^a)=k\le n$.

Next we prove statement 2.1. So consider a $M\subseteq N$ such that $|M|\le n-k$. This implies that $|N {\setminus } M| \ge k$. As $Q({\mathcal {I}}^a)=k$, monotonicity and anonymity property of ${\mathcal {I}}^a$ implies that $N {\setminus } M \in {\mathcal {I}}^a$. Then non-emptyness with respect to ${\mathcal {I}}^a$ property of ${\mathcal {F}}_{{\mathcal {I}}^a}$ implies that ${\mathcal {F}}_{M,{\mathcal {I}}^a}=\emptyset$.

Next we prove statement 2.2. So consider $M,M'\subseteq N$ such that $|M|=|M'|> n-k$. This implies that $|N {\setminus } M| = |N {\setminus } M'| < k$. As $Q({\mathcal {I}}^a)=k$, it follows that $N {\setminus } M \notin {\mathcal {I}}^a$ and $N {\setminus } M' \notin {\mathcal {I}}^a$. So from the non-emptyness with respect to ${\mathcal {I}}^a$ property of ${\mathcal {F}}_{{\mathcal {I}}^a}$, it follows that ${\mathcal {F}}_{M,{\mathcal {I}}^a} \ne \emptyset$ and ${\mathcal {F}}_{M',{\mathcal {I}}^a} \ne \emptyset$. Also as ${\mathcal {F}}_{{\mathcal {I}}^a}$ is anonymous, it follows that $Q({\mathcal {F}}_{M,{\mathcal {I}}^a})=Q({\mathcal {F}}_{M',{\mathcal {I}}^a})$ from the definition of Q.

Next we prove statement 2.3. So consider $M\subseteq N$ such that $|M|=n-k+l$ where $l\in \{1,\ldots ,k\}$. Suppose for contradiction that $Q({\mathcal {F}}_{M,{\mathcal {I}}^a}) > l$. So it follows that for all $S \in {\mathcal {F}}_{M,{\mathcal {I}}^a}$, $|S| > l$. Now we consider the situation when $l = 1$. Then $|M|=n-k+1$ implies that $|N {\setminus } M| = k - 1$. As $Q({\mathcal {I}}^a)=k$, it follows, from the definition of Q, that $N {\setminus } M \notin {\mathcal {I}}^a$. Now consider an $i \in M$ and the coalition $(N {\setminus } M) \cup \{i\}$. Note that $|(N {\setminus } M) \cup \{i\}| = k$. As ${\mathcal {I}}^a$ is an anonymous committee for indifference default a, it follows that $(N {\setminus } M) \cup \{i\} \in {\mathcal {I}}^a$. Then as ${\mathcal {F}}_{{\mathcal {I}}^a}$ is a collection of committees for a with respect to ${\mathcal {I}}^a$, it follows by using property 1 that $\{i\} \in {\mathcal {F}}_{M,{\mathcal {I}}^a}$. This contradicts our assumption that for all $S \in {\mathcal {F}}_{M,{\mathcal {I}}^a}$, $|S| > 1$. Now suppose that for all $M\subseteq N$ such that $|M|=n-k+l$ where $l\in \{1,\ldots ,k-1\}$, we have $Q({\mathcal {F}}_{M,{\mathcal {I}}^a})\in \{1,\ldots ,l\}$, but there exists a $M^\prime \subseteq N$ such that $|M^\prime |=n-k+l+1$ and $Q({\mathcal {F}}_{M^\prime ,{\mathcal {I}}^a}) > l+1$. So consider the case where $M^\prime = M \cup \{i\}$. Now consider a coalition $S \subseteq M$, such that $|S| = Q({\mathcal {F}}_{M,{\mathcal {I}}^a})$. As $Q({\mathcal {F}}_{M^\prime ,{\mathcal {I}}^a}) > l+1$, it follows that $S \cup \{i\} \notin {\mathcal {F}}_{M^\prime ,{\mathcal {I}}^a}$. Note that $|N {\setminus } M^\prime | = k - l - 1$ and $|(N {\setminus } M^\prime ) \cup \{i\}| = k - l$. As $Q({\mathcal {I}}^a)=k$, it follows that $N {\setminus } M^\prime \notin Q({\mathcal {I}}^a)$ and $(N {\setminus } M^\prime ) \cup \{i\} \notin Q({\mathcal {I}}^a)$. Then as ${\mathcal {F}}_{{\mathcal {I}}^a}$ is a collection of committees for a with respect to ${\mathcal {I}}^a$, it follows by using property 3 that $S \notin {\mathcal {F}}_{M^\prime {\setminus } \{i\},{\mathcal {I}}^a} = {\mathcal {F}}_{M,{\mathcal {I}}^a}$. This however contradicts anonymity of ${\mathcal {F}}_{{\mathcal {I}}^a}$ as $|S| = Q({\mathcal {F}}_{M,{\mathcal {I}}^a})$. Hence the proof of statement 2.3 is concluded by induction.

Next, we prove statement 2.4. So consider $M,M'\subseteq N$ such that $|M'|=|M|-1> n-k$. In view of statement 2.2, without loss of generality, it can be assumed that $M = M' \cup \{i\}$. Now suppose for contradiction that

• Case 1 : either $Q({\mathcal {F}}_{M,{\mathcal {I}}^a}) < Q({\mathcal {F}}_{M',{\mathcal {I}}^a})$,

• Case 2 : or $Q({\mathcal {F}}_{M,{\mathcal {I}}^a}) - 1 > Q({\mathcal {F}}_{M',{\mathcal {I}}^a})$.

In case 1, there exists $S \subseteq M$ such that $S \in {\mathcal {F}}_{M,{\mathcal {I}}^a}$ and $|S| = Q({\mathcal {F}}_{M,{\mathcal {I}}^a})$. Now if $S = M$, then we have a contradiction to $Q({\mathcal {F}}_{M,{\mathcal {I}}^a}) < Q({\mathcal {F}}_{M',{\mathcal {I}}^a})$ as $|M| \ge |S^\prime |$ for any $S' \subseteq M'$. So we have $S \subsetneq M$. Then it follows that there exists $S^\star \subsetneq M$ such that $|S^\star | = |S|$ and $S^\star \subseteq M^\prime$. As ${\mathcal {F}}_{{\mathcal {I}}^a}$ is a collection of anonymous committees for a with respect to ${\mathcal {I}}^a$, it follows that $S^\star \in {\mathcal {F}}_{M,{\mathcal {I}}^a}$. Note that as $S^\star \subseteq M'$, it follows that $i \notin S^\star$. Also as $|M|-1> n-k$, it follows that $|(N {\setminus } M) \cup \{i\}| < k$. As $Q({\mathcal {I}}^a) = k$, it follows that $(N {\setminus } M) \cup \{i\} \notin {\mathcal {I}}^a$. Then as ${\mathcal {F}}_{{\mathcal {I}}^a}$ is a collection of committees for a with respect to ${\mathcal {I}}^a$, it follows by using property 2 that $S^\star \in {\mathcal {F}}_{M {\setminus } \{i\},{\mathcal {I}}^a} = {\mathcal {F}}_{M',{\mathcal {I}}^a}$. This constitutes a contradiction with the definition of Q as $|S^\star | < Q({\mathcal {F}}_{M',{\mathcal {I}}^a})$.

In case 2, there exists $S \subseteq M'$ such that $|S| = Q({\mathcal {F}}_{M',{\mathcal {I}}^a})$. Note that if $S = M'$, it follows from case 2 that $Q({\mathcal {F}}_{M,{\mathcal {I}}^a}) > |M'| + 1$. This is a contradiction as for all $S \subseteq M$, we have $|S| \le |M| = |M'| + 1$. Now consider the set $S \cup \{i\} \subsetneq M$. Note that $|S \cup \{i\}| = Q({\mathcal {F}}_{M',{\mathcal {I}}^a}) + 1$. As $Q({\mathcal {F}}_{M,{\mathcal {I}}^a}) > Q({\mathcal {F}}_{M',{\mathcal {I}}^a}) + 1$, from the definition of Q, it follows that $S \cup \{i\} \notin {\mathcal {F}}_{M,{\mathcal {I}}^a}$. Also as $|M|-1> n-k$, it follows that $|(N {\setminus } M) \cup \{i\}| < k$ and $|(N {\setminus } M)|< k - 1 < k$. As $Q({\mathcal {I}}^a) = k$, it follows that $(N {\setminus } M) \cup \{i\} \notin {\mathcal {I}}^a$ and $(N {\setminus } M) \notin {\mathcal {I}}^a$. Then as ${\mathcal {F}}_{{\mathcal {I}}^a}$ is a collection of committees for a with respect to ${\mathcal {I}}^a$, it follows by using property 3 that $S \notin {\mathcal {F}}_{M {\setminus } \{i\},{\mathcal {I}}^a} = {\mathcal {F}}_{M',{\mathcal {I}}^a}$. This constitutes a contradiction with the anonymity property of ${\mathcal {F}}_{M',{\mathcal {I}}^a}$ as $|S| = Q({\mathcal {F}}_{M',{\mathcal {I}}^a})$. This completes the proof of statement 2.4 and concludes the proof of Lemma 3. $\square$

Observation 1

Given a GVAC rule $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}$, let $k = Q({\mathcal {I}}^a)$ and $x_l = Q({\mathcal {F}}_{M, {\mathcal {I}}^a})$, where $|M| = n - k + l$ for any $l \in \{1, 2, \ldots , k\}$. Then it follows from Lemma 3 that $f^{{\mathcal {I}}^a}_{{\mathcal {F}}_{{\mathcal {I}}^a}}(R) = f^{k, x}_a(R)$ for all $R \in {\mathcal {R}}^N$.

Lemma 4

For the GVAC rule $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}$, we have the following.

• 1. $1 \le Q({\mathcal {I}}^b)=k\le n$.

• 2. ${\mathcal {F}}_{M,{\mathcal {I}}^b}$ satisfies following conditions:

  • 2.1 For all $M\subseteq N$, $|M|\le n-k$ if and only if ${\mathcal {F}}_{M,{\mathcal {I}}^b}=\emptyset$

  • 2.2 For all $M,M'\subseteq N$ such that $|M|=|M'|> n-k$, $Q({\mathcal {F}}_{M,{\mathcal {I}}^b})=Q({\mathcal {F}}_{M',{\mathcal {I}}^b})$ and $Q({\mathcal {F}}_{M,{\mathcal {I}}^b}) \ne \emptyset$ and $Q({\mathcal {F}}_{M',{\mathcal {I}}^b}) \ne \emptyset$.

  • 2.3 For all $M\subseteq N$ such that $|M|=n-k+l$ where $l\in \{1,\ldots ,k\}$, we have $Q({\mathcal {F}}_{M,{\mathcal {I}}^b})\in \{n-k+1,\ldots ,n-k+l\}$

  • 2.4 For all $M,M'\subseteq N$ such that $|M'|=|M-1|> n-k$, $Q({\mathcal {F}}_{M,{\mathcal {I}}^d})\ge Q({\mathcal {F}}_{M',{\mathcal {I}}^d})\ge Q({\mathcal {F}}_{M,{\mathcal {I}}^d}) - 1$.

Proof

In view of Lemma 3, we will only show the proof of statement 2.3. So consider $M\subseteq N$ such that $|M|=n-k+l$ where $l\in \{1,\ldots ,k\}$. First consider the case, where $l = 1$. In this case, we have to show that ${\mathcal {F}}_{M,{\mathcal {I}}^b} = \{M\}$. As $|M|=n-k+1$, it follows that $|N {\setminus } M| = k - 1$. As $Q({\mathcal {I}}^b)=k$, it follows, from the definition of Q, that $N {\setminus } M \notin {\mathcal {I}}^a$. Now for every $i \in M$, consider the coalitions $(N {\setminus } M) \cup \{i\}$. Note that $|(N {\setminus } M) \cup \{i\}| = k$. As ${\mathcal {I}}^b$ is an anonymous committee for indifference default b, it follows that $(N {\setminus } M) \cup \{i\} \in {\mathcal {I}}^b$. Then as ${\mathcal {F}}_{{\mathcal {I}}^a}$ is a collection of committees for a with respect to ${\mathcal {I}}^b$, it follows by using property 1 that if $S \in {\mathcal {F}}_{M,{\mathcal {I}}^a}$ then $i \in S$. As this is true for all $i \in M$, it follows that ${\mathcal {F}}_{M,{\mathcal {I}}^b} = \{M\}$. Now suppose that for all $M\subseteq N$ such that $|M|=n-k+l$ where $l\in \{1,\ldots ,k-1\}$, we have $Q({\mathcal {F}}_{M,{\mathcal {I}}^b})\in \{n-k+1,\ldots ,n-k+l\}$, but there exists a $M^\prime \subseteq N$ such that $|M^\prime |=n-k+l+1$ and either $Q({\mathcal {F}}_{M^\prime ,{\mathcal {I}}^b}) > n-k+l+1$, or $Q({\mathcal {F}}_{M^\prime ,{\mathcal {I}}^b}) < n-k+1$. Note that $Q({\mathcal {F}}_{M^\prime ,{\mathcal {I}}^b}) > n-k+l+1$ implies for all $S \in {\mathcal {F}}_{M^\prime ,{\mathcal {I}}^a}$, we have $|S| > n-k+l+1$. This is a contradiction as $S \subseteq M^\prime$ and $|M^\prime |=n-k+l+1$. So assume that $Q({\mathcal {F}}_{M^\prime ,{\mathcal {I}}^b}) < n-k+1$. Now consider an $M \subseteq N$ such that $M^\prime = M \cup \{i\}$ for some $i \in N {\setminus } M$. Then it follows that $|M|=n-k+l$. So $Q({\mathcal {F}}_{M,{\mathcal {I}}^b})\in \{n-k+1,\ldots ,n-k+l\}$. Now consider a $S \subsetneq M$ such that $|S| = n-k$. As $Q({\mathcal {F}}_{M^\prime ,{\mathcal {I}}^b}) < n-k+1$; i.e.; $Q({\mathcal {F}}_{M^\prime ,{\mathcal {I}}^b}) \le n-k$, monotonicity and anonymity property of ${\mathcal {F}}_{M^\prime ,{\mathcal {I}}^b}$ implies that $S \in {\mathcal {F}}_{M^\prime ,{\mathcal {I}}^b}$. Note that $i \notin S$. Also $|(N {\setminus } M^\prime ) \cup \{i\}| = k-l < k$. Then from the definition of Q, it follows that $(N {\setminus } M^\prime ) \cup \{i\} \notin {\mathcal {I}}^b$. As ${\mathcal {F}}_{{\mathcal {I}}^a}$ is a collection of committees for a with respect to ${\mathcal {I}}^b$, it follows by using property 2 that $S \in {\mathcal {F}}_{M^\prime {\setminus } \{i\},{\mathcal {I}}^b} = {\mathcal {F}}_{M,{\mathcal {I}}^b}$. This contradicts the fact that $Q({\mathcal {F}}_{M,{\mathcal {I}}^b})\in \{n-k+1,\ldots ,n-k+l\}$ as $|S| = n-k$. Hence the proof of statement 2.3 is concluded by induction.

Observation 2

Given a GVAC rule $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}$, let $k = Q({\mathcal {I}}^b)$ and $y_l = Q({\mathcal {F}}_{M, {\mathcal {I}}^a})$, where $|M| = n - k + l$ for any $l \in \{1, 2, \ldots , k\}$. Then it follows from Lemma 4 that $f^{{\mathcal {I}}^b}_{{\mathcal {F}}_{{\mathcal {I}}^b}}(R) = f^{k, y}_b(R)$ for all $R \in {\mathcal {R}}^N$.

The proof of Proposition concludes by Observations 1 and 2. $\square$

Proof of Theorem 2

In view of Propositions 4 and 5, to prove Theorem 2, it is sufficient to show that the quota rule with indifference default a and the quota rule with indifference default b are strategy-proof, onto and anonymous. First we show that the quota rule with indifference default a ($f^{k, x}_a$) is strategy-proof, anonymous and onto. The fact that $f^{k, x}_a$ is onto and anonymous follows directly from the definition of $f^{k, x}_a$. Next, in view of Lemma 1, as $f^{k, x}_a$ is onto, it is sufficient to show that $f^{k, x}_a$ satisfies weak strategy-proofness. So consider a profile $R \in {\mathcal {R}}^N$ and an $i-$deviation $R^\prime \in {\mathcal {R}}^N$ of R. We need to show $f^{k, x}_a(R) R_i f^{k, x}_a(R^\prime )$ in the following cases.

• $a P_i b$ and $a I^\prime _i b$ : In this case, suppose $f^{k, x}_a(R) = a$. then it follows that $f^{k, x}_a(R) R_i f^{k, x}_a(R^\prime )$. So suppose that $f^{k, x}_a(R) = b$. This implies that $|N_A(R)| < k$. Also in this case we have $|N_a(R) \cup N_b(R)| = n-k+l$, for some $l \in \{2, 3, \ldots , k\}$. Otherwise, $|N_a(R) \cup N_b(R)| = n-k+1$ and $|N_a(R)| \ge 1 = x_1$ (due to the fact that $a P_i b$) would imply that $f^{k, x}_a(R) = a$, which contradict our assumption that $f^{k, x}_a(R) = b$. Also we have $|N_a(R)| < x_l$. Now $|N_a(R) \cup N_b(R)| = n-k+l$, for some $l \in \{2, 3, \ldots , k\}$ implies that $|N_A(R)| \le k-2$. So it follows that $|N_A(R^\prime )| \le k-1 < k$. Also $|N_a(R^\prime ) \cup N_b(R^\prime )| = n-k+l-1$. Note that $x_l - 1 \le x_{l-1} \le x_l$. Also $|N_a(R^\prime )| = |N_a(R)| - 1$. Now $|N_a(R)| < x_l$ implies $|N_a(R^\prime )| < x_l - 1 \le x_{l - 1}$. This shows that $f^{k, x}_a(R^\prime ) = b$ and we can conclude that $f^{k, x}_a(R) R_i f^{k, x}_a(R^\prime )$.

• $b P_i a$ and $a I^\prime _i b$ : In this case, suppose $f^{k, x}_a(R) = b$. then it follows that $f^{k, x}_a(R) R_i f^{k, x}_a(R^\prime )$. So suppose that $f^{k, x}_a(R) = a$. Now if $|N_A(R)| \ge k-1$, then it follows that $|N_A(R^\prime )| \ge k$. This implies that $f^{k, x}_a(R^\prime ) = a$. So suppose that $|N_A(R)| < k-1$ and $|N_A(R^\prime )| < k$. In this case we have $|N_a(R) \cup N_b(R)| = n-k+l$, for some $l \in \{2, 3, \ldots , k\}$ Also we have $|N_a(R)| \ge x_l$. Also $|N_a(R^\prime ) \cup N_b(R^\prime )| = n-k+l-1$. Note that $x_l - 1 \le x_{l-1} \le x_l$. Also $|N_a(R^\prime )| = |N_a(R)|$. Now $|N_a(R)| \ge x_l$ and $x_{l-1} \le x_l$ implies $|N_a(R^\prime )| \ge x_{l - 1}$. This shows that $f^{k, x}_a(R^\prime ) = a$ and we can conclude that $f^{k, x}_a(R) R_i f^{k, x}_a(R^\prime )$.

Combining these cases, it follows that $f^{k, x}_a$ satisfies weak strategy-proofness. Hence as $f^{k, x}_a$ is onto and Lemma 1 implies that $f^{k, x}_a$ is strategy-proof. In a similar way, it can be shown that $f^{k, y}_b$ is anonymous, onto and strategy-proof. This concludes the proof of Theorem 2. $\square$

The Proof of Proposition 2

Proof

Only if part. Let $f_a^{k, x}$ be a quota rule with indifference default a and it satisfies WDPR. Therefore, the length of x is either (i) $k=n$ or (ii) $k\in \{1,2,\ldots ,n-1\}$.

First we assume that $k=n$. If $x_n=1$ or n then we are done. We assume for contradiction that $x_n\in \{2,3,\ldots ,n-1\}$. Let R be a preference profile such that $N_{A}(R)=\emptyset$ and $N_a(R)=x_n$. Since $f_a^{k, x}$ be a quota rule with indifference default a, $f_a^{k, x}(R)=a$. Let $R'$ be a preference profile such that $N_{A}(R')=\emptyset$ and $N_a(R')=x_n-1$. Note that $N_a(R)$, $N_b(R)$, $N_a(R')$, $N_b(R')$$\ne$$\emptyset$. Therefore, by Lemma 2$f_a^{k, x}(R)=f_a^{k, x}(R')$. However, since $f_a^{k, x}$ be a quota rule with indifference default a, $f_a^{k, x}(R')=b$ - a contradiction. Therefore $x_n=1$ or n, which in turn imply that $x=(x_1,\ldots ,x_n)\in \{(1,1,\ldots ,1), (1,2,\ldots ,n)\}$.

Finally we assume that $k\in \{1,2,\ldots ,n-1\}$. Note that if we can show $x_i=x_{i+1}$ for all $i\in \{1,2,\ldots ,k-1\}$, then we are done. If $k=1$, we are done trivially. Therefore we assume that $k>1$. We assume for contradiction that there exists $i\in \{1,2,\ldots ,k-1\}$ such that $x_i\ne x_{i+1}$. Let $i'$ be he minimum among all $i\in \{1,2,\ldots ,k-1\}$ such that $x_i\ne x_{i+1}$. Note that $x_{i'}=1$ and $x_{i'+1}=2$. Let R and $R'$ be preference profiles such that $|N_a(R) \cup N_b(R)| = |N_a(R') \cup N_b(R')| = n - k + i'+1$. Moreover we assume that $|N_a(R)|= 2$ and $|N_a(R')|=1$. Since $N_a(R)$, $N_b(R)$, $N_a(R')$, $N_b(R')$$\ne$$\emptyset$; by Lemma 2$f_a^{k, x}(R)=f_a^{k, x}(R')$. However, since $f_a^{k, x}$ be a quota rule with indifference default a, $f_a^{k, x}(R)=a\ne b=f_a^{k, x}(R')$ - a contradiction. Therefore, $x_i=x_{i+1}$ for all $i\in \{1,2,\ldots ,k-1\}$, which in turn imply that $x=(x_1,\ldots ,x_n)=(1,1,\ldots ,1)$.

If part. We first prove the following claim.

Claim 5

Let $f:{\mathcal {R}}^n\longrightarrow A$ select the same alternative in each disagreement profile. Then f satisfies WDPR.

Proof

Let $R\in {\mathcal {R}}^n$, $i\in N$ and $R'_i\in {\mathcal {R}}$. If both R and $(R'_i,R_{-i})$ are disagreement profile then $f(R)=f(R'_i,R_{-i})$. Suppose this is not the case. Then either (i) for each $j\in N{\setminus } \{i\}$, we have $f(R)R_jf(R'_i,R_{-i})$ or (ii) for each $j\in N{\setminus } \{i\}$, we have $f(R'_i,R_{-i})R_jf(R)$. In either case WDPR is satisfied. $\square$

Let $f_a^{k, x}:{\mathcal {R}}^n\longrightarrow A$ be a quota rule with indifference default a. If x is a vector of natural numbers of length n and $x=(x_1,\ldots ,x_n)=(1,1,\ldots ,1)$, then $f_a^{k, x}$ selects a in each disagreement profile. If x is a vector of natural numbers of length n and $x=(x_1,\ldots ,x_n)=(1,2,\ldots ,n)$, then $f_a^{k, x}$ selects b in each disagreement profile. If x is a vector of natural numbers of length k, $k\in \{1,2,\ldots ,n-1\}$ and $x=(x_1,\ldots ,x_k)=(1,1,\ldots ,1)$, then $f_a^{k, x}$ selects a in each disagreement profile. Therefore, by Claim 5, all these rules satisfy WDPR. $\square$

The Proof of Proposition 3

Proof

Only if part. Let $f_b^{k, y}$ be a quota rule with indifference default b and it satisfies WDPR. Therefore, the length of y is either (i) $k=n$ or (ii) $k\in \{1,2,\ldots ,n-1\}$.

First we assume that $k=n$. If $Y_n=1$ or n then we are done. We assume for contradiction that $y_n\in \{2,3,\ldots ,n-1\}$. Let R be a preference profile such that $N_{A}(R)=\emptyset$ and $N_a(R)=y_n$. Since $f_b^{k, y}$ be a quota rule with indifference default b, $f_b^{k, y}(R)=a$. Let $R'$ be a preference profile such that $N_{A}(R')=\emptyset$ and $N_a(R')=y_n-1$. Note that $N_a(R)$, $N_b(R)$, $N_a(R')$, $N_b(R')$$\ne$$\emptyset$. Therefore, by Lemma 2$f_b^{k, y}(R)=f_b^{k, y}(R')$. However, since $f_b^{k, y}$ be a quota rule with indifference default b, $f_b^{k, y}(R')=b$ - a contradiction. Therefore $y_n=1$ or n, which in turn imply that $y=(y_1,\ldots ,y_n)\in \{(1,1,\ldots ,1), (1,2,\ldots ,n)\}$.

Finally we assume that $k\in \{1,2,\ldots ,n-1\}$. Note that if we can show $y_i\ne y_{i+1}$ for all $i\in \{1,2,\ldots ,k-1\}$, then we are done. If $k=1$, we are done trivially. Therefore we assume that $k>1$. We assume for contradiction that there exists $i\in \{1,2,\ldots ,k-1\}$ such that $y_i= y_{i+1}$. Let $i'$ be he minimum among all $i\in \{1,2,\ldots ,k-1\}$ such that $y_i= y_{i+1}$. Therefore $y_{i'}= y_{i'+1}=n-k+i'$. Let R and $R'$ be preference profiles such that $|N_a(R) \cup N_b(R)| = |N_a(R') \cup N_b(R')| = n - k + i'+1$. Moreover we assume that $|N_a(R)|= n-k+i'$ and $|N_a(R')|=n-k+i'-1$. Since $N_a(R)$, $N_b(R)$, $N_a(R')$, $N_b(R')$$\ne$$\emptyset$; by Lemma 2$f_b^{k, y}(R)=f_b^{k, y}(R')$. However, since $f_b^{k, y}$ be a quota rule with indifference default b, $f_b^{k, y}(R)=a\ne b=f_b^{k, y}(R')$ - a contradiction. Therefore, $y_i\ne y_{i+1}$ for all $i\in \{1,2,\ldots ,k-1\}$, which in turn imply that $y=(y_1,\ldots ,y_k)=(n-k+1,n-k+2,\ldots ,n)$.

If part. Let $f_b^{k, y}:{\mathcal {R}}^n\longrightarrow A$ be a quota rule with indifference default b. If y is a vector of natural numbers of length n and $y=(y_1,\ldots ,y_n)=(1,1,\ldots ,1)$, then $f_b^{k, y}$ selects a in each disagreement profile. If y is a vector of natural numbers of length n and $y=(y_1,\ldots ,y_n)=(1,2,\ldots ,n)$, then $f_b^{k, y}$ selects b in each disagreement profile. If y is a vector of natural numbers of length k, $k\in \{1,2,\ldots ,n-1\}$ and $y=(y_1,\ldots ,y_k)=(n-k+1,n-k+2,\ldots ,n)$, then $f_b^{k, y}$ selects b in each disagreement profile. Therefore, by Claim 5, all these rules satisfy WDPR. $\square$