Ali I Ozkes
email: ali.ozkes@wu.ac.at

M Remzi Sanver

M Remzi Sanver
email: remzi.sanver@lamsade.dauphine.fr

Walter Bossert

Denis Cornaz

Fatih Demirkale

Lars Ehlers

Ayça Ebru Giritligil

Je↵rey Hatley

Sean Horan

Hervé Moulin

Jean Lainé

Clemens Puppe

Yves Sprumont

William Zwicker

Anonymous, neutral, and resolute social choice revisited ⇤

Keywords: anonymity, e ciency, neutrality, resoluteness JEL Codes: D71, D72, D82

published or not. The documents may come

Introduction

Equal treatment of individuals as well as of alternatives are among the core principles of democratic decision-making. Equal treatment of individuals is usually ensured by the anonymity condition, which requires the social choice to be invariant under renaming individuals. The typical condition to ensure equal treatment of alternatives, on the other hand, is neutrality, which requires the social choice to change in compliance with renaming of alternatives.

The logical incompatibility between anonymity and neutrality while ensuring an untied outcome is among the most well-known results in social choice theory. [START_REF] Moulin | Implementing e cient, anonymous and neutral social choice functions[END_REF][START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF] characterizes the sizes of social choice problems that admit anonymous and neutral social choice rules (SCRs) that are resolute, i.e., that choose a unique alternative at any profile. More precisely, a social choice problem with n individuals and m alternatives admits an anonymous, neutral, and resolute SCR if and only if m cannot be written as the sum of some divisors of n that exceed 1 [START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF]. When (Pareto) e ciency is imposed together with anonymity and neutrality, this requirement is strengthened to "n not having a prime divisor less than or equal to m" [START_REF] Moulin | Implementing e cient, anonymous and neutral social choice functions[END_REF]. 1 dering to a very significant aspect of equal treatment of alternatives. This new condition that we call consequential neutrality requires that all alternatives are chosen at the same number of preference profiles.

For example, with an odd number of individuals, fixing two alternatives x and y and two individuals i and j, one can define the resolute SCR that picks the best alternative of individual i when a majority of individuals prefer x to y and otherwise, picks the best alternative of individual j. This SCR presents a procedure that depends on the names of the alternatives, hence failing neutrality. On the other hand, being consequentially neutral, it ensures that every alternative is chosen at the same number of preference profiles, thus putting forward an ex-ante fairness property that is more outcome-oriented compared to the classical neutrality approach that entails a more procedure-oriented equal treatment of alternatives.

Recent research on anonymous and neutral social choice mostly focus on rules that assign orderings (instead of alternatives) to preference profiles. [START_REF] Bubboloni | Anonymous and neutral majority rules[END_REF] and [START_REF] Dogan | Anonymous and neutral social choice: Existence results on resoluteness[END_REF] characterize the sizes of social choice problems for which anonymous and neutral rules that are resolute, i.e., that assign strict social welfare orderings to profiles, exist. Building on the algebraic approach in [START_REF] Bubboloni | Anonymous and neutral majority rules[END_REF], [START_REF] Bubboloni | Symmetric majority rules[END_REF] propose a weakening of neutrality by assuming that alternatives are divided into sub-classes and requiring equal treatment of alternatives within each sub-class, while alternatives in di↵erent sub-classes may be di↵erently treated. They provide necessary and su cient conditions for the existence of (reversal) symmetric majority rules that satisfy this weakening of neutrality together with a weaker version of anonymity. 2 Bubboloni and Gori (2016) adopt the aforementioned versions of anonymity and neutrality together with e ciency and characterize when rules that assign orderings to profiles admit a resolute refinement that preserves these properties. Their characterization identifies the necessary and su cient arithmetical conditions on the sizes of sub-committees and sub-classes. [START_REF] King | Beyond neutrality: Extended di↵erence of votes rules[END_REF], on the other hand, dispense with neutrality altogether and identify a characterization of rules that satisfy anonymity, monotonicity, and cancellation, in the case of two alternatives.

We start by analyzing the structure of irresoluteness imposed by anonymity, neutrality, and e ciency, a previously overlooked matter. We generalize the characterization of [START_REF] Moulin | Implementing e cient, anonymous and neutral social choice functions[END_REF] by completely describing the sizes of unavoidable ties under these conditions (Theorem 2). This generalization paves the way to identifying a method to refine SCRs that are "more irresolute than necessary," while anonymity, e ciency, and neutrality are preserved (Theorem 3).

We then turn to our analysis of consequential neutrality for resolute SCRs.

We start with counting the number of resolute SCRs that are neutral and those that are consequentially neutral (CN) as a function of the size of the social choice problem (Theorem 4). An analytical comparison of these two numbers seems beyond reach, so we take a computational approach where we compute the numbers of resolute SCRs in each class for a small set of values of the size of the social choice problem. These numerical exercises that we report on show strong tendencies in the comparison of the numbers of CN and neutral SCRs, hence we conjecture that the class of resolute SCRs that are CN is considerably larger than those that are neutral. Thereafter, we discuss the possibility of refining anonymous, e cient, and neutral SCRs by replacing neutrality with consequential neutrality and deliver a possibility result under certain conditions (Theorem 5). We also identify some cases where these conditions are not satisfied but there exist anonymous, CN, and resolute SCRs (Theorem 6). These positive results do not hold over all conceivable social choice problems: we point to instances where anonymity, consequential neutrality, e ciency, and resoluteness turn out to be incompatible (Theorem 7). These are instances where the incompatibility prevails even without e ciency. However, even in those cases, anonymous, CN, and resolute SCRs exist. In fact, we are able to identify a large class of social choice problems, namely those where the number of alternatives exceeds the number of individuals, for which anonymity, consequential neutrality, and resoluteness are compatible (Theorem 9).

The paper is organized as follows. Section 2 gives basic notation and notions. Section 3 delivers a generalization of the classical result on incompatibility of anonymity, neutrality, and e ciency with resoluteness and proposes a refinement method towards resoluteness. Section 4 introduces consequential neutrality and presents our more permissive results when it replaces neutrality. Section 5 concludes.

Basic notions and notation

Writing N for the set of natural numbers and picking m, n 2 N {1}, we conceive a social choice problem as a set A of alternatives with #A = m and a set N of individuals with #N = n. We refer to (m, n) as the size of the social choice problem (A, N ). Writing L(X) for the set of linear orders, i.e., complete, asymmetric, and transitive binary relations on a given set X, let

P i 2 L(A) denote the preference of i 2 N . 3 An n tuple of such individual preferences indicates a (preference) profile P N 2 L(A) N . A social choice rule (SCR) is a mapping f : L(A) N ! A, where A = 2 A {?} is the set of non-empty subsets of A.
Given any two sets S and T , we write S ✓ T whenever S is a subset of T and S ⇢ T whenever S is a proper subset of T . We let P N | B denote the restriction of P N 2 L(A) N to those alternatives in B 2 A so that P N | B 2 L(B) N and xP i y () xP i | B y for all x, y 2 B and i 2 N . Given any two SCRs f 1 and f 2 , we say that

f 2 refines f 1 i↵ f 2 (P N ) ✓ f 1 (P N ) 8P N 2 L(A) N and f 2 (P 0 N ) ⇢ f 1 (P 0 N ) for some P 0 N 2 L(A) N . An SCR f is resolute whenever #f (P N ) = 1 8P N 2 L(A) N . For a resolute SCR f , we write f (P N ) = x in place of f (P N ) = {x}.
We now define two equal treatment conditions that are at the core of our analysis. For any non-empty finite set X, a permutation on X is a bijection : X $ X. Let ⌃ X be the set of all permutations on X. We write, by a slight abuse of notation, (P N ) = (P (i) ) i2N for the profile obtained from P N 2 L(A) N by a permutation 2 ⌃ N . An SCR is anonymous i↵ f (P N ) = f ( (P N ))

8P N 2 L(A) N 8 2 ⌃ N . Again, by an abuse of notation, we write (P i ) for the preference obtained from P i 2 L(A) by a permutation 2 ⌃ A on A, i.e., x P i y () (x) (P i ) (y) 8x, y 2 A. and8 2 ⌃

Moreover, we set (P

N ) = ( (P i )) i2N 8P N 2 L(A) N . An SCR is neutral i↵ f ( (P N )) = (f (P N )) 8P N 2 L(A) N , 8x 2 A,
A .
We close the section by noting that an SCR f is e cient i↵ given any P N 2 L(A) N and any x 2 f (P N ), @y 2 A\{x} with y P i x 8i 2 N .

3 Anonymous, neutral, and e cient social choice Given k, l 2 N, we write k | l whenever k divides l, i.e., l k 2 N, and kl otherwise. Let D(n) = {k 2 N : k | n} be the set of divisors of n 2 N and [START_REF] Moulin | Implementing e cient, anonymous and neutral social choice functions[END_REF] to be a necessary and su cient condition for the size of a social choice problem to admit an anonymous, neutral, e cient, and resolute SCR.

D ⇤ (n) = {k is a prime : k | n} [ {1} be the set consisting of prime divisors of n as well as 1. Thus, D ⇤ (n) ✓ D(n) for all n 2 N. For any m, n 2 N, the set of divisors of n that do not exceed m is denoted D m (n) = {d 2 D(n) : d  m} and similarly D ⇤ m (n) = {d 2 D ⇤ (n) : d  m}. Again, D ⇤ m (n) ✓ D m (n) for all m, n 2 N. Imposing D ⇤ m (n) = {1} is shown by
Theorem 1 [START_REF] Moulin | Implementing e cient, anonymous and neutral social choice functions[END_REF]). A social choice problem (A, N ) with size (m, n) admits an anonymous, e cient, neutral, and resolute SCR f if and only if

D ⇤ m (n) = {1}. The condition D ⇤ m (n) = {1} in Theorem 1 can be replaced by D m (n) = {1}. 4 We will refer to D m (n) = {1} as Condition µ(m, n). 5
Theorem 1 gives a complete picture of the sizes of social choice problems where irresoluteness is inevitable but is silent about the structure of irresolute-

4 Having already noted D ⇤ m (n) ✓ Dm(n), we now remark that D ⇤ m (n) = {1} =) Dm(n) = {1} for all m, n 2 N.
To prove this by contradiction, we first let k 2 Dm(n)\{1}. Thus, we have k 2 D(n) and k  m. Due to the fundamental theorem of arithmetic, k has a prime divisor k ⇤ , which divides n as well, hence 5 This condition is equivalent to asking the greatest common divisor of m! and n to be 1, as mentioned by [START_REF] Dogan | Anonymous and neutral social choice: Existence results on resoluteness[END_REF], who reconsider the problem through a group theoretic approach. Interestingly, as [START_REF] Dogan | Anonymous and neutral social choice: Existence results on resoluteness[END_REF] as well as [START_REF] Bubboloni | Anonymous and neutral majority rules[END_REF] show, gcd(m!, n) = 1 turns out to be necessary and su cient for the existence of anonymous and neutral social welfare functions (i.e., functions which assign to every preference profile a strict ranking of alternatives).

k ⇤ 2 D ⇤ m (n), implying D ⇤ m (n) 6 = {1}.
ness in such cases. To analyze this, we define

K f = {#f (P N ) : P N 2 L(A) N }
as the irresoluteness outlook of SCR f . So for any natural number k  m, we have k 2 K f if and only if there exists a profile to which f assigns a set of k alternatives. 6Theorem 2. Take any social choice problem (A, N ) with size (m, n).

i . An SCR f is anonymous, e cient, and neutral only if

K f ◆ D m (n).
ii . There exists an anonymous, e cient, and neutral SCR f with

K f = D m (n). Proof. i. Take d 2 D m (n). As d 2 D(n), there exists t 2 N such that n = dt. Take any set of alternatives {x 1 , . . . , x d } ✓ A and the partition {S 1 , . . . , S d } of N with S 1 = {1, . . . , t}, S 2 = {t + 1, . . . , 2t}, S 3 = {2t + 1, . . . , 3t}
, and so on. Let

X = A\{x 1 , . . . , x d }.
Note that X may be empty. Now construct a profile P N as depicted below:

S 1 S 2 S 3 • • • S d x 1 x 2 x 3 • • • x d . . . • • • x 1 . . . • • • . . . . • • • . . . x d • • • x d 3 . x d x 1 • • • x d 2 x d x 1 x 2 • • • x d 1 X X X • • • X As f is e cient, f (P N ) ✓ {x 1 , . . . , x d }. Note that when d = 1, this implies #f (P N ) = 1, hence 1 2 K f . Now let d > 1. Consider the permutation of A such that (x i ) = x i+1 8i 2 {1, . . . , d 1}, (x d ) = x 1 , and (x) = x 8x 2 X.
Next, let 0 2 ⌃ N be such that 0 (i) = i t for all i 2 {t + 1, . . . , dt = n} and 0 (i) = (d 1)t + i for all i 2 {1, . . . , t}. Note that (P N ) = ( 0) 1 (P N ).

Since f (P N ) is a nonempty subset of A, there exists x i 2 f (P N ) for some i 2 {1, . . . , m}. By neutrality, x i 2 f (P N ) implies (x i ) 2 f ( (P N )). By anonymity, x i 2 f (P N ) implies x i 2 f ( (P N )). This is only possible when

f (P N ) = {x 1 , . . . , x d }, as x i 2 f (P N ) implies both x i 2 f ( (P N )) and x i+1 2 f ( (P N )) for all i 2 {1, . . . , d 1} and x d 2 f (P N ) implies both x d 2 f ( (P N ))
and

x 1 2 f ( (P N )). Hence, #f ( (P N )) = d, thus d 2 K f .
ii. Let ⌧ (x, P N ) = # {i 2 N : xP i y 8y 2 A\{x}} denote the number of individuals that rank x on top of their preferences in the profile P N . Define the

plurality rule ⌥ : L(A) N ! A so that ⌥(P N ) = {x 2 A : ⌧ (x, P N ) ⌧ (y, P N ) 8y 2 A}.
We now define the iterative plurality rule : S B2A L(B) N ! A such that (P N ) ✓ B for all P N 2 L(B) N and B 2 A, which selects the plurality winners after successive restriction of profiles to plurality winners.7 Let ⌥ i+1 (P N ) = ⌥(P N | ⌥ i (P N ) ) for all i 1 and ⌥ 1 (P N ) = ⌥(P N ). Define

(P N ) = ⌥ k (P N ),
where k is the minimal integer that satisfies ⌥ k (P N ) = ⌥ k+1 (P N ). Such an integer always exists given the finiteness of A. It is easily checked that is anonymous, e cient, and neutral. We will show that K = D m (n) for all n, m 2 N. By definition, for any x, y 2 A and any

P N 2 L(A) N , x, y 2 (P N ) implies ⌧ (x, P N | ⌥ k (P N ) ) = ⌧ (y, P N | ⌥ k (P N ) ) = t for some t 2 N. Furthermore, for any z / 2 (P N ), ⌧ (z, P N | ⌥ k (P N ) ) = 0. Thus, we have (# (P N ))t = n, implying K ✓ D(n). As # (P N )  m, in fact, K ✓ D m (n). Given part i of the theorem, we have K = D m (n).
Theorem 2 generalizes Theorem 1, which now comes as a corollary; when Condition µ(m, n) fails, by Theorem 2.i , every anonymous, e cient, and neutral SCR has #f (P N ) > 1 for some P N 2 L(A) N and when Condition µ(m, n) is satisfied, the iterative plurality rule ensures the existence of an anonymous, e cient, and neutral f with #f (P N ) = 1 for all P N 2 L(A) N .8

As a matter of fact, Theorem 2 establishes that the irresoluteness outlook K of the iterative plurality rule is the best that an anonymous, e cient, and neutral SCR can achieve. To be sure, this does not mean that cannot be refined while preserving anonymity, neutrality, and e ciency. But surely, any anonymous, e cient, and neutral refinement of will have the same irresoluteness outlook as itself. Moreover, as we formally state in the next theorem, any anonymous, e cient, and neutral SCR whose irresoluteness outlook is a proper superset of K can be refined while anonymity, neutrality, and e ciency are preserved.

Before, we define, for any SCR f : L(A) N ! A, the composite rule f :

L(A) N ! A by f (P N ) = (P N | f (P N ) ) 8P N 2 L(A) N .
Theorem 3. Given a social choice problem (A, N ), an anonymous, e cient, and neutral SCR f with K f K admits the anonymous, e cient, and neutral

refinement f : L(A) N ! A with K f = K .
Proof. Take any social choice problem (A, N ) and any anonymous, e cient, and neutral f with K f K . By definition of f , we have f (P N ) ✓ f (P N ) for all

P N 2 L(A) N . Take any P 0 N 2 L(A) N . First, let #f (P 0 N ) 2 K . As K = D m (n) by Theorem 2, we have #f (P 0 N ) 2 D m (n) which implies # f (P 0 N ) 2 K as well. Now, let #f (P 0 N ) 2 K f \ K . As # f (P 0 N ) 2 D(n) by definition of , we cannot have f (P 0 N ) = f (P 0 N ). Thus, f (P 0 N ) ⇢ f (P 0 N ). Furthermore, as # f (P 0 N )  m, we have # f (P 0 N ) 2 D m (n) = K .
Noting that f is anonymous, e cient, and neutral concludes the proof.

As an instance of Theorem 3, consider the social choice problem A = {x, y, z}, N = {1, 2}, and P N 2 L(A) N with xP 1 yP 1 z and zP 2 yP 2 x. For the Borda rule , which chooses the alternatives that have the minimal sum of ranks over individuals, we have (P N ) = {x, y, z}, thus 3 2 K , while one can check that K = {1, 2}, and, indeed, the composite rule , which gives (P N ) = {x, z} ⇢ (P N ), refines and is anonymous, e cient, and neutral.

Theorem 3 points to the possibility of shrinking the irresoluteness outlook of an anonymous, e cient, and neutral SCR f down to K by composing f with , while f preserves all three properties. However, this does not mean that f can refine f at every P N 2 L(A) N with f (P N ) (P N ). To see this, let m = 5

and n = 6, and consider the following profile P N .

P We have (P N ) = {x, y} and '(P N ) = {x, y, z}, where ' denotes the fallback bargaining rule. 9 However, the composite rule ' does not refine ' at this profile, i.e., '(P N ) = {x, y, z}.

Consequential neutrality

Let W f (S) = {P N 2 L(A) N : f (P N ) = S} for any S 2 A be the set of profiles to which an SCR f assigns S. We write W f (x) in place of W f ({x}) in case of singletons. Define an SCR f : L(A) N ! A to be consequentially neutral

(CN) i↵ #W f (S) = #W f (S 0
) for all S, S 0 2 A with #S = #S 0 . Thus, when f is resolute, CN requires that any two alternatives are assigned to the same number of profiles.

Proposition 1. An SCR f is neutral only if f is CN .

Proof. Take any neutral SCR f . Let S, S 0 ✓ A be such that S = {x 1 , . . . , x h } and S 0 = {x 0 1 , . . . , x 0 h } for some h 2 {1, . . . , m}. Take any P N 2 W f (S). Thus, we have f (P N ) = S. Take any : A $ A such that (x i ) = x 0 i for all i 2 {1, . . . , h}. By neutrality, P N 2 W f (S) implies f ( (P N )) = S 0 , or (P N ) 2 9 Define, for any P N 2 L(A) N , ↵(P N , x, k) = #{i 2 N : #{y 2 A\{x} : xP i y} k}, which gives the number of individuals that rank x higher than at least k alternatives. Now, define the fallback bargaining rule ' :

L(A) N ! A so that, 8x 2 A, x 2 '(P N ) i↵ max k2{0,...,m 1} {k 2 N : ↵(P N , x, k) = n} max k2{0,...,m 1} {k 2 N : ↵(P N , y, k) = n}
for all y 2 A\{x}.

W f (S 0 ). Thus, we have #W We know from Proposition 1 that F NEUT RAL m,n ✓ F CN m,n for all m, n 2 N\{1}. The inclusion is indeed strict. To see this, fix a profile PN 2 L(A) N . Take the permutation 2 ⌃ A such that (x 1 ) = x 2 , (x 2 ) = x 1 , and if m 3, let (x j ) = x j for all j 2 {3, . . . , m}. Take any partition P = {P 1 , . . . , P m } of L(A) N such that #P i = #P j for all i, j 2 {1, . . . , m} and PN , ( PN ) 2 P 1 .

f (S)  #W f (S 0 ). As #W f (S 0 )  #W f (S)
Define f : L(A) N ! A such that f (P N ) = x i for all P N 2 P i and i 2 {1, . . . , m}.

By construction, #{P

N 2 L(A) N : f (P N ) = x i } = #{P N 2 L(A) N : f (P N ) =
x j } for all i, j 2 {1, . . . , m}, hence f is CN. However, it fails neutrality as

f ( PN ) = x 1 = f ( ( PN )).
This raises the following two issues: How large is

F CN m,n compared to F NEUT RAL m,n
and which interesting resolute SCRs, if any, does it contain? We address the first question through a counting approach.10

Theorem 4. The following equalities hold.

i. #F RESOLU T E m,n = m (m! n ) . ii. #F NEUT RAL m,n = m (m! n 1 ) . iii. #F CN m,n = (m! n )!m! (m! n 1 (m 1)!)! m .
Proof. i. This is straightforward, as we noted before that #L(A) N = m! n .

ii. We say that P 0 N is a renaming (for alternatives) of P N i↵ there exists 2 ⌃ A such that P 0 N = (P N ). We write P N ⇢P 0 N when P 0 N is a renaming of P N . Noting that ⇢ ✓ L(A) N ⇥ L(A) N is an equivalence relation, we write E for the partition of L(A) N provided by ⇢. Note that each profile P N admits m! renamings and that #L(A) N = m! n . Thus, E admits m! n 1 equivalence classes, each of which contains m! profiles. We write E = {E i } i2{1,...,m! n 1 } with #E i = m! for all i 2 {1, . . . , m! n 1 }.

Take any E t 2 E and pick any P N 2 E t . Let f (P N ) = x for some x 2 A.

Neutrality, together with the definition of E t , determines f (P 0 N ) for all P 0 N 2 E t \ {P N }. As there are m alternatives that can be assigned to P N by f , there are m neutral and resolute ways an SCR can be defined for the profiles in E t . As t 2 {1, . . . , m! n 1 }, there are m (m! n 1 ) neutral and resolute SCRs altogether.

iii. First observe that, given any two natural numbers p and q, there are (pq)! q! p ways to partition a set of cardinality pq into p sets, each with cardinality q. Hence, there are

(m! n )! (m! n 1 (m 1)!)! m ways to partition L(A) N with cardinality m! n into m sets, each with cardinality m! n /m = m! n 1 (m 1)!.
For each of these ways, m! distinct resolute SCRs can be defined. As a result,

(m! n )! (m! n 1 (m 1)!)! m m!
resolute SCRs that satisfy consequential neutrality can be constructed.

From Theorem 4, one can compute

#F NEUT RAL m,n #F RESOLU T E m,n = m ( 1+ 1 m! )m! n .
As 1 m! < 1 for all m > 1, this ratio approaches to 0 as m ! 1 or n ! 1. Thus, we conclude that the ratio of the number of neutral and resolute SCRs to the number of all resolute SCRs is negligible in the limit. Although we do not have analytical solutions for the comparisons regarding consequential neutrality, we obtained some numerical observations through computations for small values of m and n that are provided in Appendix A. These indicate that both

#F CN m,n #F RESOLU T E m,n and #F NEUT RAL m,n #F CN
A k = {S ✓ A : #S = k}. Thus, we have #A k = m k = m ⇣ m 1 k 1 /k ⌘ . Condition (m, n) ensures that m 1 k 1 /k (= t from now on
) is a natural number. We want to show that each x i 2 A can be assigned to t distinct sets of cardinality k that contains x i . This will su ce to prove the theorem, given Proposition 1, as the number of profiles these k sets are assigned to under a neutral SCR are equal. To do that, we introduce the following iterative approach.

First, define : A $ A such that (x i ) = x i+1 for all i 2 {1, . . . , m 1} and (x m ) = x 1 . Next, let A k denote the lexicographic order of the k sets in

A k according to the order x 1 • • • x m . Thus, for instance, {x 1 , . . . , x k } A k {x 1 , . . . , x k 1 , x k+1 } A k S for all S 2 A k \{{x 1 , . . . , x k }, {x 1 , . . . , x k 1 , x k+1 }}.
Step 1.

-Take the first set in A k according to A k , i.e., {x 1 , . . . , x k }, and denote this set with A k,1 . Now, denote with r (A k,1 ), the r time application of permutation , with a slight abuse of notation. Thus, for instance, -Take the first set in A k \ A k,1 according to A k and denote this set with

A k,2 . Construct A k,2 as in Step 1 so that A k,2 = {A k,2 , 1 (A k,2 ), . . . , m 1 (A k,2 )}.
Step j for j 2 {3, . . . , t} if t > 2.

-Take the first set in A k \ S j 1 c=1 A k,c according to A k and denote this set with A k,j . Construct A k,j as in Step 1.

The proof concludes by constructing an SCR g that refines f such that for all P N 2 L(A) N , k 2 D m (n) \ {1}, and j 2 {1, . . . , t},

• f (P N ) = A k,j =) g(P N ) = x 1 and • f (P N ) = r (A k,j ) =) g(P N ) = x r+1 8r 2 {1, . . . , m 1}.
We need to make sure that the following hold.

(i) x 1 2 A k,j for all j 2 {1, . . . , t}.

(ii) x r+1 2 r (A k,j ) for all j 2 {1, . . . , t} and for all r 2 {1, . . . , m 1}.

(iii) {A k,j } j2{1,...,t} is a partition of A k . (i): First, note that x 1 2 A k,1 . Next, observe that #{S 2 A k,1 : x 1 2 S} = k as #A k,1 = k, x 1 2 A k,1
, and for each x j 2 A k,1 \ {x 1 }, there exists a unique r 2 {1, . . . , m 1} such that r (x j ) = x 1 . Thus, in fact, for all j 2 {2, . . . , t}, S j 1 c=1 A k,c contains (j 1)k sets that contain x 1 and there remain (t j + 1)k sets in A k \ S j 1 c=1 A k,c that contain x 1 .12 As for each j 2 {2, . . . , t}, the first set in A k \ S j 1 c=1 A k,c according to A k is chosen to be A k,j , x 1 2 A k,j for all j 2 {1, . . . , t} is established.

(ii): As x 1 2 A k,j for all j 2 {1, . . . , t} and r (x 1 ) = x r+1 , it is straightforward to note that x r+1 2 r (A k,j ) for all j 2 {1, . . . , t} and for all r 2 {1, . . . , m 1}.

(iii): First, note that #A k,i = m for all i 2 {1, . . . , t}. We need to show that A k,i \ A k,j = ; for any i, j 2 {1, . . . , t}. This follows from the statement

(i) as A k,j 2 A k \ S j 1 c=1 A k,c
for all j 2 {1, . . . , t}. To see that, suppose for a contradiction that there exists S 2 A k,i \ A k,j for some i, j 2 {1, . . . , t} with j > i. We must have S = ri (A k,i ) = rj (A k,j ) for some r i , r j 2 {1, . . . , m 1}.

Note that r i 6 = r j as A k,i 6 = A k,j . In case r i > r j , we have ri rj (A k,i ) = A k,j and in case r i < r j , we have ri+m rj (A k,i ) = A k,j , both contradicting that

A k,j 2 A k \ S j 1 c=1 A k,c . 13 We let g(P N ) = f (P N ) for all P N 2 L(A) N with # f (P N ) = 1. g is a
resolute refinement of f . Naturally, g is anonymous as f is. Furthermore, by construction of the iterative process above, g is also CN. Finally, as f is e cient, g is e cient as well.

To see how the refinement in Theorem 5 can be constructed, consider the following example with A = {x 1 , . . . , x 7 } and n = 5. Take any f that is anonymous, e cient, and neutral. We have D 7 (5) = {1, 5}, so we focus on k = 5 for the iterative process. We have 7 5 = 21 and t = 3, that is, there are 21 distinct sets with 5 alternatives and all profiles that result in 5 alternatives under f should be assigned to each of the 7 alternatives so that each will be chosen within 3 di↵erent sets. So in Step 1, we set A 5,1 = {x 1 , x 2 , x 3 , x 4 , x 5 } and construct A 5,1 . In Step 2, we set A 5,2 = {x 1 , x 2 , x 3 , x 4 , x 6 } which follows {x 1 , x 2 , x 3 , x 4 , x 5 } in the lexicographic order A5 and construct A 5,2 . In Step 3, final step, we cannot set the next set according to A5 , i.e., {x 1 , x 2 , x 3 , x 4 , x 7 }, as A 5,3 because it already appears in A 5,1 as 6 (A 5,1 ) = {x 1 , x 2 , x 3 , x 4 , x 7 }. However, we can set {x 1 , x 2 , x 3 , x 5 , x 6 } as A 5,3 , which follows {x 1 , x 2 , x 3 , x 4 , x 7 } in the lexicographic order A5 and construct A 5,3 to complete the iterative process as depicted in the Table 1.

The refinement g is constructed so that for all P N 2 L(A) N and for all j 2 {1, 2, 3} (i) f (P N ) 2 A 5,j implies g(P N ) = x 1 and (ii) f (P N ) 2 r (A 5,j ) implies g(P N ) = x r+1 for all r 2 {1, . . . , 6}.

Note that Condition (m, n) ensures the existence of anonymous, CN, ecient, and resolute SCRs by asking m | m k to hold for every k 2 D m (n). On the other hand, as it follows from the proof of Theorem 5, a weaker version of Condition (m, n) that asks m | m k to hold for some k 2 D m (n), although j = 1 j = 2 j = 3 A 5,j {x 1 , x 2 , x 3 , x 4 , x 5 } {x 1 , x 2 , x 3 , x 4 , x 6 } {x 1 , x 2 , x 3 , x 5 , x 6 } (A 5,j ) {x 2 , x 3 , x 4 , x 5 , x 6 } {x 2 , x 3 , x 4 , x 5 , x 7 } {x 2 , x 3 , x 4 , x 6 , x 7 } 2 (A 5,j ) {x 3 , x 4 , x 5 , x 6 , x 7 } {x 3 , x 4 , x 5 , x 6 , x 1 } {x 3 , x 4 , x 5 , x 7 , x 1 } 3 (A 5,j ) {x 4 , x 5 , x 6 , x 7 , x 1 } {x 4 , x 5 , x 6 , x 7 , x 2 } {x 4 , x 5 , x 6 , x 1 , x 2 } 4 (A 5,j ) {x 5 , x 6 , x 7 , x 1 , x 2 } {x 5 , x 6 , x 7 , x 1 , x 3 } {x 5 , x 6 , x 7 , x 2 , x 3 } 5 (A 5,j ) {x 6 , x 7 , x 1 , x 2 , x 3 } {x 6 , x 7 , x 1 , x 2 , x 4 } {x 6 , x 7 , x 1 , x 3 , x 4 }

6 (A 5,j ) {x 7 , x 1 , x 2 , x 3 , x 4 } {x 7 , x 1 , x 2 , x 3 , x 5 } {x 7 , x 1 , x 2 , x 4 , x 5 } A 5,1 A 5,2 A 5,3
Table 1: Iterative process for constructing the partitioning {A 5,j } j2{1,...,t} of A 5 , where t = 7 5 /7 = 3.

does not ensure resoluteness, allows the existence of anonymous and e cient refinements that satisfy CN. We state this formally in the following remark and leave out its proof as it follows from the proof of Theorem 5. Let us say that

(m, n) satisfies Condition 0 (m, n) i↵ m | m k for some k 2 D m (n).
Remark 1. Let (A, N ) be a social choice problem with size (m, n) where Condition 0 (m, n) is satisfied. Every anonymous, e cient, and neutral SCR f admits a refinement which is anonymous, e cient, and CN .

How restrictive is Condition (m, n)? Note that when m is a prime, Condition (m, n) is satisfied.14 Thus, anonymous, CN, e cient, and resolute SCRs exist when m is prime and does not divide n. [START_REF] Campbell | The finer structure of resolute, neutral, and anonymous social choice correspondences[END_REF] show that when n has at least two distinct prime factors, there can only be finitely many values of m for which there are anonymous, neutral, and resolute SCRs.

Our result implies, for instance, that for such n, there are infinitely many values of m (such as all primes that are greater than n) for which there are anonymous, CN, and resolute SCRs. Furthermore, these SCRs can be e cient.

To expand the picture drawn by Theorem 5, we show that Condition (m, n)

is not necessary for the existence of anonymous, CN, e cient, and resolute SCRs.

As a matter of fact, the theorem below spans some instances where Condition (m, n) fails, e.g., m = 4 and n = 2 (note that 2 2 D 4 (2) and 4 -4 2 ).

now define an SCR h. We let h(P N ) = ⌥(P N ) for all P N 2 L(A) N \T . For any P N 2 T {xq,xr,xt} , let j 2 N denote the individual such that x q P j x w for all w 2 {1, . . . , m} \ {q}. We let h(P N ) = x q if x M ({q,r,t}) P j x z for all z 2 {r, t}, h(P N ) = x r if x z P j x M ({q,r,t}) for all z 2 {r, t}, and h(P N ) = x t if either

x r P j x M ({q,r,t}) P j x t or x t P j x M ({q,r,t}) P j x r .

Note that h is resolute by construction and is e cient as it refines the plurality rule. Moreover, it is anonymous, as h(P N ) = h(P 0 N ) whenever P 0 N is anonymously equivalent to P N . Since we have #{P N 2 T {xq,xr,xt} |x M ({q,r,t}) P j x z 8z 2 {r, t}} = #{P N 2 T {xq,xr,xt} |x z P j x M ({q,r,t}) 8z 2 {r, t}} = #{P N 2 T {xq,xr,xt} |x r P j x M ({q,r,t}) P j x t or x t P j x M ({t,q,r}) P j x r }, h is also CN.

At this stage, one may be tempted to ask whether one can find an anonymous, CN, e cient, and resolute SCR at any (m, n). The following theorem advises caution on this.

Theorem 7. There exists a social choice problem which admits no anonymous, CN, e cient, and resolute SCR.

Proof. Let A = {x, y} and N = {1, 2}. We have four possible profiles, P N , P

) = f (P 000 N ) by anonymity. Hence, #{P N 2 L(A) N : f (P N ) = x} 6 =#{P N 2 L(A) N : f (P N ) = y}, a failure of consequential neutrality.
Nevertheless, the social choice problem in the proof of Theorem 7 admits an anonymous, CN, and resolute SCR. 15 This raises the question of how general 15 To see this, consider g : L(A) N ! A such that g(P N ) = g(P 0 N ) = x and g(P 00 N ) = g(P 000 N ) = y, which is both anonymous and CN while not e cient.

is the compatibility between anonymity and consequential neutrality when we dispense with the e ciency condition. [START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF] introduces the following condition that we call (m, n). Let

D(n)\{1} = {d 1 , . . . , d K } for some K 2 N. Condition (m, n): @(a 1 , . . . , a K ) 2 (N [ {0}) K such that P K i=1 a i d i = m. Remark 2. µ(m, n) =) (m, n) for all n, m 2.
The following theorem states the cases of incompatibility of anonymity and neutrality in resolute social choice.

Theorem 8 [START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF]). There exists an anonymous, neutral, and resolute SCR if and only if (m, n) holds.

We are now ready to state and prove our final theorem, which shows that if m > n, there exist anonymous, CN, and resolute SCRs for any social choice problem with size (m, n).

Theorem 9. For all social choice problems with n < m, there exists an anonymous, CN, and resolute SCR.

Proof. Given any preference profile, we observe k distinct preferences for some k 2 {1, . . . , min{m!, n}}. There are m! k ways to choose k preferences from L(A). Let P = {p 1 , . . . , p k } be a set of k distinct preferences. Write V k for the set of vectors v = (v 1 , . . . , v k ) with v i 1 for all i 2 {1, . . . , k} and P k i=1 v i = n. Each v 2 V k , combined with P, induces a set of profiles E P v that consists of all profiles where p i appears v i times for all i 2 {1, . . . , k}. Let E P = S v2V k E P v . Three remarks are in order. First, #E P depends on k and not on the preferences in P. Second, an SCR f that satisfies at any given k 2 {1, . . . , min{m!, n}} and P the invariance f (P N ) = f (P 0 N ) for all P N , P 0 N 2 E P is anonymous. Third, m | m! k if k < m, which is ensured when n < m. Now, let t k = m! k /m. Write A = {x 1 , . . . , x m } and at each k 2 {1, . . . , min{m!, n}} assign to every x i t k distinct sets P = {p 1 , . . . , p k } and let f (P N ) = x i for all P N 2 E P at every P assigned to x i for all i 2 {1, . . . , m}. By the three remarks, f is anonymous, CN, and resolute.

Conclusion

Using an irresolute SCR, one cannot reach a collective choice without referring to an additional mechanism that is external to the SCR. Therefore, Theorems 1 and 8 reflect the impossibility of making a collective choice by being confined to anonymous and neutral (e cient) SCRs as collective choice procedures. We take two di↵erent but related approaches to address how severe this impossibility is.

First, we identify the minimal irresoluteness outlook that would arise when anonymity, e ciency, and neutrality make ties inevitable. Based on this analysis, we deliver a method which, while preserving anonymity, e ciency, and neutrality, refines SCRs that deliver more ties than necessary.

Next, we introduce consequential neutrality as a weakening of neutrality. As expected, we obtain results that are more permissive than the (im-)possibilities announced by Theorems 1 and 8. We identify a large class of social choice problems where resoluteness becomes possible just because consequential neutrality replaces neutrality. Nevertheless, when e ciency is preserved, we know that this possibility does not hold for every social choice problem.

Dispensing with e ciency presents a case of interest. We show that anonymous, CN, and resolute social choice is possible when m > n. Although this condition is logically independent of the necessary and su cient condition of Theorem 8, it opens the door of resoluteness to a large class of social choice problems that are doomed to irresoluteness by Theorem 8. Moreover, we are not able to find any social choice problem where anonymity, consequential neutrality, and resoluteness are incompatible. This provokes to ask whether these three conditions are compatible for any size of the social choice problem, which we leave as a -combinatorically di cult-open question.

  holds as well, the proof is completed. Now, we focus on resolute SCRs. Given m, n 2 N\{1} with #A = m and N = {1, . . . , n}, we write F CN m,n for the set of resolute SCRs that are CN; F NEUT RAL m,n for the set of resolute and neutral SCRs; and F RESOLU T

  m,n converge to 0, as m or n increases. Thus, although consequential neutrality and neutrality are both hard to satisfy, neutrality seems to be considerably more demanding compared to consequential neutrality. 11Now we address whether F CN m,n \F NEUT RAL m,n contains interesting SCRs and the answer is a rmative, at least for certain sizes of the social choice problem.We say that (m,n) satisfies Condition (m, n) i↵ m | m k for all k 2 D m (n).This condition ensures the existence of anonymous, CN, e cient, and resolute SCRs, as shown in Theorem 5 below. Theorem 5. Let (A, N ) be a social choice problem with size (m, n) where Condition (m, n) is satisfied. Every anonymous, e cient, irresolute, and neutral SCR f admits a resolute refinement which is anonymous, CN, and e cient. Proof. Fix m, n 2 N as such, let A = {x 1 , . . . , x m }, and take any anonymous, e cient, and neutral f : L(A) N ! A. Clearly, # f (P N ) 2 D m (n) for all P N 2 L(A) N due to Theorems 2 and 3. Next, observe that mn, as otherwise we would have m 2 D m (n), while mm m = 1. Thus, there does not exist a profile P N with f (P N ) = A. For any k 2 D m (n)\{1}, denote with A k the subsets of A with precisely k elements, that is,

  1 P 2 P 3 P 4 P 5 P 6

	x	x	t	r	y	y
	y	y	z	z	x	x
	z	z	x	y	r	z
	r	t	y	x	z	t
	t	r	r	t	t	r

They propose a weaker version of anonymity in a similar way by assuming that individuals are divided into sub-committees and requiring that, within each sub-committee, individuals have equal influence on the collective decision, while people in di↵erent sub-committees may enjoy di↵erent levels of influence.

So, given any distinct x, y 2 A and P i 2 L(A), precisely one of xP i y and yP i x holds. Moreover, xP i y and yP i z implies xP i z for all x, y, z 2 A and P i 2 L(A). Finally, xP i x does not hold for any x 2 A.

Note that the irresoluteness outlook of an SCR f does not specify to how many profiles f assigns k alternatives when k 2 K f .

Note that the iterative plurality rule presents a generalization of our concept of an SCR in the sense that it is defined on the domain of preference profiles over every B 2 A.

Part (ii) of Theorem 2 can be proven with rules other than the iterative plurality rule, such as Coombs rule, as in[START_REF] Moulin | The strategy of social choice[END_REF] p. 24. We are thankful to a referee for pointing out this fact.

[START_REF] Perry | Aggregation rules that satisfy anonymity and neutrality[END_REF] propose a method to count, in the case of two alternatives, the number of aggregation rules that satisfy anonymity and neutrality.[START_REF] Bubboloni | Resolute refinements of social choice correspondences[END_REF] give a method to perform these counts for any number of alternatives.

We are providing computational results for only some small values of m and n because as m and n increase, these values grow dramatically. As diminution in the ratios are also fast, these values appear to be su cient for this conclusion. Since the aim of this counting exercise is to assess the comparison of numbers of functions that satisfy the two versions of neutrality, we leave out other axioms (such as anonymity and e ciency), although it certainly is an interesting question.

(A k,1 ) = {x

, . . . , x k+1 }. Denote with A k,1 the set comprising of A k,1 together with m 1 other k sets in A k that are constructed from A k,1 by applying iteratively m 1 times. Thus, A k,1 = {A k,1 , 1 (A k,1 ), . . . , m 1 (A k,1 )}.Step 2.

This holds for any x i 2 A.

Note that r+m (x i ) = r (x i ) for all r 2 N and i 2 {1, . . . , m}.

To see this, note that the numerator inm k = m•...•(m k+1) k!is divisible by m whereas none of {2, . . . , k} divides m.

the thoughtful comments of three anonymous referees to whom we are grateful. Our work is partly supported by the projects ANR-14-CE24-0007-01, CoCoRICo-CoDec, and IDEX ANR-10-IDEX-0001-02 PSL* MIFID.

Theorem 6. Any social choice problem (A, N ) with m 4 and n 2 {2, 3} admits an anonymous, CN, e cient, and resolute SCR.

Proof. Let m 4 and N = {1, 2}. For any x, y 2 A, let T xy ⇢ L(A) N denote the set of profiles where individual 1 ranks x first and individual 2 ranks y first.

Hence {T xy } x6 =y partitions the set of profiles where there is no unanimously top ranked alternative. Given any x, y 2 A, note that

and hence, #T xy = #T yx . Now, let A = {x 1 , . . . , x m } and define for any distinct i, j 2 {1, . . . , m}, D m (i, j) = k, l 2 {1, . . . , m}\{i, j} : k < l < t 8t 2 {1, . . . , m}\{i, j, k, l} , as the doubleton that contains the lowest two indices in A excluding i and j.

Let g : L(A) N ! A be a resolute SCR that assigns to any profile the alternative that is ranked first by both individuals, if exists. Note that #{P N 2 L(A) N :

Furthermore, for all P N 2 T xixj with i < j and D m (i, j) = {k, l}, let g(P N ) = x i when x k P 1 x l () x k P 2 x l and g(P N ) = x j otherwise. Hence, we have #{P N 2

g is CN and anonymous. Moreover, as g picks an alternative only if it is ranked first by an individual, it is also e cient.

Now let N = {1, 2, 3}, hence n = 3. Let T ⇢ L(A) N denote the subset of profiles where each individual has a distinct alternative as most preferred. That is, P N 2 T i↵ x 1 P 1 y for all y 2 A\{x 1 }, x 2 P 2 y for all y 2 A\{x 2 }, and x 3 P 3 y for all y 2 A\{x 3 } implies x 1 , x 2 , and x 3 are all distinct. Note that under the plurality rule ⌥, #⌥(P N ) = 1 for all P N 2 L(A) N \T and #⌥(P N ) = 3 for all P N 2 T .

Let A = {x 1 , . . . , x m }. For any q, r, t 2 {1, . . . , m} with q < r < t, let M ({q, r, t}) denote the minimal element in {1, . . . , m}\{q, r, t}. So for instance, when m = 5, M ({2, 3, 4}) = 1 and M ({1, 2, 4}) = 3. Let T {xq,xr,xt} ⇢ T denote the set of profiles where each of x q , x r , and x t appears on top. We A Appendix: Observations on the numbers of CN, neutral, and resolute SCRs

Tables 1 and2 for di↵erent values of (m, n).


Justin Kruger

M Remzi Sanver
email: remzi.sanver@dauphine.fr

Markus Brill

Franz Dietrich

Sean Horan

Jean-François Laslier

Philippe Mongin

Dominik Peters

Clemens Puppe

Shin

An Arrovian impossibility in combining ranking and evaluation *

Keywords: JEL Classifications: D71 preference-approval, majoritarian judgment, approval voting, preference aggregation, evaluation

In a world where voters not only rank the alternatives but also qualify them as "approved" or "disapproved", we observe that majoritarianism in preferences and majoritarianism in approvals are logically incompatible. We show that this observation generalises to the following result: every aggregation rule that respects unanimity and decomposes the aggregation of preferences and approvals is dictatorial. Our result implies an incompatibility between ordinal and evaluative approaches to social choice theory under two weak assumptions: respect for unanimity and independence of evaluation of each alternative. We describe possibilities when the latter assumption is relaxed. On the other hand, our impossibility generalises to the case where there are more than the two evaluative levels of "approved" and "disapproved".

Introduction

The traditional approach in social choice theory involves aggregating ordinal preferences over alternatives. We will refer to this as the ranking approach. This can be contrasted with what we call the evaluative approach, which involves aggregating evaluations of the alternatives made by the voters. For example, approval voting, as pioneered by [START_REF] Brams | Approval voting[END_REF], is evaluative; it affords two possible evaluations for each of the alternatives: approved or disapproved. In this paper we prove an impossibility in combining the ranking and evaluative approaches. Our result implies that there is an incompatibility between the two.

Suppose that a committee is tasked with selecting a candidate for a position that can be left vacant if no suitable candidate is found. The committee has identified the best candidate and considers her suitable, so offers this candidate the position. If this first choice candidate rejects the offer, the position can then be offered to the second best candidate, and so on until the next candidate is considered unsuitable. Overall, the committee's task can be divided into two: creating a ranking over the candidates-the ordinal part; and determining which candidates are suitable for the position-the evaluative part. It is these two different parts that are the subject of this paper.

In the above task, candidates are individually evaluated as being suitable, or not, for a position. A more neutral presentation of the evaluation part, which does not assign it such a specific meaning, occurs in the preference-approval framework-originally conceived by [START_REF] Brams | Voting systems that combine approval and preference[END_REF]. Let us describe the smallest non-trivial version of this framework. This involves two alternatives, a and b, which are ranked with respect to each other and also individually evaluated as approved or disapproved. The ordering over the two possible evaluations brings about natural restrictions upon how rankings and evaluations should be combined. For example, if a is approved and b is disapproved, it would be unreasonable to also rank the two alternatives as indifferent. A consistent combination of ranking and approvals is known as a preference-approval.

A preference-approval can be represented as a complete preorder over the alternatives that is also equipped with a "zero-line" to demarcate which alternatives are approved. For the two alternatives a and b there are eight possible preference-approvals. These are displayed below. The preference-approvals read from left to right. When the two alternatives are within paranthesis, the voter is indifferent between them. Otherwise, an alternative is strictly preferred to the other if and only if it is at the left of the other; and alternatives are approved if and only if they are at the left of the horizontal line:

1st a b | 2nd a | b 3rd | a b 4th b a | 5th b | a 6th | b a 7th (ab) | 8th | (ab)
The following collection of preference-approvals may set off alarm bells. Suppose that there are only three voters and that they have, respectively, the first, third and fifth preference-approvals displayed above. Amongst these voters a is ranked above b by a majority-if we aggregate the ranking according to the majority method of [START_REF] May | A set of independent necessary and sufficient conditions for simple majority decision[END_REF], a will be ranked above b in the social ordering. At the same time, a is disapproved by a majority and b is approved by a majority-if we aggregate the evaluations by majority, thereby complying with [START_REF] Sanver | Approval as an intrinsic part of preference[END_REF] axiom of majoritarian approval, b should be uniquely approved in the output. Thus applying majority on the decomposed components of these preference-approvals results in an inconsistent outcome.

The collection of preference-approvals described above effectively recreates the Condorcet paradox with the zero-line as an implicit third alternative. Compare the following profile of preference-approvals and profile of rankings.

V oter

1 a b | V oter 2 | a b V oter 3 b | a
V oter 1 a b z V oter 2 z a b V oter 3 b z a This Condorcet-like example presages a more general phenomenon, which we prove as an impossibility theorem. This impossibility states that if aggregation of preference-approvals is performed in a decomposed manner and the approval aggregation part satisfies unanimity, then the only possibility is a dictatorship. Thus we extend the example into a more general result, mirroring the connection between Condorcet's paradox and [START_REF] Arrow | A difficulty in the concept of social welfare[END_REF] impossibility theorem.

Unanimity is a weak condition; the important condition is decomposability, which takes the place of the well-known independence condition of [START_REF] Arrow | A difficulty in the concept of social welfare[END_REF]. Decomposability requires that the social evaluation for each alternative only depends upon the individuals' evaluations for that alternative, and that the social ranking of the alternatives only depends upon the individuals' rankings over the alternatives. Decomposability can be weakened in a variety of ways. We identify various possibilities when decomposability is weakened within the evaluative part, but the ordinal and evaluative parts are kept separate-these possibilities are stated as Theorems 4.1, 4.2 and 4.3. We also identify four specific possibilities that arise when the decomposability between the ordinal and evaluative parts is relaxed.

To give a brief overview of the rest of the paper: in Section 2 we define the basic model of preference-approvals. We show our central impossibility concerning the aggregation of preference-approvals in Section 3. Possibilities arise if one does not require that preference-approvals are aggregated in a decomposed manner, which we explore in Section 4. We prove an extended version of the impossibility, applicable for more than two evaluation levels, in Section 5. Final remarks are provided in Section 6.

The preference-approval model

The basic building blocks of our model are a finite set of alternatives A = {a 1 , ..., a m } with m ≥ 2, and a set of voters N = {1, ..., n} with n ≥ 2. We write W (A) for the set of complete preorders over A. A complete preorder is linear if it is antisymmetric; we write L(A) for the set of linear orders over A. We use R i ∈ W (A) for the preference of i ∈ N over A, and use P i for the strict part of R i . We write 2 A for the set of subsets of A and we use B i ∈ 2 A for the set of alternatives approved by i ∈ N .

A preference-approval of voter i ∈ N is a pair

p i = (R i , B i ) ∈ W (A) × 2 A
, composed of a complete preorder and set of approved alternatives, with the extra consistency requirement that ∀x, y ∈ A, (x R i y and y

∈ B i ) =⇒ x ∈ B i .
We write Π for the set of all preference-approvals. A profile of preference approvals is some p = (p 1 , ..., p n ) = Π N . As a general rule we write vectors in boldface.

A preference-approval aggregator is a function π : D N -→ Π, where D ⊆ Π. A preference-approval aggregator π is dictatorial if there is a voter d whose strict preference and approval line are reproduced in the output preference-approval; i.e., d ∈ N is a dictator if for all p = ((R 1 , B 1 ), ..., (R n , B n )) ∈ D N we have π(p) = (R, B d ) where R is some preference such that x P y if x P d y

A social welfare function is some f : D N -→ W (A), where D ⊆ W (A). We write f * (R) for the strict part of f (R), for all R ∈ D N . We say that f is Pareto optimal if, for all x, y ∈ A and for all R ∈ D N with x P i y for all i ∈ N , we have x f * (R) y. We say that f is dictatorial if there is some d ∈ N such that for all x, y ∈ A and for all R ∈ D N with x P d y we have x f * (R) y.

We also consider aggregation in the approval voting tradition. For x ∈ A, an elementary approval aggregator is a function α x : {0, 1} N -→ {0, 1}. We refer to the elementary approval aggregator of a subscripted alternative, such as a j , directly with the subscript, i.e,. α j = α aj . An elementary approval aggregator should be interpreted as a map from a profile where each voter either approves x (assigns it 1) or disapproves x (assigns it 0) into a situation where either x is globally approved (the result is 1) or x is globally disapproved (the result is 0). Such a function satisfies unanimity if α x (0, ..., 0) = 0 and α x (1, ..., 1) = 1. An approval aggregator is a function α : (2 A ) N -→ 2 A . We say that α satisfies (alternative-wise) unanimity if, for any x ∈ A and any

B ∈ (2 A ) N , (i) if x ∈ B i for all i ∈ N then x ∈ α(B) and (ii) if x ∈ B i for no i ∈ N then x / ∈ α(B). 1
Our final definitions concern splitting up various aggregators into subfunctions. An approval aggregator α is decomposable if, for each alternative x ∈ A there is an elementary approval aggregator α x such that, for all

B ∈ (2 A ) N , x ∈ α(B) ⇐⇒ α x (1 B1 (x), ..., 1 Bn (x)) = 1 where 1 X : A → {0, 1} is the indicator function of X ⊆ A, defined for each x ∈ A as 1 X (x) = 1 ⇐⇒ x ∈ X.
In such a case we write α = (α x ) x∈A . Similarly, π can be decomposed into (f, α) if for all

((R 1 , B 1 ), ..., (R n , B n )) ∈ D N , we have π((R 1 , B 1 ), ..., (R n , B n )) = (f (R 1 , ..., R n ), α(B 1 , ..., B n ))
, and further into (f, (α x ) x∈A ) if also α = (α x ) x∈A . In such cases we write, respectively, π = (f, α) and π = (f, (α x ) x∈A ).

An impossibility in aggregating preferenceapprovals

Theorem 3.1. If D = Π then any preference-approval aggregator π = (f, α 1 , ..., α m ) such that α x satisfies unanimity for all x ∈ A is dictatorial.

Proof: Take a preference-approval aggregator π = (f, α 1 , ..., α m ) : Π N -→ Π such that each α j satisfies unanimity. We first show that f is Pareto optimal. Take any a, b ∈ A and any R with a P i b for all i ∈ N . To establish a f * (R) b, define B ∈ (2 A ) N such that for all i ∈ N and for all x ∈ A, x ∈ B i if and only if x R i a. For each i ∈ N , the ordered pair (R i , B i ) forms a preference-approval. By unanimity, x ∈ α(B) and y / ∈ α(B). By consistency of the output, a f * (R) b, thus f satisfies Pareto optimality.

To show that π is dictatorial, we define a social welfare function f over an extended set of alternatives A ∪ {z} = X . The function f corresponds to π, while the alternative z represents the "zero-line". Using two results from the literature on social welfare functions, we show that f is dictatorial, which in turn implies that π is dictatorial.

We say that a social welfare function g :

D N -→ W (X), D ⊆ W (X), satisfies binary independence if for every pair {x, y} ⊆ X, for all R, R ∈ D N , if R| {x,y} = R | {x,y} then g(R)| {x,y} = g(R )| {x,y} . 2
Note that in order for binary independence to not be trivially satisfied it is necessary that |X| > 2. We say a domain is Arrovian if every Pareto optimal social welfare function that satisfies binary independence is dictatorial. [START_REF] Kelly | The Bordes-LeBreton exceptional case[END_REF] gives conditions for a domain to be Arrovian.

For a preference-approval p = (R, B), define a complete preorder p ∈ W (A ∪ {z}) by, for {a, b} ⊆ A, a pb ⇐⇒ aRb, b pa ⇐⇒ bRa. Moreover, for x ∈ {a, b}, x pz ⇐⇒ x ∈ B and, z px ⇐⇒ x / ∈ B. It can be verified that p is complete and transitive. Write p * for the strict part of p; the above definitions imply that, for any {a, b} ⊆ A, aP b ⇔ ap * b while for any x ∈ {a, b}, x ∈ B ⇐⇒ xp * z.

Define D = {p : p ∈ Π} ⊂ W (A ∪ {z}). By definition p -→ p is a bijection from Π to D. This means there is also a bijection from preference approval profiles p ∈ Π

N to p = (p i ) i∈N ∈ D N . The domain D N is a (Cartesian) product
domain that contains all possible linear orders and yet does not contain the complete preorder where all pairs of alternatives are considered indifferent. Thus this domain is Arrovian according to [START_REF] Kelly | The Bordes-LeBreton exceptional case[END_REF] "Theorem 1". Define the social welfare function f : D N -→ W (A ∪ {z}) as, for an arbi-

trary p ∈ D N , f (p) = π(p).
It may be noted that f is defined in terms of a decomposable preference-approval aggregator π = (f, (α x ) x∈A ), and thus that the output ranking over a, b ∈ A can be determined by the output of f , and also that the output ranking over a ∈ A and z can be determined by the output of α a . We now show that f is Pareto optimal and satisfies binary independence. For Pareto optimality, take an arbitrary p. We split into two cases. First we consider pairs {a, b} ⊆ A. If a p * i b for all i ∈ N then the result follows directly from the fact that f is Pareto optimal. Second, we consider pairs {a, z} with a ∈ A. As a first subcase, suppose a p * i z for all i ∈ N . This implies that all voters approve a in p. By unanimity of α a , a is approved in π(p), thus a f * (p)z as required. For the subcase where z p * i a for all i ∈ N , replace approve with disapprove in the preceding sentence.

For the proof of binary independence, we utilise results due to [START_REF] Campbell | Information and preference aggregation[END_REF], who establish the notion of relevant sets. A relevant set is defined with respect to a Pareto optimal social welfare function g :

D N -→ W (X), where D ⊆ W (X). A relevant set for a pair {x, y} ⊆ X is the minimal (by inclusion) set of alternatives Y ⊇ {x, y}, Y ⊆ X, such that for all profiles R, R ∈ D N ⊆ W (X) N , if R| Y = R | Y then g(R)| {x, y} = g(R )| {x, y} .
Campbell and Kelly's "Theorem 2 part (I)", paraphrased, states: for any Pareto optimal social welfare function g and distinct alternatives x, y, w, if the relevant set of {x, y} is {x, y} then the relevant set of {y, w} either contains x or is identical to {y, w}.

We know already that f is Pareto optimal. Take arbitrary {a, b} ⊆ A. By the decomposability of π, and by the definition of relevant sets as minimal by inclusion, the relevant set of {z, a} is {z, a} and the relevant set of {a, b} is a subset of A that does not contain z. Thus, by "Theorem 2 part (I)", the relevant set of {a, b} must be {a, b}, which establishes binary independence.

Altogether this implies that f is dictatorial, with a dictator d. We claim that d must also be a dictator for π. Take an arbitrary profile p = (R, B) and write π(p) = (R, B). Remark 1: There are two subtle requirements in this proof, concerning properties of the created domain and the informational restrictions of the created social welfare function. Concerning the first, the presence of all linear orders and the absence of the preference of complete indifference is sufficient for a domain to be Arrovian. This means that for a possibility based on a restricted domain it will be necessary to remove at least one preference-approval that corresponds to a linear order. Concerning the second, it is crucial that the relevant set of an alternative and the "zero-line" alternative was exactly that pair: if we do not decompose the aggregation of approvals, then this need no longer be the case, and the theorem of [START_REF] Campbell | Information and preference aggregation[END_REF] no longer applies.

The impossibility vanishes for certain interesting restricted domains of preference-approvals. Denote by Π -the domain where all alternatives below the line must be considered indifferent. 4 Hence, a preference approval (R, B) is in Π -if and only if x R y for all x, y ∈ A\B. For A = {a, b}, Π -contains exactly the following six preference-approvals:

a b | a | b b a | b | a (ab) | | (ab)
For any I ⊆ N , I = ∅, let α ud x be the "unanimous disapproval rule" that disapproves x ∈ A if and only if x is disapproved by all voters in N . Note that this elementary approval aggregator satisfies unanimity. Given that all alternatives below the line must be considered indifferent, the unanimous disapproval rule will only disapprove alternatives that all voters are indifferent between. Any approved alternative will be weakly preferred by all voters, and strongly preferred by at least one voter. It is a somewhat natural strengthening of Pareto optimality to require that in such cases the sometimes preferred alternative is ranked above the others. Formally, we say that a social welfare function f is strongly Pareto optimal if, for all x, y ∈ A and for all R ∈ D N with x R i y for all i ∈ N while x P i y for some i ∈ N , we have x f * (R) y. Obviously, if a social welfare function is strongly Pareto optimal, it is also Pareto optimal. Note that although for the example of Π -given above |A| = 2, the following result holds for |A| ≥ 2.

Theorem 3.2. If f is a strongly Pareto optimal social welfare function with domain W (A) N then (f, (α ud x ) x∈A ) is a preference-approval aggregator with domain Π -.

Proof: We need to verify that for all (R, B)

∈ (Π -) N , (f (R), (α ud x ) x∈A (B)) = (R, B) ∈ Π. For any x, y ∈ A, let x R y, without loss of generality. If x ∈ B, then (R, B) is a preference-approval whether y ∈ B or not. Now let x / ∈ B. For (R, B
) to be a preference-approval, we need to show that y / ∈ B. As x / ∈ B, by definition of α ud x , all voters disapprove x. Given this, the definition of Π -implies that each voter must be of one of two types: first, a voter can approve y and disapprove x; second, a voter can disapprove both and rank them as indifferent. But if any voter is of the first type, then y P x by the strong Pareto criterion, contradicting x R y. Thus all voters disapprove y, and thus y / ∈ B by definition of α ud y . Q.E.D.

Possibilities from relaxing decomposability

Our notion of decomposing a preference-approval aggregator takes place at two different levels. Theorem 3.1 requires: 1. that determining whether a specific alternative is approved is independent of the approvals of the other alternatives in the profile.

2. that the aggregation of rankings and approvals are independent of each other.

Relaxing either of these requirements leads to possibilities.

Relaxing the decomposability of the approval aggregation

We describe two families of rules that arise when we relax the internal decomposabil-ity of the approval part of a preference-approval aggregator.

Our descriptions apply to the two alternative case: well-behaved approval aggregators that work alongside any Pareto optimal social welfare function; and maximally discriminating approval aggregators that distinguish between alternatives as often as possible. However, for three or more alternatives, these descriptions can no longer be applied. We nevertheless show that there are still possibilities in the three alternative case.

Well-behaved approval aggregators

There are approval aggregators over {a, b} that create a preference-approval aggregator no matter what Pareto optimal social welfare function they are paired with. Let N be the set of non-empty proper subsets of N . Take any function g : N × N -→ {0, 1}. Define the approval aggregator α g as follows:

1.

If a is approved by all voters and b approved by none, approve only a.

2.

Else if b is approved by all voters and a approved by none, approve only b.

Else: (a)

if a is approved by no voters or b is approved by none, approve neither.

(b) if a is approved by all voters or b is approved by all, approve both. (c) otherwise, let N a be the set of voters that approve a and N b be the set of voters that approve b; if g(N a , N b ) = 1 then approve both alternatives, otherwise disapprove both.

Note that α g satisfies unanimity. Let G be the set containing all functions of type g : N × N -→ {0, 1}. One may consider an approval aggregator α as well-behaved if (f, α) is well-defined for any Pareto optimal f . That is to say, well-behaved approval aggregators are compatible with any reasonable social welfare function, if one takes Pareto optimality as a minimal requirement for a social welfare function to be reasonable. Under such an interpretation, the theorem below characterises the well-behaved approval aggregators.

Theorem 4.1. Let m = 2. If f is Pareto optimal and has domain W (A) N then for any g ∈ G, (f, α g ) defines a preference-approval aggregator with domain Π N . In the other direction, if α = α g for no g ∈ G then there is some Pareto optimal f with domain W (A) N such that (f, α) does not define a preference-approval aggregator with domain Π N .

Proof: Take f and α g as described above and let π = (f, α g ). Take a profile p = (R, B). Suppose x ∈ π 2 (p) and y / ∈ π 2 (p) for {x, y} = {a, b}.5 It suffices to show that x π * 1 (p) y. As we must be in case 1 or case 2, x is approved by all voters and y is approved by none, thus by consistency x P i y for all i ∈ N , thus by Pareto optimality x π * 1 (p) y, as desired. Now take an arbitrary approval aggregator α = α g that satisfies unanimity. This implies that the outputs given in cases 1 and 2 still apply, thus the output in one or other of 3. (a), (b) or (c) must be different. Suppose that (a) is not the case; the proof for the others is similar. This implies that there is a non-empty proper subset N x of voters such that when x is approved only by all voters in N x and y is approved by no voters, x is approved in the output and y disapproved in the output. Consider the function f such that w f (R) z if and only if w P i z for some i ∈ N . It is not hard to see that f is a well-defined Pareto optimal social welfare function, however (f , α ) is not admissible. Q.E.D.

Maximally discriminating approval aggregators

The approval aggregators of the previous subsection are very undiscriminating, which is precisely what is needed to make them compatible with many different Pareto optimal social welfare functions. On the other hand, if we start with a social welfare function, we can choose an approval aggregator that tends to discriminate between the alternatives, in terms of approvals, as much as possible.

We start with a Pareto optimal social welfare function f over {a, b}. Consider a linear order profile R ∈ L(A) N over the two alternatives with a reduced electorate N ⊆ N . We say that R is sufficient for x ∈ A if for all profiles R ∈ L(A) N with R i = R i for all i ∈ N , we have x f * (R) y where y ∈ A\{x}.

We now define an aggregator α f in terms of f . Take an arbitrary approval profile B. The total approval count is i∈N |B i |. Let I be the set of voters who approve a and disapprove b, and let J be the set of voters who b and disapprove a. Let R ∈ L(A) I∪J be such that a

P i b if i ∈ I and b P i a if i ∈ J. If R is sufficient for x ∈ A then α f (B) = {x}.
Otherwise, if the total approval count is greater than or equal to n = |N |, approve both alternatives; if the total approval count is less than n disapprove both alternatives.

One may consider an approval aggregator maximally discriminating if it classifies different alternatives into different classes as often as possible. The theorem below shows that α f is maximally discriminating if one wants to be consistent with f . Theorem 4.2. Let m = 2. If f is Pareto optimal and has domain W (A) N then (f, α f ) is a preference-approval aggregator with domain Π N . Further, if α is an approval aggregator such that for some profile B and alternative x ∈ {a, b}, α(B) = {x} but α f (B) = ∅ or α f (B) = A, then (f, α) does not define a preference-approval aggregator with domain Π N .

Proof: We first show that, for an arbitrary profile (R, B), the output of (f, α f )(R, B) = (R, B) is a preference-approval. Supposing that x ∈ B and y / ∈ B, we need to show that x P y. Because α f (B) = {x}, by the definition of α f there is a reduced electorate N and a profile R ∈ L(A) N over this reduced electorate that is sufficient for x. Furthermore, every voter in this electorate must either approve x and disapprove y; or disapprove x and approve y. Formally, for each i ∈ N , either

B i = {x} or B i = {y}. So, for each i ∈ N , because (R i , B i )
is a preference-approval and thus R i must be consistent with B i , we must have R i = R i . Because R is sufficient for x, this implies that x P y, as desired. Now suppose α is an approval aggregator such that for some profile B and alternative x ∈ {a, b}, α(B) = {x} but α f (B) = ∅ or α f (B) = A. First, consider the case α f (B) = ∅. This means that the total approval count is less than n, and that R ∈ L(A) N , N ⊆ N , is not sufficient for x, which in turn implies that there is some R such that for all i ∈ N , R i = R i but y f (R) x. Applying (f, α) to the profile (R, B) will not produce a preference-approval. Similar arguments reach the same conclusion for the case α f (B) = A. Q.E.D.

Relaxing the decomposability of the approval aggregation with three or more alternatives

For three or more alternatives, our analysis is complicated by the fact that there are Pareto optimal social welfare functions which cannot be used to create a consistent preference-approval aggregator. Ranking by the sum of Borda scores provides an example-we take the Borda score of an alternative to be the number of other alternatives it is weakly preferred to. Consider the two following preference-approval profiles, each with two voters and three alternatives.

V oter

1 a b | c V oter 2 a | c b V oter 1 b a | c V oter 2 a | b c
Note that in both profiles a must be approved and c must be disapproved, by the unanimity condition. Using Borda scoring, b is considered indifferent to c in the left profile, and indifferent to a in the right profile. This then means that b must be disapproved in the left profile and approved in the right profile, however b has the same approvals for both, thus no approval aggregator is consistent with ranking by Borda scores.

This means that for three or more alternatives there are no well-behaved approval aggregators. Nor can we find maximally discriminating approval aggregators for any given ranking function, because no approval aggregator may exist at all. So Theorems 4.1 and 4.2 cannot be interestingly extended to the case of three or more alternatives.

Nonetheless, there are still possibilities when there are three or more alternatives. Define a "disjunctive" social welfare function f * as ranking by Borda scores if any voter is completely indifferent between all the alternatives and as a copy of the first voter's preferences otherwise. Similarly, define α * such that it approves all alternatives if each alternative is approved at least once, otherwise it disapproves all alternatives if each alternative is disapproved at least once, otherwise it copies the approvals of the first voter.

Theorem 4.3. For m ≥ 2, (f * , α * ) is a preference-approval aggregator with domain Π N .

Proof: We need to check the consistency of the output. So suppose that for two alternatives x, y ∈ A, x is approved and y is disapproved. We need to show that x P y. Because x and y are in different approval classes, we must be in a profile where the first voter must have had her approvals copied. As such, no voter can be indifferent between all the alternatives, so the first voter also has her preference copied, thus x P y as desired.

Q.E.D.

Relaxing decomposability between rankings and approvals

There are also possibilities if the output ranking is allowed to depend upon the approvals in the profile. In this subsection we describe four such preferenceapproval aggregators.

Shortlist by elementary approval aggregators then rank

We first give an example of a preference-approval aggregator π I , where the approval aggregation is internally decomposed and independent of the ranking aggregation while the output ranking depends upon the approvals in the profile. Under π I , the approvals are used to select an approved shortlist, and then the ranking is performed separately upon the approved and non-approved alternatives. For x ∈ A, we define α maj x for arbitrary z ∈ {0, 1} N as α maj

x

(z) = 1 if |{i ∈ N : z i = 1}| ≥ n 2 , and α maj x (z) = 0 otherwise. Define the approval part of π I such that π I 2 (R, B) = α maj x (B).
For the ranking part, we use a local version of Borda where the score for an alternative is calculated using either only the approved or only the disapproved alternatives. First, for each X ⊆ A, let bscore X :

W (A) N -→ X -→ N be defined as bscore X (R)(x) = i∈N |{y ∈ X : x R i y}|. Define borda X : W (A) N -→ W (X) by (x, y) ∈ borda X (R) if and only if bscore X (R)(x) ≥ bscore X (R)(y).
Returning to the definition of π I , and writing B = π I 2 (R, B), let R = π I 1 (R, B) be defined by x P y for x ∈ B and y / ∈ B; x R y if and only if (x, y) ∈ borda B (R) for x, y ∈ B; and x R y if and only if (x, y) ∈ borda A\B (R) for x, y / ∈ B. If we suppose that an approval aggregator is composed of elementary approval aggregators such as α maj x , there will be many cases where either all alternatives are approved or all alternatives are disapproved. One may desire instead to try to approve half of the alternatives. It is impossible to always do so without violating unanimity, but we can create an approval aggregator that only approves all alternatives when every alternative is approved by all voters and only disapproves all alternatives when every alternative is disapproved by all voters.

Shortlist by non-decomposable approval aggregator then rank

We now describe a preference-approval aggregator π II that typically approves around half the alternatives; under π II , the approval aggregation is not anymore internally decomposed but is still independent of the ranking aggregation while the output ranking depends upon the approvals in the profile. Our informal description is iterative. First approve all alternatives that are each approved by all the voters. If more than half of the alternatives are approved, disapprove the remaining alternatives. Otherwise, from the remaining set of alternatives, approve all those alternatives with maximal approval support-repeat this step until at least half the alternatives are approved, and afterwards disapprove the remaining alternatives. Formally, define6 γ :

N -→ (A -→ N) -→ 2 A by x ∈ γ j (g) if and only if g(x) ≥ j.
Define ascore:

(2 A ) N -→ A -→ N by ascore(B)(x) = |i ∈ N : x ∈ B i |.
Note that for j < k we have γ k (ascore(B)) ⊆ γ k (ascore(B)) and that in particular, γ 0 (ascore(B)) = A and γ n+1 (ascore(B)) = ∅. These facts mean that the following definition is well-formed: Let α half (B) = γ j (ascore(B)) for the maximal j ∈ N such that |γ j (ascore(B))| ≥ m 2 . Our second preference-approval aggregator is like the first, only using the non-decomposable approval aggregator defined above. Define the approval part of π II such that π II 2 (R, B) = α half (B). For the ranking part, and writing

B = π II 2 (R, B), let R = π II 1 (R, B
) be defined such that x P y whenever x ∈ B and y / ∈ B; x R y if and only if (x, y) ∈ borda B (R) for x, y ∈ B; and x R y if and only if (x, y) ∈ borda A\B (R) for x, y / ∈ B.

Perform ranking aggregation then approve according to the ranking

We now consider a function π III whose ranking aggregation is independent of approvals while the output approvals depend upon the rankings in the profile.

There is a somewhat trivial family of examples here: perform ranking aggregation by any desired method, and approve some fixed number or proportion of alternatives. This method completely ignores the input approvals, so the output ranking is obviously independent of the approvals in the profile. For an example social welfare function, we consider Borda ranking. Formally, define the ranking part of π III such that π III 1 (R, B) = borda A (R). For the approval part, let π III = γ j (bscore(R)) for the maximal j ∈ N such that |γ j (bscore(R))| ≥ m 2 . Note that B occurs nowhere in the definition of π III ; the output completely ignores the input approvals.

Borda with a movable zero determined by the zero-line

For completeness, we also describe a natural function π IV for which both the ranking and the approvals are interdependent. Suppose that each voter assigns a score to each alternative depending upon how many alternatives there are in between the alternative and the zero-line, with a positive or negative score respectively if the alternative is above or below the zero-line; for each alternative, sum their scores; rank the alternatives according to their sum, and disapprove any and only alternatives with a sum strictly less than zero. This may be thought of as Borda ranking with a movable zero-note that although the idea behind this is natural, the detailed definition requires some arbitrary decisions. For π IV , first define mscore:

Π → A → N by mscore(R, B)(x) = |{y ∈ B : x R y}| if x ∈ B, 0 -|{y ∈ A\B : y R x}| if x / ∈ B Define π IV (R, B) = (R, B) by x R y if and only if i∈N mscore(R i , B i )(x) ≥ i∈N mscore(R i , B i )(y) and x ∈ B if and only if mscore(R i , B i )(x) ≥ 0.

Extending the impossibility to more evaluation levels

The impossibility of combining the ordinal and evaluative approaches also applies to the case where there are more than two evaluation levels. In order to consider multiple evaluation levels we must extend the preference-approval framework, which requires more definitions that immediately follow.

Denote by E a set of possible evaluations, |E| ≥ 2. A preference-evaluation is a pair v = (R, s) where s : A -→ E is a sorting function into |E| categories. 7 We suppose that there is a linear order on E. A preference-evaluation v = (R, s) is consistent with if x R y implies s(x) s(y). Let Ω be the set of consistent preference evaluations. The existence of a linear order on E is central to our interpretation of the evaluative approach. For e, e ∈ E, the interpretation of e e is that e is a better evaluative category than e . Consistency with ordinal preference states, roughly speaking, that it is impossible to prefer a worse category to a better category.

A preference-evaluation aggregator is a function ω : Ω N → Ω. We say that ω is dictatorial if there is a voter d whose strict preference and evaluations are reproduced in the output preference-evaluation

; i.e., d ∈ N is a dictator if for all v = ((R 1 , s 1 ), ..., (R n , s n )) ∈ Ω N we have ω(v) = (R, s d )
where R is some ranking such that x P y if x P d y for all x, y ∈ A.

An elementary-evaluation aggregator for an alternative x is a function η x : E N -→ E. For j ∈ {1, ..., m}, we typically shorten η aj to η j . Such a function satisfies unanimity if η x (t, . . . , t) = t for all t ∈ E. We write ω = (f, η 1 , . . . , η m ) if for every ((R 1 , s 1 ), ..., (R n , s n )) ∈ Ω N we have ω((R 1 , s 1 ), ..., (R n , s n )) = (f (R 1 , ..., R n ), s) where s(x) = η x (s 1 (x), ..., s n (x)) for all x ∈ A. Note that this implicitly means that ω can be decomposed into a ranking part f and m evaluation parts η j , one for each alternative a j ∈ A.

Theorem 5.1. Any preference-evaluation aggregator ω = (f, (η x ) x∈A ) such that η x satisfies unanimity for all x ∈ A is dictatorial.

Proof: Take a preference-evaluation aggregator ω as in the statement of the theorem. We first show that f satisfies Pareto optimality. We then show that every pair of evaluation categories has a "local" dictator. Such a local dictator must be a dictator on the ranking function-this implies that all such local dictators coincide. Finally, we argue that this voter is also an evaluation dictator.

Take any a, b ∈ A and any R with a P i b for all i ∈ N . To establish a f * (R) b, take e 1 , e 2 ∈ E with e 1 e 2 and define s such that for all i ∈ N and for all x ∈ A, s i (x) = e 1 whenever x R i a and s i (x) = e 2 otherwise. For each i ∈ N , (R i , s i ) is a preference-evaluation consistent with . By unanimity, ω 2 (R, s)(a) = e 1 and ω 2 (R, s)(b) = e 2 . By consistency of the output, a f * (R) b, thus f satisfies Pareto optimality.

Let ω = (f, (η x ) x∈A ) : Ω N → Ω such that f is Pareto optimal and η x satisfies unanimity for all x ∈ A. Take an arbitrary pair of evaluation categories e, e ∈ E. Write Ω| e,e = Ω ∩ (W (A) × {e, e } A ). There is a voter d e,e = d such that for all (R, s) ∈ (Ω| e,e ) N , for x ∈ A and ω(v) = (R, s) we have s d (x) = s(x), otherwise we can translate ω with its domain restricted to (Ω| e,e ) N into a preference-approval aggregator that violates Theorem 3.1.

We now argue that d is a dictator over f . Take arbitrary x, y ∈ A and R ∈ W (A) N such that x P d y. Without loss of generality, suppose e e . Consider a profile s such that s d (z) = e for all z ∈ A with z R d x; s d (z) = e for all z ∈ A with x R d z; and s i (z) = e for all i ∈ N \{d} and for all z ∈ A. This s forms a consistent preference-evaluation profile when combined with R. By consistency, for ω(R, s) = (R, s), x P y. Thus x f * (R) y if and only if x P d y. Note that this implies d e,e = d e ,e for any e, e , e , e ∈ E.

Finally we argue that d is also an evaluation dictator. Take arbitrary x ∈ A and s ∈ (E A ) N . We want to show that η x (s) = s d (x). Write e = s d (x), and pick some y ∈ A\{x}. Consider some profile s where for all i ∈ N , s i (x) = s i (x) and s i (y) = e. Consider any profile R such that x P d y and that is consistent with s , note that such a profile exists. By unanimity, for ω(R, s ) = (R, s), s(y) = e. By dictatorship of d on f , x P y. By consistency, s(x) s(y) = e. Similar to above, consider any profile R such that y P d x and that is consistent with s , and write ω(R , s ) = (R , s ). By a similar chain of arguments, s (y) s (x),

thus s (x) = e. Because for each i ∈ N , s i (x) = s i (x), η x (s) = s d (x). Q.E.D.
By allowing more than two evaluation levels, Theorem 5.1 generalizes Theorem 3.1. We nevertheless present the two theorems separately. One reason for this is because we do not see an obvious direct proof of Theorem 5.1 that does not use Theorem 3.1. Moreover, it is less obvious how the possibilities expressed in Section 4 (which hold even when the social welfare function is required to be Pareto optimal) apply when there are more than two evaluation levels-while positive results are possible, the extra technicalities are cumbrous and would clutter the results. We do not consider domain restrictions when there are more than two evaluation levels for similar reasons.

Final remarks

There is a view that social choice should be performed using evaluations rather than rankings. In fact, the literature contains several examples of social choice procedures that use evaluations, including approval voting [START_REF] Brams | Approval voting[END_REF], threshold aggregation involving three-graded rankings [START_REF] Aleskerov | A 'threshold aggregation' of three-graded rankings[END_REF][START_REF] Alcantud | Dis&approval voting: a characterization[END_REF], utilitarian voting [START_REF] Hillinger | The case for utilitarian voting[END_REF] and range voting [START_REF] Gaertner | A general scoring rule[END_REF][START_REF] Pivato | Formal utilitarianism and range voting[END_REF][START_REF] Zahid | The Borda majority count[END_REF][START_REF] Macé | Voting with evaluations: characterizations of evaluative voting and range voting[END_REF]. A further example is majority judgment, introduced by [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF], which selects the alternative with the highest median evaluation.

To be sure, the median has earlier 8 usages as a social choice rule, for example by [START_REF] Bassett | Robust voting[END_REF] who apply it within the traditional Arrovian ranking framework, however it should be noted that majority judgment can choose between alternatives with tied highest median, which (depending on the setting) may significantly reduce the size of the chosen set. Balinski and Laraki's contribution goes beyond this extra tiebreaking step: they provide a whole framework within which evaluative methods can be analysed. 9 Part of their defense of majority judgment consists of a defense of the evaluative approach as a whole, for example they claim that "the central problem becomes how to transform many individual grades of a common language into a single collective grade where the individuals may have unknown preferences that are too complex to be formulated. Sharing a common language of grades makes no assumptions about a voter's or a judge's utilities or preferences." (Balinski and Laraki 2011, p. xiii, their italics.) The debate between defenders of ranking aggregation and defenders of evaluation aggregation goes back to the early days of approval voting, 10 but has been reactivated by the work of Balinski and Laraki. 11 This literature not only notes that particular evaluative methods are incompatible with majoritarianism conditions defined on social welfare functions (such as our example in the introduction) but reflects an incommensurability between the two approaches which is substantiated by our results. In fact, Theorem 5.1 shows that when unanimous evaluation aggregators are used, dictatorship is the only consistent way to independently aggregate rankings and evaluations. Even dictatorship fails to work when the social welfare function is assumed to satisfy mild conditions such as near unanimity, where if everyone except one voter ranks an alternative top, this alternative should be ranked top in the output. In brief, caution is advised in searching for a compromise that combines the two approaches by allowing individuals to have both rankings and evaluations. 12 The impossibilities expressed by Theorems 3.1 and 5.1 depend on decom-8 As noted by Jean-François Laslier, methods that implicitly select the alternative with the highest median have been rediscovered many times. As well as Bucklin voting (used under this name in the early 20th century) and majoritarian compromise [START_REF] Sertel | The majoritarian compromise is majoritarian-optimal and subgame-perfect implementable[END_REF], such a method was proposed as early as 1793 by Condorcet (McLean et al. 1994). 9 Later work picks up this approach and compares different evaluative methods within an evaluative framework, for example work by [START_REF] Brams | The paradox of grading systems[END_REF].

10 Consider the back-and-forth between [START_REF] Saari | The problem of indeterminacy in approval, multiple, and truncated voting systems[END_REF], [START_REF] Brams | The responsiveness of approval voting: Comments on Saari and Van Newenhizen[END_REF], [START_REF] Saari | The problem of indeterminacy in approval, multiple, and truncated voting systems[END_REF] and again Brams et al. (1988a).

11 For example: [START_REF] Balinski | A theory of measuring, electing, and ranking[END_REF], [START_REF] Felsenthal | The majority judgement voting procedure: a critical evaluation[END_REF], [START_REF] Brams | Grading candidates[END_REF], [START_REF] Edelman | Review of majority judgment: measuring, ranking and electing[END_REF], [START_REF] Balinski | Majority Judgment vs Majority Rule[END_REF] and [START_REF] Laslier | L'étrange "jugement majoritaire[END_REF].

12 The preference-approval framework that we treat in this paper can, as Sanver (2010) discusses, be mathematically placed within the traditional literature of social welfare functionals [START_REF] Sen | On weights and measures: informational constraints in social welfare analysis[END_REF] where cardinal or interpersonal comparisons are allowed. Preference-approvals present a weak version of ordinal level comparisons (OLC) which are explored by [START_REF] Roberts | Possibility theorems with interpersonally comparable welfare levels[END_REF]. The closest previous work of this type that we are aware of is due to [START_REF] List | A note on introducing a "zero-line" of welfare as an escape route from Arrow's theorem[END_REF], who considers a narrow informational addition that he calls OLC+0, which only allows a single level of ordinal comparability. This is almost equivalent to the preference-approval framework, but it allows for alternatives to be on the zero-line, thus there is a third evaluative category within which indifference is forced. Also, List's results concern functions that produce choice sets or ordinal rankings, not functions that output preference-approvals or their equivalent.

posing the ranking and evaluation aggregators from each other (which embodies the incommensurability between the two approaches) but also on the decomposability of the evaluation aggregation itself. This latter decomposability is satisfied by every evaluative method that we are aware of; indeed, [START_REF] Balinski | Majority Judgment: Measuring, Ranking, and Electing[END_REF] argue that this decomposability is the correct interpretation of the independence property.

To justify our interest in decomposability, let us expand upon the analogy to the traditional issue concerning Arrovian independence. To determine social ranking between two alternatives, one can very well use information about how voters compare these to a third alternative. In fact, we know by Arrow's Theorem that this must be the case (if one wants a sensible ranking aggregation). One may like or dislike Arrovian independence as a principle of ranking aggregation but it is important to know that ranking aggregation is not decomposable into pairs. In a similar vein, one may like or dislike decomposability between ranking and evaluation aggregation as a principle, but it is worth knowing that such a decomposition is not possible.

When decomposability is relaxed there are various possibilities, as described in Section 4. In particular, relaxing the internal decomposability of the approval aggregation leads to the possibilities given by Theorem 4.1 and Theorem 4.2. More generally, we can structure the space of possible preference-approval aggregators along two axes. One axis imposes restrictions upon the ranking part of the aggregation: the strongest restriction here is a version of binary independence applied to preference-approval aggregators, which requires that the output ranking of each pair only depends upon the input rankings of these pairs. Binary independence can be weakened to the condition that the ranking aggregation only depends upon the ranking part of the profile, i.e., that the ranking aggregation is independent of approvals. Finally, there are aggregators with no restriction on the ranking aggregation. The second axis imposes restrictions on the evaluative part of the aggregation: the evaluations of each alternative can be computed independently of any other information; or can depend upon the evaluations of all the alternatives; or can be calculated using all the information from the profile. This structure, and various possibilities and impossibilities within, is drawn in Table 1 below. The results of the table only apply to preference-approvals, not to preference-evaluations. The first column expresses the restrictions on the evaluative part of aggregation (we suppose that the evaluative part respects unanimity) and the first row expresses the restrictions on the ranking part of the aggregation. Theorem 3.2 gives some possibilities on one natural domain restriction in the preference-approval framework. We do not know if there are other interesting domain restrictions that would lead to similar results, but believe that there is potential further work to be done concerning extensions of the single-peaked or single-crossing conditions to the preference-approval framework.

As a final note, it may be wondered: given that we consider a particular form of aggregation, can we embed our work into a more general aggregation [START_REF] Wilson | On the theory of aggregation[END_REF], [START_REF] Nehring | Arrow's theorem as a corollary[END_REF], or [START_REF] Maniquet | A theorem on aggregating classifications[END_REF] provide possibilities, but perhaps the most promising general framework would be that of judgment aggregation [START_REF] List | Judgment aggregation: a survey[END_REF] and [START_REF] Mongin | The doctrinal paradox, the discursive dilemma, and logical aggregation theory[END_REF] provide surveys). It is relatively easy to express preference-approvals with linear rankings in the judgment aggregation framework. One way of doing so is to follow the method used to embed Arrow's theorem into judgment aggregation [START_REF] Dietrich | Arrow's theorem in judgment aggregation[END_REF]: assign a two-place predicate representing strict preference, and a one-place predicate representing approval, and add rationality conditions for asymmetry, transitivity, connectedness, and consistency of approval with preference. Alternative embeddings that instead use propositional logic are equally possible. However, imposing the axiom of independence (in the judgment aggregation sense) in these settings is a much stronger restriction than the decomposability that we apply in our work. More precisely, any impossibility result that would be obtained for this embedding would only correspond to the top-left cell of Table 1. Further, it is yet more work to apply this process to weak orders. To fully recreate our results, we would need to apply a weaker version of the axiom of independence in the judgment aggregation setting, which would require something along the lines of the generalised definitions of Dietrich (2015). 14 7 Appendix: Limited possibilities in the presence of binary independence

During the review process, we became aware that all the cases of Table 1 are not fully covered in the main text. Specifically, we do not cover the cases where there are three or more alternatives, the ranking aggregation satisfies binary independence and either (1) the approval aggregation is independent of rankings or (2) there is no restriction on the approval aggregation; i.e., the bottom-left and middle-left cells of the table. Indeed, there are limited possibilities in these cases, a fact brought to our attention by Clemens Puppe. The issue is further complicated as our Theorems 3.1 and 5.1 do not assume Pareto optimality, thus binary independence only gets us [START_REF] Wilson | Social choice theory without the Pareto principle[END_REF] result as opposed to [START_REF] Arrow | A difficulty in the concept of social welfare[END_REF].

We will now briefly sketch these limited possibilities. We classify these in terms of ( 1) and ( 2) given above and in terms of the orthogonal axis provided by Wilson's theorem: either (i) the ranking part always returns complete indifference between all alternatives; or (ii) there is a ranking dictator; or (iii) there is a ranking anti-dictator.

We will first suppose that there is no restriction on the approval rankings (1). If the ranking part always returns full indifference between the alternatives (1i), then the evaluative part cannot distinguish the alternatives: for each evaluative profile, all alternatives must be approved or disapproved. Roughly speaking, if the ranking part is "null", the evaluative part must be similarly "null". Now suppose that there is a ranking dictator (1ii). The evaluations must follow the ranking of this dictator, in the sense that if she evaluates x better than y, then x must be ranked better than y in the output of the aggregator. If two alternatives are placed in the same evaluative class by the dictator, then they must also be placed in the same evaluative class by the aggregator, because the dictator may rank either alternative better than the other. Finally, unanimity must be respected. Altogether, given two evaluative categories, the approval aggregator must be of the following form. For each evaluative profile, there are three possibilities, two of which require further conditions: first, the output evaluations are identical to that of the dictator. Second, all alternatives are approved, this requires that no alternative is unanimously disapproved by all voters. Third, all alternatives are disapproved, this requires that no alternative is unanimous approved by all voters. The case of a ranking anti-dictator is symmetric (1iii).

We now move to the case where there is no restriction on the approval aggregation (2). Technically, our definition of alternative-wise unanimity does not apply to non-decomposed preference-approval aggregators, but one can imagine that we impose a natural such translation of this axiom to such aggregators. Then the possibilities of (2i) are almost identical to the (1i) case: for each preference-approval profile, all alternatives must be approved or disapproved.

The case of (2ii) provides richer possibilities than (1ii). In particular, for every preference-approval profile, there is some threshold in the ranking dictators

3

  Take any a, b ∈ A. Let a P d b which, by definition of p, implies a p * d b. As f is dictatorial, we have a f * (p)b which, by construction of f , gives a π(p) * b, implying a P b, as desired. Now, let a ∈ B d which, by definition of p, implies a p * d z. As f is dictatorial, we have a f * (p)z which, by construction of f , gives a π(p) * z, implying a ∈ B, proving that π is dictatorial. Q.E.D.

The term "alternative-wise" indicates a distinction from a weaker version of unanimity which requires that if all voters have exactly the same evaluations for all the alternatives, then the output evaluations are identical. We do not consider the weaker version of unanimity in this paper.

By g(R)| {x,y} , we mean the restriction of g(R) over {x, y}, i.e., the ranking of {x, y} as in g(R). In a similar vein, R| {x,y} is the restriction of R over {x, y}, i.e., the preference profile over {x, y} where each i ∈ N orders {x, y} as in R i .

To ease presentation, we transpose the Cartesian product without comment, i.e., when we write (R, B), where R = (R 1 , ..., Rn) and B = (B 1 , ..., Bn), we are technically referring to the profile ((R 1 , B 1 ), ..., (Rn, Bn)).

The restriction to the domain Π -is reasonable for many applications of the preferenceapproval framework. Suppose we need to select a date for a meeting; attendees may have preferences over those dates they can attend, but it seems reasonable to assume that they would be indifferent between those dates that they are unavailable.

For preference-approval aggregators, and other functions that return pairs, sometimes we will want to isolate the first or second coordinate of the returned value. We do this by subscripting the function with 1 or 2. Generally, for a function of type h : X -→ Y × Z, we write h 1 for the projection of the function onto the first coordinate and h 2 for the projection of the function onto the second coordinate, i.e., for h(x) = (y, z) we have h 1 (x) = y and h 2 (x) = z.

Our definitions here are given in functional style, i.e., functions are used as arguments. We assume left associativity of expressions, i.e., h(i)(x) is (h(i))(x), indeed we will typically write h i (x); and that we assume right associativity of type definitions, i.e., h : X -→ Y -→ Z is implicitly h : X -→ (Y -→ Z).

If one thinks of 2 as the set {0, 1}, our previous definition of preference-approvals comprises the special case where E = 2.

In particular we thank Phillipe Mongin for considerable efforts made in this direction.

We thank Clemens Puppe for these observations.

* Our work is partly supported by the projects ANR-14-CE24-0007-01 "CoCoRICo-CoDec" and IDEX ANR-10-IDEX-0001-02 PSL* "MIFID".