1 Introduction
Societies make decisions by means of voting rules, mapping profiles of voters’ preferences into social alternatives. However since individual preferences are private information, voters may behave strategically by not submitting their preferences truthfully. Voting rules that are immune to this kind of manipulation are called strategy-proof. Another way of behaving strategically, especially when the identities of the agents cannot be verified, is by voting several times under other identities. This is in fact a real and growing phenomenon in anonymous online mechanisms where agents can participate several times. Many social decisions processes are held online worldwide, particularly during the Covid-19 lockdowns. Selection processes for Massive Open Online (MOO) Courses or MOO Schools, rating systems for goods and services, Internet auctions (a popular part of Electronic Commerce), or Facebook allowing users to vote on its future terms of use (see (Zuckerberg, 2009)), are all examples where an agent could vote multiple times. As many institutions or websites may not have enough resources to correctly identify each agent in these kinds of situations, repeated participation can be a highly relevant issue. An online anonymous poll on a specific political issue, run by a popular news website, although not binding, may lead to overwhelming pressure on the government. A voting rule where voters cannot benefit by voting several times is usually known in the literature as false-name-proof (see (Yokoo et al., 2004)).1
When voters’ preferences do not have a specific structure, results on voting rules satisfying some form of false-name-proofness are rather negative, even for random voting rules. Nanyang (2013) shows that, under unrestricted domains of voters’ preferences, if a voting rule is strategy-proof, anonymous, and population monotonic, then it is strongly false-name-proof; moreover, under strict preferences, the converse also holds.2
Anzeige
Conitzer (2008) characterizes all anonymous-proof and neutral randomized voting rules under strict preferences over a finite set of alternatives.3 Each element in the class identified by Conitzer (2008) is described by a probability \(p\in [0,1]\) with which an alternative is chosen with uniform probability and with probability \(1-p\) a pair of alternatives is chosen with uniform probability and if all voters unanimously prefer one alternative over the other, this preferred alternative is chosen, and otherwise a fair coin is used to decide between the two. These voting rules are perceived as being very unresponsive to voters’ preferences.
Nevertheless, in many applications, the particular structure of the set of alternatives suggests that not all voters’ preferences are conceivable. An extensive literature on social choice presumes that a natural restriction on the domain of voters’ preferences holds, one that is meaningful with respect to that structure. A prominent example of this kind of domain restriction is when the set of alternatives has a linear order structure relative to which single-peaked preferences can be naturally defined. Then, the median voter rule (that selects the median of the profile of voters’ best alternatives relative to the linear order) is strategy-proof (see (Moulin, 1980)). However, the median voter rule is not false-name-proof since a voter with the lowest best alternative can manipulate the voting rule by casting several votes for her own best alternative. The latter was shown by Todo et al. (2011), who also characterize the class of all strongly false-name-proof, efficient, and anonymous voting rules as those that, for each set of voters N (with cardinality n), the voting rule selects the median of the n reported best alternatives together with \(n-1\) fixed ballots for a given a priory alternative.4 Some form of false-name-proofness has also been studied in other settings, often under the name of duplication as in Congar and Merlin (2012) and García-Lapresta and Martínez-Panero (2017). For instance, in social networks (see (Brill et al., 2016)), in matching problems (see (Todo & Conitzer, 2013)), in sybil attacks (see (Shahaf et al., 2019) and Meir et al. (2020)), or together with other properties (see (Wagman & Conitzer, 2008) and Waggoner et al. (2012)). What most of these papers have in common, is that they assume that voting rules are anonymous, so anonymity does not appear explicitly in their characterizations. Since we are considering problems where voters’ identities are not easily verifiable, anonymity is a very natural requirement. However, we show that in our setting with separable preferences, anonymity follows from false-name-proofness, strategy-proofness, and ontoness (see Proposition 3).
In this paper, we consider social choice problems where societies have to choose a subset from a given set of objects (candidates, binary issues, or alike), and voters have separable preferences over subsets of objects. A voter’s preference is separable over the family of all subsets of objects if the ranking of subsets is guided by the partition separating the set of objects into the set of good objects (as singleton sets, objects that are better than the empty set) and bad objects (as singleton sets, objects that are worse than the empty set). Adding a good object to any set leads to a better set while adding a bad object leads to a worse set. Note that the best subset of objects of a separable preference is the union of all good objects and that all additively representable preferences are separable. This is the setting considered by Barberà et al. (1991), where they characterize the family of all strategy-proof, anonymous, onto, and neutral voting rules as the class of all voting by quota.5 A (neutral) voting by quota for N specifies (and it can be identified with) an integer \(q_N\) between 1 and n, where \(n=|N|\). Then the choice of the subset of objects made by the voting by quota \(q_N\) at a profile of separable preferences is done object-by-object as follows: object x belongs to the chosen set if and only if the set of voters for which x is a good object has cardinality larger or equal to \(q_N\). Hence, voting by quota can be seen as a family of qualified majority voting where the two alternatives at stake (in each voting) are whether or not x belongs to the collectively chosen subset of objects.
We want to identify here, for this setting under separable preferences, simple voting rules that are simultaneously immune to two types of manipulations: not voting according to the true preferences (strategy-proofness) and voting many times (false-name-proofness). Observe that our notion of false-name-proofness is weaker than most of the notions that can be found in the literature (for example in Conitzer (2008), Todo et al. (2011), and Nanyang (2013)). We consider situations where each agent must submit one vote under its identity, but it can also repeat this vote using other identities, while the most common notion allows each agent to additionally vote several times submitting any kind of vote, not necessarily equal to the vote cast by the agent under its identity. Our notion of false-name-proofness protects against an extremely easy way to manipulate an election by a (not necessarily human) voter: clicking several times to submit the same vote seems easier than voting several times, changing the vote each time.
Anzeige
On the way to our characterization result, we prove some auxiliary results. The first one is important by itself since it states that any false-name-proof, strategy-proof, and onto voting rule is indeed anonymous. Hence, anonymity does not have to be explicitly imposed (as most of the literature does). This implication is also very intuitive: if no voter has the incentive to use other identities to repeat her vote, then voters’ identities should not matter at all. Additionally, we prove two propositions that identify implications that false-name-proofness has in this setting: an object should be chosen if either it has at least one vote in every possible set of voters or if it has a unanimous vote in every possible set of voters. These results help us to build the proof for our main result (Theorem 1) that characterizes all voting rules that satisfy false-name-proofness, strategy-proofness, and ontoness as the class of voting by quota where to be chosen, each object needs either at least one vote or a unanimous vote. This means that each voter can either impose the object (by voting for it) or veto the object (by not voting for it). Our proof of Theorem 1 shows that false-name-proofness in this characterization can be replaced by strong false-name-proofness (Corollary 1). Moreover, we show in Proposition 6 that if a voting rule is strategy-proof, false-name-proof, and onto, then it satisfies participation. In Proposition 8, we establish that, in any setting and any domain of preferences, if a voting rule is strongly false-name-proof and satisfies anonymity and participation, then it is strategy-proof as well. Finally, Example 1 indicates that the statement of Proposition 8 does not hold if strong false-name-proofness is replaced by false-name-proofness, even under the domain of separable preferences.
The rest of the paper is organized as follows. Section 2 contains preliminaries, the definition of separable preferences, properties of voting rules, and the definition of voting by quota. Section 3 contains the results. In Sect. 3.1 we state Theorem 1, the main result of the paper. Section 3.2 contains preliminary results that are used in the proof of Theorem 1. In Sect. 3.3, we prove Theorem 1 and state two of its Corollaries. Section 3.4 contains additional results. Finally, in Sect. 3.5, we show that the axioms used in Theorem 1 are independent. Section 4 contains a final remark.
2 Preliminaries and definitions
2.1 Voters, alternatives, separable preferences, and voting rules
We are interested in studying social choice procedures under which societies choose a subset from a given set of objects, as in Barberà et al. (1991). Our aim is to identify those which are simultaneously immune to voters’ manipulations by revealing non-truthful preferences and by providing additional preferences under other identities. While the first property does not require that the society be variable, the second one requires to consider different societies. For this reason, we consider societies with a variable set of voters. Let \({\mathcal {N}}\) be the family of all finite and no-empty subsets of the set of positive integers \({\mathbb {Z}}_+\). An element \(N\in {\mathcal {N}}\) is interpreted as a society. We denote the cardinality of N by n and refer to an element \(i\in N\) as a voter. Each set of voters \(N\in {\mathcal {N}}\) has to collectively choose a subset from a given finite set \({\mathcal {M}}=\{1,\ldots ,M\}\) of objects. Then, the set of alternatives from which any society has to choose from is the family of all subsets of objects \(2^{{\mathcal {M}}}\).
For each voter i, let \(P_{i}\) be voter i’s preference over \(2^{{\mathcal {M}}}\). We assume that \(P_{i}\) is a strict linear order and denote by \({\mathcal {D}}\) a generic set of strict preferences over \(2^{{\mathcal {M}}}\), which we will refer to as a domain. We denote the weak counterpart of \(P_i\) by \(R_i\). A profile (for \(N\in {\mathcal {N}}\)) is an ordered list of preferences \(P=(P_{i})_{i\in N}\in {\mathcal {D}}^{N}\), one for each voter in N. By convention, we set \({\mathcal {D}}^{\emptyset }=\emptyset\). For \(N,N^{\prime }\in {\mathcal {N}}\) (with \(N\cap N^{\prime }= \emptyset\)) and two profiles of preferences \(P=(P_{i})_{i\in N}\in {\mathcal {D}}^{N}\) and \(P^{\prime }=(P_{i}^{\prime })_{i\in N^{\prime }}\in {\mathcal {D}}^{N^{\prime }}\), we denote the profile \(((P_{i})_{i\in N},(P_{i}^{\prime })_{i\in N^{\prime }})\in {\mathcal {D}}^{N\cup N^{\prime }}\) by \((P, P^{\prime })\). Let \(P=(P_{i})_{i\in N}\in {\mathcal {D}}^{N}\) be a profile, let \(i\in N\) be a voter, and let \(S\subset N\) be a subset of N, we denote by \(P_{-i}\in {\mathcal {D}}^{N\backslash \{i\}}\) the profile obtained from P after deleting \(P_{i}\) and by \(P_S\in {\mathcal {D}}^S\) and by \(P_{-S}\in {\mathcal {D}}^{N\setminus S}\) the profiles obtained from P restricted to S and to \(N\setminus S\), respectively.
Let \(P_i\) be a preference over \(2^{\mathcal {M}}\). An object is good (respectively, bad) according to \(P_i\) if as a singleton set is strictly preferred (respectively, less preferred) to the empty set. A preference \(P_{i}\) is separable if the division between good and bad objects guides the ordering between some pairs of subsets: adding a good object to any set leads to a better set, while adding a bad object to any set leads to a worse set. Formally, a preference \(P_{i}\in {\mathcal {D}}\) is separable if for all \(T\in 2^{{\mathcal {M}}}\) and \(x\notin T\),Let \({\mathcal {S}}\) be the set of all separable preferences over \(2^{{\mathcal {M}}}\).
$$\begin{aligned} T\cup \{x\}\,P_{i}\,T\text { if and only if }\{x\}\,P_{i}\,\emptyset . \end{aligned}$$
A preference \(P_{i}\in {\mathcal {D}}\) is additive if there exists a function \(u:{\mathcal {M}}\cup \{\emptyset \}\rightarrow {\mathbb {R}}\) such that \(u(\emptyset )=0\) and for all \(T,T^{\prime }\in 2^{{\mathcal {M}}}\),where by convention we set \(\sum _{x\in {\widehat{T}}}u(x)=0\) for \({\widehat{T}}=\emptyset\). In this case, we say that u (additively) represents \(P_{i}\). Of course, all additive preferences are separable. Let \({\mathcal {A}}\) be the set of all additive preferences over \(2^{{\mathcal {M}}}\).
$$\begin{aligned} T\,P_{i}\,T^{\prime }\text { if and only if }\sum _{x\in T}u(x)>\sum _{x\in T^{\prime }}u(x), \end{aligned}$$
Given \(P_{i}\in {\mathcal {D}}\), let \(b(P_{i})\) and \(w(P_{i})\) be, respectively, the best and the worst subsets of \(2^{{\mathcal {M}}}\) according to \(P_{i}\); namely, \(b(P_{i})\,P_{i}\,T\) for all \(T\in 2^{{\mathcal {M}}}{\setminus } {b(P_{i})}\) and \(T\, P_i\,w(P_{i})\) for all \(T\in 2^{{\mathcal {M}}}\setminus {w(P_{i})}\). It is easy to see that if \(P_{i}\in {\mathcal {S}}\), then \(b(P_{i})=\{x\in {\mathcal {M}}\mid \{x\}\,P_{i}\,\emptyset \}\) and \(w(P_{i})=\{x\in {\mathcal {M}}\mid \emptyset \, P_{i}\,\{x\}\}\).
A voting rule for \(N\in {\mathcal {N}}\) on a domain \({\mathcal {D}}\) selects a subset of \({\mathcal {M}}\) for each profile \(P\in {\mathcal {D}}^{N}\). Namely, given a domain \({\mathcal {D}}\), a voting rule for N is a mapping \(f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\). A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) (on \({\mathcal {D}}\)) is a family of voting rules, one for each \(N\in {\mathcal {N}}\).
2.2 Properties of voting rules
We define desirable properties for voting rules.
The first property states that all possible subsets of objects should be feasible to be selected; that is, for each \(N\in {\mathcal {N}}\), \(f_N\) is onto. Barberà et al. (1991) refer to ontoness as voters’ sovereignty.
Definition 1
A voting rule \(f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\) for N is onto if, for all \(T\in 2^{\mathcal {M}}\), there exists a \(P\in {\mathcal {D}}^{N}\) such that \(f_{N}(P)=T\). A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is onto if \(f_{N}\) is onto for each \(N\in {\mathcal {N}}\).
The following two properties are very natural in online environments, and state that no voter nor object should receive a differential treatment.
Definition 2
A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is anonymous if, for each bijection \(\sigma :{\mathbb {Z}}_+\rightarrow {\mathbb {Z}}_+\), each \(N\in {\mathcal {N}}\) and each \(P\in {\mathcal {D}}^N\), \(f_N(P)=f_{\sigma (N)}(\sigma (P))\), where \(\sigma (P)=(P_{\sigma (i)})_{i\in N}\). A voting rule \(f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\) for N is anonymous if, for each bijection \(\sigma _N:N\rightarrow N\) and each \(P\in {\mathcal {D}}^{N}\), \(f_{N}(P)=f_{N}(\sigma _N (P))\).6
Definition 3
A voting rule \(f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\) for N is neutral if, for each bijection \(\mu :{\mathcal {M}}\rightarrow {\mathcal {M}}\) and each \(P\in {\mathcal {D}}^{N}\), \(\mu (f_{N}(P))=f_{N}(\mu (P))\), where \(\mu (T)\) and \(\mu (P)=(P_{i}^{\prime })_{i\in N}\) are the subset of objects and the preference profile obtained, respectively, from \(T\in 2^{\mathcal {M}}\) and \(P\in {\mathcal {D}}^{N}\) by permuting the objects according to \(\mu\); namely, \(\mu (T)=\{x\in {\mathcal {M}}\mid x=\mu (y)\) for \(y\in T\}\) and, for each \(i\in N\) and pair \(S,T\in 2^{{\mathcal {M}}}\), \(\mu (S)\,P_{i}^{\prime }\,\mu (T)\) if and only if \(S\,P_{i}\,T\). A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is neutral if \(f_{N}\) is neutral for each \(N\in {\mathcal {N}}\).
The first manipulation property that we are interested in is the one that requires that the voting rule does not give incentives to report non-truthful preferences.
Definition 4
A voting rule \(f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\) for N is strategy-proof if for all \(P\in {\mathcal {D}}^{N}\), all \(i\in N\) and all \(P_{i}^{\prime }\in {\mathcal {D}}\),A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is strategy-proof if \(f_{N}\) is strategy-proof for each \(N\in {\mathcal {N}}\).
$$\begin{aligned} f_N(P_i,P_{-i})\,R_{i}\,f_N(P_{i}^{\prime },P_{-i}). \end{aligned}$$
Another important requirement, especially in online voting, is that a voter should never have incentives to cast repeated votes.
Definition 5
A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is false-name-proof if for all \((N,P)\in {\mathcal {N}}\times {\mathcal {D}}^{N}\), all \(i\in N\) and all \((N^{\prime },P^{\prime })\in {\mathcal {N}}\times {\mathcal {D}}^{N^{\prime }}\) such that \(N\cap N^{\prime }= \emptyset\) and \(P_{j}^{\prime }=P_{i}\) for all \(j\in N^{\prime }\),
$$\begin{aligned} f_N(P)\,R_{i}\,f_{N\cup N^{\prime }}(P, P^{\prime }). \end{aligned}$$
Conitzer (2008) refers to false-name-proof (randomized) voting rules as those satisfying a stronger version of our notion for non-randomized voting rules. Conitzer’s (Conitzer, 2008) condition imposes stronger restrictions on the voting rule by not requiring that the additional preferences submitted by voter \(i\in N\) coincide with agent i’s original preference \(P_i\).7 For this reason, we refer here to Conitzer’s (Conitzer, 2008) original notion as strong false-name-proofness.
Definition 6
A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is strongly false-name-proof if for all \((N,P)\in {\mathcal {N}}\times {\mathcal {D}}^{N}\), all \(i\in N\) and all \((N^{\prime },P^{\prime })\in {\mathcal {N}}\times {\mathcal {D}}^{N^{\prime }}\) such that \(N\cap N'=\emptyset\),
$$\begin{aligned} f_N(P)\,R_{i}\,f_{N\cup N^{\prime }}(P, P^{\prime }). \end{aligned}$$
Moreover, Conitzer (2008) also requires that (randomized) voting rules induce voters to vote. We shall show that, in our context, this participation property follows from false-name-proofness, strategy-proofness, and ontoness. For non-randomized voting rules, participation is as follows.
Definition 7
A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) satisfies participation if, for all \((N,P)\in {\mathcal {N}}\times {\mathcal {D}}^{N}\) such that \(n\ge 2\) and all \(i\in N\),
$$\begin{aligned} f_N(P)\,R_{i}\,f_{N\setminus \{i\}}(P_{-i}). \end{aligned}$$
2.3 Voting by committees and voting by quota
To define a class of anonymous voting rules required to state our main result, we need the concept of a committee.
Definition 8
A committee \({\mathcal {W}}_N\) is a non-empty family of non-empty coalitions of N, which satisfies coalition monotonicity; that is, if \(I\in {\mathcal {W}}_N\) and \(I\subseteq J\), then \(J\in {\mathcal {W}}_N\). Such coalitions are called winning. A minimal winning coalition is an \(I\in {\mathcal {W}}_N\) such that for every \(J\subsetneq I\), \(J\notin {\mathcal {W}}_N\). We denote by \({\mathcal {W}}_N^m\) the family of minimal winning coalitions of \({\mathcal {W}}_N\).
Following Barberà et al. (1991), we introduce voting by committees.
Definition 9
A voting rule \(f_N:{\mathcal {D}}^N\rightarrow 2^{{\mathcal {M}}}\) is voting by committees for N if, for each \(x\in {\mathcal {M}}\), there exists a committee \({\mathcal {W}}_{N,\,x}\) such that, for every \(P\in {\mathcal {D}}^N\),A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is voting by committees if for each \(N\in {\mathcal {N}}\), \(f_{N}\) is voting by committees for N.
$$\begin{aligned} x\in f_{N}(P)\text { if and only if } \{i\in N\mid x\in b(P_{i})\}\in {\mathcal {W}}_{N,\,x}. \end{aligned}$$
Let \(N\in {\mathcal {N}}\) be a given set of voters with cardinality n, and let \(x\in {\mathcal {M}}\) be an object. A quota for N and x is an integer \(q_{N,\,x}\in \{1,\dots ,n\}\). Set \(q_N=(q_{N,\,x})_{x\in {\mathcal {M}}}\).
Definition 10
A voting rule \(f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\) for N is voting by quota \(q_N=(q_{N\,,\,x})_{x\in {\mathcal {M}}}\) if, for all \(P\in {\mathcal {D}}^{N}\),A voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is voting by quota if, for each \(N\in {\mathcal {N}}\), \(f_N\) is voting by quota \(q_N\).
$$\begin{aligned} x\in f_{N}(P)\text { if and only if } |\{i\in N\mid x\in b(P_{i})\} |\ge q_{N,\,x}. \end{aligned}$$
Note that by definition, a voting by quota rule is very simple. It can be seen as a family of extended majority voting, one for each object x, where voters have to decide whether x is chosen or not; specifically, it is anonymous, as the voting rule only takes into account the number of votes that each object receives, not the voters’ identities.
For a fixed society, Barberà et al. (1991) characterize the class of strategy-proof and onto voting rules when the preferences are separable or additive representable. The following proposition follows from their results.
Proposition 1
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\). Then, a voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is strategy-proof and onto if and only if f is voting by committees.
Adding anonymity to the requirements gives us, also from Barberà et al. (1991), the following result.
Proposition 2
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\). Then, a voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is strategy-proof, anonymous, and onto if and only if f is voting by quota.
3 Results
3.1 Main result
We now state our main result characterizing the family of all false-name-proof, strategy-proof, and onto voting rules, on any separable domain that contains all additively representable preferences.
Theorem 1
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\). Then, a voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is false-name-proof, strategy-proof, and onto if and only f is a voting by quota such that, for each \(x\in {\mathcal {M}}\), either \(q_{N\,,\,x}=1\) for all \(N\in {\mathcal {N}}\) or \(q_{N,\,x}=n\) for all \(N\in {\mathcal {N}}\).
3.2 Preliminary results for the proof of Theorem 1
In this Subsection, we introduce additional notation and obtain some preliminary results that will be useful to prove Theorem 1.
Given \(x\in {\mathcal {M}},\) we denote by \(u^{x}:{\mathcal {M}}\cup \{\emptyset \}\rightarrow {\mathbb {R}}\) any function such that \(u^{x}(x)>\left| u^{x}(y)\right| >u^{x}(\emptyset )=0\) for all \(y\in {\mathcal {M}}\setminus \{x\}\), and if \(x\in T\) and \(x\notin T^{\prime }\) then \(\sum _{y\in T}u^{x}(y)>\sum \nolimits _{y\in T^{\prime }}u^{x}(y)\); accordingly, if \(u^{x}\) represents \(P_{i}\), then \(x\in T\) and \(x\notin T^{\prime }\) imply \(T\, P_{i}\,T^{\prime }\). Similarly, given \(y\in {\mathcal {M}}\), we denote by \(u_{y}:{\mathcal {M}}\cup \{\emptyset \}\rightarrow {\mathbb {R}}\) any function such that \(\left| u_{y}(y)\right|>\left| u_{y}(x)\right|>u_{y}(\emptyset )=0>u_{y}(y)\) for all \(x\in {\mathcal {M}}{\setminus } \{y\}\), and if \(y\in T\) and \(y\notin T^{\prime }\) then \(\sum _{x\in T}u_{y}(x)<\sum \nolimits _{x\in T^{\prime }}u_{y}(x)\); accordingly, if \(u_{y}\) represents \(P_{i}\), then \(y\in T\) and \(y\notin T^{\prime }\) imply \(T^{\prime }\,P_{i}\,T\).
We first show that in our context, false-name-proofness, strategy-proofness, and ontoness imply anonymity.
Proposition 3
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\) and let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be a false-name-proof, strategy-proof, and onto voting rule. Then, f is anonymous.
Proof
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\) and let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be a false-name-proof, strategy-proof, and onto voting rule. Then, by Proposition 1, for each \(N\in {\mathcal {N}}\), \(f_N\) is voting by committees for N. Let \(({\mathcal {W}}_{N,\,x})_{x\in {\mathcal {M}}}\) be the family of committees associated with \(f_N\). Before going on with the proof, we present the following useful result.
Lemma 1
Let \(S,N,N'\in {\mathcal {N}}\) be such that \(N\cap N'=\emptyset\) and \(S \subsetneq N\), and let \(x\in {\mathcal {M}}\). Then, \(S\in {\mathcal {W}}_{N\cup N'\,,\,x}\) if and only if \(S\in {\mathcal {W}}_{N\,,\,x}\).
Proof of Lemma 1
\((\Rightarrow )\) To obtain a contradiction, let \(S\in {\mathcal {W}}_{N\cup N'\,,\,x}\) and assume that \(S\notin {\mathcal {W}}_{N\,,\,x}\) holds. Then, there exists a profile \(P\in {\mathcal {D}}^N\) such that \(x\in b(P_i)\) for all \(i\in S\) and \(x\notin f_N(P)\). Consider voter \(i\in S\) and any additive preference \(P^{\prime }_i\in {\mathcal {A}}\) such that (i) \(b(P^{\prime }_i)=b(P_i)\) and (ii) \(P^{\prime }_i\) is represented by \(u^x\). Since \(f_N\) is voting by committees, it depends only on the profile of tops. Accordingly, \(x\notin f_N(P^{\prime }_i,P_{N{\setminus }\{i\}})=f_N(P)\). Consider the profile \({\widehat{P}}\in {\mathcal {D}}^{N^{\prime }}\) where, for each \(j\in N^{\prime }\), \({\widehat{P}}_j=P_i^{\prime }\). Since f is false-name-proof, \(f_N(P^{\prime }_i,P_{N{\setminus }\{i\}})\,R_i^{\prime }\,f_{N\cup N'}(P^{\prime }_i,P_{N{\setminus }\{i\}},{\widehat{P}})\) which, by (ii) in the definition of \(P^{\prime }_i\), implies that \(x\notin f_{N\cup N'}(P^{\prime }_i,P_{N{\setminus }\{i\}},{\widehat{P}})\). Define \(P''=(P^{\prime }_i,P_{N{\setminus }\{i\}},{\widehat{P}})\in {\mathcal {D}}^{N\cup N^{\prime }}\). Hence, at profile \(P''\), \(S\subseteq \{j\in N\cup N'\mid x\in b(P''_j)\}\notin {\mathcal {W}}_{N\cup N^{\prime }\,,\,x}\). Coalition monotonicity of the committee implies that \(S\notin {\mathcal {W}}_{N\cup N',\,x}\), which is a contradiction.
\((\Leftarrow )\) To obtain a contradiction, let \(S\in {\mathcal {W}}_{N\,,\,x}\) and assume that \(S\notin {\mathcal {W}}_{N\cup N'\,,\,x}\) holds. Then, there exists a profile \(P'\in {\mathcal {D}}^{N\cup N'}\) such that \(x\in b(P'_i)\) for all \(i\in S\) and \(x\notin f_{N\cup N'}(P')\). Consider the profile \(P\in {\mathcal {D}}^N\) such that \(P_i=P'_i\) for all \(i\in S\) and \(P_j\) is represented by \(u_x\) for all \(j\in N\backslash {S}\). Observe that the assumption \(S\subsetneq N\) implies \(N\backslash {S}\ne \emptyset\). Since \(S\in {\mathcal {W}}_{N\,,\,x}\), \(x\in f_N(P)\) holds. Consider now the profile \(P^*\in {\mathcal {D}}^{N\cup N'}\) such that \(P^*_i=P'_i=P_i\) for all \(i\in S\) and each \(j\in (N\cup N'){\setminus } S\) has the same preference \(P^*_j\in {\mathcal {A}}\) represented by \(u_x\). Since f is false-name-proof, we have that \(x\in f_{N\cup N'}(P^*)\), otherwise an agent \(j\in N\backslash {S}\ne \emptyset\) has the incentive to replicate its vote under the identities of voters in \(N'\). Now, for a given \(j\in (N\cup N')\backslash {S}\), we have by strategy-proofness that \(x\in f_{N\cup N'}(P^*_{-j},P'_j)\). Otherwise, agent j has the incentive to misreport her vote. By repeating this procedure for each \(j\in (N\cup N')\backslash {S}\) and by strategy-proofness, we obtain that \(x\in f_{N\cup N'}(P')\), a contradiction. \(\square\)
We now proceed with the proof of Proposition 3.
Suppose f is not anonymous. Then, there exists a bijection \(\sigma :Z_+\rightarrow Z_+\), a society \(N\in {\mathcal {N}}\) and a profile \(P\in {\mathcal {D}}^N\) such that \(f_N(P)\ne f_{\sigma (N)}(\sigma (P))\). Since \(\sigma\) is a bijection we can assume, without loss of generality, that there exist \(x\in {\mathcal {M}}\) and \(S\in N\) such that (i) \(x\in f_N(P)\) and \(x\notin f_{\sigma (N)}(\sigma (P))\). Hence, there is \(S\in {\mathcal {W}}_{N,x}\) such that \(T:=\sigma (S)\notin {\mathcal {W}}_{\sigma (N),x}\). As the whole society always is a winning coalition, we have that \(T\subsetneq \sigma (N)\), and thus \(S\subsetneq N\). Define \(N^*=\sigma (N)\cup N\) and \(N'=N^*{\setminus }{S}\). We proceed by distinguishing between two cases.
Case 1: \(T\ne S\).
Since \(\sigma\) is a bijection, \(T{\setminus } S\ne \emptyset\). To obtain a contradiction, suppose \(T{\setminus } S\notin {\mathcal {W}}_{N^*,x}\). As \(T{\setminus } S\subsetneq (\sigma (N)\cup N){\setminus } S\) we have, by Lemma 1, that \(T{\setminus } S\notin {\mathcal {W}}_{N'\,,\,x}\). This means that there is a profile \(P'\in {\mathcal {D}}^{N'}\) such that \(x\in b(P'_t)\) for all \(t\in T{\setminus } S\) and \(x\notin f_{N'}(P')\). By Lemma 1, as \(S\in {\mathcal {W}}_{N\,,\,x}\) and \(S\subsetneq N\), we have that \(S\in {\mathcal {W}}_{N^*\,,\,x}\). As \(S\subsetneq (T{\setminus } S)\cup S\), by coalitional monotonicity, we have that \((T{\setminus } S)\cup S\in {\mathcal {W}}_{N^*\,,\,x}\). Now, consider a profile \(P''\in {\mathcal {D}}^{N'}\) such that \(b(P''_t)=b(P'_t)\) and \(P''_t\) is represented by \(u^x\) for all \(t\in T{\setminus } S\), and \(P''_k=P'_k\) for all \(k\notin T{\setminus } S\). As \(f_{N'}\) is voting by committees, it depends only on the profile of tops, so \(x\notin f_{N'}(P'')=f_{N'}(P')\). But then any agent \(t\in T{\setminus } S\) has the incentive to replicate her vote under the identities of voters in S, to obtain \(x\in f_{N^*}(P'',P_{S})\), where \(P_i=P''_t\) for all \(i\in S\), violating false-name-proofness. So we have that \(T{\setminus } S\in {\mathcal {W}}_{N^*\,,\,x}\). As \(T{\setminus } S\ne \emptyset\), by Lemma 1, we obtain that \(T{\setminus } S\in {\mathcal {W}}_{\sigma (N)\,,\,x}\) and thus, by coalition monotonicity, \(T=\sigma (S)\in {\mathcal {W}}_{\sigma (N),\,x}\), a contradiction with our initial hypothesis.
Case 2: \(T=S\)
Since we have that \(S\subsetneq N\), by Lemma 1, \(S\in {\mathcal {W}}_{N^*,\,x}\), Then, as \(T\subsetneq \sigma (N)\), and again by Lemma 1, we obtain that \(T\in {\mathcal {W}}_{\sigma (N),\,x}\), a contradiction with our initial hypothesis that f is not anonymous.
This finishes with the proof of Proposition 3\(\square\)
The second preliminary result shows the effect that false-name-proofness has on the quotas of a voting rule.
Proposition 4
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\) and let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be a false-name-proof, strategy-proof, and onto voting rule. Then, f is voting by quota \(q=(q_{N\,,\,x})_{N\in {\mathcal {N}}\,,\,x\in {\mathcal {M}}}\) where, for each \(x\in {\mathcal {M}}\), either \(q_{N\,,\,x}=1\) for all \(N\in {\mathcal {N}}\) or \(q_{N,\,x}=n\) for all \(N\in {\mathcal {N}}\).
Proof
Assume \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is a false-name-proof, strategy-proof, and onto voting rule. By Propositions 1, 2, and 3, for each \(N\in {\mathcal {N}}\), \(f_{N}\) is a voting by quota \(q_N=(q_{N,x})_{x\in {\mathcal {M}}}\). For an object \(x\in {\mathcal {M}}\), a set of voters N, and a profile \(P\in {\mathcal {D}}^N\), define \(x_N(P)=|\{i\in N\mid x\in b(P_i)\}|\). Before going on with the proof, we present the following relevant result.
Lemma 2
Let \(N,N'\in {\mathcal {N}}\) be such that \(N\cap N'=\emptyset\). Then, \(q_{N\,,\,x}\le q_{N\cup N'\,,\,x}\) for all \(x\in {\mathcal {M}}\).
Proof of the Lemma 2
To obtain a contradiction, suppose that \(q_{N\,,\,x}>q_{N\cup N'\,,\,x}\) for an object \(x\in {\mathcal {M}}\). Hence, \(q_{N,\,x}>1\). Consider \(i\in N\) and \(P\in {\mathcal {D}}^{N}\) such that \(P_i\in {\mathcal {A}}\) is additively represented by \(u^{x}\) and \(x_{N}(P)=q_{N,\,x}-1\). Observe that \(x\in b(P_i)\) by definition of \(u^{x}\), and \(x\notin f_N(P)\) by definition of voting by quota \(q_{N}\). Consider now a profile \(P'\in {\mathcal {D}}^{N'}\) such that \(P'_j=P_i\) for all \(j\in N'\). Since \(N\cap N'=\emptyset\), \(x_{N\cup N'}(P, P')=x_{N}(P)+x_{N'}(P')=q_{N\,,\,x}-1+n'>q_{N\cup N'\,,\,x}\), by our contradiction hypothesis and \(n'\ge 1\). Since \(f_{N\cup N'}\) is voting by quota \(q_{N\cup N'}\), \(x\in f_{N\cup N'}(P, P')\) and, by definition of \(u^{x}\), \(f_{N\cup N'}(P, P')\,P_{i}\,f_{N}(P)\), a contradiction with false-name-proofness.\(\Box\)
To proceed with the proof of Proposition 4, first observe that by the definition of voting by quota, anonymity, and Lemma 2, for a given x, \(q_{1\,,\,x}=1\le q_{2\,,\,x}\le 2\) holds, where \(q_{k\,,\,x}=q_{S\,,\,x}\) for any \(S\in {\mathcal {N}}\) with \(|S |=k\). Fix \(x\in {\mathcal {M}}\). We distinguish between the two possible cases and, for each of them, we show that the statement of Proposition 4 holds by induction on n (the number of voters).
Case 1: \(q_{1,\,x}= q_{2,\,x}=1\).
Induction hypothesis: Assume \(q_{1\,,\,x}=\dots =q_{n\,,\,x}=1\).
Consider the case \(n+1\), where \(n\ge 2\). We want to show that \(q_{n+1,\,x}=1\). To obtain a contradiction, suppose \(q_{n+1,\,x}>q_{n,\,x}=1\). Consider \(i\in N\) and a profile \(P\in {\mathcal {D}}^N\) such that \(P_i\in {\mathcal {A}}\) is additively represented by \(u_x\) and \(x_N(P)=1\). Observe that \(x\notin b(P_i)\) by definition of \(u_x\), and \(x\in f_N(P)\) by definition of voting by quota \(q_{n,\,x}\). Let \(j\notin N\) and \(P_j=P_i\). Then, \(x_{N\cup \{j\}}(P, P_j)=1<q_{n+1,\,x}\) and, accordingly, \(x\notin f_{N\cup \{j\}}(P, P_{j})\), which is a contradiction with false-name-proofness because, by definition of \(u_x\), \(f_{N\cup \{j\}}(P, P_{j})\,P_{i}\,f_N(P)\).
Case 2: \(q_{1,\,x}= 1<2=q_{2,\,x}\).
Induction hypothesis: Assume \(q_{x,\,t}=t=|T|\) for every \(T\in {\mathcal {N}}\) such that \(1\le t\le n\).
Consider the case \(n+1\), where \(n\ge 2\). We want to show that \(q_{n+1,\,x}=n+1\). By the definition of quota, Lemma 2, and the induction hypothesis we have that \(n\le q_{n+1\,,\,x}\le n+1\). Suppose that \(q_{n+1\,,\,x}=n\). Consider \(i\in N\), \(x\in {\mathcal {M}}\) and a profile \(P\in {\mathcal {D}}^N\) such that \(P_i\in {\mathcal {A}}\) is additively represented by \(u^x\) and \(x_N(P)=q_{n,\,x}-1=n-1\). Observe that \(x\in b(P_i)\) by definition of \(u^{x}\), and \(x\notin f_N(P)\) by definition of voting by quota \(q_{n}\). Let \(j\notin N\) and \(P_j=P_i\). Then, \(x_{N\cup \{j\}}(P, P_j)=n-1+1=q_{n+1,\,x}\) and, accordingly, \(x\in f_{N\cup \{j\}}(P, P_{j})\), which is a contradiction with false-name-proofness because, by definition of \(u^x\), \(f_{N\cup \{j\}}(P,P_{j})\,P_{i}\,f_N(P)\).
Thus, f is voting by quota \(q=(q_{N\,,\,x})_{N\in {\mathcal {N}}\,,\,x\in {\mathcal {M}}}\) where, for every \(x\in {\mathcal {M}}\), either \(q_{N\,,\,x}=1\) for every \(N\in {\mathcal {N}}\) or \(q_{N,\,x}=n\) for every \(N\in {\mathcal {N}}\). \(\square\)
The third preliminary result states that voting by quota in this subclass satisfies false-name-proofness.
Proposition 5
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\) and let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be a voting by quota \(q=(q_{N\,,\,x})_{N\in {\mathcal {N}}\,,\,x\in {\mathcal {M}}}\) such that, for every \(x\in {\mathcal {M}}\), either \(q_{N\,,\,x}=1\) for every \(N\in {\mathcal {N}}\) or \(q_{N,\,x}=n\) for every \(N\in {\mathcal {N}}\). Then f is false-name-proof.
Proof
Let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be a voting by quota \(q=(q_{N,\,x})_{N\in {\mathcal {N}},\,x\in {\mathcal {M}}}\). Assume first that, for a given \(x\in {\mathcal {M}}\), \(q_{N\,,\,x}=n\) for all \(N\in {\mathcal {N}}\). We show that f is strongly false-name-proof, which would imply that f is false-name-proof. Let \((N,P)\in {\mathcal {N}}\times {\mathcal {D}}^{N}\), \(i\in N\), and \((N^{\prime },P^{\prime })\in {\mathcal {N}}\times {\mathcal {D}}^{N^{\prime }}\) be arbitrary, and assume \(N\cap N'=\emptyset\). As \(f_{N}\) and \(f_{N\cup N^{\prime }}\) are quota n and \(n+n^{\prime }\), respectively, \(f_{N}(P)=\cap _{j\in N}b(P_{j})\supseteq \cap _{j\in N\cup N^{\prime }}b(P_{j})=f_{N\cup N^{\prime }}(P, P^{\prime })\). Therefore, \(f_{N\cup N^{\prime }}(P, P^{\prime })=f_N(P){\setminus } B\) for some \(B\subseteq b(P_{i})\). By iteratively applying separability to each object in B and transitivity of \(P_{i}\), we obtain that \(f_N(P)\;R_{i}\;f_{N\cup N^{\prime }}(P, P^{\prime })\) and so f is strongly false-name-proof. Therefore f is also false-name-proof.
Assume now that, for a given \(x\in {\mathcal {M}}\), \(q_{N\,,\,x}=1\) for all \(N\in {\mathcal {N}}\). We show that f is strongly false-name-proof, which would imply that f is false-name-proof. Let \((N,P)\in {\mathcal {N}}\times {\mathcal {D}}^{N}\), \(i\in N\), and \((N^{\prime },P^{\prime })\in {\mathcal {N}}\times {\mathcal {D}}^{N^{\prime }}\) be arbitrary, and assume \(N\cap N'=\emptyset\). As \(f_{N}\) and \(f_{N\cup N^{\prime }}\) are both quota one, \(b(P_{i})\subseteq f_{N}(P)=\cup _{j\in N}b(P_{j})\subseteq \cup _{j\in N\cup N^{\prime }}b(P_{j})=f_{N\cup N^{\prime }}(P, P^{\prime })\). Therefore, \(f_{N\cup N^{\prime }}(P, P^{\prime })=f_N(P)\sqcup W\) for some \(W\subseteq w(P_{i})\), where \(\sqcup\) stands for the disjoint union. By iteratively applying separability to each object in W and transitivity of \(P_{i}\), we obtain that \(f_N(P)\,R_{i}\,f_{N\cup N^{\prime }}(P, P^{\prime })\) and so f is strongly false-name-proof. Therefore, f is also false-name-proof. \(\square\)
3.3 Proof of Theorem 1 and two corollaries
Proof of Theorem 1
\((\Leftarrow )\) Let f a voting by quota such that, for each \(x\in {\mathcal {M}}\), either \(q_{N\,,\,x}=1\) for all \(N\in {\mathcal {N}}\) or \(q_{N,\,x}=n\) for all \(N\in {\mathcal {N}}\). By Proposition 2, f is strategy-proof and onto and, by Proposition 5, f is false-name-proof.
\((\Rightarrow )\) Let f be a false-name-proof, strategy-proof and onto voting rule. Then, by Proposition 4, f is voting by quota \(q=(q_{N,\,x})_{N\in {\mathcal {N}},\,x\in {\mathcal {M}}}\) where, for each \(x\in {\mathcal {M}}\), either \(q_{N,\,x}=1\) for all \(N\in {\mathcal {N}}\) or \(q_{N,\,x}=n\) for all \(N\in {\mathcal {N}}\). \(\square\)
Since strong false-name-proofness implies false-name proofness, we obtain, as a consequence of the proof of Proposition 4, that the statement in Theorem 1 still holds under this stronger notion.
Corollary 1
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\). Then, a voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is strong false-name-proof, strategy-proof, and onto if and only f is a voting by quota such that, for each \(x\in {\mathcal {M}}\), either \(q_{N\,,\,x}=1\) for all \(N\in {\mathcal {N}}\) or \(q_{N,\,x}=n\) for all \(N\in {\mathcal {N}}\).
Finally, asking for neutrality means that all objects need to have the same quota.
Definition 11
Let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be a voting by quota \(q=(q_{N,\,x})_{N\in {\mathcal {N}},\,x\in {\mathcal {M}}}\). We say that f is voting by quota one if, for each \(x\in {\mathcal {M}}\), \(q_{N\,,\,x}=1\) for every \(N\in {\mathcal {N}}\). We say that f is voting by full quota if, for each \(x\in {\mathcal {M}}\), \(q_{N\,,\,x}=n\) for every \(N\in {\mathcal {N}}\).
These two voting by quota are very extreme, and each of them can be seen as the dual of the other. Voting by quota one gives to each voter i the power of imposing x (i.e., i is decisive for x), while voting by full quota gives to each voter i the power to veto x, or imposing that x is not selected (i.e., i is decisive for not x).
Corollary 2
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\). Then, a voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is strategy-proof, false-name-proof, onto and neutral if and only if f is either voting by quota one or voting by full quota.
3.4 Additional results
In this subsection, we present additional results. We first show that if objects only need one vote or a unanimous vote to be chosen, then the rule must verify participation. Hence, participation follows from false-name-proofness, strategy-proofness, and ontoness.
Proposition 6
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\) and assume the voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is false-name-proof, strategy-proof, and onto. Then, f satisfies participation.
Proof
Let f be a voting rule that satisfies false-name-proofness, strategy-proofness, and ontoness. Then, by Theorem 1, f is a voting by quota such that, for each \(x\in {\mathcal {M}}\), either \(q_{N,\,x}=1\) for all \(N\in {\mathcal {N}}\) or \(q_{N,\,x}=n\) for all \(N\in {\mathcal {N}}\). Let \(Q_1\) be the subset of objects that have quota 1 and \(Q_n\) be the subset of objects that have quota n. Let \((N,P)\in {\mathcal {N}}\times {\mathcal {D}}^{N}\) be such that \(n\ge 2\) and let \(i\in N\) be arbitrary. Since each object has either quota 1 or quota n, we have that \(f_N(P)=[\bigcup _{j\in N}(b(P_{j})\cap Q_1)]\cup [\bigcap _{j\in N}(b(P_{j})\cap Q_n)]\). Accordingly, we also have \(f_{N\backslash \{i\}}(P_{-i})=[\bigcup _{j\in {N\backslash \{i\}}}(b(P_{j})\cap Q_1)]\cup [\bigcap _{j\in {N\backslash \{i\}}}(b(P_{j})\cap Q_n)]\). Therefore, \(f_N(P)= [(f_{N\backslash \{i\}}(P_{-i})\cup (b(P_{i}))\cap Q_1]\cup [(f_{N\backslash \{i\}}(P_{-i})\cap b(P_{i}))\cap Q_n]\), which means that \(f_{N\backslash \{i\}}(P_{-i})=(f_N(P)\setminus B)\sqcup W\) for some \(B\subseteq b(P_{i})\) and for some \(W\subseteq w(P_{i})\). By iteratively applying separability to each object in B and W, and transitivity of \(P_{i}\), we obtain that \(f_N(P)\;R_{i}\;f_{N\setminus \{i\}}(P_{-i})\) and so f satisfies participation. \(\square\)
For the case of a unique object, which corresponds to the general setting where there are only two alternatives (identified as \(\{x\}\) and \(\emptyset\)), participation implies strategy-proofness.8
Proposition 7
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\). Let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be a voting rule and assume \({\mathcal {M}}=\{x\}\). If f satisfies participation, then f is strategy-proof.
Proof
Assume f satisfies participation and, to obtain a contradiction, suppose f is not strategy-proof. Let \(N\in {\mathcal {N}}\), \(P\in {\mathcal {D}}^N\), \(i\in N\) and \(P'_i\in {\mathcal {D}}\) be such that \(P'_i\ne P_i\) andSince \({\mathcal {M}}=\{x\}\), \({\mathcal {D}}\) contains only two preferences and so either \(\{x\}\,P_i\,\emptyset\) or \(\emptyset \,P_i\,\{x\}\). Suppose that the first hold. Then,Observe that with only one object, the chosen alternative is either \(f_N(P)=\{x\}\) or \(f_N(P)=\emptyset\). In the former case, it is clear that \(f_N(P_i,P_{-i})\,R_i\,f_N(P'_i,P_{-i})\), which contradicts (1). Therefore, we must have that \(f_N(P)=\emptyset\) and, according to (1) and \(\{x\}\,P_i\,\emptyset\),holds. By participation, \(f_N(P)\,R_i\,f_{N\setminus \{i\}}(P_{-i})\), and so by (3), \(f_{N\setminus \{i\}}(P_{-i})=\emptyset\). Applying now participation to agent i with preference \(P'_i\), \(f_N(P'_i,P_{-i})\,R'_{i}\,f_{N\setminus \{i\}}(P_{-i})\) holds as well. But then, by (3), we have \(\{x\}\,R'_i\,\emptyset\), a contradiction with (2). The proof is analogous for the case when \(\emptyset \,P_i\,\{x\}\). \(\square\)
$$\begin{aligned} f_N(P'_i,P_{-i})\;P_i\;f_N(P_i,P_{-i}). \end{aligned}$$
(1)
$$\begin{aligned} \emptyset \,P'_i\,\{x\}. \end{aligned}$$
(2)
$$\begin{aligned} f_N(P'_i,P_{-i})=\{x\}\,P_i\,\emptyset =f_N(P_i,P_{-i}) \end{aligned}$$
(3)
It is easy to see that if there are two or more objects, participation does not imply strategy-proofness: the Borda count, combined with a tie-breaking that selects one among the potentially many subsets of winners, is an example of a voting rule that satisfies participation and it is not strategy-proof.
We now show that in any setting (and, in particular, in any domain of preferences) strong false-name-proofness, anonymity, and participation imply strategy-proofness.9 Let A be any set of social alternatives, let \({\mathcal {U}}\) be any set of complete and transitive preferences over A, and adapt the properties of a rule \(f_N:{\mathcal {U}}^N\rightarrow A\) for N as previously defined for our setting. Denote by \(R_i\) a generic (and possibly weak) preference of voter i over A in \({\mathcal {U}}\) and let \(R=(R_i)_{i\in N}\in {\mathcal {U}}^N\) be a profile.
Proposition 8
Let \({\mathcal {U}}\) be any domain of preferences over A and let \(f=\{f_{N}:{\mathcal {U}}^{N}\rightarrow A\}_{N\in {\mathcal {N}}}\) be a strongly false-name-proof voting rule that satisfies anonymity and participation. Then, f is strategy-proof.
Proof
Fix \(N\in {\mathcal {N}}\), \(R\in {\mathcal {U}}^N\), \(i\in N\), and let \(R'_i\in {\mathcal {U}}\) be arbitrary. Consider any \(j\notin N\) and set \(R_j=R'_i\). Then,Hence, f is strategy-proof. \(\square\)
$$\begin{aligned} \begin{array}{llll} f_N(R_i,R_{-i}) &{} R_i &{} f_{N\cup \{j\}}(R, R_j) &{} \qquad \text {by strong false-name-proofness} \\ &{} = &{} f_{N\cup \{j\}}((R_{-i},R_j), R_i) &{} \qquad \text {by anonymity} \\ &{} R_i &{} f_{(N\cup \{j\})\setminus \{i\}}(R_{-i},R_j) &{} \qquad \text {by participation} \\ &{} = &{} f_{(N\setminus \{i\})\cup \{j\}}(R_{-i},R_j) &{} \qquad \text {by anonymity} \\ &{} = &{} f_{(N\setminus \{i\})\cup \{i\}}(R_{-i},R_j) &{} \qquad \text {by anonymity} \\ &{} = &{} f_{N}(R_{-i},R'_i) &{} \qquad \text {since} R_j=R'_i. \end{array} \end{aligned}$$
Corollary 3
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\). Then, a voting rule \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) is strong false-name proof, onto, anonymous and verifies participation if and only f is voting by quota such that, for each \(x\in {\mathcal {M}}\), either \(q_{N\,,\,x}=1\) for all \(N\in {\mathcal {N}}\) or \(q_{N\,,\,x}=n\) for all \(N\in {\mathcal {N}}\).10
Example 1 below shows that the statement of Proposition 8 does not hold if strong false-name-proofness is replaced by false-name-proofness, even if the domain of the voting rule is restricted to be the set of separable preferences.
Example 1
For \(P_i\in {\mathcal {S}}\) denote by \(s(P_i)\) the most-preferred singleton set from the set of good objects or the empty set if there is none. Let \(f^s=\{f^s_{N}:{\mathcal {S}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be the voting rule where, for each \(N\in {\mathcal {N}}\), \(f^s_N: {\mathcal {S}}^N \rightarrow 2^{\mathcal {M}}\) is defined by setting, for each \(P\in {\mathcal {S}}^N\), \(f^s_N(P)=\cup _{i\in N}s(P_i)\). It is easy to check that \(f^s\) is false-name-proof and verifies participation. The following example for \(N=\{1,2\}\) and \({\mathcal {M}}=\{x,y\}\) shows that \(f^s\) is neither strategy-proof nor strongly false-name-proof. Consider the separable profile \((P_1,P_2,P'_1)\in {\mathcal {S}}^{N\cup \{3\}}\), where
\(\{x,y\}\;P_1\;\{x\}\;P_1\;\{y\}\;P_1\;\emptyset\), \(\{x\}\;P_2\;\emptyset \;P_2\;\{x,y\}\;P_2\;\{y\}\) and \(\{x,y\}\;P'_1\;\{y\}\;P'_1\;\{x\}\;P'_1\;\emptyset\). Then, by definition of \(f_N^s\), \(f^s_N(P'_1,P_2)=\{x,y\}\;P_1\;\{x\}=f^s_N(P_1,P_2)\), which means that \(f^s_N\) is not strategy-proof, so neither is \(f^s\). Moreover, \(f^s_{\{1,2,3\}}(P_1, P_2,P'_1)=\{x,y\}\;P_1\;\{x\}=f^s_{\{1,2\}}(P_1,P_2)\), which means that \(f^s\) is not strongly false-name-proof.
3.5 Independence of the axioms of the main result
We conclude by showing that the axioms in Theorem 1 are independent. For each of the axioms in the statement of Theorem 1, we exhibit an example of a voting rule, different from the voting by quota characterized in Theorem 1, that satisfies all axioms but one.
Let \({\mathcal {D}}\) be a domain such that \({\mathcal {A}}\subseteq {\mathcal {D}}\subseteq {\mathcal {S}}\) and let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be a voting rule.
-
All but false-name-proofness: Fix \(m\in {\mathbb {Z}}_+\) with \(m\ge 2\). For each \(N\in {\mathcal {N}}\), let \(f_N\) be voting by quota n if \(n\le m\) and quota \(n-1\) if \(n>m\), and let \(f=\{f_{N}:{\mathcal {D}}^{N}\rightarrow 2^{{\mathcal {M}}}\}_{N\in {\mathcal {N}}}\) be the voting rule defined accordingly. By Proposition 2, f is strategy-proof and onto. To see that f is not false-name-proof, consider the case where \(m=3\), \(N=\{1,2,3\}\), and the profile \(P=(P_1,P_2,P_3,P_4)\in {\mathcal {D}}^{N\cup \{4\}}\) with \(b(P_i)=\{x\}\) for \(i=1,2,4\), \(P_1=P_4\), and \(b(P_3)=\emptyset\). Then, since \(f_{N\cup \{4\}}(P_1,P_2,P_3, P_4)=\{x\}\;P_1\;f_N(P_1,P_2,P_3)=\emptyset\), f is not false-name-proof.
-
All but Ontoness: For each \((N,P)\in {\mathcal {N}}\times {\mathcal {D}}^N\), define \(f_N(P)={\mathcal {M}}\). Then, f is trivially false-name-proof and strategy-proof but it is not onto.
4 Final remark
Our characterization shows that the notion of false-name-proofness, together with strategy-proofness, is indeed very strong, even for the particular setting where the set of alternatives is the family of all subsets of a given set of objects and voters have separable preferences over all subsets of objects: Only voting rules that require extreme forms of unanimity can accommodate the stringent incentive requirements of no misrepresentation by either submitting non-own preferences or by submitting several times the own preferences under other voters’ identities. The two incentive requirements allow only for voting rules that are not appealing and reasonable, especially in the context of social choice problems with a large number of voters, where unanimity is very unlikely to ever occur. Furthermore, observe that our result can not be seen as a direct extension of Conitzer (2008)’s result for at least two reasons. First, in our setting, the set of alternatives has a very special structure that suggests the natural restricted domain of separable preferences, which admits, by Barberà et al. (1991), a rich and appealing class of strategy-proof and onto voting rules. Since smaller domains may admit larger strategy-proof, false-name-proof, and onto voting rules, it is not obvious whether or not the domain of separable preferences does admit interesting onto voting rules. However, our result says that this is not the case; but this is a new result, not a consequence of Conitzer (2008)’s result. Second, Conitzer (2008)’s result uses, in addition to anonymity (which is embedded in the definition of a voting rule), neutrality and anonymity-proofness (which implies strategy-proofness, strong false-name-proofness and participation), while our characterization result uses strategy-proofness, false-name-proofness and ontoness (which together imply anonymity).
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.