Sidartha Gordon
email: sidartha.gordon@sciencespo.fr.

Hans Bandelt

Biung-Ghi Ju

Jim Schummer

Unanimity in Attribute-Based Preference Domains

Keywords: JEL classi…cation codes: D63, D71, H41 Solidarity, Population-monotonicity, Replacement-domination, Unanimity, Strategy-proofness, Attribute-based Domains, Generalized Single-Peaked Domains

, and with Pareto-e¢ ciency if and only if the attribute space is a tree. Each of these combinations characterizes unanimity.

Introduction

Unanimity decision rules are used in many political institutions, such as the United Nations Security Council, the rati…cation procedure for treaties in the European Union, and criminal law juries. Surprisingly few justi…cations for such rules are available [START_REF] Berga | Stability and Voting by Committees with Exit[END_REF][START_REF] Ju | Unanimity and Resource Monotonicity[END_REF]. We provide several characterizations of unanimity in a general public choice problem. Decision rules prescribe an outcome as a function of the preferences submitted by individuals. The set of admissible preferences is constrained by a set of objective attributes possessed by the alternatives: we consider the class of attribute-based domains, introduced by Nehring and Puppe (2007a, 2007b[START_REF] Ju | Unanimity and Resource Monotonicity[END_REF][START_REF] Nehring | Abstract Arrowian Aggregation[END_REF]. Solidarity conditions are the key element in all of our characterizations.

Solidarity is a principle of justice with respect to changes in circumstances. It says that all agents not responsible for these changes should be a¤ected in the same direction.

Possible changes include the arrival or departure of individuals, as well as changes in their preferences. "Replacement-domination" is introduced by [START_REF] Moulin | The Pure Compensation Problem: Egalitarianism Versus Laissez-Fairism[END_REF] in the context of quasi-linear binary public decision. It applies to a model with a …xed population of agents and requires that the replacement of the preferences of one agent causes the other agents to either all weakly win or all weakly lose. "Population-monotonicity"is introduced by Thomson (1983aThomson ( , 1983b) ) in the context of bargaining. It applies to a model with a variable population of agents and requires that when one agent joins the population, the other agents whose preferences are kept …xed either all weakly win or they all weakly lose. 1In the context of public choice, solidarity conditions are …rst studied in location models. [START_REF] Thomson | The Replacement Principle in Public Good Economies with Single-Peaked Preferences[END_REF]) considers a continuous line over which agents have single-peaked preferences. For any preference pro…le, a target rule selects the Pareto-e¢ cient alternative that is closest to some exogenously …xed alternative on the line. [START_REF] Thomson | The Replacement Principle in Public Good Economies with Single-Peaked Preferences[END_REF] shows that the target rules are the only Pareto-e¢ cient rules that satisfy replacement-domination. [START_REF] Ching | Population-Monotonicity in Public Good Economies with Single-Peaked Preferences[END_REF] show that these rules are also the only Pareto-e¢ cient rules that satisfy population-monotonicity. [START_REF] Ching | Population-Monotonicity in Public Good Economies with Single-Peaked Preferences[END_REF], [START_REF] Vohra | The Replacement principle and Tree Structured Preferences[END_REF] and [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] extend these results for single-peaked preferences on a tree network. [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] further shows that the target rules are the only ones that satisfy unanimity (if all agents' preferred alternative is the same, it should be selected), strategy-proofness (reporting true preferences is a weakly dominant strategy for all agents) and either condition of solidarity, on a tree network. Finally [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] extends this second result to Euclidean spaces, when agents'preferences are separable across dimensions and quadratic, and characterizes coordinatewise target rules on this domain. Gordon (2007b) obtains an impossibility result for single-peaked preferences on a circle, except on small discrete domains (less than …ve alternatives) of symmetric preferences. 2 In this paper, we extend the analysis to a larger class of models in which the set of admissible preferences is constrained by a set of objective attributes possessed by the alternatives. This class of domains generalizes discrete versions of all of the locations models listed in the last paragraph. One di¤erence is that these models assume a continuum of alternatives, while we assume a discrete set. This di¤erence is however not fundamental.

The real novelty of our work is that the class of attribute-based domains is larger than the class of domains structured around a location model. For example, the unrestricted domain, the domain of separable preferences over sets of objects (Barberà, Sonnenschein and Zhou 1991) and models of voting under constraints [START_REF] Barberà | Voting under Constraints[END_REF] and 2005) can be viewed as attribute-based domains.

Our starting point, in section 3, is a characterization by Nehring and Puppe (2007b), which mirrors results by Barberà, Massó andNeme (1997, 2005) in the closely related model of voting under constraints These authors show that the rules that satisfy voter-sovereignty (any alternative is selected for some pro…le) and strategy-proofness in any attribute-based domain form a class of "voting by issues" rules which make separate decisions between 2 Solidarity conditions were also studied in the problem of locating multiple public goods by [START_REF] Miyagawa | Mechanisms for Providing a Menu of Public Goods: Population-Monotonicity[END_REF][START_REF] Miyagawa | Locating Two Libraries on a Street: Replacement Principle[END_REF], [START_REF] Ehlers | Multiple Public Goods and Lexicographic Preferences[END_REF][START_REF] Ehlers | Multiple Public Goods, Lexicographic Preferences, and Single-Plateaued Preference Rules[END_REF], and [START_REF] Umezawa | The Replacement Principle for the Provision of Multiple Public Goods on Tree Networks[END_REF] and in the problem of selecting a probabilitic location by [START_REF] Ehlers | Solidarity and Probabilistic Target Rules[END_REF]. These models di¤er from ours in that they include some alternatives which are not considered best by any preference in the domain.

each attribute and its complement.

In section 4, we show that in any attribute-based domain, the rules satisfying votersovereignty, strategy-proofness and solidarity, when they exist, are unanimity rules, in which each of the attributes of some prespeci…ed "target"alternative can only be defeated by an unanimous vote. This result can be viewed as a generalization of a discrete counterpart of the similar characterizations by [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] on trees and Euclidean spaces.

Nehring and Puppe (2007b) have characterized the class of attribute spaces in which unanimity voting by issues rules exist, the "quasi-median" spaces [START_REF] Nehring | Social Aggregation without Veto[END_REF]). It follows that the quasi-median domains are exactly the ones where these three conditions are compatible. We provide examples to illustrate how this class of domains extends the discrete counterparts of the domains studied by [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF].

In section 5, we study the compatibility of Pareto-e¢ ciency and solidarity in attributebased domains. Here, we do not assume strategy-proofness and hence cannot restrict attention to "voting by issues" rules from the outset, but this last condition turns out to be implied by the other two. 3 Unfortunately, our result is negative. "Trees", which are precisely the discrete counterpart of the domains studied by [START_REF] Ching | Population-Monotonicity in Public Good Economies with Single-Peaked Preferences[END_REF], [START_REF] Vohra | The Replacement principle and Tree Structured Preferences[END_REF] and [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] in continuous location models are the only attribute-based domains where the two conditions are compatible. Finally, we provide a characterization on discrete trees, that mirrors the results obtained by these authors in the continuum case.

Our proof di¤ers from theirs, in that we rely on the theory of voting by issues.

The model

In this section, we present the class of attribute-based domains (Nehring and Puppe 2007a,b). Then we present the …xed and variable population models and the conditions we are interested in.

Let A be a nonempty …nite set of alternatives. Let H 2 A be a non-empty family of subsets of A, with typical element H A: The elements of H are called attributes. We can think of each of them as a descriptive characteristic relevant for the choice and de…ned by the set of alternatives that possess it. For example, if the set A is a set of possible constitutions for a nation, the attributes could be "federal", "non-federal", "presidential", "parliamentary" and the attribute "presidential" is de…ned as the subset of constitutions in A that are presidential. Suppose that H satis…es the following three conditions. Nontriviality: for all H 2 H, H 6 = ;: Closedness under negation: for all H 2 H, H c 2 H.

Separation: for all x 6 = y 2 A; there is H 2 H such that x 2 H and y = 2 H. A family H that satis…es these three conditions is called an attribute space. 4 Following Nehring (1999), an attribute space enables us to de…ne a notion of betweenness of alternatives as follows. More generally, an attribute space can be de…ned on a tree, de…ned as a graph (set of undirected edges) on A without cycles. For each x 2 A; the set A n fxg can be uniquely represented as the union of two connected components H + x and H x whose intersection is the singleton fxg : The family H of all sets of the form H +

x and H x for all x 2 A de…ne an attribute space.

Example 2 (The hypercube) Let A = f0; 1g K : An alternative is represented by a sequence a = a 1 ; :::; a K with a k 2 f0; 1g : For all k; let H k 0 := fa : a k = 0g and H k 1 := fa : a k = 1g and consider the family H of all such subsets. The induced hypercube betweenness is given, for all a; b; c 2 A; by b 2 [a; c] :, for all k :

a k = c k ) b k = a k = c k : Geometrically,
p (R i ) 2 A such that for all a 6 = b 2 A; a 2 [p (R i ) ; b] ) a P i b: This means that p (R i ) is
the "single peak" of preference R i , i.e. its most preferred alternative. Moreover if a has more attributes (in an inclusion sense) in common with p (R i ) than b; then preference R i prefers a to b:

Let R be the set of preferences, which are adapted to H: In this paper, we focus on domains of preferences, which are adapted to some attribute space:

The and [START_REF] Schummer | Strategy-proof Location on a Network[END_REF]. The unrestricted domain, the domain of separable and single-peaked domains on product of lines are also special cases.

We consider problems with a …xed population and problems with a variable population.

For each, we de…ne a relevant solidarity condition.

Fixed population. Let N be a …xed nonempty …nite set of agents with generic agent denoted by i: A …xed population problem is de…ned by an attribute space H and a …xed population N:

Each agent i is equipped with a preference R i 2 R: A preference pro…le is a list R N = (R i ) i2N 2 R N : A rule is a mapping f : R N ! A:
We are interested in solutions such that when the preference of one agent changes, the other agents are all a¤ected in the same direction: either they all weakly win or the all weakly lose.

Replacement-domination. For all R N 2 R N ; all i 2 N; all R 0 i 2 R; either for all j 2 N nfig ; f R 0 i ; R N nfig R j f (R N ) ; or for all j 2 N n fig, f (R N ) R j f R 0 i ; R N nfig :
We assume that jN j 3; which is the minimal cardinality for which replacementdomination has bite.

Variable population. Let N be a …nite set of potential agents with generic agent denoted by i: A variable population problem is de…ned by an attribute space H and a set of potential agents N : It consists of the collection of problems with …xed population (H; N ) for all nonempty N N . A preference pro…le is given by a set N and a list R N 2 R N :

A (variable population) rule is a mapping f : [ N R N ! A: For all N N …nite, the restriction of f to R N is denoted by f N :
We are interested in solutions such that when one agent joins the economy and the preferences of the agents already present in the economy are kept …xed, these agents who were present before the change are all a¤ected in the same direction: either they all weakly win or they all weakly lose.

Population-monotonicity. For all N N ; R N 2 R N ; all i 2 N n N; all R 0 i 2 R; either for all j 2 N; f (R 0 i ; R N ) R j f (R N ) ; or for all j 2 N; f (R N ) R j f (R 0 i ; R N ) :
We assume that jN j 3; which is the minimal cardinality for which populationmonotonicity has bite.

In each of these models, we study the compatibility of these conditions with the following additional requirements. A …xed population rule satis…es voter-sovereignty if it is onto, i.e. if every alternative is selected by the rule for some pro…le in its domain. Next, a rule is strategy-proof if revealing their true preferences is a weakly dominant strategy for all agents: for all R N 2 R N , all i 2 N and all

R 0 i 2 R, we have f (R N ) R i f R 0 i ; R N nfig :
Last, a rule satis…es Pareto-e¢ ciency, if at any pro…le, there is no alternative that is weakly preferred by all agents in the economy and strictly preferred by at least one agent to the alternative selected by the choice function: for all R N 2 R N , there exists no a 2 A such that for all i 2 N; a R i f (R N ) and for some j 2 N , a P j f (R N ) : A variable population rule f satis…es either of these three properties if for all N; the restriction f N satis…es it. We are interested in rules that satisfy solidarity and either voter-sovereignty and strategy-proofness, or Pareto-e¢ ciency.

Voting by issues

In this Section, we present a classic result in the literature, on which our results are based.

It characterizes the class of rules that satisfy voter-sovereignty and strategy-proofness as "voting by issues."The results in this section were obtained by Nehring and Puppe (2007b) in the attribute-based framework. Similar results were previously obtained by Barberà, Massó andNeme (1997, 2005) in the related model of voting under constraints.

An issue is de…ned as the pair formed by an attribute and its complement. Under "voting by issues," the agents vote separately on each issue, over the two corresponding competing attributes, using an issue-speci…c voting rule for each of the issues. The alternative that is selected is the one that possesses all of the adopted attributes. Of course, such a procedure is well de…ned only if the issue-speci…c voting rules satisfy certain joint restrictions.

More precisely, consider a …xed population problem (H; N ). A family of winning coalitions is a non-empty family W of subsets of N satisfying [W 2 W and W W 0 ] ) W 0 2 W: For example, for any q 2 (0; 1) ; the quota q family consists of the coalitions W N such that jW j > q jN j : A structure of winning coalitions is a list (W H ) H2H of families of winning coalitions indexed by the attributes of H such that for each W N and each attribute H; we have

W 2 W H , N n W = 2 W H c : (1)
Let W = (W H ) H2H be a structure of winning coalitions. Voting by issues associated with W is the rule f :

R N ! A such that for all R N 2 R N ; a = f (R N ) :, for all H 2 H such that a 2 H we have fi : p (R i ) 2 Hg 2 W H :
In general, the rule f need not be well-de…ned. 6 Nehring and Puppe (2007b) provide the following important characterization.

Proposition 1 (Nehring and Puppe, 2007b) A rule f satis…es voter-sovereignty and strategy-proofness if and only if it is voting by issues and well-de…ned.

Obviously, this result extends to variable population problems in the following way.

Corollary 1 A variable population rule satis…es voter-sovereignty and strategy-proofness if for each nonempty N N ; the rule f N is voting by issues and well-de…ned.

An important feature of voting by issues is that the rules in this class always selects an alternative that lies in the convex hull of the peaks of the agents: for all

R N 2 R N ; f (R N ) 2 Co (fp (R i ) : i 2 N g) :
In particular, for all preference pro…le with exactly two distinct peaks, the choice function selects an alternative that lies between the two peaks: for all R N such that there is

a 6 = b 2 A such that fp (R i )g i2N = fa; bg ; we have f (R N ) 2 [a; b] : 4

Strategy-proofness and Solidarity

In this section, we study the compatibility of voter-sovereignty, strategy-proofness and either solidarity conditions.

In If there is such an alternative, it is necessarily unique and it is precisely Similarly, in a variable population model, a rule f is a variable-population unanimity rule if there exists b a 2 A; such that for all N; the restriction f N is the unanimity rule f b a :

f b a (R N ). The condition f b a (R N ) 2
We now show that unanimity rules are the only rules that satisfy voter-sovereignty, strategy-proofness and the relevant solidarity condition both with a …xed and a variable population.

Proposition 2 (i) A rule f satis…es voter-sovereignty, strategy-proofness and replacementdomination if and only if it is a unanimity rule. (ii) A variable-population rule f satis…es voter-sovereignty, strategy-proofness and population-monotonicity if and only if it is a unanimity rule.

Proof. It is clear that a unanimity rule satis…es the conditions. We prove the converse implications.

(i) From Proposition 1, we know that f is voting by issues and well-de…ned, characterized by a winning coalition structure (W H ) H :

H 2 H; either W H = 2 N n f;g or W H = fN g : Next, let H f := H 2 H : W H = 2 N n f;g : We now show that T H2H f H 6 = ;
. Suppose by contradiction that this set is empty. Then there is H 1 ; :::; H l 2 H f ; where l > 2; such that T l 1 k=1 H k 6 = ; and

T l k=1 H k = ;: Let Let R a ; R b 2 R be such that p (R a ) 2 T l 1 k=1 H k and p (R b ) 2 H l : Let R be the pro…le (R a ; R b ; :::; R b ) where R b is repeated jN j 1 times.
Since all the H k for k = 1; :::; l are in H f ; we have f (R) 2

T l k=1 H k = ;; which is a contradiction. Therefore T H2H f H 6 = ;: Last, we show that this intersection has exactly one element b a: Suppose that a 6 = b 2 It is easy to see that the direct implication is true. If f b a is well-de…ned at some pro…le with peaks located at b and c; it is necessarily a median of b a, b and c: The fact that when b a is a median point, the rule f b a is well-de…ned is less clear. Nehring andPuppe (2005, 2010) provide an abstract proof of this fact. For completeness, we provide here a constructive proof of this result, which we believe is more transparent.

T H2H f H: Let H 2 H such that a 2 H and b = 2 H: If H 2 H f ; then b 2 T H2H f H is contradicted. If instead H = 2 H f ; then by (1), H c 2 H f and a 2 T H2H f H is contradicted. Therefore there is b a 2 A such that b a = T H2H f H: Moreover, for all R N 2 R N ; we have f (R N ) 2 Co (p (R i ) : i 2 N ) and f (R N ) 2 [f (R i ) ; b a]
Proof. First, suppose that the rule f b a is well-de…ned on R N ; with jN j Since this construction is feasible for all R N 2 R N ; the rule f b a is well-de…ned.

An attribute space is called quasi-median [START_REF] Nehring | Social Aggregation without Veto[END_REF] if it contains at least one median alternative and it is called median if all alternatives in A are median. From these de…nitions and Proposition 3, it follows that the attribute-structures that admit a unanimity rule are exactly the quasi-median spaces. From this observation and Proposition 2, we obtain the following characterization.

Corollary 2

The following three statements are equivalent.

(i) The attribute space H admits a rule that satis…es voter-sovereignty, strategy-proofness and replacement-domination.

(ii) The attribute space H admits a variable population rule that satis…es voter-sovereignty, strategy-proofness and population-monotonicity.

(iii) H is quasi-median.

Nehring and Puppe (2005) provide several interesting characterizations of quasi-median spaces. We end this section by two examples of such spaces, whose associated domains are not discrete counterparts of the domains considered by [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF].

Example 4 A subset of at most L out of K public projects, with 1 L < K; has to be selected. An alternative speci…es which of the projects will be carried out. Attributes are the sets of alternatives of the form "yes to project k" and "no to project k" for all k = 1; :::; K:

This attribute space has exactly K + 1 median alternatives. These are all the alternatives of the form"only project k is carried out" for all k = 1; :::; K and "no project is carried out". Consequently, exactly K + 1 rules satisfy the conditions of Proposition 2. In any rule in this class, each of the projects, except perhaps one, require unanimous support for approval. If a project does not require unanimous support for approval, a single vote in its favour su¢ ces to get it approved. In this section, we study the compatibility of Pareto-e¢ ciency and either solidarity conditions. [START_REF] Ching | Population-Monotonicity in Public Good Economies with Single-Peaked Preferences[END_REF], [START_REF] Vohra | The Replacement principle and Tree Structured Preferences[END_REF] and [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] have shown that Pareto-e¢ ciency is compatible with either replacement-domination or populationmonotonicity on domains of single-peaked preferences de…ned on trees. 7 Both the set of alternatives and the preference domain these authors consider are continua. Their discrete counterpart in our setting is the class of domains of single-peaked preferences on discrete trees, such as the ones presented in Example 1.

In the light of the results by [START_REF] Ching | Population-Monotonicity in Public Good Economies with Single-Peaked Preferences[END_REF], [START_REF] Vohra | The Replacement principle and Tree Structured Preferences[END_REF] and [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF], it is natural to ask the following question: Are these properties compatible in other attribute-based preferences domains? Unfortunately, we …nd that the answer to this question is negative: tree structures are the only attribute-based domains on which Pareto-e¢ ciency and solidarity properties are compatible.

To establish this result, we …rst provide an abstract characterization of the attribute spaces that generate domains in the class presented in Example 1. It is well known and easily veri…ed that the attribute spaces H constructed in Example 1 are median and in addition satisfy the following condition.

Condition (T ) :

For all H; H 0 2 H; at least one of the sets

H \ H 0 ; H \ H 0c ; H c \ H 0 ; H c \ H 0c is empty.
Conversely, we establish that these two conditions, the median condition and (T ), characterize tree structures, a result we believe is of independent interest. 8 From any median attribute space H that satis…es (T ) ; one can recover a discrete graph-theoretic tree, that is a graph (a …nite set of vertices and edges) that is connected (any two vertices are connected through some path) and has no cycles.

Proposition 4 Let H be a median attribute space that satis…es (T ). Then the graph on

A = S H2H
H whose edges are the pairs (a; b) such that there exists a unique attribute H a 2 H such that a 2 H a and b 2 H c a is a tree, i.e. it is connected and has no cycles.

Proof. Throughout the proof, let H be a tree attribute space.

Step 1: The graph de…ned in the Proposition is connected. It follows immediately from the previous paragraph that the graph de…ned in the Proposition is connected.

Step 2: Monotonicity of attributes along a path.

Let a and b be arbitrary alternatives. Consider a path a 0 ; :::; a n with a 0 = a and a n = b connecting a and b: For all i; since (a i ; a i+1 ) is an edge, there exists exactly one attribute, let it be denoted H i ; such that a i 2 H i and a i+1 = 2 H i : We will show that for all i; we have

H i i H i : Since (a i 1 ; a i ) form
Thus H i \ H i 1 contains a i 1 ; H i \ H c i 1 contains a i and H c i \ H c i 1 contains a i+1 ; therefore (T ) implies that H i 1 H i : The inclusion is strict because a i 2 H i \ H c i 1 :
Step 3: The graph does not contain any cycles. Suppose by contradiction that there exists a path a 0 ; :::; a n with a n = a 0 . By Step 2, we …nd that H 0 ::: H n H 0 ; a contradiction. We conclude that the graph does not contain any cycles, i.e. it is a tree in a graph theoretic sense.

From now on, a tree attribute space is a median attribute space that satis…es (T ) :

We are now ready to show that Pareto-e¢ ciency and solidarity are only compatible on tree attribute spaces. Note that we do not assume strategy-proofness, thus we cannot restrict attention to voting by issues from the outset, as we did in the previous section. The idea of proof is the following. We associate to any rule satisfying the conditions a R N : Similarly, in the last replacement, agent n cannot strictly bene…t. If this where the case, since all agents 1; :::; n 1 are a¤ected in the same direction, these agents must weakly lose (at least one of them strictly), otherwise f (R 1 ; R 0 2 ; :::; R 0 2 ; R 2 ) is not Pareto-e¢ cient for (R 1 ; R 0 2 ; :::; R 0 2 ; R 2 ) : But this in turns contradicts the Pareto-e¢ ciency of f (R 1 ; R 0 2 ; :::; R 0 2 ) for (R 1 ; R 0 2 ; :::; R 0 2 ) : Therefore agent n weakly loses. Last f (R 1 ; R 0 2 ; :::; R 0 2 ) = g (R 1 ; R 0 2 ) : In summary, we obtain that g (R 1 ; R 2 ) R 2 g (R 1 ; R 0

2 ) ; i.e. g satis…es strategy-proofness. Last, since g satis…es strategy-proofness and voter-sovereignty, it only depends on the agents'peaks. Therefore, the property established in the second paragraph of Step 1 implies that g satis…es anonymity.

Step 2: The rule g is a unanimity rule. Let b a be the unique alternative such that for all (R 1 ; R 2 ) ; g (R 1 ; R 2 ) = med (b a; p (R 1 ) ; p (R 2 )) :

Step 3: The attribute space H satis…es condition (T ) : 9Suppose by contradiction that H violates condition (T ) : If this is the case, then there are alternatives a 1 ; :::; a 4 2 A and attributes H and H 0 ; such that a 1 2 H \ H 0 ; a 2 2 H \ H 0c ; a 3 2 H c \ H 0c ; and a 4 2 H c \ H 0 : Then b a is an element of exactly one of these four sets. Suppose for example that b a 2 H \ H 0 : Consider now a pro…le (R 1 ; R 2 ) such that p (R 1 ) = a 2 and p (R 2 ) = a 4 ; and moreover for all a 2 H \ H 0 ; we have a 3 P 1 a and a 3 P 2 a: Therefore none of the alternatives in H \ H 0 is Pareto-e¢ cient. However, g (R 1 ; R 2 ) = med (b a; p (R 1 ) ; p (R 2 )), which is an element of H \ H 0 , contradicting Pareto-e¢ ciency. Therefore the attribute space H satis…es condition (T ) :

Step 4: The space H is a median space: Suppose, by contradiction that H is not a median space. Then, we know from Nehring and Puppe (2007b, Proposition 4.1) that there is a family of attributes H 1 ; :::; H k ; with k 3; such that T k l=1 H l = ; and for each h 2 f1; :::; kg ; T l6 =h H l 6 = ;:For each h = 1; :::; k; let a j 2 T l6 =h H l : For each pair l; l 0 ; l 6 = l 0 ; the sets H l \ H l 0 ; H c l \ H l 0 and H l \ H c l 0 are non-empty. Therefore, by Step 3, it must be that, for each pair l; l 0 ; l 6 = l 0 ; H c l \ H c l 0 = ;:

Therefore any alternative a 2 A is an element of exactly k 1 sets H l and one set H l 0 :

Without loss of generality, let's suppose that b a 2 H 1 \::

:\H k 1 \H c k : Consider now a pro…le (R 1 ; R 2 ) such that p (R 1 ) = a 1 and p (R 2 ) = a 2 : Then g (R 1 ; R 2 ) = med (b a; p (R 1 ) ; p (R 2 )) ; which is an element of [p (R 1 ) ; p (R 2 )] T k l=3 H l ; of [b a; p (R 1 )] H 2 and of [b a; p (R 2 )] H 1 : Since T k l=1 H l = ;
; this is a contradiction. Therefore H is a median space: Therefore H is a tree attribute space.

(ii) : The proof follows exactly the same steps, therefore we only provide a sketch. Let jN j 3: Let f be a variable-population rule that satis…es Pareto-e¢ ciency and populationmonotonicity. Let g be the restriction of f to R M with M := f1; 2g : Each preference replacement in the proof of (i) is achieved in two steps by …rst withdrawing the agent whose preference is replaced and then adding him back with the new preference. At the end, all agents with labels other than 1 and 2 are removed. The remaining steps are identical to those in (i).

To end this section, we provide the discrete counterparts of the characterizations obtained by [START_REF] Ching | Population-Monotonicity in Public Good Economies with Single-Peaked Preferences[END_REF], [START_REF] Vohra | The Replacement principle and Tree Structured Preferences[END_REF] and [START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] on trees. 10 Our proof di¤ers from theirs, as it relies on the theory of voting by issues and does not require an in…nite set of alternatives.

Proposition 6 Let H be a tree attribute space. (i) Let jN j 3: Let f be a rule. Then f satis…es Pareto-e¢ ciency and replacement-domination if and only if f is a unanimity rule.

(ii) Let jN j 3: Let f be a variable population rule. Then f satis…es Pareto-e¢ ciency and population-monotonicity if and only if f is a unanimity rule.

Proof. It is clear that a unanimity rules satis…es the conditions. We prove the converse implication. Throughout the proof, let H be a tree.

(i) : Let jN j 3: Let f be a rule that satis…es Pareto-e¢ ciency and replacementdomination. Let M := f1; 2g and g : R M ! A; such that for all (R 1 ; R 2 ) 2 R M ; we have g (R 1 ; R 2 ) := f (R 0 N ) ; where R 0 N 2 R N is such that R 0 1 = R 1 and R 0 i = R 2 ; for all [START_REF] Vohra | The Replacement principle and Tree Structured Preferences[END_REF] and [START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] both point out that their characterization on trees is valid even in the subdomain of symmetric preferences. This is not the case in the discrete setting, as shown in the following example. A: Then the rule, which for any preference pro…le maximizes the linear ordering x 0 1 on the set of Pareto-e¢ cient alternatives satis…es the conditions of Proposition 6 and is not the restriction to this domain of any voting by issues rule.

We end this section by discussing the relation between the results by Gordon (2007a) and the ones in this paper. Gordon (2007a) considers a general variable population public choice problem, without assumptions on the preference domain, other than symmetry (all agents have the same set of possible preferences) and that the set of alternatives does not depend on the population. In this very general framework, Gordon (2007a) does not provide a characterization, but establishes that under Pareto-e¢ ciency, both population-monotonicity the one hand, and replacement-domination together with replication-indi¤erence (the decision change that follows the cloning replication of the entire population leaves all agents indi¤erent) have the following strong implications. First, either combination implies strategy-proofness and even the stronger requirement of groupstrategy-proofness (no group of agents can jointly bene…t from misrepresenting the preferences of its members). Second, they imply anonymity (up to Pareto-indi¤erence). Third, they imply that there is a "status-quo alternative"that is always Pareto-dominated by the choice of the rule. These results are obtained under the assumption that the population is variable and that the set N is in…nite. 11 In contrast, we do not assume that such an in…nite variable population is available and focus on a more restricted class of models. Our results con…rm that, in this more speci…c The status quo alternative of a unanimity rule on a tree is its target b a: Moreover, both anonymity and the existence of a status quo alternative are also shown to be implications of the weaker conditions of voter-sovereignty, strategy-proofness and solidarity.

Example 1 (

 1 Let a; b; c 2 A: We say that b is between a and c, denoted by b 2 [a; c] if b possesses all attributes that are common to a and c: For all a; b; c 2 A; b 2 [a; c] :, for all H 2 H, fa; cg H ) b 2 H: Here are some simple examples. It is important to realize that an attribute space could be much more intricate than the ones shown here. Lines and Trees) Suppose that the alternatives can be ordered from left to right by some linear ordering on X: The family H of all sets of the form H x := fa 2 A : a xg or H x := fa 2 A : a xg for all x 2 A de…ne an attribute space. Each attribute is thus of the form "greater than or equal to x"or "lesser than or equal to x": The induced line betweenness is given, for all a; b; c 2 A; by b 2 [a; c] :, [a b c or c b a] :

  line attribute space in Example 1 generates a discrete version of the classic singlepeaked domain on a line studied by[START_REF] Moulin | On Strategy-Proofness and Single-Peakedness[END_REF],[START_REF] Thomson | The Replacement Principle in Public Good Economies with Single-Peaked Preferences[END_REF] and[START_REF] Ching | Population-Monotonicity in Public Good Economies with Single-Peaked Preferences[END_REF]. The tree attribute space in Example 1 generates a discrete version of the domain of single-peaked preferences on a tree studied by[START_REF] Ching | Population-Monotonicity in Public Good Economies with Single-Peaked Preferences[END_REF],[START_REF] Vohra | The Replacement principle and Tree Structured Preferences[END_REF],[START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF][START_REF] Klaus | Target Rules for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF] and[START_REF] Schummer | Strategy-proof Location on a Network[END_REF]. The attribute space in Example 2 generates the separable domain over subsets of objects, introduced by Barberà, Sonnenschein and Zhou (1991). The attribute space in Example 3 generates a discrete version of the domain of single-peaked preferences on a circle studied byGordon (2007a)

  Co (fp (R 1 ) ; :::; p (R n )g) expresses the fact that any attribute that is unanimously supported gets approved. The condition f b a (R N ) 2 [b a; p (R i )] expresses the fact that any attribute possessed by b a and supported by at least one agent gets approved.

First, we show

  that for all H 2 H; either W H = 2 N n f;g or W H = fN g : Suppose by contradiction that this is not the case. Then let H 2 H, W 2 W H and i 2 W; such that W 6 = N and W n fig 6 = ; and W n fig = 2 W H : Let a 2 H and b = 2 H: Let R a 2 R be a preference such that p (R a ) = a and for all x 2 H and all y = 2 H; x P a y: Similarly, let R b 2 R be such that p R b = b and for all x = 2 H and all y 2 H; x P b y: Let R N 2 R N such that for all j 2 W; R j := R a and for all j 2 N n W; R j := R b : Next, let R 0 i := R b : By de…nition of voting by issues, this implies that f (R N ) 2 H but f R 0 i ; R N nfig = 2 H: Therefore the replacement of R i by R 0 i hurts all agents in W n fig and bene…ts all agents in N n W; which contradicts replacement-domination. Thus, for all

N with jN j 2; each W N such that jW j 1 ;

 1 for all i 2 N: Therefore f is a unanimity rule with parameter b a.(ii) First, we show that for each H 2 H; each population N N with jN j 3; each W N such that jW j 2; and each i 2 W; we have W 2 W H;N =) W n fig 2 W H;N nfig : Let H; N; W and i satisfy these conditions and suppose that W 2 W H;N : Let a 2 H and b = 2 H: Let R a 2 R be a preference such that p (R a ) = a and for all x 2 H and all y = 2 H; x P a y: Similarly, let R b 2 R be such that p R b = b and for all x = 2 H and all y 2 H; x P b y: Let R N 2 R N such that for all j 2 W; R j := R a and for all j 2 N n W; R j := R b : By de…nition of voting by issues, since W 2 W H;N ; we have f (R N ) 2 H: Next, consider the pro…le R N nfig ; where agent i has left: By population-monotonicity, we have f R N nfig 2 H: By de…nition of voting by issues, this implies that W n fig 2 W H;N nfig : Second, we show that for each H 2 H; each population N and each i = 2 N; we have W 2 W H;N =) W 2 W H;N [fig : Let H; N; W and i satisfy these conditions and suppose that W 2 W H;N : Let a 2 H and b = 2 H: Let R a 2 R be a preference such that p (R a ) = a and for all x 2 H and all y = 2 H; x P a y: Similarly, let R b 2 R be such that p R b = b and for all x = 2 H and all y 2 H; x P b y: Let R N 2 R N such that for all j 2 W; R j := R a and for all j 2 N n W; R j := R b : By de…nition of voting by issues, we have f (R N ) 2 H: Next, consider the pro…le (R 0 i ; R N ) ; where agent i is added, with the preference R 0 i := R b : By population-monotonicity, we have f (R 0 i ; R N ) 2 H: By de…nition of voting by issues, this implies that W 2 W H;N [fig : The implication proved in last paragraph, together with the implication for all H; N; W; [W 2 W N;H and W W 0 ] ) W 0 2 W N;H implies that for all H; either W H;N = 2 N n f;g for all N or W H;N = fN g for all N: Last, we de…ne the family H f := H 2 H : W H = 2 N n f;g ; which as we saw does not depend on N; and b a = T H2H f H exactly like in (i) : Thus for all N; the rule f N is the unanimity rule with parameter b a: For all (a; b; c) 2 A; if the set [a; b] \ [b; c] \ [a; c] is not empty, it necessarily contains a single element called the median of (a; b; c) ; denoted by med (a; b; c) : An alternative a 2 A is called a median alternative for H if and only if for all b; c 2 A the triple (a; b; c) has a median: Nehring and Puppe (2005, 2010) obtained the following result. Proposition 3 (Nehring and Puppe 2005, 2010) For all b a 2 A; and all N such that jN j 2; the unanimity rule f b a is well-de…ned on R N ; if and only if b a is a median alternative for H.

2 : 2 :

 22 Let b; c be arbitrary alternatives in A: Consider a pro…le R N such that all agents have their peaks in fb; cg and not all agents have the same peak: Then by de…nition, f b a (R N ) is an element of [b a; b] \ [b a; c] \ [b; c] : Therefore this set is not empty. Since this is true for all b; c 2 A; then b a is a median alternative. Conversely, suppose that b a is a median alternative. Let jN j Without loss of generality, let 1; :::; n be the agents in N: De…ne the sequence x 1 := p 1 and for all i 2 f2; :::; ng ; let x i := med (b a; x i 1 ; p i ) : Since b a is a median point, the sequence is well-de…ned. By construction, x n 2 Co (fx n 1 ; p n g) Co (fx n 2 ; p n 1 ; p n g) ::: Co (fx 1 ; :::; p k g) : Again by construction, we know that x n 2 [b a; p n ]; x n 2 [b a; x n 1 ] [b a; p n 1 ] ; ... and x n 2 [b a; x n 1 ] ::: [b a; x 2 ] [b a; p 1 ] : Therefore x n is an element in Co (fx 1 ; :::; p k g) that is in the interval [b a; p i ] for all i = 1; :::; n: Therefore f b a (R N ) is well-de…ned and f b a (R N ) = x n :

Example 5

 5 Let A := fa; b; c; d; eg : The attributes are the sets fa; b; cg ; fb; c; dg ; fc; d; eg ; fa; eg ; fa; bg and fd; eg : This attribute space has two median points b and d: Therefore the two rules that satisfy the conditions of Proposition 2 are the unanimity rules with parameter either b or d: 5 Pareto-e¢ ciency and Solidarity

For any two alternatives

  a; b let a b if [a; b] = fa; bg : We will show that (a; b) is an edge if and only if a b: Let a; b be alternatives such that a b: Let H and H 0 be any two attributes such that a 2 H \ H 0 and b 2 H c \ H 0c : We need to prove that H = H 0 : By contradiction, suppose that this is not the case. For example H 0 H: Then there exists c 2 H 0 n H: Then by condition (T ) it must be that either H H 0 : Moreover b and c are in H c and b is in H 0c : Then the median of a; b and c is an element of [a; b] ; but it is neither a 8 Buneman (1971) and Bandelt and Dress (1986) provide related constructions, without assuming amedian space. Their construction, however, allows introducing "latent alternatives", i.e. additional alternatives outisde of the set A in order to construct a tree consistent with an attribute structure that satis…es (T ). Our result shows that when the space is median, latent alternatives are not needed. In addition, our construction relies on elementary arguments.nor b; since it is an element of H c (ruling out a) and it is also an element of H (ruling out b). This contradicts that [a; b] = fa; bg : Therefore necessarily H = H 0 ; which proves that (a; b) is an edge.

Proposition 5 3 :

 53 Let H be an attribute space. (i) Let jN j 3: Let f be a rule. If f satis…es Pareto-e¢ ciency and replacement-domination, then H is a tree attribute space. (ii) Let jN j Let f be a variable-population rule. If f satis…es Pareto-e¢ ciency and populationmonotonicity, then H is a tree attribute space.

Example 6

 6 Let A := f0; 1; xg ; with x 2: Consider the domain of preferences represented by the utility functions u 0 (a) = jaj ; u 1 (a) = ja 1j and u x (a) = ja xj for all a 2

1 1

 1 In a similarly general framework,[START_REF] Bu | Unfolding the mystery of false-name-proofness[END_REF] establishes a general equivalence between false-nameproofness, which requires non-manipulability via the creation of …ctitious identities, and strategy-proofness, anonymity and population-monotonicity. It would be interesting to study the implications of false-nameproofness in the class of attribute-based preference domains. context, the above implications remain true as long as the …xed population has at least three agents in the …xed population model, or as long as there are at least three potential agents in the variable population model, and without the assumption of replication-indi¤erence.

  b is between a and c if and only if b is contained in the subcube spanned by

	a and c:
	Example 3 (Cycles) Let A = fa 1 ; :::; a k g and consider the k-cycle on A; i.e. the graph
	with the edges (a l ; a l+1 ) with the convention a l+k = a l : If k is odd, de…ne H as the family n o
	of sets of the form n	o	a l ; :::; a l 1+ k 1 2	: If k is even, de…ne H as the family of sets of the
	form	2 a l ; :::; a l 1+ k		:
	A subset S A is convex if it is the intersection of attributes. By convention \ ; = A,
	hence A is also convex. For all B	A, the convex hull of B; denoted by Co (B) is the
	smallest convex set that contains it. For all a; b 2 A; the segment [a; b] is the convex hull
	of fa; bg. The elements of [a; b] are exactly the alternatives that are between a and b:
	A binary relation R i is called a preference if it is re ‡exive, transitive and complete,
	i.e. a weak ordering.

5

Let P i and I i be the associated strict preference and indi¤erence relation. Let H be an attribute space. A preference R i is adapted to H if there exists

  the last section, we introduced voting by issues. A rule in this class is a unanimity rule if there exists a "target" b a 2 A whose attributes can only be defeated by unanimity, i.e. such that W H = 2 N n f;g for all H such that b a 2 H and W H = fN g for all H such that b a = 2 H: Such a rule is denoted by f b a : As Nehring and Puppe (2005) note, it follows directly from this de…nition that for any R N 2 R N ; f b a (R N ) is well-de…ned if and only if there exists an alternative that is both in Co (fp (R 1 ) ; :::; p (R n )g) and in [b a; p (R i )] for all i 2 N:

  an edge, and a i 1 and a i are already separated by H i 1 and H c i 1 ; then they are not separated by H i and H c i : Since a i 2 H i ; then a i 1 2 H i : Similarly, since (a i ; a i+1 ) form an edge, and a i and a i+1 are already separated by H i and H c i ; then they are not separated by H i 1 and H c i 1 : Since a i 2 H c i 1 ; then a i+1 2 H c i 1 :

For surveys on these two conditions, see[START_REF] Thomson | Population-Monotonic Allocation Rules[END_REF][START_REF] Thomson | Welfare-domination under Preference-replacement: a Survey and Open Questions[END_REF].

In a companion paper,Gordon (2007a) studies Pareto-e¢ ciency and solidarity in a general public choice problem and establishes several of these conditions' general implications. We defer the discussion of the relation between the two papers to the end of section 5.

Note that the set A can be recovered from an attribute space H since A = S H2H H:

Nehring and Puppe work with linear orderings (2007a,b). Here we consider weak orderings. Either domain is rich enough for our results to hold.

Nehring and Puppe (2007b) provide a necessary and su¢ cient condition on the structure of winning coalitions under which voting by issues is well-de…ned: the "intersection property." Barberà, Massó and Neme (1997) provide a di¤erent necessary and su¢ cient condition, also labelled "intersection property" under which separable voting under constraints is well-de…ned.

Other properties are studied on these domains by[START_REF] Demange | Single-peaked Orders on a Tree[END_REF] and[START_REF] Danilov | The Structure of Non-manipulable Social Choice Rules on a Tree[END_REF] and[START_REF] Schummer | Strategy-proof Location on a Network[END_REF].

Steps 3 and 4 in the proof can be deduced from the main result in Nehring and Puppe (2007a), more precisely from Claim (a) in their Theorem. For the sake of completeness, we provide a direct proof that exploits the special structure of this model to avoid the complexities of their analysis.

0 The proofs in[START_REF] Vohra | The Replacement principle and Tree Structured Preferences[END_REF] and[START_REF] Klaus | Status Quo Solutions for Public Choice Economies on Tree Networks and in Euclidean Spaces[END_REF]

2001) require in…nitely many alternatives. This assumption is implicitly used, for example, in Vohra's Lemma 3.

two agents rule, which turns out to be a Pareto-e¢ cient unanimity rule (Steps 1 and 2).

Then in Steps 3 and 4, we show that this implies that H is a tree.

Proof. Throughout the proof, let H be an attribute space.

(i) : Let jN j 3: Let f be a rule that satis…es Pareto-e¢ ciency and replacementdomination.

Let M := f1; 2g and g : R M ! A; such that for all (R 1 ; R 2 ) 2 R M ; we have

Step 1: The rule g satis…es anonymity, strategy-proofness and Pareto-e¢ ciency.

First, it is obvious that the rule g satis…es Pareto-e¢ ciency.

Next, we prove that for all (R 1 ; R 2 ) ; we have g (R 1 ; R 2 ) I i g (R 2 ; R 1 ) for all i 2 f1; 2g.

for all i 2:: Consider the transformation of R 0 N = (R 1 ; R 2 ; :::; R 2 ) in R 00 N = (R 2 ; R 1 ; :::; R 1 ) where for each agent i 2 f3; :::; ng ; the preference R 0 i = R 2 is replaced by the preference R 00 i = R 1 in decreasing index order. Then the preference R 0 1 = R 1 is replaced by the preference R 00 1 = R 2 and last the preference R 0 2 = R 2 is replaced by the preference R 00 2 = R 1 : At each step in the transformation, the Pareto-set for the preference subpro…le of the agents whose preferences are kept …xed is the same at the Pareto-set for the entire pro…les (of any pro…le along the path). By Pareto-e¢ ciency and replacement-domination, this implies that the preferences R 1 and R 2 remain indi¤erent between the images by f along the path. Therefore g (R 1 ; R 2 ) = f (R 1 ; R 2 ; :::; R 2 ) I i f (R 2 ; R 1 ; :::; R 1 ) = g (R 2 ; R 1 ) ; for all i 2 f1; 2g.

Last, we prove that g satis…es strategy-proofness. By anonymity, it su¢ ces to prove

R 2 ; :::; R 2 ) : Consider the sequence of transformations where the preference R i = R 2 is replace by the preference R 0 i = R 0 2 ; for each i 2 f2; :::; ng in increasing order. When replacing the preference of an agent of indices in f3; :::; n 1g ; the image by f remains unchanged by the same argument as in the last paragraph. In the …rst replacement, agent 2 cannot strictly bene…t, since this would imply agent 3 strictly bene…ts, which would imply that f R 0 2 ; R N nf2g Pareto-dominates f (R 1 ; R 2 ; :::; R 2 ) for (R 1 ; R 2 ) ; i.e. for i 2: From Step 1 in the proof of Proposition 5, we know that g satis…es Pareto-e¢ ciency and strategy-proofness and that it is a unanimity rule with status quo b a: Let f b a be the unanimity rule with status quo b a on R N . We will prove here that f = f b a :

Once this is done, we obtain the pro…le R 0 N such that R 0 i = R i and R 0 l = R j for all l 6 = i: If i = 1; the transformation ends here. If not, then 1 6 = i; so that R 0 1 = R j : In this case, let R 00 1 := R i and R 00 i := R j : Replace …rst the preference R 0 1 = R j by R 00 1 = R i and then the preference

The transformation ends and we obtain the pro…le R 00 N such that R 00 1 = R i and R 00 2 = ::: = R 00 n = R j : At each elementary step in this transformation, there are always at least two agents whose preferences are kept …xed and are R i and R j : We will show that the image by f remains b along the path. Along the path, the set of preferences represented in the pro…le decreases or remains constant at each step. By Pareto-e¢ ciency and replacement-domination, this implies that the change weakly bene…ts preferences R i and R j . Since this is true at each step, and by transitivity, it must be that f (R 00

: By de…nition of a ; we know that a 2 [a ; p (R j )] \ [a ; p (R i )] : By de…nition of i and j, we know that a 2

is true for all R N 2 R N ; we conclude that f is the unanimity rule with status quo b a:

(ii) The proof follows exactly the same steps, therefore we only provide a sketch. In this case the rule g is the restriction of the variable-population rule f to R f1;2g : Each preference replacement in the proof of (i) is achieved in two steps by …rst withdrawing the agent whose preference is replaced and then adding him back with the new preference.

Last all agents with labels other than 1 and 2 are removed.