{'fraction_non_alphanumeric': 0.04428690336098275, 'fraction_numerical': 0.005912574265951035, 'mean_word_length': 3.99383689264727, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On societies choosing social outcomes, and their memberships: strategy-proofness

We consider a society whose members have to choose not only an outcome from a given set of outcomes but also the subset of agents that will remain members of the society. We assume that each agent is indifferent between any two alternatives (pairs of final societies and outcomes) provided that the agent does not belong to any of the two final societies, regardless of the chosen outcome. Under this preference domain restriction we characterize the class of all strategy-proof, unanimous and outsider independent rules as the family of all serial dictator rules.

of the two final societies, regardless of the chosen outcome. Under this preference domain restriction we characterize the class of all strategy-proof, unanimous and outsider independent rules as the family of all serial dictator rules.

Introduction
A classical social choice problem is the following. A society formed by a set of agents has to choose an outcome from a given set of outcomes. Since agents may have different preferences over outcomes, and it is desirable that the chosen outcome be perceived as a compromise among their potentially different preferences, they have to be asked about them. A social choice function (a rule) collects individual preferences and selects, in a systematic and known way, an outcome taking into account the profile of revealed preferences.
This classical approach assumes that the composition of the society is fixed and, in particular, independent of the chosen outcome. There are situations for which this assumption may not be appropriate. For instance, in the case of an excludable and costly public good, agents' preferences may depend on the level of the public good and on the size of the set of agents consuming (and contributing to finance) it. Also, when membership is voluntary in a double sense: no agent can be forced to belong to the final society and any agent can be part of it, if the agent whishes to be. A prototypical example of this class of problems is a political party, whose membership may depend on the positions the party takes on issues like the death penalty, abortion or the possibility of allowing a region of a country to become independent. Or when no agent can be forced to belong to the final society but to be a member requires some kind of approval of the current members. For example, a department whose members decide upon its new members but then a professor, already a member of the department, may start looking for a position elsewhere if he considers that the recruitment of the department has not been satisfactory to his standards; and this in turn might trigger further exits. Or finally, when no stability property is required since agents can simultaneously be forced to remaining and to be excluded from the final society. For example, extremely hierarchical societies like traditional families, religious orders or criminal organizations. 1 To be able to deal with such situations the classical social choice model has to be modified. Agents' preferences have to be extended to order pairs formed by the final society and the chosen outcome.
There is a large literature that has already considered explicitly the dependence of the final society on its choices in specific settings, in terms of two issues: the voting methods under which members choose the outcome, and the timing under which members reconsider their membership. See for instance Roberts (1999), Demange and Wooders (2005), and Berga et al. (2006) for problems related to the club model; Barberà et al. (1991), Barberà et al. (2001), and Berga et al. (2004Berga et al. ( , 2007 for a society choosing a subset of new members; and Jackson and Nicolò (2004) for a provision of excludable public goods when agents care also about the number of other consumers. In the last section of the paper, we comment with more detail some of this literature.
In this paper we look at the general setting without being specific about the two issues, and by not requiring a priori any stability property on the final society. We do that by considering that the set of alternatives are all pairs formed by a subset of the original society (an element in 2 N , the subset of the set of agents N that will remain in the society) and an outcome in the set X . Then, we assume that agents' preferences are defined over the set of alternatives 2 N × X and satisfy two requirements. First, each agent has strict preferences between any two alternatives, provided he belongs to at least one of the two corresponding societies. Second, each agent is indifferent between any two alternatives, provided he is not a member of any of the two corresponding societies; namely, agents that do not belong to the final society do not care about neither its composition nor the chosen outcome. 2 We consider rules that operate on this restricted domain of preference profiles by selecting, for each profile, an alternative (a final society and an outcome); that is, direct revelation mechanisms. Note that the alternative chosen by a rule at a preference profile may be the consequence of the application of a potentially complex mechanism, where agents' behavior are driven by (and linked to) their preferences over the set of alternatives. 3 We abstract from this, by focusing on direct revelation mechanisms. An agent that understands the effect of his revealed preference on the chosen alternative faces the strategic problem of selecting it. Depending on the rule under consideration, the agent may realize that the solution to this problem is ambiguous because it may depend on the agent's expectations that he has about the revealed preferences of the others, and in turn he may also realize that to formulate hypothesis about those revealed preferences require hypothesis about the others' expectations, and so on. Strategyproof rules make all these considerations unnecessary since truthtelling is a weakly dominant strategy of the direct revelation mechanism at each profile; namely, each agent's decision problem is independent of the revealed preferences by the others, and truth-telling is an optimal decision. In addition to strategy-proofness, we will also consider two weak versions of efficiency and non-bossiness. A rule is unanimous if it always selects an alternative belonging to the set of common best alternatives, whenever this set is nonempty. A rule is outsider independent if it is invariant with respect to the change of preferences of an agent who is not a member of the two final societies.
Observe that the (natural) domain restriction under consideration requires that each agent i ∈ N is indifferent among a large subset of alternatives, all those for which i does not belong to their corresponding final societies; namely, i is indifferent among all alternatives in the subset 2 S −i × X , where 2 S −i is the family of all subsets of N that do not contain i. Hence, the set of individual preferences over which we want the rule to operate is far from being the universal domain of preferences over the set of alternatives. Thus, the Gibbard-Satterthwaite theorem (see Gibbard 1973;Satterthwaite 1975) does not apply and the goal of identifying all strategy-proof rules (or a tractable subclass) remains meaningful and interesting. We want to emphasize that the reason why our model is not a particular case of the classical social choice model, where one can directly apply the Gibbard-Satterthwaite theorem, is the specific domain restriction we are interested in. It follows from the particular indifferences admitted over the set 2 N × X which are natural for settings where agents, to enjoy the effects of the chosen outcome, have to remain members of the final society and, at the same time, non final members do not care about the specific chosen outcome. Of course, without this kind of indifferences, the domain of preferences would be the universal domain and the Gibbard-Satterthwaite theorem would apply, precipitating dictatorship.
Our result, Theorem 1, characterizes the class of all strategy-proof, unanimous and outsider independent rules as the family of all serial dictator rules. A serial dictator rule, relative to an ordering of the agents, gives to the first agent the power to select his best alternative, and only if this agent has many indifferent alternatives at the top of his preference, the second agent in the order has the power to select his best alternative among those declared as being at the top and indifferent by the first agent, and proceeds similarly following the ordering of the agents. A serial dictator rule moves away from just dictatorship by using the loophole left by the potential indifferences, present in the domain, and it does so by allocating the power among agents to break the indifferences sequentially. Often, this can be done in a strategy-proof way and satisfying at the same time other desirable properties like weak notions of efficiency (unanimity), non arbitrariness (non-bossiness or order independence), or neutrality, consistency, and so on. Serial dictator rules have been characterized as the family of strategy-proof rules (satisfying in addition some other properties) in many different settings. See, for instance, Satterthwaite and Sonnenschein (1981), Svensson (1999), Papai (2001) and Bade (2015).
In a companion note (Bergantiños 2016) we consider the same setting but assume that the preference profile is common knowledge (and hence, the strategic revelation of agents' preferences is not an issue) and focus on the properties of internal stability and consistency, which guarantee that the chosen alternative is indeed the final one in a double sense. Internal stability says that nobody can force an agent to remain in the society if the agent does not want to do so. Consistency says that if the rule would be applied again to the final society it would choose the same alternative, so there is no need to do so. We exhibit the difficulties of finding rules satisfying the two properties; however, we show that approval voting, adapted to our setting, not only satisfies internal stability and consistency but it also satisfies efficiency and neutrality.
The paper is organized as follows. In Sect. 2 we describe the model. Section 3 contains the definitions of the basic properties of rules that we will be interested in. In Sect. 4 we state, as Theorem 1, the characterization of the class of all strategy-proof, unanimous and outsider independent rules as the family of all serial dictator rules. Section 5 contains the proof of Theorem 1. Section 6 concludes with several final remarks.

Preliminaries
Let N = {1, . . . , n} be the set of agents, with n ≥ 2, and let X be the finite set of possible outcomes. We are interested in situations where some agents may not be part of the final society, perhaps as the consequence of the chosen outcome. To model such situations, let A = 2 N × X be the set of alternatives and assume that each i ∈ N has preferences over A. 4 We will often use the notation a for a generic (S, x) ∈ A; i.e., a ≡ (S, x), a ≡ (S , x ), and so on. Let R i denote agent i's (weak) preference over A, where for any pair a, a ∈ A, a R i a means that i considers a to be at least as good as a . Let P i and I i denote the strict and indifference relations over A induced by R i , respectively; namely, for any pair a, a ∈ A, a P i a if and only if a R i a and ¬a R i a, and a I i a if and only if a R i a and a R i a. We assume that each i does not care about all alternatives at which he does not belong to their corresponding final societies and i is not indifferent between any pair of alternatives at which he belongs to at least one of the two corresponding final societies. Namely, we assume that R i satisfies the following two properties: for all S, T ∈ 2 N and x, y ∈ X, The fact that agents' preferences satisfy (P.1) is the reason why our model cannot mechanically be embedded into the classical model and a specific analysis is required. We see property (P.1) as being a natural assumption for our setting, and it is a critical requirement for our results to hold. Let R i be the set of i's preferences satisfying (P.1) and (P.2), and let R = × i∈N R i be the set of (preference) profiles.
We denote the subset of alternatives with the property that i is not a member of the corresponding final society by [∅] y) for all x, y ∈ X and [∅] i can be seen as the indifference class generated by the empty society. Observe that [∅] i may be at the top of i's preferences. With an abuse of notation we often treat, when listing a preference ordering, the indifference class [∅] i as if it were an alternative; for instance, given To clarify the model, we relate it with two of the examples used in the introduction. The set of initial members of the political party corresponds to the set of agents, the set of outcomes to the set of choices (X could be written as {0, 1} 3 where for instance, x = (0, 1, 0) would correspond to the choices of not supporting the death penalty, admitting abortion, and standing against the independence of the region) and the set S, if the chosen alternative is (S, x), corresponds to the set of final members of the party that want to stay after it supports outcome x. Similarly, all professors in the department correspond to the agents, the set of outcomes X to all subsets of hired candidates (again, an outcome x ∈ X could be identified with x = (x 1 , . . . , x K ) ∈ {0, 1} K , where K is the number of candidates and x k = 1 if and only if candidate k is hired) and the set S, if the chosen alternative is (S, x), corresponds to the set of professors who remain in the department after x has been selected.
Given A ⊆ A and R i , the choice of i in A at R i is the set of best alternatives in A according to R i ; namely, Since the set 2 N × X is finite, the choice set is well-defined and non-empty.
We define three different sets that we will use later on, all related to R i . The top of R i , denoted by τ (R i ) , is the set of all best alternatives according to R i ; namely, is the set of alternatives that are at least as bad as a according to R i ; namely, The upper contour set of R i at a, denoted by U (a, R i ) , is the set of alternatives that are at least as good as a according to R i ; namely, To be explicit about the two components of the alternative chosen by f at R, we will often write f Notice that we allow rules that choose outcomes ( f X (R)) and agents ( f N (R)) simultaneously but also rules that first choose outcomes (or agents) and later agents (or outcomes).

Basic properties of rules
We present three properties that a rule f : R → A may satisfy, and that we will use in our characterization result. The first one imposes a minimal efficiency requirement at each profile.
A rule is unanimous if it selects an alternative in the intersection of all tops, whenever this intersection is nonempty.

Unanimity
The next two properties impose conditions by comparing the alternatives chosen by the rule at two different profiles. A rule is strategy-proof if it is always in the best interest of the agents to reveal their preferences truthfully; namely, truth-telling is a weakly dominant strategy in the direct revelation game induced by the rule.

Strategy-proofness
Outsider independence requires that any modification of the preferences of an agent who was not a member of the society and remain nonmember once she changes her preferences, does not modify the alternative chosen.

Outsider independence
The notion of outsider independence was used in the context of public goods with exclusion by Deb and Razzolini (1999), under the name of non-bossiness of excluded individuals, and by Jackson and Nicolò (2004). It constitutes a weakening of non-bossiness, a property introduced by Satterthwaite and Sonnenschein (1981). Different variants of non-bossiness have been intensively used in the literature. Often, to eliminate arbitrary (and hence, difficult to describe) rules in axiomatic characterizations where strategy-proofness plays a salient role. Thomson (2016) contains a systematic analysis of non-bossiness by giving alternative definitions and interpretations of it, and by relating them to a large family of allocation problems. Outsider independence requires that the rule does not change only after a change of preferences of an agent that is not a member of the two final societies, for which he is indifferent to. We think that this is a natural requirement in our setting; otherwise, by changing his preferences the agent could lead the rule to select different alternatives, inducing welfare changes to the other agents but not to himself. 5

Characterization result
In this section we state the result of the paper characterizing the class of all strategyproof, unanimous and outsider independent rules. 6 This class coincides with the family of all serial dictator rules. To define a serial dictator rule we need some preliminaries. Let π : N → {1, . . . , n} be an ordering (one-to-one mapping) of the set of agents. Given i ∈ N , π(i) is the position in the order assigned to i after applying π to N . The set of all orderings π : N → {1, . . . , n} will be denoted by . For π ∈ and 1 ≤ k ≤ n, we write π k to denote the agent π −1 (k); i.e., the kth agent in the ordering π .
A serial dictator rule induced by π ∈ and x ∈ X , denoted by f π,x , proceeds (in up to n steps) as follows. Fix a profile R ∈ R and look for any alternative (S 1 , x 1 ) in the best indifference class of agent π 1 , the first agent in the ordering induced by π. If π 1 ∈ S 1 , set f π,x (R) = (S 1 , x 1 ). Otherwise, look for any alternative (S 2 , x 2 ) in the best indifference class of agent π 2 , the second agent in the ordering induced by π , only among those classes satisfying the property that π 1 / ∈ S 2 , If π 2 ∈ S 2 , set f π,x (R) = (S 2 , x 2 ). Otherwise, proceed similarly until the nth step, if reached, by looking for any alternative (S n , x n ) in the best indifference class of agent π n , the last in the ordering induced by π, only among those classes satisfying the property that for Otherwise, and since no agent wants to stay in the society whatever element of X is selected, set f π,x (R) = (∅, x) . So, x plays the role of the residual outcome only when no agent wants to stay in the society under any circumstance.
We now define a serial dictator rule formally. Fix π ∈ and x ∈ X , and let R ∈ R be a profile. Define f π,x (R) recursively, as follows.
Step 1 Let A 1 = A. Consider two cases: Example 1 below illustrates this procedure.
Example 1 Let N = {1, 2} and X = {a, b, c} be respectively the set of agents and the set of outcomes, and consider the ordering π , where π 1 = 1 and π 2 = 2, and x = a. We apply the serial dictator rule f π,a to the following four preference profiles, where we give the list of the alternatives in decreasing order from the top and we only order the alternatives needed to compute f π,a at the four profiles.
We are now ready to state Theorem 1, the characterization of the class of all strategyproof, unanimous and outsider independent rules as the family of all serial dictator rules. Section 5 contains the proof of Theorem 1 and three examples of rules indicating the independence of the three properties used in the characterization.
Theorem 1 Assume |X | ≥ 3. A rule f : R → A is strategy-proof, unanimous and outsider independent if and only if f is a serial dictator rule for some ordering π ∈ and alternative x ∈ X.

Proof of Theorem 1
We start by presenting an additional notion, two properties that a rule may satisfy and a sketch of the proof that follows. Given f : R → A, the option set of i ∈ N at , is the set of alternatives that may be chosen by f when the other agents declare the subprofile R −i ; namely, Notice that the option set of i at R −i does not depend on R i . A rule is efficient if it always selects a Pareto optimal allocation.

Efficiency
For each R ∈ R there is no a ∈ A with the property that a R i f (R) for all i ∈ N and a P j f (R) for some j ∈ N .
Monotonicity requires that the chosen alternative at a profile is still selected at a new profile if the alternative improves in the ordering of an agent.

Monotonicity
Since the set of indifferent alternatives for an agent coincides in all of his preferences, monotonicity could be reformulated in an equivalent way by stating that for The proof that, for any π and x, the serial dictator rule f π,x is strategy-proof, unanimous and outsider independent is easy. The main idea of the proof of the other implication is as follows. We first show that any strategy-proof, unanimous and outsider independent rule is efficient and monotonic; moreover, at every profile R, the rule selects the alternative that is simultaneously the best alternative on the option set of each agent i at R −i . These three facts will be useful later on. The main step of the proof is to construct from f , and for every subset of agents N * ⊆ N , a rule g on the set of strict preferences over the set of outcomes X only, which depends on N * . Since |X | ≥ 3 (here is when this assumption plays a crucial role) and g is onto (because f is unanimous), by the Gibbard-Satterthwaite theorem, g is dictatorial; denote by d(N * ) its dictator. The remainder of proof consists of two last steps (the structure of the options sets plays an important role here). First, a preliminary extension in which we show that f has to be also dictatorial on a subdomain of profiles (over A) related with the universal domain of preferences over X (which depends on N * ) under which d(N * ) is the dictator of g. Second, we obtain the series of dictators by applying the above result sequentially to N * = N , and setting π 1 = d(N ), to N * = N \{π 1 }, and setting π 2 = d(N \{π 1 }), and so on. Finally, the default outcome x, needed to define a serial dictator rule, is obtained by looking at the outcome chosen by f (together with the empty society) at any profile R for which τ ( We proceed formally by presenting some lemmata that will be used in the proof.
Lemma 1 Let f : R → A be a strategy-proof, unanimous and outsider independent rule. Then, the following hold.
(3) For all R ∈ R and i ∈ N , Proof Assume f : R → A is strategy-proof, unanimous and outsider independent. We prove the three statements. ( . Three cases are possible: (2) Suppose f is not efficient. Namely, there exist R ∈ R and a ∈ A such that a R i f (R) for all i ∈ N and a P j f (R) for some j ∈ N . Let R ∈ R be such that for each k ∈ N , τ (R k ) = {a ∈ A | a I k a} and orders the rest of alternatives as R k does. Consider the profile (R 1 , R −1 ) ∈ R and suppose that Repeating this argument sequentially for agents k = 2, . . . , n we obtain that f (R ) = f (R). However, by unanimity, can not be dominated by a, implying that f is efficient.
(3) Let R ∈ R and i ∈ N be arbitrary and consider a = (S, Since by definition f (R) ∈ o i (R −i ), we must have that a R i f (R). If f (R) = a, then the equality in the statement follows (either as singleton sets or as the indifference class [∅] i ). Assume f (R) = a. Two cases are possible: . Then, f (R) = [∅] i = a, a contradiction. Hence, i ∈ f N (R) and a P i f (R) . Now, we obtain a contradiction with strategyproofness of f by proceeding in a similar way as we did in the previous case.
For the next steps in the proof, it will be useful to consider the set F of all complete, transitive and antisymmetric binary relations over X. Namely, F can be seen as the set of all strict preferences over X. Now, for each N * ⊂ N , each i ∈ N and each strict preference i over X we associate a preference over 2 N × X (namely, an element of R i ), denoted by R N * , i , by selecting one among those satisfying the following features.
• If i ∈ N * , consider several cases: y) for all x, y ∈ X.
• If i / ∈ N * , then (∅, x) P N * , i (S, y) for all S ⊂ N such that i ∈ S and for all x, y ∈ X. 7 Note that for each N * , each i ∈ N and each i over X there are many preferences in R i satisfying the above conditions. We just select one of them, and denote it by R N * , i . Fix N * ⊆ N and define a rule g : F N * → X as follows. For each subprofile ( i ) i∈N * ∈ F N * of preferences over X set Lemma 2 Below says that if f is strategy-proof, unanimous and outsider independent, then g is dictatorial; namely, there exists j ∈ N * such that for all Lemma 2 Let f : R → A be strategy-proof, unanimous and outsider independent. Then, for all N * ⊆ N , the rule g is dictatorial.
Proof Fix N * ⊆ N . Since f is unanimous, |X | ≥ 3 and g is defined on the universal domain of strict preference profiles over X, the Gibbard-Satterthwaite theorem says that if g is onto (for each x ∈ X there exists ( i ) i∈N * such that g(( i ) i∈N * ) = x) and strategy-proof, then g is dictatorial.
We first prove that g is onto. Let x and ( i ) i∈N * ∈ F N * be such that for each We now prove that g is strategy-proof. Suppose otherwise. Then, there exist ( i ) i∈N * , j ∈ N * and j such that (1) . By definition of R N * , i we know that for each i ∈ N * , each i ∈ F, each x ∈ X, and each S ⊂ N with S = N * , we have that (N * , x) P N * , i (S, x). Besides, for each i ∈ N \N * , each i ∈ F, each x ∈ X, and each S ⊂ N with i ∈ S, we have that (N * , x) P N * , i (S, x) . Since f is efficient, By definition of R N * , j and (1) which contradicts that f is strategy -proof.
Fix R i ∈ R i and a ∈ A. Denote by R a,i the preference over A obtained from R i by just placing a, and all its indifferent alternatives (if any), at the bottom of the ordering. Formally, R a,i is defined so that a R a,i a, for all a ∈ A and, for all  a , a ∈ A\ {a}, a R a,i a if and only if a R Notice that a I i a does not hold since i ∈ S and a = (S, x). Symmetrically, consider any R j ∈ R j , where Again, a I j a does not hold since j ∈ S and a = (S, x). By monotonicity, Proof We only prove (i) (the proof of (ii) is similar and we omit it). Suppose otherwise and assume We now distinguish between two cases (observe that a I j a does not hold because j ∈ S and a = (S, x)).
Case 1 a P j a. Then, Thus, j manipulates f at (R a i , R j , R −i, j ) via R j , which is a contradiction. Case 2 a P j a. By definition of R j , a P j a. Then, Thus, j manipulates f at (R a i , R j , R −i, j ) via R j , which is also a contradiction.
We now define two new preferences,R i andR j , wherẽ Proof We only prove (i) (the proof of (ii) is similar and we omit it). Since We now proceed with the proof of Lemma 3 by considering four different cases: and by monotonicity, (2) Assume a P i a.
and by monotonicity, and by monotonicity, (4) Assume a P j a.
and by monotonicity, Thus, in each of the four possible cases a P i a and a P j a , a P i a and a P j a, a P i a and a P j a , and a P i a and a P j a, we have that f (R i ,R j , R −i, j ) = a and f (R i ,R j , R −i, j ) = a , which is a contradiction with a = a .
Given N * ⊆ N , by Lemma 2, the rule g (induced by f ) is dictatorial on its domain F N * . Let d (N * ) ∈ N * be the dictator. Using the identification described just before Lemma 2, for every i ∈ N and any (N * , i ), choose a particular R N * , i ∈ R i . Consider the subdomain Proof Assume the hypothesis of Lemma 4 holds. Suppose first that R ∈ R N * , and let Claim A: f (R) = (N * , x).
Continuing with this procedure, at the end we would reach agent π n = d(N \{π 1 , ..., π n−1 }) and we would need to consider two subcases separately depending on whether |C(A π n , R π n )| is equal to one or strictly larger, where If |C(A π n , R π n )| = 1 then C(A π n , R π n ) = ({π n } , x n ) . Thus, f π,x (R) = ({π n } , x n ) . Using arguments similar to those used above we can show that f (R) = ({π n } , x n ) .
The three properties used in the characterization of Theorem 1 are independent. Consider the approval voting rule f AV,ρ defined as follows. Each i ∈ N votes for the subset A i = {a ∈ A | a R i [∅] i }. For each a ∈ A, compute the number of votes received by a; namely, |{i ∈ N : a ∈ A i }| . The outcome with more votes is selected. The tie-breaking rule ρ is applied whenever several alternatives obtain the largest number of votes, where ρ : It is easy to see that, for any tie-breaking rule ρ, f AV,ρ is unanimous and outsider independent but it is not strategy-proof.
Any constant rule satisfies strategy-proofness and outsider independence but it is not unanimous.
Let x, y ∈ X with x = y. Define It is easy to see that f is strategy-proof and unanimous but it does not satisfy outsider independence.

Final remarks
Before finishing the paper several remarks are in order. First, the equivalence between the class of strategy-proof, unanimous and outsider independent rules and the set of serial dictator rules is a negative result. Serial dictator rules are not appealing for many reasons. In particular, in our setting, they do no satisfy any stability property: some agents may be forced to belong to the society and others may be excluded, all against their own will. Although our general model was able to encompass problems where the composition of the final society could be endogenous (by being a consequence of the chosen outcome) and stable, our result says that if we insist on requiring strategy-proofness only serial dictators remain.
Second, this negative result holds because our domain of preferences under which we want the non-trivial and strategy-proof rule to operate is, although restrictive, still very large. And hence, one may ask whether there are interesting and meaningful subdomains admitting non-trivial and strategy-proof rules. That is, what kind of possibilities can arise from imposing further preference restrictions than just condition (P.2). Some papers have followed this line of inquiry by considering stronger domain restrictions. For instance, for the case of an excludable public good (in a linearly ordered set X of outcomes) when agents also care about the size of the set of its users, Jackson and Nicolò (2004) identifies classes of strategy-proof and efficient rules on the domain of single-peaked preferences on the level of the public good and alternative specifications of how agents order different sets of users. Roughly, those classes (which depend on the particular preference specification and may require that the rule be in addition outsider independent) consists of selecting the size of the set of users independently of the preference profile and then, choose the level of the public good according to a generalized median voter scheme. Although some of the results in Jackson and Nicolò (2004) are also negative, they identify restricted domains that admit more appealing rules; for instance, when preferences on the size of the set of users come from cost-sharing considerations. Berga et al. (2004) studies a particular instance of our model. It consists of a society choosing a subset of new members, from a finite set of candidates. They consider explicitly the possibility that initial members of the society (founders) may want to exit, if they do not like the resulting new society. They show that, if founders have separable (or additive) preferences, the unique strategy-proof, stable and onto rule is the one where candidates are chosen unanimously and no founder exits. In this case, the restricted domain of preferences admits (non-dictatorial) strategy-proof rules that are in addition anonymous and stable. But there are many other restricted domain possibilities, among which two appear as promising. They are based on betweenness and separability requirements, as follows. First, assume agent i has (x, S) as top-ranked and i ∈ S. If i ∈ T, then (x, T ) should be ranked higher than (x, T \{i}); that is, (x, T ) lies somehow between (x, S) and (x, T \{i}), and since (x, S) is the top-ranked alternative, agent i should prefer the alternative that is closer to the top. Second, agent i has a strict order over X and a strict order over N \{i} and then, the ranking of alternatives of the form (x, S), where i ∈ S, must be consistent to these two strict orders (and so, the preference would violate (P.1) as well). Most likely then, separability of the rule (as in Jackson and Nicolò (2004)) would be a necessary condition of strategy-proofness. 8 Third, the class of rules that satisfy only strategy-proofness and unanimity but fail outsider independence is extremely large, even inside the class of rules based on serial dictators (which guarantee that strategy-proofness and unanimity are also satisfied). Its richness comes from the fact that, without outsider independence, the sequence of dictators may not be given from the very beginning, and independently of the preference profile R ∈ R. Instead, at each step, the dictator may be selected as a function of the entire subprofile of the set of agents, say S, that have already declared that τ (R i ) = [∅] i , for i ∈ S. Then, the choice of the agent selected as dictator in the current step could depend, in so many and arbitrary ways, on any conceivable characteristic of the subprofile R S , that its full and systematic description seems unworkable. We think that outsider independence structures in a simple way this arbitrariness by requiring that the sequence of dictators is not profile dependent. In addition, together with strategy-proofness and unanimity, insider independence imply group strategy-proofness, because serial dictators are trivially group strategy-proof; however, it is easy to see that the rules that are not outsider independent just described above, are not group strategy-proof because a change in a preference of an agent may produce a strictly improvement of the welfare of another agent, without affecting the welfare of the agent that has changed the preference, and hence inducing a group manipulation of the rule.
Fourth, our proof of Theorem 1 requires explicitly that |X | ≥ 3. In particular, in the proof of Lemma 2, we show that the rule g, defined from f on the universal domain of preferences over X, is onto and dictatorial. This follows from the Gibbard-Satterthwaite theorem and the unanimity and strategy-proofness of f , which can be applied because |X | ≥ 3. And this is a key step in the full proof. Of course, the case |X | ≤ 2 is interesting since |A| may still be large, whenever the set of agents is large; in particular, if |X | = 1 the problem resembles the "Who is a J?" problem, where a set of N agents has to decide who, among them, fulfills a specific binary characteristic, although we are not aware of any strategic analysis of this problem based explicitly on agents' preferences over families of subsets of agents. But we have not attempted to perform this analysis; it remains open for further research.