Amílcar Mata Díaz

Ramón Pino

Pérez Jahn

Franklin Leal
email: jleal@ula.ve

Ramón Pino Pérez
email: pinoperez@cril.fr

Franklin Jahn

Leal

Keywords: Manipulation, Social Choice, Lifting, Preferences, Powerful Voters Mathematics Subject Classification (2010) 91B12, 91B14

In this work we pursue the study of manipulability of social choice functions through "liftings", that is, mappings which extend orderings over points to orderings over subsets of points. We discover a very weak notion of monotony which is closely related to independence of irrelevant alternatives. This allows us to establish an interesting and general theorem on manipulability. We show that this theorem is indeed equivalent to Arrow-Sen Theorem in the class of nonmanipulable social choice functions. As a consequence of this general theorem we obtain a manipulation theorem for linear profiles in the style of Gibbard-Satterthwaite Theorem but for social choice functions instead of voting schemes. We introduce the notion of nominator, which is a natural generalization of the notion of pairwise nominator introduced by Kelly. Then, we establish that, in the presence of rational properties over liftings, a social choice function is either manipulable, or it admits a nominator. In addition, we do a comparative study on different types of powerful voters (dictators, nominators, pairwise nominators and weak-dictators) present in the literature. Although, in general, they are non-equivalent notions, we show that under some natural conditions, modulo nonmanipulability, the last three are equivalent or even all the notions are equivalent.

Taxonomy of powerful voters and manipulation in the framework of Social Choice Functions

Let us note that many among the known results about manipulability are a sort of dichotomy in the style of Gibbard-Satterthwaite Theorem: any "normal" voting process is manipulable or dictatorial. Or, it can be put in the following form: for the "normal" voting processes, if they are nonmanipulable then they are dictatorial. Actually, in the case of Gibbard-Satterthwaite Theorem, a "normal" voting scheme has at least three outputs and that theorem can be seen, without effort, as a characterization of dictators: a "normal" and resolute voting scheme is nonmanipulable if and only if it is dictatorial. We will see that in more general cases this equivalence fails. It is possible to have dictatorial functions which are manipulable (see Observation 7).

In a more abstract and general manner, most results about manipulability have the following logical structure: under certain conditions of normality, a kind of nonmanipulability entails the existence of a powerful voter (dictator, nominators, etc.). In this work we establish some results of this sort, and we include an analysis of the different classes of powerful voters and their relationships.

We establish three theorems about manipulability for social choice functions. 1 In the first theorem (Theorem 2), a fundamental result in our work, the normality conditions are standard domain, transitive explanations, pairwise nonimposition plus pairwise indifference (see Section 2 and 3 for the definitions). This last condition is a weak form of monotony; it is a novel and very important notion which is equivalent to independence of irrelevant alternatives under the hypothesis of nonmanipulability. Then, under these conditions, the nonmanipulable functions for a G-lifting admit a dictator. As a matter of fact, we prove that in the class of nonmanipulable social choice functions, Arrow-Sen impossibility theorem and Theorem 2 are equivalent (cf. Theorem 3). Our second manipulability theorem (Theorem 4) is essentially a consequence of our first fundamental theorem. In Theorem 4 the normality conditions are standard domain, transitive explanations and pairwise nonimposition. Then, under these conditions and restricted to linear profiles, the nonmanipulable functions are exactly the dictatorial functions. In our third result (Theorem 5, where we consider again all kinds of profiles), the normality conditions are the same, i.e., standard domain, transitive explanations and pairwise nonimposition. Then, under these conditions, the nonmanipulable functions for a G-lifting admit a nominator.

Concerning the taxonomy of powerful voters: dictators, nominators, pairwise nominators and weak-dictators (see Section 2 for the definitions), we establish four results. The first one (Theorem 6) is that the classes of these powerful voters form a strict hierarchy. The second one (Theorem 7) is that the classes of nominators and pairwise nominators coincide under the hypothesis of transitive explanations. The third one (Theorem 8) is that all the classes coincide under the hypotheses of resoluteness, nonmanipulability and transitive explanations. The fourth result (Theorem 9) is that nominators, pairwise nominators and weak-dictators coincide under the hypotheses of transitive explanations and nonmanipulability with respect to one G1-lifting. Figure 3 summarizes these results.

The rest of this work is organized as follows: Section 2 contains the fundamental notions and tools used to present the ideas of this work. Section 3 contains our results of manipulability. Section 4 is devoted to the taxonomy of powerful voters. It contains the study of the relationships between them. Section 5 contains some remarks about related works. Finally, in Section 6 we conclude with some final remarks and perspectives.

Preliminaries

In this section, we briefly introduce some fundamental notions and tools needed for developing the main ideas of this work. Namely, we establish some basic notions concerning preferences, liftings and social choice functions.

Orderings and Liftings

A preorder over a set X is a binary relation, , which is reflexive and transitive. Given a preorder , we define the strict relation , and the indifference relation , both associated to , respectively, as follows: x y iff x y and y x; and x y iff x y and y x.

Given a preorder over X and a subset A of X, we say that a is a maximal (resp. minimal) element of A, with respect to , iff a ∈ A and there is no x ∈ A such that x a (resp. a x). The set of maximal (resp. minimal) elements of A, with respect to , will be denoted max(A, ) [resp. min(A, )]. From now on, we will write max( ) [resp. min( )] instead of max(X, ) [resp. min(X, )] in order to denote the set of maximal (resp. minimal) elements of the whole set X. We will denote by

A the restriction of to the set A. An important class of preorders is that consisting of total preorders, which are total (then reflexive) and transitive binary relations. It is important to note that, if is a total preorder over a set X and A is a subset of X, then a in A is one of its maximal elements, with respect to , iff a x, for all x in A. The set of total preorders over X will be denoted by P(X).

Simple examples of total preorders are given by linear orders and the flat order. 2 An interesting example of a total preorder is the lexicographical combination of two total preorders. Consider two total preorders, 1 and 2 , over a set A. We define lex ( 1, 2) , the lexicographical combination of 1 with 2 , by putting:

x lex( 1, 2) y ⇔ x 1 y, or x 1 y & x 2 y
A more complex class of total preorders is that of precise-leximax orders, introduced by Leal and Pino Pérez [START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF]. These types of orders are defined over finite ordered tuples of different elements of a finite nonempty set X. More precisely, given a total preorder over a set X with n elements, we define the precise-leximax order Plmax over the set V ↓ X (the set formed by all the vectors of size less or equal to n whose inputs are not repeated elements of X, ordered in decreasing manner by ) as follows, for every couple of vectors -→ x = (x 1 , x 2 , . . . , x k ), -→ y = (y 1 , y 2 , . . . , y m ) in V ↓ X :

-→ x Plmax -→ y ⇔ k ≤ m and x i y i , for all i ≤ k, or there is j ≤ min{k, m} : x i y i , for all i < j and x j y j It is not hard to see that precise-leximax orders are actually total preorders. Note that when a vector is an initial segment of another, then, in the preciseleximax orders, the vector which is the initial segment is bigger than the other, as in the antilexicographical order. Otherwise, the behaviour of a preciseleximax order is as that of the lexicographical order.

It is well known that every total preorder over a set X is given by a ranking function f : X -→ E where E is linearly ordered by a relation ≥ and f (x) ≥ f (y) iff x y. When a total preorder is finite, the ranking functions representing it can be defined taking values in the natural numbers with the usual order. From now on we consider the canonical ranking function, r , associated to a total preorder over X: r (x) = max{n ∈ N : ∃ x 0 , x 1 , . . . , x n ∈ A; x i+1 x i and x n = x} A preorder might be seen as a preference or plausibility measure over the elements in X: x y expresses that x is at least as preferred as y, x y means that x is more preferred than y, while x y says that x and y are indifferent. This classical point of view about preferences will be adopted from now on in this work.

It is possible to extend preferences over single elements of a set X to preferences over its subsets in different rational manners. This can be done either quantitatively or qualitatively. Perhaps the first methods have been quantitative and related to probability. Actually, if p is a probability measure over a finite nonempty set X, we can see p as a representation of the preferences (in this case the plausibility) over X as follows: x y iff p({x}) ≥ p({y}). As p extends additively the preferences of points in X to subsets (events) of X, we can define the probabilistic relation p over P(X) (the powerset of X) as follows:

A p B iff p(A) ≥ p(B).
The idea of using qualitative methods to extend preferences over points to preferences over sets of points goes back to the work of Bruno de Finetti [START_REF] De Finetti | La prévision: Ses lois logiques, ses sources subjectives[END_REF], in which he searches to characterize qualitative probabilities. Actually, this important idea has been considered in logical frameworks by Halpern [START_REF] Halpern | Defining relative likelihood in partially-ordered preferential structures[END_REF], van Benthem, Girard and Roy [START_REF] Van Benthem | Everything else being equal: A modal logic for ceteris paribus preferences[END_REF], and Mata Díaz and Pino Pérez [START_REF] Mata Díaz | Epistemic states, fusion and strategy-proofness[END_REF][START_REF] Mata Díaz | Manipulability in logic-based fusion of belief bases: Indexes vs. liftings[END_REF][START_REF] Mata Díaz | Merging epistemic states and manipulation[END_REF].

An application → which maps any total preorder over a set X into a preorder over P(X), will be called a lifting if the following property holds: {x} {y} iff x y

From now on, given a total preorder , the preorder will also be called a lifting of .

In the literature concerning manipulability, there are several specific and well known liftings. Next, we present some examples of these extensions. The first lifting to be presented, which is a very standard one, is called possibilistic lifting, → Π . This idea (in a preliminary form) goes back to Shackle [START_REF] Shackle | On the meaning and measure of uncertainty[END_REF][START_REF] Shackle | Uncertainty in economics and other reflections[END_REF] and it was proposed in different forms by Lewis [35], Spohn [START_REF] Spohn | Ordinal conditional functions: A dynamic theory of epistemic states[END_REF], Dubois, Lang and Prade [START_REF] Dubois | Possibilistic logic[END_REF], Friedman and Halpern [START_REF] Friedman | Plausibility measures and default reasoning[END_REF], and others.

A Π B iff there exists x in max(A, ) and y in max(B, ) s.t. x y For a fixed total preorder over a set X, Π is actually a total preorder over P(X), as can be easily shown. The relation Π can be seen as a "comparative possibility" relation associated with the plausibility measure , as it was highlighted by Dubois, Lang and Prade [START_REF] Dubois | Possibilistic logic[END_REF]. Actually, A Π B expresses that the "best" elements in A are at least as good as the "best" elements in B, with respect to .

Analogously, we can define the pessimistic lifting, → W . This lifting has been addressed in decision making (cf. [START_REF] Barberà | Ranking sets of objects[END_REF][START_REF] Duggan | Strategic manipulability without resoluteness or shared beliefs: Gibbard-satterthwaite generalized[END_REF][START_REF] Taylor | The manipulability of voting systems[END_REF][START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]) as well as in logical frameworks (cf. [START_REF] Lang | From belief change to preference change[END_REF]). It says that the "worst" elements in A are at least as good as the "worst" elements in B:

A W B iff there exists x in min(A, ) and y in min(B, ) s.t. x y Another classical lifting in the literature is Kelly lifting, → K , introduced by Jerry Kelly [START_REF] Kelly | Strategy-proofness and social choice functions without singlevaluedness[END_REF]. This lifting expresses that the "worst" elements in a set A are at least as good as the "best" elements in a set B. More specifically:

A K B iff A = B
or for all x in A and for all y in B, x y

The following lifting to be presented is the precise-leximax lifting, denoted by Plmax . This lifting was proposed by Leal and Pino Pérez [START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF] as a variant of Moulin lifting, introduced by Hervé Moulin [START_REF] Moulin | Axioms of cooperative decision making[END_REF], and the leximax lifting (cf. [START_REF] Barberà | Ranking sets of objects[END_REF][START_REF] Bossert | Ranking opportunity sets: an axiomatic approach[END_REF][START_REF] Camacho | Leximax relations in decision making through the dominance plausible rule[END_REF][START_REF] Camacho | Decision-making through dominance plausible rule: New characterizations[END_REF][START_REF] Dubois | A unified framework for order-of-magnitude confidence relations[END_REF]). In order to define it, we will use the precise-leximax orders over V ↓ X . For every subset C of X and every total preorder over X, we will consider [C] , the subset of V ↓ X formed by all the vectors of length |C| whose inputs are in C:

A Plmax B iff for all - → y in [B] there exists - → x in [A] s.t. - → x Plmax - → y
This lifting tries to capture the idea that one has to prefer a group of alternatives which is smaller than another group of alternatives if the alternatives of the first group are at least as preferred as the alternatives of the second group. In order to give a real example of this kind of preference, we can imagine that alternatives are workers and for economical reasons (e.g. economy of salaries) a corporation prefers a team of workers with the same degree of skills as another one if the former has fewer persons. Some properties of liftings have been studied in ordering theory. An important example of such properties are the simple dominance conditions introduced by Peter Gärdenfors [START_REF] Gärdenfors | Manipulation of social choice functions[END_REF][START_REF] Gärdenfors | On definitions of manipulation of social choice functions[END_REF] in a general form and deeply studied by Barberà, Bossert and Pattanaik [START_REF] Barberà | Ranking sets of objects[END_REF] in the form proposed here. 3Simple dominance 1: {x, y} {y}, whenever x y. Simple dominance 2: {x} {x, y}, whenever x y.

The simple dominance conditions will be called companionship properties because they have a very natural interpretation: simple dominance 1 expresses that "good company" improves the group; while simple dominance 2 tells us that "bad company" worsens the group. These properties have also been considered in the computational social choice framework by Christian Geist and Ulle Endriss [START_REF] Geist | Automated search for impossibility theorems in social choice theory: Ranking sets of objects[END_REF], whose work concerns the automatized search of impossibility theorems.

A lifting that satisfies simple dominance 1 will be called G1-lifting, while that for which simple dominance 2 holds will be called G2-lifting. A lifting for which both instances of simple dominance hold will be denominated G-lifting (all the G's in honour of Gärdenfors). It is not hard to see that Kelly lifting and the precise-leximax lifting are actually instances of G-liftings, in contrast to the possibilistic lifting which is a G1-lifting for which simple dominance 2 does not hold, or the pessimistic lifting which is a G2-lifting that does not satisfy simple dominance 1, as can be easily verified.

From now on, we will focus on these types of liftings, that is, those that satisfy one or both of companionship properties. Other well known examples of this kind of liftings are the Fishburn lifting [START_REF] Fishburn | Even-chance lotteries in social choice theory[END_REF] and the Gärdenfors lifting [START_REF] Gärdenfors | Manipulation of social choice functions[END_REF].

Social choice functions and Arrow's impossibility theorem

In order to introduce the notion of social choice function, we will present some notation and special sets that will be used throughout this work. From now on, N = {1, 2, . . . , n} will denote a finite set of voters; X = {x, y, z, . . . } will denote a finite set of alternatives. The ballot (or preference) of a voter i will be given by a total preorder i over X. A profile of ballots (or simply profile) is an n-tuple P = ( 1 , 2 , . . . , n ), which collects the ballots of all the voters in N , in an ordered manner. We will say that P is a linear profile if each i in P is a linear order over X. The set of all the profiles of ballots will be denoted P n (X). An agenda is a nonempty set A formed by alternatives in X. An agenda contains only those alternatives which are available for choice. We denote by P * (X) the set of all agendas. Given an agenda A and a profile P = ( 1 , 2 , . . . , n ), we denote by P A , the restriction of P to the agenda A, that is, P A = ( 1 A , 2 A , . . . , n A ). We will denote by P [ * /i] the profile obtained from profile P by replacing ballot i , in its input i, by ballot * .

A social choice function is a map F : P n (X) × P * (X) → P * (X), such that for every profile P and agenda A, if F (P, A) is defined then F (P, A) ⊆ A. Thus, F might be a partial function. 4 By tradition, F P (A) denotes F (P, A).

We will say that F is a resolute social choice function if the outputs, when defined, are singletons.

The most trivial social choice function is that which we call the indifference function: I P (A) = A, for every agenda A and every profile P . For this social choice function, no matter what the voters express, all the available alternatives will be chosen. Another example of social choice function is the dictatorship function: given a fixed voter d in N , we define D P (A) = max(A, d ), for every agenda A and every profile P . Thus, this function is fully determined by the preferred alternatives of the voter d. As a counterpart of this last function, we have the anti-dictatorship function, which was presented by Taylor [START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]: T P (A) = min(A, d ), for every agenda A and every profile P . Converse to the dictatorship function, the anti-dictatorship function is determined by the less preferred alternatives of an agent d. Many other examples can be found in the literature (cf. [START_REF] Arrow | Handbook of Social Choice and Welfare[END_REF][START_REF]Handbook of Computational Social Choice[END_REF][START_REF] Kelly | Social Choice Theory: An Introduction[END_REF][START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]).

The following properties were proposed by Arrow [START_REF] Arrow | Social choice and individual values. 1st Edition[END_REF] as a set of suitable features that a reasonable social choice function F has to satisfy: 5Standard domain (SD): F is a total function and X has at least three alternatives. Pareto condition (PC): If P = ( 1 , 2 , . . . , n ), x i y for every i in N and x is in A, then y is not in F P (A). Independence of irrelevant alternatives (IIA):

If P A = P A then F P (A) = F P (A).

Transitive explanations (T):

There exists a mapping P → P (a social welfare function, which aggregates the preferences of the voters collected in P into a global preference P ) such that, for every profile P and every agenda A, we have F P (A) = max(A, P ). 6Another desirable property concerns the absence of voters with a strong decision power. More precisely, we have the following definition: Definition 1 A dictator for the social function F is a voter d in N satisfying the following: for any profile P = ( 1 , . . . , n ), any agenda A and any pair of alternatives x, y, if x d y and x is in A then y is not in F P (A).

It is not hard to see that when there exists a dictator d for F , this dictator is unique. Now we can state the property:

Absence of dictator: There is no voter d in N which is a dictator for F .

Standard domain states that there are three or more alternatives and that the process of election gives always a result. The Pareto condition says that if all the voters preferred alternative x to alternative y, and x is an available alternative, then alternative y cannot be chosen. Independence of irrelevant alternatives states the following: if the voters express in two different situations different preferences, but these preferences coincide over the available alternatives, then in both situations the result has to be the same. Transitive explanations states that the process of election can be decomposed in two parts: first taking a preference of the group, and then taking the best available alternatives with respect to this group's preference. The property Absence of dictator is quite clear: it states that there is not a voter (dictator) who imposes his preferences. In particular, this type of powerful voter forces that the result does not contain those available alternatives which he does not prefer. Actually, it is not hard to see that d is a dictator for F iff we have F P (A) ⊆ max(A, d ). When a social choice function does not satisfy this property, we say that it is a dictatorial social choice function or that it admits a dictator. It is worth mentioning that every dictatorial function satisfies the Pareto condition, as can be easily verified.

Observation 1 It is not hard to see that the indifference function, the dictatorship function, and the anti-dictatorship function, satisfy standard domain (whenever X has at least three alternatives) and transitive explanations. 7However, the indifference function satisfies independence of irrelevant alternatives and absence of dictator, but does not satisfy Pareto condition; the dictatorship function satisfies Pareto condition and independence of irrelevant alternatives, but absence of dictator does not hold; and for the anti-dictatorship function, independence of irrelevant alternatives and absence of dictator hold, but Pareto condition does not hold.

The following result, which was established in its first version by Sen [START_REF] Sen | Quasi-transitivity, rational choice and collective decisions[END_REF], expresses the fact that, although the properties given above seem very reasonable and suitable in a selection process, there is no social choice function satisfying all these properties together. As Kelly [START_REF] Kelly | Social Choice Theory: An Introduction[END_REF] and Taylor [START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF] pointed out, this result is equivalent to Arrow's theorem [START_REF] Arrow | Social choice and individual values. 1st Edition[END_REF], which was first stated in terms of social welfare functions.

Theorem 1 (Arrow-Sen impossibility theorem) Any social choice function that satisfies standard domain, Pareto condition, independence of irrelevant alternatives and transitive explanations is dictatorial.

There are other interesting properties considered in the literature on social choice functions. One of these expresses the diversity of possible results of electoral processes (cf. [START_REF] Barberá | Manipulation of social decision functions[END_REF][START_REF] Gibbard | Manipulation of voting schemes: A general result[END_REF][START_REF] Satterthwaite | Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions[END_REF]). These are regrouped under the term of nonimposition (see [START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]). The next property, first introduced by Wilson [START_REF] Wilson | Social choice theory without the Pareto principle[END_REF] and then considered by Barberà [7] and others (see [START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]), tries to capture such a diversity:

Pairwise nonimposition (PNI): For every couple of alternatives x, y in X, there exists a profile P such that F P ({x, y}) = {x}.

This property states that given two alternatives, the voters can establish preferences in order to choose one of them, that is, any of these might be chosen. A function for which this property holds is also called pairwise nonimposed social choice function, and will be called pairwise imposed if pairwise nonimposition does not hold.

Observation 2 It is worth noting that every social choice function that satisfies standard domain and Pareto condition is pairwise nonimposed, as it can be easily verified. It is also easy to verify that if a social choice function admits a dictator, it is pairwise nonimposed: let x, y be a pair of alternatives in X and consider a profile P such that x d y, where d is the dictator, then F P ({x, y}) = {x}. From this fact, we get that the dictatorship function is a pairwise nonimposed function. Note that, similarly, we can see that the anti-dictatorship function is a pairwise nonimposed function for which Pareto condition does not hold, showing that the converse of the first remark fails. Moreover, from its definition, it is easy to see that the indifference function is pairwise imposed.

In the literature, different types of powerful voters -that is voters which, in some manner, can impose their will in the process of choice -have been studied. Some of them are weaker than the Arrovian dictator previously defined. In the sequel, we introduce other notions of powerful voters which should be avoided by reasonable social choice functions.

The first notion is introduced by Kelly [START_REF] Kelly | Strategy-proofness and social choice functions without singlevaluedness[END_REF]. It concerns powerful voters restricted to agendas of size two.

Definition 2 A pairwise nominator (for the social choice function F ) is a voter d in N satisfying the following: for every couple of alternatives x, y in X and every profile P = ( 1 , . . . , n ), if x d y, then x is in F P ({x, y}). We will say that F admits a pairwise nominator if such voter d exists.

We have to mention that, in his work, Kelly called weak-dictators what we call pairwise nominators, but we prefer this nomenclature, also used by Taylor [START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF], because we reserve the name of weak-dictator for a different notion of powerful voter (see Definition 4).

A suitable property for social choice functions is, of course, the following:

Absence of pairwise nominator: There is not a pairwise nominator.

See Observation 3 below, in order to see functions admitting pairwise nominator and one satisfying absence of pairwise nominator.

We introduce now a very natural generalization of the notion of pairwise nominator: Definition 3 A nominator (for the social choice function F ) is a voter d in N satisfying the following: for every agenda A and every profile P = ( 1 , . . . , n ), there exists x in max(A, d ) such that x is in F P (A). We will say that a social choice function F admits a nominator if such a voter d exists.

Again, reasonable social functions have to satisfy the following property:

Absence of nominator: There is not a nominator. This property expresses that, restricted to the available alternatives, no voter can guarantee that one of his preferred alternatives will always appear in the result of the process of choice. Observation 3 It is not hard to see that the indifference function and the dictatorship function are instances of social choice functions that admit a nominator (and also a pairwise nominator), while the anti-dictatorship function satisfies absence of nominator (and also absence of pairwise nominator). Moreover, it is clear that every voter is a nominator (and also a pairwise nominator) for the indifference function. Thus, unlike dictatorial functions in which the dictator is unique, a social choice function might admit more than one nominator (and more than one pairwise nominator).

Finally, concerning powerful voters we present a notion established by Leal and Pino Pérez [START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF]: the notion of weak-dictator. More precisely, we have the following definition.

Definition 4 A weak-dictator (for the social choice function F ) is a voter d in N satisfying the following: for all x in X there exists a preference x over X such that x is in F P [ x /d] ({x, y}), for every alternative y in X and for every profile P .

As before, the suitable property for social choice functions is the following:

Absence of weak-dictator: There is not a weak-dictator. This property, restricted to agendas of size two, expresses that no voter can give a ballot in order to include a specific alternative, independently of the preferences of the remaining voters.

A social choice function F for which absence of weak-dictator does not hold is called weak-dictatorial function.

Observation 4 It is easy to see that the indifference function, the dictatorship function and the anti-dictatorship function are weak-dictatorial functions.

In Section 4 we will make a comparative study of the relationships between the different notions of powerful voters previously defined.

General results of manipulability through liftings

In this section we deal with the manipulability of social choice functions. Roughly speaking, a manipulability situation occurs when a voter (the manipulator) expresses in his ballot a choice which differs from his real preference, in order to obtain a more "convenient" result for him than the result he would obtain by expressing his true preference in his ballot. The literature in social choice about manipulability is very broad. The works of Gibbard [START_REF] Gibbard | Manipulation of voting schemes: A general result[END_REF] and Satterthwaite [START_REF] Satterthwaite | Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions[END_REF] in the case of voting schemes can be considered pioneers in the subject. 8 In the case of social choice functions, the literature concerning studies of manipulability is quite vast. Among the first works in this framework, we can cite the works of Barberà [4,[START_REF] Barberá | Manipulation of social decision functions[END_REF], Kelly [START_REF] Kelly | Strategy-proofness and social choice functions without singlevaluedness[END_REF] and Gärdenfors [START_REF] Gärdenfors | Manipulation of social choice functions[END_REF][START_REF] Gärdenfors | On definitions of manipulation of social choice functions[END_REF]. There are also more recent works about manipulability in more abstract frameworks (see, for instance, the works of Brandt [START_REF] Brandt | Group-strategyproof irresolute social choice functions[END_REF], Brandt and Brill [START_REF] Brandt | Necessary and sufficient conditions for the strategyproofness of irresolute social choice functions[END_REF], Pini et al. [START_REF] Pini | Aggregating Partially Ordered Preferences[END_REF] and Ching and Zhou [START_REF] Ching | Multi-valued strategy-proof social choice rules[END_REF]). For a survey in manipulability, see the works of Barberà [5] and Taylor [START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF] . In this section we present other general results of manipulability through liftings, similar to those presented by Leal and Pino Pérez [START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF], now involving nominators and dictators.

In what follows, we present the notion of manipulability of a social choice function, based on liftings. This notion, implicit in the literature of manipulability, was explicitly defined and studied by Leal and Pino Pérez [START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF].

Definition 5 (Manipulation through liftings) Let F be a social choice function and → be a lifting. We will say that F is manipulable with respect to → if there exists a voter i in N , an agenda A, a profile P = ( 1 , . . . , n ) and a ballot * such that

F P [ * /i] (A) i F P (A)
We say that F is nonmanipulable with respect to → , if the statement above does not hold. 9 We also say that F is manipulable if it is manipulable with respect to some lifting, and F is said to be nonmanipulable (NM) if it is nonmanipulable with respect to every lifting. We say that F is absolutely manipulable if it is manipulable with respect to every lifting. When F is nonmanipulable for a G-lifting we say that F satisfies the property (∃G-NM).

The set formed by voter i, the agenda A, the profile P and the (new) ballot * , that witnesses the manipulability of a social choice function F , is called manipulability situation for F , with respect to the lifting → , or simply manipulability situation when the context is clear. Therefore, a social choice function F is manipulable with respect to → if such a manipulability situation exists. In the manipulability situation above, the agent i is called the manipulator, while * is the lie ballot expressed by i in order to get a better result for him than the one obtained when he expresses his true preferences in his ballot.

Observation 5 From the definition of lifting, straightforwardly follows that a resolute social choice function is absolutely manipulable iff it is manipulable. This is due to the fact that, restricted to singletons, all the liftings are the same. Thus, for resolute social choice functions, the manipulability situation does not depend on the selected lifting.

The next example illustrates the notion of manipulability through liftings. In fact, we will review the behaviour, concerning manipulability, of the concrete examples presented in Subsection 2.2: the indifference function, the dictatorship function and the anti-dictatorship function.

Example 1 Due to the fact that I P (A) = A, it is clear that the indifference function is nonmanipulable.

The anti-dictatorship, T P (A) = min(A, d ), is absolutely manipulable. To see that, consider a couple of alternatives x, y in X, a profile P = ( 1 , . . . , n ) such that x d y and a ballot * such that y * x; thus, T P ({x, y}) = {y} and T P [ * /d] ({x, y}) = {x}. Then, we get T P [ * /d] ({x, y}) d T P ({x, y}), for every lifting → .

More surprising is the fact that the dictatorship function, which is defined D P (A) = max(A, d ), is manipulable. Actually, it is manipulable through the precise-leximax lifting. In order to see this, let us consider a couple of alternatives x, y in X, and a profile of ballots P = ( 1 , . . . , n ) such that x d y. Thus,

D P ({x, y}) = {x, y}. Now, if * is such that x * y, we get D P [ * /d] ({x, y}) = {x}. But it is clear that {x} Plmax d {x, y}, that is, D P [ * /d] ({x, y}) Plmax d D P ({x, y}), as desired.
However, the dictatorship function is not absolutely manipulable. In fact, it is not manipulable for Kelly lifting. To see that, consider an agenda A, a voter i in N , a profile P , and a ballot * . Let us note that, if i = d, then D P (A) = D P [ * /i] (A). Now suppose that i = d, and let us note that if x is in D P (A) and y is in D P [ * /d] (A), then x d y. Therefore, in any case we get D P (A) K i D P [ * /i] (A). This last example shows that the nonmanipulation of a social choice function heavily relies on the lifting selected. However, one might think that a gauge for the goodness of a lifting is the strategy behaviour of a social choice function, which we expect to be nonmanipulable. Thus, if such a function is manipulable with respect to a given lifting, one could think that the problem comes from this lifting and not from the function. But, as we show in Example 7, there are dictatorial functions which are manipulable for any lifting. Therefore, the idea of using such a gauge is not convenient.

There are several properties over social choice functions intimately related with manipulability. The next one, is a pairwise version of a series of principles regrouped under the name of monotonicity in the literature. The property here presented appears in Taylor [START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]. It concerns the stability of an election process when only two alternatives are available: if one alternative is selected and if a voter changes his mind in such a way that the losing alternative is strictly less preferred than the winner, then winner remains the same. More precisely:

Pairwise down-monotonicity for singleton winners: For all i in N , if

x * y and F P ({x, y}) = {x}, then F P [ * /i] ({x, y}) = {x}.

The indifference and the dictatorship functions, presented in Subsection 2.2, are instances of social choice functions that satisfy pairwise down-monotonicity for singleton winners. As a matter of fact, the satisfaction of this property by the indifference function follows trivially from the fact that there are no singleton winners when the agenda is a set of a couple of alternatives. We can also easily see, from the definition of the dictatorship function, that this function satisfies pairwise down-monotonicity for singleton winners. However, the anti-dictatorship function does not satisfy this property. In order to see this, consider a ballot * and a profile P = ( 1 , . . . , n ) such that x * y and y d x. Thus,

T P ({x, y}) = {x} but T P [ * /d] ({x, y}) = {y}.
Observation 6 If F is a social choice function that satisfies pairwise downmonotonicity for singleton winners and F P ({x, y}) = {x}, it is easy to see that, if O is a set of voters in N and, for every i in O, * i is a ballot such that x * i y, then F P * ({x, y}) = {x}, where P * is the profile obtained from P when every voter i in O has the ballot * i .

There is a tight relationship between pairwise down-monotonicity for singleton winners and nonmanipulability. This fact is stated in the next result.

Proposition 1 If a social choice function satisfying standard domain is nonmanipulable with respect to a G2-lifting, then it satisfies pairwise downmonotonicity for singleton winners.

Proof Suppose that F is a social choice function which satisfies standard domain and is nonmanipulable with respect to → . We will show that F satisfies down-monotonicity for singleton winners. Towards a contradiction, consider a pair of alternatives x, y in X, a profile P and a ballot * such that x * y, F P ({x, y}) = {x} and suppose that y is in F P [ * /i] ({x, y}). Thus, since x * y, we get {x} * {y} and, by simple dominance 2, {x} * {x, y}. Now, if we consider the profile P * := P [ * /i], we get P * [ i /i] = P . Moreover, the following hold: F P * [ i/i] ({x, y}) = {x} and either F P * ({x, y}) = {y} or F P * ({x, y}) = {x, y}. Therefore, for any of the two possible outputs of F P * ({x, y}), we have F P * [ i/i] ({x, y})

* F P * ({x, y}). Thus, P * , i, {x, y} and i (the lie ballot) is a manipulation situation of F with respect to → , a contradiction.

The converse of this result does not hold. The following is an example of a classical social choice function that satisfies standard domain (when there are at least three alternatives) and pairwise down-monotonicity for singleton winners, but it is manipulable with respect to any G2-lifting.

Example 2

The plurality rule, defined by:10

C P (A) = {x ∈ A : ∀y ∈ A; |{i : max(A, i ) = {x}}| ≥ |{i : max(A, i ) = {y}}|}
satisfies pairwise down-monotonicity for singleton winners, and it is also manipulable with respect to any G2-lifting.

To show that pairwise down-monotonicity for singleton winners holds, consider a pair of alternatives x, y, a voter i, a profile P = ( 1 , . . . , n ), a ballot To prove that the plurality rule is manipulable with respect to any G2lifting, assume N = {1, 2, 3}, X = {x, y, z} and consider the next manipulation situation: the agenda A = X and a profile of ballots P = ( 1 , 2 , 3 ) such that y 1 x 1 z, x 2 y 2 z and x 3 z 3 y. In this case, we obtain C P (A) = {x, y}. Moreover, if the voter 3 expresses a ballot * such that x * z * y, we obtain C P [ * /3] (A) = {x}. Now, since x 3 y, for any G2-lifting → , we get {x} 3 {x, y}, that is, C P [ * /3] (A)

3 C P (A). This shows the manipulability of the plurality rule with respect to any G2-lifting.

The Pareto condition is obtained when pairwise nonimposition and pairwise down-monotonicity for singleton winners are present. More precisely, we have the following proposition.

Proposition 2 If F is a social choice function for which standard domain, transitive explanations, pairwise nonimposition and pairwise down-monotonicity for singleton winners hold, then F satisfies the Pareto condition.

Proof Let us suppose that F is a pairwise nonimposed social choice function that satisfies standard domain, transitive explanations, pairwise nonimposition and pairwise down-monotonicity for singleton winners. We want to see that the Pareto condition holds. Consider an agenda A, a couple of alternatives x, y in X, with x in A, and a profile of ballots P = ( 1 , . . . , n ) such that x i y, for all i in N . We will show y is not in F P (A).

Note that the result is trivial if y is not in A. Now, suppose that y is in A. Since F is pairwise nonimposed, there is a profile P * = ( * 1 , . . . , * n ) such that F P * ({x, y}) = {x}. Thus, by Observation 6, we get that F P ({x, y}) = {x}. From this, by transitive explanations, we get x P y. Again, from transitive explanations, we get that y is not in F P (A).

The converse of the previous proposition does not hold. Actually, in Observation 2 we have seen that, under standard domain, the Pareto condition entails pairwise nonimposition. However, pairwise down-monotonicity for singleton winners is not entailed by the Pareto condition. This will be seen through an example using a generalization of a classic social choice function, namely, the Borda rule (cf. [START_REF] De Borda | Mémoire sur les élections au scrutin[END_REF][START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF][START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]). Let us define the generalized Borda rule. Let X = {x 1 , . . . , x k } be the set of alternatives and N = {1, . . . , n} be the set of voters; we define the generalized Borda rule (which we will continue to call Borda rule for simplicity) as follows: for a profile P = ( 1 , . . . , n ) and a nonempty subset A of X, we put B P (A) = max(A, Σ P ), where the global preference Σ P (the Borda relation) is defined by putting a Σ P b iff Note that, by Example 3 and Proposition 1, the Borda rule is manipulable with respect to any G2-lifting (even if this function satisfies the Pareto condition). Moreover, this function is absolutely manipulable, as we will see through the next example.

Example 4 Suppose X = {w, x, y, z} and N = {1, 2, 3}. If we consider the profile P given in Figure 1, it is easy to see that B P ({x, y}) = {y}. However, if voter 3 expresses his preferences through the ballot * (see Figure 1) instead of his true preferences, we have B P [ * /3] ({x, y}) = {x}. Now, since x 3 y, for every lifting → , we have {x} 3 {y}. Therefore, B P [ * /3] ({x, y})

3 B P ({x, y}). Thus, the Borda rule is absolutely manipulable.

From Propositions 1 and 2 and Observation 2, we get straightforwardly that, modulo nonmanipulability, pairwise nonimposition is equivalent to the Pareto condition. More precisely, we obtain the following corollary.

Corollary 1 Let F be a social choice function satisfying standard domain and transitive explanations. If F is nonmanipulable with respect to a G2-lifting, then F is pairwise nonimposed iff F satisfies the Pareto condition.

There is another natural property that any rational social choice function should satisfy. This concerns a sort of monotonous behaviour. We call this property pairwise indifference. To our knowledge, it is introduced in this work for the first time.

Pairwise indifference (PI): If x is in F P ({x, y}), y i x and x * y, then

x is in F P [ * /i] ({x, y}). 12Pairwise indifference expresses that, if only two alternatives are available in a process of choice, an alternative chosen under a profile must not be rejected if a voter expresses through a new ballot that the two alternatives are indifferent and in the old ballot, this alternative was not better than the other available alternative. This is a sort of monotonicity, as we mentioned previously. Some natural social choice functions satisfy PI, as we will see in the next example.

Example 5 From the monotonicity of the sum it follows that the Borda rule is a classical instance of a natural social choice function that satisfies pairwise indifference. Another classical example of a natural function that satisfies this property is the plurality rule, which was presented in Example 2:

C P (A) = {x ∈ A : ∀y ∈ A; |{i : max(A, i ) = {x}}| ≥ |{i : max(A, i ) = {y}}|}
To show that the strict plurality rule satisfies pairwise indifference, let us consider a pair of alternatives x, y, a voter i, a profile P = ( 1 , . . . , n ), a ballot * and, for every pair of alternatives w, z and every profile P It is also easy to see that the indifference, the dictatorship and the antidictatorship functions are instances of social choice functions that satisfy pairwise indifference. Then, classical examples of social choice functions satisfy this property. Therefore, it is quite natural to consider it as a rational property.

Under nonmanipulability, pairwise indifference and independence of irrelevant alternatives are equivalent. More precisely, we have the following result.

Proposition 3 Let F be a social choice function that satisfies standard domain and transitive explanations and suppose that it is nonmanipulable with respect to a G-lifting. Then F satisfies pairwise indifference iff it satisfies independence of irrelevant alternatives.

Proof Assume that F satisfies standard domain, transitive explanations and it is nonmanipulable with respect to a G-lifting → . We will show that pairwise indifference holds iff independence of irrelevant alternatives also holds.

In order to show the only if part, let us consider an agenda A and a couple of profiles P = ( 1 , . . . , n ), P * = ( * 1 , . . . , * n ) such that P A = P * A and, towards a contradiction, suppose F P (A) ⊂ F P * (A) [the case F P * (A) ⊂ F P (A) is analogous].

Let x be an alternative in F P (A) such that x is not in F P * (A) and consider an alternative y in F P * (A). From transitive explanations we get that x is in F P ({x, y}) and F P * ({x, y}) = {y}. Put P o = P * and, for every i in N ,

P i = P i-1 [ i /i].
Let us note that P n = P and, given i in N , P i-1 = P i [ * i /i]. Therefore, F Po ({x, y}) = {y} and F Pn ({x, y}) = {y}. Let k be the greatest integer in N , such that F P k ({x, y}) = {y}. Note that k < n; by simplicity denote j = k+1. Thus, we have F Pj ({x, y}) = {y}, and then F Pj ({x, y}) = {x} or F Pj ({x, y}) = {x, y}.

Since P j [ * j /j] = P k , we obtain F Pj [ * j /j] ({x, y}) = {y}. Thus, x is in F Pj ({x, y}) but x is not in F Pj [ * j /j] ({x, y}). Then, by pairwise indifference, it is not the case that y j x and x * j y. Therefore we have the following three cases: x j y, x * j y and y * j x. x j y: In this case, since j {x,y} = * j {x,y} , we get x * j y. From this we have {x} * j {y} and, by simple dominance 1, {x, y} * j {y}. Therefore, since P j = P k [ j /j], we get F P k [ j/j] ({x, y}) * j F P k ({x, y}), independently of the two possible outputs for F P k [ j/j] ({x, y}) = F Pj ({x, y}). This shows the manipulation of F , a contradiction. x * j y: Since j {x,y} = * j {x,y} , we have x j y, and by the previous argument this is impossible. y * j x: Since j {x,y} = * j {x,y} , we have y j x. Thus, {y} j {x} and, by simple dominance 2, {y} j {x, y}. Therefore, for any of the two possible outputs for F Pj ({x, y}), we get F Pj [ * j /j] ({x, y}) j F Pj ({x, y}). This shows the manipulation of F , a contradiction.

To prove the if part, suppose that y i x, x * y, x is in F P ({x, y}) and, towards a contradiction, assume that x is not in F P [ * /i] ({x, y}). Thus, we get, on one hand, F P ({x, y}) = {x} or F P ({x, y}) = {x, y}, and, on the other hand, F P [ * /i] ({x, y}) = {y}. Let us consider the following two cases for which y i x holds: y i x: In this case, we have P {x,y} = P [ * /i] {x,y} . Therefore, from IIA, we have F P ({x, y}) = F P [ * /i] ({x, y}), a contradiction. y i x: In this case, {y} i {x} and, by simple dominance 2, {y} i {x, y}. Thus, F P [ * /i] ({x, y})

i F P ({x, y}), regardless of the two possible outputs for F P ({x, y}). This shows the manipulation of F , a contradiction.

It is worth mentioning that Proposition 3 says that under standard domain and transitive explanations, the nonmanipulability is a sufficient condition to obtain the equivalence between independence of irrelevant alternatives and pairwise indifference. However, it is not a necessary condition for this equivalence. For instance, the anti-dictatorship function is an example of a social choice function that satisfies standard domain, transitive explanations, independence of irrelevant alternatives and pairwise indifference, but, as we have seen previously, it is absolutely manipulable (cf. Example 1).

The following result, which is straightforwardly derived from Proposition 3, provides a tool for determining when a social choice function having good properties is absolutely manipulable, in terms of independence of irrelevant alternatives.

Corollary 2 Every social choice function that satisfies standard domain, transitive explanations and pairwise indifference is either manipulable with respect to any G-lifting or it satisfies independence of irrelevant alternatives.

It is worth mentioning that Gibbard [START_REF] Gibbard | Manipulation of voting schemes: A general result[END_REF] and Satterthwaite [START_REF] Satterthwaite | Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions[END_REF] are the pioneers in stating such a duality between independence of irrelevant alternatives and nonmanipulation, but in the context where ties are dismissed.

Actually, a reading of Corollary 2 has another interesting consequence related to the postulate of independence of irrelevant alternatives and the controversies around its acceptance. On one hand, this postulate is accused of being too strong. Moreover, it is pointed at as the cause of Arrow's impossibility theorem (cf. Hansson [START_REF] Hansson | The independence condition in the theory of social choice[END_REF]). However, some classical democratic social choice functions satisfy it, like the plurality rule (cf. Example 2 and 5), even if some other procedures, like the Borda rule, do not (cf. Example 3 and also [START_REF] Arrow | Social choice and individual values. 1st Edition[END_REF][START_REF] Hansson | The independence condition in the theory of social choice[END_REF]). On the other hand, nonmanipulation is a good criteria. Indeed, Barberà [START_REF] Barberá | Manipulation of social decision functions[END_REF], Kelly [START_REF] Kelly | Strategy-proofness and social choice functions without singlevaluedness[END_REF] and Feldman [START_REF] Feldman | Nonmanipulable multi-valued social decision functions[END_REF] considered that any good system of social choice should be free of manipulation. Then, under the hypotheses of standard domain, transitive explanations and pairwise indifference, Corollary 2 leads us to the following:

-Independence of irrelevant alternatives will be accepted, whenever nonmanipulation for at least some G-lifting is accepted. -If independence of irrelevant alternatives is rejected, absolute manipulation with respect to G-liftings must be accepted.

In order to illustrate how this observation can help in extracting information about the behavior of certain functions, let us consider again the Borda rule and the dictatorship function. As we mentioned before, these functions satisfy transitive explanations and pairwise indifference. Note that it is well known that independence of irrelevant alternatives is incompatible with the Borda rule [START_REF] Fishburn | The theory of social choice[END_REF][START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]. Therefore, from Corollary 2 it follows that it is manipulable with respect to any G-lifting. This supports what we showed in Example 4 (at least when we restrict to G-liftings). Also note that the dictatorship function is nonmanipulable with respect to a G-lifting (cf. Example 1), then, by Corollary 2, we get that this function satisfies independence of irrelevant alternatives. This confirms our remark in Observation 1.

We are now ready to establish our main general theorem of manipulability, which involves Arrovian dictators. This result is a straightforward consequence of Arrow-Sen Theorem (Theorem 1) and Corollaries 1 and 2.

Theorem 2 Let F be a social choice function that satisfies standard domain, transitive explanations, pairwise nonimposition and pairwise indifference. If F is nonmanipulable with respect to a G-lifting, then it admits a dictator. This result is interesting for at least two reasons. First of all, because it establishes, with weak hypothesis, when the nonmanipulability entails the presence of an Arrovian dictator. Or the other way around, with very weak assumptions, if a function does not admit an Arrovian dictator, necessarily it is manipulable for any G-lifting. The other important reason is that it entails Theorem 1 for the class of functions which are nonmanipulable with respect to a G-lifting. This entailment follows from the fact that Pareto condition clearly implies PNI (cf. Observation 2) and IIA implies PI (under nonmanipulability; cf. Proposition 3). This equivalence is in our view quite remarkable and it is worth to underline as a result: Theorem 3 In the class of social choice functions which are nonmanipulable with respect to a G-lifting, Theorem 1 and Theorem 2 are equivalent.

The equivalence given by the previous theorem might be seen as an answer to the quest of a right proof of Gibbard-Satterthwaite Theorem.

The following observation shows that the converse of Theorem 2 fails. Moreover, it surprisingly establishes that there are dictators who are absolutely manipulable.

Observation 7 (Absolutely manipulable dictators) For every profile of ballots P = ( 1 , . . . , n ), define the total preorder E P = lex( 1, Σ P ) , where Σ P is the Borda relation, and consider the social choice function E, defined by E P (A) = max(A, E P ). Note that E is a social choice function that satisfies transitive explanations and the standard domain condition (when there are at least three alternatives). Moreover, as we will see in the following, this is a dictatorial and pairwise nonimposed social choice function that satisfies pairwise indifference, but it is absolutely manipulable (when at least three voters and four alternatives are available in the election process).

Let us show that voter 1 is a dictator for E. In order to do this, we consider a profile of ballots P = ( 1 , . . . , n ), an agenda A and a pair of alternatives x, y in X, such that x is in A and x 1 y. Thus, x E P y, and therefore y is not in max(A, E P ), that is, y is not in E P (A). From this it straightforwardly follows that E is pairwise nonimposed, as we pointed out in Observation 2.

To see that pairwise indifference holds, assume that a voter i and a couple of alternatives x, y are such that x is in E P ({x, y}), y i x and x * y. We show that x is in E P [ * /i] ({x, y}). To do so, note that x E P y and consider the following cases: i = 1 : Since x E P y, we have either x 1 y, or x 1 y and x Σ P y. If x 1 y, since i = 1, it straightforwardly follows that x E P [ * /i] y. Suppose then x 1 y and x Σ P y. Since y i x, x * y and x Σ P y, we have r i (y) ≥ r i (x), r * (x) = r * (y) and r j (x) ≥ r j (y). Then, from the monotonicity of addition, we get j =i r j (x) ≥ j =i r j (y). From this, we obtain r * (x) + j =i r j (x) ≥ r * (y) + j =i r j (y), that is, x Σ P [ * /i] y. Therefore, since x 1 y and x Σ P [ * /i] y, we have x E P [ * /i] y. i = 1 : Again, because x E P y, we get x 1 y. Thus, since y i x and i = 1, we have x 1 y, and therefore x Σ P y. Then, by an argument which is similar to the previous one, we obtain x E P [ * /i] y. In any case, x is in max({x, y}, E P [ * /i] ) = E P [ * /i] ({x, y}), as desired. In order to show the absolute manipulability of E, consider N = {1, 2, 3}, X = {w, x, y, z} and the manipulability situation given in Example 4: the agenda A = {x, y}, the voter (the manipulator) i = 3, the profile of ballots P and the (lie) ballot * , given in Figure 1.

Note that x 1 y and, as we saw in Example 4, y Σ P x and x Σ P [ * /3] y. From this we get y E P x and x E P [ * /3] y, that is, E P ({x, y}) = {y} and E P [ * /3] ({x, y}) = {x}. Now, since x 3 y, for any lifting → , we have {x} 3 {y}. Therefore, E P [ * /3] ({x, y}) 3 E P ({x, y}). This shows the absolute manipulability of E.

Theorem 2 entails two other important manipulation theorems:

Theorem 4 Restricted to linear profiles, let F be a social choice function that satisfies standard domain and transitive explanations. Then, F is pairwise nonimposed and nonmanipulable with respect to a G-lifting iff F admits a dictator.

Theorem 5 Let F be a social choice function that satisfies standard domain and transitive explanations. If F is pairwise nonimposed and nonmanipulable with respect to a G-lifting, then F admits a nominator.

Before giving the formal proofs of these theorems, let us make some observations. Note that Theorem 4 says that, restricted to linear profiles, the functions that satisfy standard domain and transitive explanations, which are pairwise nonimposed and nonmanipulable are exactly the dictatorial ones. This result is similar to Gibbard-Satterthwaite Theorem [START_REF] Gibbard | Manipulation of voting schemes: A general result[END_REF][START_REF] Satterthwaite | Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions[END_REF] for voting schemes. Even if there are some similarities between these two theorems, they are indeed very different in nature. As a matter of fact, Gibbard-Satterthwaite Theorem says that for the voting schemes which are resolute (i.e. the output is only one alternative) and nonimposed (all alternatives are possible outputs), the conditions of being nonmanipulable and admitting a dictator are equivalent. Unlike this, Theorem 4 concerns social choice functions, a framework which is richer than voting schemes. Moreover, we do not consider that the social choice functions are resolute. The other difference is that the social choice functions have an additional parameter: the agenda. These two differences force to consider notions of manipulation and dictator which are different than the corresponding notions considered in the case of resolute voting schemes, because our notions are adapted to deal with (in principle) nonresolute social choice functions and agendas. Thus, on one hand, it is far from clear that Gibbard-Satterthwaite Theorem entails our Theorem 4. On the other hand, our Theorem 4 relies on a hypothesis which is absent in Gibbard-Satterthwaite Theorem: the assumption that the social choice functions satisfy transitive explanations. Thus, it is not clear that Theorem 4 entails Gibbard-Satterthwaite Theorem. All this makes it difficult to establish the precise relationships between both theorems.

Before giving the proof of Theorem 4, we must note it is quite clear that, for any agenda A, if is a linear order then max(A, ) is a singleton. Moreover, if F is a dictatorial function, and d is the dictator, we have that for every profile P = ( 1 , . . . , n ) and every agenda A, if d is a linear order then F P (A) = max(A, d ). This is due to the fact that if max(A, d ) = {x} then for every y ∈ A such that y = x, necessarily x d y and, as d is the dictator, y ∈ F P (A). Thus, the only possibility is F P (A) = {x}. Summarizing this, we have the next observation which will be very useful in the proof of Theorem 4.

Observation 8 Suppose that F is a dictatorial function satisfying standard domain, and assume d is the dictator. Then, for every profile P = ( 1 , . . . , n ) and every agenda A, if d is a linear order then F P (A) = max(A, d ) and therefore F P (A) is a singleton.

We are now ready to prove Theorem 4.

Proof of Theorem 4

The proof of the only if part straightforwardly follows from Theorem 2 and from the fact that PI is trivially satisfied for linear profiles. In order to show the if part, let us suppose that F is a dictatorial social choice function, and suppose that d in N is the dictator for F . We will see that F is a pairwise nonimposed function which cannot be manipulable with respect to any G-lifting → . Restricted to linear ballots, by Observation 8, F P (A) = max(A, d ), for every agenda A and every linear profile P . Moreover, F is a resolute social choice function.

Pairwise nonimposition: this follows from Observation 2. Nonmanipulation: Towards a contradiction, let us suppose that F is manipulable with respect to a G-lifting → . Thus, there exists an agenda A, a voter i in N , a linear profile P and a linear ballot * such that

F P [ * /i] (A) i F P (A).
Due to the resoluteness of F , suppose F P (A) = {x} and F P [ * /i] (A) = {y}, where x = y. Let us note that, if i = d, from the remark above we get F P (A) = F P [ * /i] (A), a contradiction. Thus, i = d, which leads us to {y} d {x}. From this, we get y d x. Therefore, since d is a dictator for F , x is not in F P (A), a contradiction. Due to Observations 5 and 8, we have as a corollary of Theorem 4 the following:

Corollary 3 Restricted to linear profiles, let F be a social choice function that satisfies standard domain, transitive explanations and pairwise nonimposition. If F is nonmanipulable with respect to a G-lifting, then F is nonmanipulable with respect to any lifting.

Note that Theorem 4 establishes a deep relationship between nonimposition, nonmanipulability and the existence of powerful voters in processes of choice, when restricted to the linear ballots' context. Thus, it is natural to wonder if it is possible to extend this type of results to the nonlinear ballots' framework. Affirmative responses for this question were established when pairwise nominator (cf. Bárberà-Kelly Theorem [START_REF] Barberá | Manipulation of social decision functions[END_REF][START_REF] Kelly | Strategy-proofness and social choice functions without singlevaluedness[END_REF]) and weak-dictator (cf. Leal-Pino Pérez Theorem [START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF]) were considered. Actually, Theorem 5 states that the existence of a nominator is a necessary condition for having a nonimposed and nonmanipulable social choice function. As we will see below, Theorem 5 is a consequence of Theorem 4 and, therefore, of Theorem 2.

Proof of Theorem 5 Assume that F is pairwise nonimposed and nonmanipulable with respect to a G-lifting → . We must show that F admits a nominator, that is, there exists d in N for which the following holds: for every agenda A and every profile P , there exists x in max(A, d ) such that x is also in F P (A). In order to see this, consider f , the restriction of F to linear profiles. We claim that f is pairwise nonimposed and nonmanipulable with respect to → . The nonmanipulation of f straightforwardly follows from the nonmanipulation of F . Now we prove that f is pairwise nonimposed. Consider a couple of alternatives x, y in X. We want to see that there exists a linear profile P such that f P ({x, y}) = {x}. Since F is pairwise nonimposed and nonmanipulable with respect to → for which simple dominance 2 holds, from Corollary 1 we get that F satisfies the Pareto Condition. Thus, if we consider a linear profile P , such that x i y, for every i in N , then F P ({x, y}) = {x}, that is, f P ({x, y}) = {x}. Now, by Theorem 4, it follows that f admits a dictator d in N . We claim that d is a nominator for F . Towards a contradiction, suppose that d is not a nominator for F , and consider a profile P = ( 1 , . . . , n ) and an agenda A such that, for all x in max(A, d ), x is not in F P (A). Let us fix x in max(A, d ) and y in F P (A); note that x is not in F P (A) and, since y is in A but not in max(A, d ), x d y. Then, {x} d {y}. Since x is not in F P (A), from transitive explanations it straightforwardly follows that F P ({x, y}) = {y}. Moreover, by Proposition 1, we have that F satisfies pairwise down-monotonicity for singleton winners. Then, if we consider a profile of ballots P * = ( Theorem 5 is indeed a corollary of [START_REF] Kelly | Strategy-proofness and social choice functions without singlevaluedness[END_REF]. In Section 5 we will discuss this fact. However, we have to say that the proof of Theorem 5 presented here uses a technique which is simpler and more direct than the techniques used by Barberà and Kelly. We must note that the converse of Theorem 5 is not true. As a matter of fact, there exist some instances of social choice functions that satisfy standard domain, transitive explanations and admit a nominator but either pairwise nonimposed or nonmanipulation with respect to a G-lifting fails.

For instance, the indifference function, I P (A) = A, is an example of a function that satisfies standard domain, transitive explanations, admits a nominator, is nonmanipulable, but it is pairwise imposed, as we saw above.

Another example of the failure of the converse of Theorem 5 is the fact that there are absolutely manipulable nominators . Indeed, in Observation 7 the existence of absolutely manipulable dictators is shown and it is not hard to see that all dictators are, in fact, nominators (cf. Theorem 6).

The following figure summarizes the main results of this section. As we mentioned earlier, different types of powerful voters have been studied in the literature of social choice function. In this section, we are going to establish some relationships that hold between the powerful voters presented in this paper. As a matter of fact, Theorem 6 establishes a strict hierarchy among the powerful voters introduced so far.

The following notions regroup a taxonomy for some classes of powerful voters. The set of all dictatorial social choice functions satisfying the standard domain condition is denoted by D. The set formed by all social choice functions that admit a nominator, and for which standard domain holds, is denoted by N . The set of all social choice functions that satisfy standard domain and admit a pairwise nominator is denoted by N * . The set of all weak-dictatorial social choice functions satisfying standard domain is denoted by D * . The set of all social choice functions that admit a nominator and satisfy standard domain and transitive explanations is denoted by N T . The set of all the social choice functions that admit a pairwise nominator and satisfy standard domain and transitive explanations is denoted by N * T . The set of all nonmanipulable, dictatorial and resolute social choice functions that satisfy standard domain and transitive explanations is denoted by D N M T -R . The set of all nonmanipulable, resolute social choice functions that satisfy standard domain, transitive explanations and admit a nominator is denoted N N M T -R . The set of all nonmanipulable, resolute social choice functions that satisfy standard domain, transitive explanations and admit a pairwise nominator is denoted by

N N M * T -R .
The set of all nonmanipulable, resolute social choice functions that satisfy standard domain, transitive explanations and admit a weak-dictator is denoted by D N M * T -R . The set of all social choice functions that satisfy standard domain, transitive explanations, admit a nominator and which are nonmanipulable with respect to a G1-lifting is denoted by N N M 1 T . The set of all social choice functions that satisfy standard domain, transitive explanations, admit a pairwise nominator and which are nonmanipulable with respect to a G1lifting is denoted by N N M 1 * T . The set of all social choice functions that satisfy standard domain, transitive explanations, admit a weak-dictator and which are nonmanipulable with respect to a G1-lifting is denoted by D N M 1 * T . Note that by Observation 5 we have that

N N M T -R ⊆ N N M 1 T . Theorem 6
The following inclusions hold:

D N N * D *
Moreover, every dictator for a social choice function F satisfying standard domain is a nominator for F . Every nominator for F is also a pairwise nominator for F , and every pairwise nominator for F is a weak-dictator for F .

Proof We will show that D N . Let us consider F in D, and suppose that d in N is a dictator for F . In order to show that F is in N , we will see that d is a nominator for F . Towards a contradiction, suppose that d is not a nominator for F . Thus, there exist an agenda A and a profile P such that, for every alternative x in max(A, d ), x is not in F P (A). Let x be an alternative in max(A, d ) and consider an alternative y in F P (A). Since y is in A but it is not in max(A, d ) we have x d y. Thus, since d is a dictator for F and x is in A, we have that y is not in F P (A), a contradiction.

In order to show that N ⊂ D, we consider the indifference social choice function, I P (A) = A. As we mentioned earlier, every voter i in N is a nominator for I. However, if we consider any voter d in N , an agenda A, two alternatives x, y in A and a profile P = ( 1 , . . . , n ), even if x d y, we get y is in I P (A). Thus, d is not a dictator.

We will see that N N * . Suppose that F is a social choice function in N and consider d in N a nominator for F . In order to show that d is also a pairwise nominator for F , it is enough to note that if x, y are a couple of alternatives in X and P = ( 1 , . . . , n ) is a profile such that x d y, then max({x, y}, d ) = {x}. Thus, the result straightforwardly follows from the fact that d is a nominator for F .

To show N * ⊂ N , let us consider a prefixed voter d in N and the following function: G P (A) = A if |A| ≤ 2 and G P (A) = min(A, d ) otherwise. From its definition, it straightforwardly follows that every voter i in N is a pairwise nominator for G. However, G does not admit a nominator. In order to show this claim, let us consider an agenda A with at least three alternatives, two different alternatives x, y in A and a profile P = ( 1 , . . . , n ) such that min( d ) = {x} and max( i ) = {y}, for every i in N . Thus, G P (A) = {x} and, if we consider any voter i in N , max(A, i ) = {y} but y is not in G P (A). This shows that i is not a nominator for G. Now, we will prove that N * ⊂ D * . Let us suppose thus that F is a social choice function in N * and consider d a pairwise nominator for F . In order to show that F is in D * we will see that d is a weak-dictator for F , that is, d satisfies the following: for every x in X there exists a ballot x such that x is in F P [ x /d] ({x, y}), for every alternative y in X and every profile P . Let x be an alternative in X and x be a ballot such that max( x ) = {x}. Thus, given a profile P and an alternative y in X, different from x, we have that P [ x /d] is a profile for which the voter d prefers x against y, that is, x x y. Since d is a pairwise nominator for F , we get that x is in F P [ x /d] ({x, y}).

In order to see that D * ⊂ N * , let us consider the anti-dictatorship function, T P (A) = min(A, d ). It is not hard to see that d is a weak-dictator for T . In order to show this, it is enough to consider for every alternative x in X, a ballot

x such that x is in min( x ). However, this function does not admit a pairwise nominator. Indeed, if we consider a couple of different alternatives x, y in X and a profile P = ( 1 , . . . , n ) such that min( d ) = {x} and max( i ) = {y}, for every i in N , then we will have T P ({x, y}) = {x}. However, considering any voter i in N , we get y i x but y is not in T P ({x, y}). This shows that i is not a pairwise nominator for T .

Although, in general, the inclusions of the classes given in Theorem 6 are strict, under certain hypothesis the classes collapse. The following result establishes precisely the hypothesis under which a first collapse occurs.

Theorem 7

We have that N T = N * T . More precisely, for every social choice function F that satisfies standard domain and transitive explanations, d in N is a nominator for F iff d is a pairwise nominator for F . Proof Let F be a social choice function that satisfies transitive explanations. The only if part straightforwardly follows from Theorem 6. To show the if part, assume that d in N is a pairwise nominator for F and, towards a contradiction, suppose that d is not a nominator for F . Then, there exists an agenda A and a profile P = ( 1 , . . . , n ) such that, for every alternative x in max(A, d ), x is not in F P (A). Thus, consider x in max(A, d ) and y in F P (A). Since x is not in F P (A), by transitive explanations we get F P ({x, y}) = {y}. However, because y is in A but it is not in max(A, d ), then x d y. From this, since d is a pairwise nominator for F , we get x is in F P ({x, y}), a contradiction.

A consequence of this theorem is that the function G of the proof of Theorem 6, which admits a pairwise nominator but not a nominator, does not satisfy transitive explanations.

Next, we give our second result of collapse:

Theorem 8 For every nonmanipulable resolute social choice function F that satisfies standard domain and transitive explanations, the following assertions are equivalent:

(i) d in N is a dictator for F (ii) d in N is a nominator for F (iii) d in N is a pairwise nominator for F (iv) d in N is a weak-dictator for F That is, D N M T -R = N N M T -R = N N M * T -R = D N M * T -R
Proof In order to show this result, let us note that, due to Theorem 6, it is enough to see that (iv) entails (i). Assume that d in N is a weak-dictator for F and, towards a contradiction, assume that d is not a dictator for F . Thus, there exist a profile P = ( 1 , . . . , n ), an agenda A and a couple of alternatives x, y in X such that x is in A, x d y but y is in F P (A). It is worth noting that, by the resoluteness of F , we get F p (A) = {y}. From this, by transitive explanations, we obtain F p ({x, y}) = {y}. Now, because d is a weak-dictator for F , when considering x, there exists a ballot x such that F P * [ x /d] ({x, z}) = {x}, for every profile P * and every alternative z in X. In particular, we have

F P [ x /d] ({x, y}) = {x}. Now, since x d y, if we consider a lifting → , we have {x} d {y}, that is, F P [ x /d] ({x, y}) d F p ({x, y}). Thus F is manipulable, a contradiction.
It is interesting to note the role of nonmanipulability in the previous result. Actually, there exist resolute social choice functions that satisfy transitive explanations and admit a weak-dictator, which are not dictatorial. In particular, the anti-dictatorship function, T ≥ with a rule (≥) for breaking ties is an example of such a function (see the definition below), as can be easily checked. More precisely, this function is defined as follows: fix a linear order ≥ over X; then put

T ≥ P (A) = max(A, lex( -1 d ,≥) ) where -1
d is the reflection of d , i.e., x -1 d y iff y d x. It is clear that this function satisfies transitive explanations, is resolute, admits a weak-dictator but is not dictatorial. Therefore, this observation together with the previous theorem entail that the anti-dictator function with a rule is manipulable. Indeed, this last claim can also be easily verified, finding a manipulability situation for T ≥ .

If we remove the hypothesis of resoluteness in the previous proposition, we maintain the identification between nominators, pairwise nominators and weak-dictators (see Theorem 9 below). However, we cannot identify these classes with the class of dictators. As a matter of fact, it is easy to see that the indifference function, I P (A) = A, is an example of a function which satisfies transitive explanations, it is nonmanipulable (with respect to any lifting), it admits a nominator, but it does not admit a dictator, as we highlighted in Subsection 2.2 (see also the proof of Theorem 6).

Theorem 9 For every social choice function F which satisfies standard domain, transitive explanations and is nonmanipulable with respect to a G1lifting, the following are equivalent:

(i) d in N is a nominator for F (ii) d in N is a pairwise nominator for F (iii) d in N is a weak-dictator for F Therefore we have N N M 1 T = N N M 1 * T = D N M 1 *

T

Proof Due to Theorem 6, we only have to show that every weak-dictator for F is also a nominator for F . Let d in N be a weak-dictator for F and, towards a contradiction, suppose that d is not a nominator for F . Then, there exist an agenda A and a profile P = ( 1 , . . . , n ) such that, for all x in max(A, d ), x is not in F P (A).

Consider an alternative x in max(A, d ). Since d is a weak-dictator for F , there exists a ballot x such that, for every profile P * and every alternative z in X, x is in F P * [ x /d] ({x, z}). In particular, for y in F P (A) and the chosen profile P , we have that x is in F P [ x /d] ({x, y}). Then, F P [ x /d] ({x, y}) = {x} or F P [ x /d] ({x, y}) = {x, y}. Moreover, since y is in A but it is not in max(A, d ), x d y. Then, {x} d {y} and by simple dominance 1, {x, y} d {y}. In addition, since x is not in F P (A), by transitive explanations, y P x, and therefore F P ({x, y}) = {y}. Thus, in any case, F P [ x /d] ({x, y}) d F P ({x, y}).

This shows the manipulability of F with respect to → , a contradiction.

The picture in Figure 3 summarizes the results established in this section concerning the taxonomy of powerful voters. As we can see in this picture, the nonmanipulable social choice functions are highly concentrated in N (the class of functions that admit a nominator), except for the specific case of resolute functions, which are concentrated in D (the class of functions that admit an Arrovian dictator). This suggests that N might be seen as the kernel of nonmanipulable functions. One interesting feature of the classification results of Section 4 is that they allow establishing clear connections with some results in the literature about manipulation. Let us examine, for instance, the following theorem (see [START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF]):

Theorem 10 (Leal-Pino Pérez) Let F be a pairwise nonimposed social choice function satisfying the standard domain condition and transitive explanations. Then, F is manipulable with respect to a G-lifting or it has a weak-dictator.

Note that the assumptions in the previous Theorem are exactly the same as those in Theorem 5. Thus, from Theorem 9, it straightforwardly follows that Leal-Pino Pérez Theorem is equivalent to our Theorem 5. However, it is important to say that the proofs of both theorems are completely different.

Moreover, Theorem 5 is also a corollary of Barberà-Kelly Theorem. Actually, as it was pointed out in [START_REF] Leal | A weak version of Barberà-Kelly's theorem[END_REF], Theorem 10 is a corollary of Barberà-Kelly Theorem, therefore, by the previous remark, we can deduce that Theorem 5 follows from Barberà-Kelly Theorem.

It is interesting to note that Brandt [START_REF] Brandt | Group-strategyproof irresolute social choice functions[END_REF] proved that the social choice functions which are Condorcet extensions 13 are manipulable for the Kelly lifting. Using Theorem 5, we can obtain a result related to this. Actually, it is easy to see that when the number of voters is greater or equal to three, the social choice functions which are Condorcet extensions do not admit a nominator. Moreover, these functions are pairwise nonimposed. Then, under the hypotheses of Theorem 5, they are manipulable with respect to all the G-liftings. More precisely, we have the following result:

Corollary 4 Let F be a social choice function that satisfies standard domain and transitive explanations. If F is a Condorcet extension, then it is manipulable with respect to any G-lifting.

In another work, Brandt and Brill [START_REF] Brandt | Necessary and sufficient conditions for the strategyproofness of irresolute social choice functions[END_REF] study the manipulability under the liftings of Kelly, Fishburn and Gärdenfors. Actually, they gave sufficient (and necessary) conditions for nonmanipulability under such liftings. Again, using Theorem 5 and their results we obtain interesting information: the social choice functions which do not admit a nominator and satisfy standard domain, pairwise nonimposition and transitive explanations, fail to satisfy all conditions given by Brandt and Brill in order to have nonmanipulability with respect to the liftings of Kelly, Fishburn and Gärdenfors.

We also have to mention some similarities and differences with the work of Pini et al. [START_REF] Pini | Aggregating Partially Ordered Preferences[END_REF]. In their work, they generalize the results of impossibility and nonmanipulability to the case where the ballots are expressed as partial preorders. They also considered different notions of dictators which are related to our notions of powerful voters. Indeed, their strong dictator notion is not considered by us. However, in our work this kind of functions is considered as an example of dictators (see function D in subsection 2.2). Their notion of dictator is the normal Arrovian notion of dictator. In addition, their notion of weak dictator corresponds to our notion of nominator. They do not consider other notions of powerful voters we consider, such as the notion of pairwise nominator and our notion of weak-dictator.

The processes of voting represented in their framework and those represented in the one we discuss are different: they study social welfare functions where the input is a profile P of (strict) partial orders and the output is a (strict) partial order; they also consider voting rules (they call this kind of functions social choice functions) in which the input is a profile of (strict) partial orders and the output is a set of candidates. We consider social choice functions where the input is a profile and an agenda and the output is a set of candidates. Nevertheless, the framework of social welfare functions and that of social choice functions we treat here, are strongly related when we assume that transitive explanations hold.

It is interesting to note that their notion of monotonicity evokes our notion of pairwise indifference which plays a central role in our results.

To finish our discussion of relationships between the work of Pini et al. and our work, we have to say that their notion of manipulability (also considered by Ching and Zhou [START_REF] Ching | Multi-valued strategy-proof social choice rules[END_REF]) can be viewed as a particular case of our general notion of lifting.

To conclude, we have to mention that tight links between social choice theory and some topics in Artificial Intelligence, in particular with logical belief merging, have been recently revealed by Mata Díaz and Pino Pérez [START_REF] Mata Díaz | Impossibility in belief merging[END_REF]. Therein, an impossibility theorem is proved which generalizes Theorem 1. Pursuing this line of research, some works have also been done by these authors about manipulability in belief merging [START_REF] Mata Díaz | Epistemic states, fusion and strategy-proofness[END_REF][START_REF] Mata Díaz | Manipulability in logic-based fusion of belief bases: Indexes vs. liftings[END_REF][START_REF] Mata Díaz | Merging epistemic states and manipulation[END_REF]. In particular, Theorem 3 and Theorem 4 in [START_REF] Mata Díaz | Epistemic states, fusion and strategy-proofness[END_REF] could be seen as the counterparts of Theorem 4 and Theorem 5 respectively of the current work; Theorem 3 in [START_REF] Mata Díaz | Merging epistemic states and manipulation[END_REF] is a counterpart of Theorem 2 of the current work.

6 Final remarks and perspectives

  * and, for every couple of alternatives w, z and every profile P * , consider the set O w z (P * ) = { ∈ P * : max({w, z}, ) = {w}}. If C P ({x, y}) = {x} and x * y, then |O x y (P [ * /i])| ≥ |O x y (P )| > |O y x (P )| ≥ |O y x (P [ * /i])|. From this, we get C P [ * /i] ({x, y}) = {x}, as desired.

n i=1 r i (a) ≥ n i=1 r i (b). 11 Example 3

 113 Let X = {x, y, z} be the set of alternatives and N = {1, 2} be the set of voters. It is well known that the Borda rule satisfies the Pareto condition (due to the monotonicity of addition). However, this function does not satisfy pairwise down-monotonicity for singleton winners. In order to show this claim, let us consider the profile P = ( 1 , 2 ) where x 1 z 1 y and z 2 y 2 x. Now define * by putting z * x * y. Then, with an easy calculation, we get B P ({x, y}) = {x} and B P [ * /1] ({x, y}) = {x, y}. Therefore, B does not satisfy pairwise down-monotonicity for singleton winners.

1 Fig. 1

 11 Fig. 1 Profiles of ballots considered in Example 4

1 Fig. 2

 12 Fig. 2 Summary of manipulability theorems that involve powerful voters

N N M 1 T= 1 Fig. 3

 113 Fig. 3 Diagram summarizing the taxonomy of powerful voters

  * 1 , . . . , * n ) such that * i is a linear ballot for which y * i x, for every voter i different from d, and * d = d , by Observation 6, we get F P * ({x, y}) = {y}. [ /d] is a linear profile in which the voter d prefers x against y, that is, x y. Thus, since d is a dictator for f , we get f P * [ /d] ({x, y}) = {x}, that is, F P * [ /d] ({x, y}) = {x}. Then, F P * [ /d] ({x, y}) d F P * ({x, y}). Therefore, F is manipulable with respect to → , a contradiction.

	Now, let us consider	a linear ballot for which x	y and note that
	P

*

Figure

summarizes all these results.

A linear order is a total preorder for which antisymmetry holds, and the flat order is that for which all the elements are indifferent between them.

These properties are also known as Gärdenfors principles.

Note that we have chosen to have only nonempty outputs, in order to allow the possibility of having real partial functions. If we admit the empty set as output, we could define as the empty set the output of undefined inputs and then all the functions would be total.

Although Arrow's conditions were stated in the context of social welfare functions, it is not hard to see that, modulo transitive explanations, they are equivalent to the versions presented here for social choice functions (cf.[START_REF] Kelly | Social Choice Theory: An Introduction[END_REF][START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]).

The name of Transitive explanations is the one used by Kelly[START_REF] Kelly | Social Choice Theory: An Introduction[END_REF] for this axiom. This axiom is also called Transitive rationality by Taylor in his book of 2005[START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF]. Moulin[START_REF] Moulin | Axioms of cooperative decision making[END_REF] calls the social choice functions satisfying this property rationalizable choice functions. Sen[START_REF] Sen | Choice functions and revealed preference[END_REF] gives an axiomatic characterization of these functions.

For the case of the indifferent function, it is enough to associate every profile with the flat order.

A voting scheme is a function V that maps a profile P into an element V (P ) of X.

This version of the plurality rule is an adaptation of the plurality rule presented by Taylor[START_REF] Taylor | Social Choice and the Mathematics of Manipulation[END_REF] in the setting of voting rules.

It is easy to see that this function coincides with the Borda rule when the profile is constituted by linear ballots.

A strong version of PI can be established if we consider x * y instead of x * y.

Those social choice functions which give as output the Condorcet winner whenever it exists.

We end this work with some remarks about our results.

1. We have put in evidence a very natural notion which is equivalent to IIA under the hypothesis of nonmanipulability: pairwise indifference. 2. Theorem 2 is interesting because it shows that, under very normal situations as pairwise indifference, the nonmanipulable functions are dictatorial. Actually, this theorem is equivalent to Arrow-Sen impossibility theorem in the class of nonmanipulable social choice functions. 3. Another important feature of Theorem 2 is that it can be considered the source from which other manipulability theorems follow (cf. Figure 2). 4. Theorem 4 is a characterization of dictatorial social choice functions in terms of nonmanipulability when the profiles are restricted to linear ballots. The precise links between this theorem and Gibbard-Satterthwaite Theorem are indeed an interesting challenge. 5. We have established in Theorems 6 to 9 some relations between different notions of powerful voters. Though, in general, these notions are different, under certain conditions these notions coincide. 6. The previous point allows establishing a link between our results and others in the literature (see our discussion in the previous section about our Theorem 5). It is worth to note, however, that the technique used for the proof of Theorem 5 is new and more in the Arrovian style, that is, reducing the problem to an application of Arrow's Theorem. 7. We comment in the previous section that there are some relations between social choice theory and logical belief merging. We wonder if there exists a technical result allowing to translate the information of one domain to the other.

Acknowledgments

We thank the anonymous reviewers for their remarks, which have been very helpful for improving our work. We also thank Professor Olga Porras for her careful proof reading.

The second author has benefited from the support of the AI Chair BE4musIA of the French National Research Agency (ANR-20-CHIA-0028) and has also been partially funded by the program PAUSE of Collège de France and by the Consejo de Desarrollo Científico Humanístico Tecnológico y de las Artes de la Universidad de Los Andes (CDCHTA-ULA) through the Project N • C-1855-13-05-AA.