Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions

1 Introduction

In decision making and social choice theory, a number of studies are devoted to ranking individuals based on the performance of the coalitions formed by them. For instance, given values on coalitions of individuals, power indices map these values of coalitions on values of individuals. The seminal works of Shapley [1953] and Banzhaf III [1964] paved the way of a whole research domain and a related literature with many issues, including axiomatization [Laruelle and Valenciano, 2001; Holler and Packel, 1983], applications [Bilbao et al., 2002; Moretti and Patrone, 2008], algorithmic analysis [Matsui and Matsui, 2000] and computational complexity [Deng and Papadimitriou, 1994; Bachrach and Rosenschein, 2009; Faliszewski and Hemaspaandra, 2009]. The nonmanipulability (or strategy proofness) is another fundamental issue. In social choice, since the seminal theorems of Gibbard and Satterthwaite ([Gibbard, 1973] and [Satterthwaite,

∗We are grateful to anonymous reviewers for their critical and helpful comments.

†Contact author.

1975]), we know that every interesting social choice function is manipulable by misrepresentation of preferences. The manipulability is also analysed for power indices. We quote in particular the literature on the paradoxical behaviour of power indices under the modification of some elements of the game, like the number of players or the size of coalitions [Felsenthal et al., 1998; Laruelle and Valenciano, 2005], or the study of manipulation in weighted voting games [Aziz et al., 2011; Zuckerman et al., 2012]. In these models, players are analyzed from a strategic perspective to establish under which conditions they can increase their power adopting malicious behaviors like, for example, splitting or merging.

Power indices (and other indices of individual productivity based on the evaluation of revenues generated by teams [Flores-Szwagrzak and Treibich, 2020]) require a numerical evaluation of coalitions of individuals. Following classical situations in social choice where ordinal data are provided (for instance, voting theory), several articles address the question of defining ordinal notions of power indices when we only have ordinal information over coalitions. This has been formalized as the social ranking from coalitions (SRC) problem, where the objective is to evaluate the "influence" of individuals involved in a collective decision process like an electoral system, a parliament, a governing council, a management board, etc. ([Moretti, 2015; Moretti and ¨Ozt¨urk, 2017]). Basically, an SRC problem consists of a finite set N of individuals and a binary relation ⪰ over some subsets (hereafter called coalitions) of N; the binary relation ⪰ is called power relation and represents the relative power of coalitions in a decision process. A solution or rule for an SRC problem is a "suitable" method aimed to convert the information contained in a power relation ⪰ into a ranking over the single elements of N representing their overall individual power. Several solutions for SRC problems have been proposed in the literature. For instance, in the work by Haret et al. [2018] (and the one by Fayard and ¨Ozt¨urk [2018]) two individuals are compared using information from subsets ranking them under a ceteris paribus interpretation. Bernardi et al. [2019] axiomatically characterize a solution based on the idea that the most influential individuals are those appearing more frequently in the highest positions of the power relation. A rule based on the idea of ordinal marginal contribution has been recently introduced in the paper by Khani et al. [2019].

Following these lines of research, in this article we are interested in the analysis of the strategic manipulation of SRC rules, in the sense that an individual may be interested in behaving maliciously within one or more teams (weakening their group's effectiveness) in order to obtain a better position in the individual ranking. The notion of manipulability for SRC considered in this paper assumes that an individual can only weaken the ranking of teams to which she belongs. In other words, an individual i cannot affect the performances of teams not containing i and, in addition, cannot improve the position of a coalition already containing i.

Example 1. Consider a manager who must decide how to allocate two bonuses over three employees (denoted by 1, 2 and 3). Suppose that she can only compare the performance of teams in an ordinal way: {1, 2, 3} ≻ {1, 3} ≻ {1} ≻ {1, 2} ≻ {2, 3} ≻ {2} ≻ {3} ∼ ∅1 . Suppose the manager wants to keep into account the attitude of employees to cooperate. So, an option is to count the number of (ordinal) positive and negative marginal contributions provided by each employee to all possible coalitions, i.e. 1 contributes positively to four teams (i.e., {1, 2, 3} ≻ {2, 3}, {1, 3} ≻ {3}, {1, 2} ≻ {2} and {1} ≻ ∅), 3 contributes positively to three coalitions while 2 also contributes positively to three coalitions, but negatively to coalition {1, 2}. Therefore the manager would end up to award players 1 and 3. Such a rule could push individual 2 to behave strategically and to undermine the cooperation within coalition {2, 3}. So the new ranking being {1, 2, 3} ≻′ {1, 3} ≻′ {1} ≻′ {1, 2} ≻′ {2} ≻′ {2, 3} ≻′ {3} ∼′ ∅, individuals 1 and 2 should now get the bonus.

To our knowledge, this article is the first one which investigates the manipulation for SRC rules. As in social choice, the manipulability is an important issue in many real-world coalitional frameworks. For instance, within a parliament, small political parties are often able to blackmail a majority coalition by threatening to withdraw from the coalition or to run a candidate of their own [Ferrara, 2004]. In international organizations, the capacity to block the proposals of a group ensures a great visibility of the blocking state's positions. In any organizational context, like a business company or an academic institution, any perceived disparity about the merits of a team's members (e.g., over-remuneration of a leader) may engender internal competition, or even the sabotage of the team by some of it's members. As a sensible example of this kind of behaviors, consider the situation following the Italian general election of March 2018, where no political party got an absolute majority. After 3 months of negotiation, a coalition government was finally formed by the two parties casting the highest number of votes, precisely, the Five Star Movement and the League. However, such a government ended one year after, in August 2019, when the League withdrew its support to the coalition government. As a consequence, the League substantially increased its position in the opinion polls done immediately after the government crisis [Chiaramonte et al., 2020].

The article is organized as follows. We present basic notions and notations in Section 2. In Section 3, we introduce a formal definition of manipulability for an SRC rule and provide theoretical results on four social ranking rules: Copeland-like, Kramer-Simpson-like, Lexicographic Excellence [Bernardi et al., 2019] and Ordinal Banzhaf [Khani et al., 2019]. These social ranking rules display a wide variety of characteristics. The two first ones are based on ceteris paribus comparisons and use the majority principle in a different way. Copeland-like solution is a kind of flow analysis of majority graphs, whereas Kramer-Simpson is a minmax score. Ordinal Banzhaf rule is based on a marginal contribution principle. Lexicographic Excellence (lexcel) considers only information from the best ranked coalitions. We show that only lexcel is not manipulable. In Section 4, we analyse the computational complexity of manipulating each of the three manipulable social ranking rules, and prove that for each of them determining whether an individual can manipulate or not is an NP-hard problem. In Section 5, we present some simulation results on manipulable social ranking rules showing the manipulation frequencies and their vulnerability against the manipulation. Section 6 concludes the article.

1≻ : strict preference, ∼ : indifference.

2 Preliminaries

Let N = {1, . . . , n} be a finite set of elements called individuals and let R ⊆ N × N be a binary relation on N. A preorder is a reflexive and transitive binary relation. A preorder that is total is called total preorder. An antisymmetric 2 total preorder is called linear order. We denote by T (N) the set of all total preorders on N and by 2N the powerset of N, i.e. the set of all subsets (also called, coalitions) of N. Let P ⊆ 2N be a non-empty collection of subsets of N. A power relation on P is a total preorder ⪰⊆ P × P. We denote by T (P) the family of all power relations on every non-empty collection P ⊆ 2N . Given a power relation ⪰∈ T (P) on P ⊆ 2N , we denote by ∼ its symmetric part (i.e. S ∼ T if S ⪰ T and T ⪰ S) and by ≻ its asymmetric part (i.e. S ⪰ T and not T ⪰ S). So, for each pair of subsets S, T ∈ P, S ≻ T means that S is strictly stronger than T , whereas S ∼ T means that S and T are indifferent.

Let ⪰∈ T (P) be of the form S1 ⪰ S2 ⪰ S3 ⪰ · · · ⪰ S|P|. The quotient order of ⪰ is denoted as Σ1 ≻ Σ2 ≻ Σ3 ≻ · · · ≻ Σm in which the subsets Sj are grouped in the equivalence classes Σk generated by the symmetric part of ⪰. This means that all the sets in Σ1 are indifferent to S1 and are strictly better than the sets in Σ2 and so on. So, Σi = Si for any i = 1, . . . , |P| if and only if ⪰ is a linear order.

A social ranking solution or solution on N, is a function R : T (P) -→ T (N) associating to each power relation ⪰∈ T (P) a total preorder R(⪰) (or R⪰) over the elements of N. By this definition, the notion iR⪰j means that applying the social ranking solution to the power relation ⪰ gives the result that i is ranked higher than or equal to j. We denote by I ⪰ the symmetric part of R⪰, and by P ⪰ its asymmetric part. The social score pi(R⪰) of individual i ∈ N in R⪰ is defined as the number of individuals in N \ {i} that are ranked lower than i minus the number of individuals in N \ {i} that are ranked higher than i, that is

2∀i, j ∈ N, iRj and jRi ⇒ i = j.

3 Manipulability

In this paper we focus on a particular notion of manipulation, intended as the "unlimited" capacity of individuals to undermine the position of coalitions to which they belong in a power relation ⪰ on P ⊆ 2N .

Definition 1. Let ⪰∈ T (P) on P be a power relation with the associated quotient order ≻:

Let i be an individual, and C ⊆ P be a collection of coalitions in P all containing i. For all S ∈ C, let j(S) ∈ {1, . . . ,m} be such that S ∈ Σj(S) 3 .

A manipulation of ⪰ by individual i via collection C is another power relation ⪰C on P with ⪰C ̸=⪰ and with the associated quotient order ≻C such that the following two conditions hold:

A social ranking R is manipulable by i on a power relation ⪰ on P if there exists a collection of coalitions C ⊆ P containing i, a manipulation ⪰C of ⪰ by i via C such that

A social ranking solution R is manipulable on a power relation ⪰ if it is manipulable by some individual i.

Condition (ii) says that ⪰C is obtained from ⪰ moving each coalition S ∈ C from the equivalence class to which it belongs in ⪰, to a strictly lower equivalence class (that can also be a new singleton equivalence class containing only S in ⪰C ), while the relation among all the other coalitions not in C is maintained as in ⪰ (condition(i)). The family of all manipulations of ⪰ via collection C is denoted by MC(⪰).

Example 2. Consider the power relation ⪰ such that 4 23 ≻ (123 ∼ 12) ≻ 13 (hence, Σ1 = {23}, Σ2 = {123, 12}, Σ3 = {13}). Imagine that individual 1 wants to manipulate by deteriorating the positions of coalitions in C = {12, 13}. Condition i) of Definition 1 imposes to maintain 23 ≻C 123, condition ii) imposes 23 ≻C 12, 23 ≻C 13, 123 ≻C 12 and 123 ≻C 13 . Hence, the family of all possible manipulations of ⪰ by 1 via collection C is MC(⪰) = {⪰Ca , ⪰Cb , ⪰Cc }, with 23 ≻Ca 123 ≻Ca 12 ≻Ca 13, 23 ≻Cb 123 ≻Cb 13 ≻Cb 12 and 23 ≻Cc 123 ≻Cc 12 ∼Cc 13.

We will now analyse the manipulability of different social ranking rules.

3.1 Copeland-like and Kramer-Simpson-like Rules

Copeland-like and Kramer-Simpson (KS)-like rules are both based on Ceteris Paribus-majority relation, where individuals i and j are ranked according to their relative success over comparisons of coalitions of the type S ∪ i vs. S ∪ j (CPcomparisons), more precisely:

3 j(S) represents the rank of the equivalence class to which S belongs in the initial power relation ⪰.

4 To avoid cumbersome notations later, sets will be written for short without commas and parentheses, e.g., 123 instead of {1, 2, 3}, and S ∪ i instead of S ∪ {i}.

Definition 2 (CP-Majority [Haret et al., 2018]). Let ⪰∈ T (P). The Ceteris Paribus (CP-) majority relation is the binary relation R⪰ CP ⊆ N ×N such that for all i, j ∈ N:

where dij(⪰) represents the cardinality of the set Dij(⪰), the

set of all coalitions S ∈ 2N-{i,j} for which S ∪ i ⪰ S ∪ j 5 . Example 3. Consider: (123 ∼ 12 ∼ 3 ∼ 1) ≻ (2 ∼ 23) ≻ 13. Then, we obtain 1I ⪰ CP 2, 1P ⪰ CP 3, 2I ⪰ CP 3. For instance, 1I ⪰ CP 2 : D12(⪰) = {∅} (1 ≻ 2); D21(⪰) = {3} (23 ≻ 13).

The CP-Majority relation has a major drawback: it can generate cycles within the individual ranking (except under some particular domain restrictions, as suggested in [Haret et al., 2018]). For this reason, we investigate the manipulability of two transitive solutions derived from the CP-Majority, which are inspired, respectively, by the Copeland [Copeland, 1951] and Kramer-Simpson [Simpson, 1969] [Kramer, 1977] voting schemes. These two rules are known to be Condorcet coherent, meaning that when a Condorcet winner (a candidate beating all the other candidates by the majority rule) exists, it is chosen by them. Interestingly, while it can be easily proved that CP-majority relation is not manipulable, Copeland like and KS like solutions are manipulable.

Copeland-like Method

Strongly inspired by the Copeland score of social choice theory, we define Copeland-like solution based on the net flow of CP-majority graph. According to the Copeland solution, individuals are ordered according to the number of pairwise winning comparisons, minus the one of pairwise losing comparisons, over the set of all CP-comparisons.

Definition 3 (Copeland-like solution). Let ⪰∈ T (P). The Copeland-like relation is the binary relation R⪰ Cop ⊆ N × N such that for all i, j ∈ N:

Theorem 1. The Copeland-like solution is manipulable.

Proof. See Example 4 for an instance of manipulation.

Hence, the Copeland-like relation is: 1P ⪰ Cop 2P ⪰ Cop 3. Now imagine that 3 deteriorates the performance of 23 (C = {23})

Now we have: Score⪰C cop (1) = 2, Score⪰C cop (2) = -1, Score⪰C cop (3) = -1. So, now, 3 shares the second position with 2.

5 Note that S can be ∅.

Kramer-Simpson-like Method

Strongly inspired by the Kramer-Simpson method of social choice theory (Minmax), individuals are ranked inversely to their greatest pairwise defeat over all possible CPcomparisons.

Definition 4 (Kramer-Simpson-like solution). Let ⪰∈ T (P). The KS-like relation (KS relation) is the binary relation R⪰KS ⊆ N ×N such that for all i, j ∈ N:

Theorem 2. The Kramer-Simpson (KS)-like solution is manipulable.

Proof. See Example 5 for an instance of manipulation.

Example 5. Consider ⪰ : 2 ≻ (1 ∼ 3) ≻ 12 ≻ (13 ∼ 23) ≻ ∅ ≻ 123. Then, Score⪰KS (1) = 1, Score⪰KS (2) = 0, Score⪰KS (3) = 2. Hence, KS-like solution is: 2P ⪰ KS 1P ⪰ KS 3. Now consider the following manipulation operated by 1 on C = {12}:

The new scores are: Score⪰C KS (1) = 1, Score⪰C KS (2) = 1, Score⪰C KS (3) = 1. So, individual 1 now gets the first position.

Remark 1. For n = 2, the Copeland-like solution and the KS-like solution coincide with the CP-majority relation, hence these solutions are not manipulable for n = 2.

3.2 Ordinal Banzhaf

In the same spirit of the Banzhaf index [Banzhaf III, 1964], the ordinal Banzhaf solution is based on counting the number of positive and negative ordinal marginal contributions.

Definition 5 (Ordinal marginal contribution [Khani et al., 2019]). Let ⪰∈ T (P). The ordinal marginal contribution mSi (⪰) of player i w.r.t. coalition S, i /∈ S, in power relation ⪰ is defined as:

Definition 6 (Ordinal Banzhaf relation). Let ⪰∈ T (P). The ordinal Banzhaf relation is the binary relation R⪰ Banz such that for all i, j ∈ N:

where Score⪰Banz (i) = u+,⪰ i - u-,⪰ i and u+,⪰ i (u-,⪰ i ) is defined as the number of coalitions S with i /∈ S such that mSi (⪰) = 1 (mSi (⪰) = -1).

Theorem 3. The Ordinal-Banzhaf solution is manipulable.

Proof. See Example 6 for an instance of manipulation.

Example 6. Consider ⪰ : 13 ≻ 1 ≻ 12 ≻ 23 ≻ 2 ≻ 3 ≻ 123 ≻ ∅. Then, 1I ⪰ Banz 3P ⪰ Banz 2 since Score⪰Banz (1) = 2, Score⪰Banz (2) = 0, Score⪰Banz (3) = 2 . However, if 2 undermines the cooperation with 1 and 3 (C = {12, 23}): 13 ≻C 1 ≻C 2 ≻C 23 ≻C 3 ≻C 12 ≻C 123 ≻C ∅. Then the three individuals would have a null Banzhaf score and would be ranked equally.

3.3 Lexicographic Excellence Solution

The idea of lexicographic excellence is based on the lexicographic comparison of the frequency of individuals within equivalence classes, and taking care to reward individuals within the most excellent ones. Given the power relation ⪰ and its associated quotient ranking Σ1 ≻ Σ2 ≻ Σ3 ≻ · · · ≻ Σm, we denote by ik the number of sets in Σk containing i:

for k = 1, . . . , l. Now, let θ⪰(i) be the l-dimensional vector θ⪰(i) = (i1, . . . , il) associated to ⪰. Consider the lexicographic order ≥L among vectors i and j: i ≥L j if either i = j or there exists t : ir = jr, r = 1, . . . , t - 1, and it > jt.

Definition 7 (Lexicographic-excellence solution [Bernardi et al., 2019]). Let ⪰∈ T (P). The lexicographic excellence (lexcel) relation is the binary relation R⪰ lexcel such that for all i, j ∈ N:

Example 7. Consider the power relation of Example 2. We have θ⪰(1) = (0, 2, 1) (since 1 is twice in Σ2 and once in Σ3), θ⪰(2) = (1, 2, 0), θ⪰(3) = (1, 1, 1), which yields the following lexcel ranking: 2P ⪰ lexcel 3P ⪰ lexcel 1.

Theorem 4. The lexcel solution is not manipulable.

Proof. Let ⪰∈ T (P) be a power relation on P ⊆ 2N with the associated quotient order ≻:

and let C = {S1, S2, . . . , Sl} ⊆ P and i ∈ N be such that i ∈ ⋂S∈C S (wlog, assume S1 ⪰ S2 ⪰ . . . ⪰ Sl).

Suppose there exists a manipulation ⪰C of ⪰ by i such that pi(R⪰C ) ≥ pi(R⪰). Then there must be some k ∈ N \ {i} such that

First, notice that there exists some coalition S ∈ C such that k /∈ S (otherwise, if i, k ∈ ⋂S∈C S, the manipulation would have no impact on the relative comparison of i and k, since in this case θ⪰(i) ≥L θ⪰(k) ⇔ θ⪰C (i) ≥L θ⪰C (k)).

Now let S∗ ∈ C be a coalition not containing k with the smallest index in C, and let j(S∗ ) ∈ {1, . . . ,m} be such that S∗ ∈ Σj(S∗ ). Since kR⪰ lexcel i, we distinguish two cases:

1. kI ⪰ lexcel i (k and i are indifferent in ⪰ according to the lexcel relation). Then, by Definition 7, θ⪰C v (k) = θ⪰ v (k) = θ⪰ v (i) = θ⪰C v (i) for all v < j(S∗ ), while θ⪰C j(S∗ ) (k) > θ⪰C j(S∗ ) (i). So, kP ⪰C lexcel i;

• ii) kP ⪰ lexcel i (k is strictly stronger than i in ⪰ according to the lexcel relation). So, let t be the smallest index such that θ⪰ t (k) > θ⪰ t (i). Moreover, let q = min(t, j(S∗ )). By Definition 7, θ⪰C v (k) = θ⪰ v (k) = θ⪰ v (i) = θ⪰C v (i) for all v < q and θ⪰C q (k) > θ⪰C q (i). So, again, kP ⪰C lexcel i.

In both cases we get a contradiction with the fact that iR⪰C lexcel k by relation (4). Since C is an arbitrary collection of coalitions in P, we have proved that the lexcel solution is not manipulable.

A drawback of the lexcel solution is that it makes use of a limited amount of information, giving a quasi-dictatorial power to the best ranked coalitions. On the other hand, Copeland-like and KS-like rules are based on the intuitive idea of ceteris paribus comparisons and have the advantage of choosing the Condorcet winner (with respect to the CPmajority relation) when it exists. The Ordinal Banzhaf rule, based on the intuitive notion of ordinal marginal contribution of individuals, also offers another interesting interpretation in terms of fairness. In order to further study the effective impact of manipulation on these three appealing solutions, in Section 4 we analyse the computational complexity of manipulation and in Section 5 we introduce some simulations on several numerical instances.

4 Computational Complexity of Manipulation

As we have seen in the previous section, the Copeland-like solution, the KS-like solution, and the Ordinal Banzhaf solution are manipulable. We strengthen these results in this section by showing that, for each of these social ranking solutions, determining whether an individual can manipulate or not is an NP-hard problem. Let us state the problem precisely. As an instance, we have a set N = {1, . . . , n} of individuals with a manipulator t ∈ N, a set P ⊆ 2N , and a power relation ⪰ on P. The question is to determine whether a given solution is manipulable by t on P, as defined in Definition 1.

Theorem 5. For the Copeland-like solution, the KS-like solution, and the Ordinal Banzhaf solution, the manipulation problem is NP-hard.

Proof. Due to lack of space, we only present the proof for the Ordinal Banzhaf solution. We build the following instance of the manipulation problem under the Ordinal Banzhaf solution. First, let us consider the following individuals:

• we associate to each edge ei ∈ E an individual that we call ei as well (for convenience), and to each vertex v an individual that we call v as well (for convenience);
• two other individuals: t (the manipulator), and α.

For each vertex v, let us call Pv the set containing the subsets of individuals {v, α, t}, {v, t} and all subsets {v, ei, α, t} for each edge ei incident to v. Pv is ordered as follows in ⪰: {v, α, t} is the first one (strictly preferred to any other sets in Pv), {v, t} is the last one, and all {v, ei, α, t} are equivalent, ranked between {v, α, t} and {v, t}.

Note that each set in Pv contains v, so for the scores the relative positions of 2 sets in Pv and Pv′ do not matter; we do not specify it.

The contribution of these sets Pv to the scores are: +|V | for α (due to {v, α, t} ≻ {v, t} for each vertex/individual v), -2 for each object ei (due to {v, α, t} ≻ {v, ei, α, t}, for each of the two extremities of edge ei), and 0 for t (each set contains t).

The idea of the reduction is that, in order to manipulate, t has to become first (defeating α). To do this she shall put {v, α, t} below {v, t} in some Pv. But doing this, the score of the edges incident to v increases. t cannot do this for the two extremities of an edge, otherwise ei defeats him.

To make this true, we need to add dummy individuals to adjust the initial scores of α and t. For the score of α, we add λ = 2k - |V | individuals b1, . . . , bλ. For each bi, we order {bi, α} ≻ {bi}. This gives an extra score of λ = 2k - |V | to α, while bi has score 0. Finally, we add an object γ, and order {γ, t} ≻ {γ}, giving an extra score of 1 to the manipulator t.

Note that as previously we do not need to further specify and/or γ, and/or in different Pv, does not matter with respect

⪰, since the relative positions of sets containing different bi, to the scores (there is no other set inclusion).

To sum up, we have |E| + |V | + 2 + (2k - |V |) + 1 individuals: each individual ei has score -2, individual t has score 1, and α has score |V | + 2k - |V | = 2k. All dummy objects and objects v have score 0. Note that the size of P is polynomial in the size of G.

We claim that t can manipulate if and only if there is an independent set of size k in G.

Suppose that there is an independent set S of size k in G. Then consider the manipulation where, for each v in S, t puts {v, eji , α, t} down to the last position in Pv. Then the score of α decreases by 2k and becomes 0. The score of ei is modified in at most one Pv, since S is an independent set, so it is at most 0. The score of t is still 1, and t manipulated the election.

Conversely, suppose that t can manipulate. Note that t cannot increase her own score, so she must make the score of α at most 1. This means that she has to put {v, α, t} in the last position in at least k sets Pv. Let S be the corresponding set of vertices. If S contains both extremities of one edge ei, then the score of ei becomes +2, and t is not better of. So, in order to manipulate, the set S must be an independent set, and it is of size at least k.

5 Simulations

Inspired by previous works in voting theory [Chamberlin, 1985], we study to what extend the three rules are manipulable. In other terms, based on computer simulations of various power relations, we estimate the probability that a manipulation occurs and we analyse the vulnerability of each solution to manipulation. We only consider situations with a single manipulator and power relations on the whole set 2N . In order to perform our simulations we need to find a manipulation strategy for each rule under the assumption that the manipulator has a complete knowledge about the power relation.

To find a manipulation, we set up an integer linear programming (ILP) formulation of the problem (not detailed here due to lack of space), the variables of which represent the ranking after manipulation. This ILP is efficient enough for small values of n, and we perform our simulation on total power relations over 2N up to n = 5, i.e., power relations on up to 25 = 32 coalitions. The data generation is done using Monte Carlo methods, following uniform (impartial culture) model, which assumes that all power relations over coalitions are equally likely to occur. For each number of individuals n, we generated 1000 random total power relations.

The proportion of manipulable cases. A power relation is manipulable if there exists at least one individual who can manipulate it. The probability of having a manipulable power relation increases rapidly with the number of individuals for the three solutions, especially for the KS relation for which it reaches 99.6% for n = 4 and 100% for n = 5. However, for Copeland it reaches 41% and 92% for Banzhaf (see Figure 1).

Number of possible manipulators. We look at the number of possible manipulators for each manipulable case. The results are shown in Figure 2. The proportion of manipulators grows with the number of individuals. We note also that for Copeland solution, there are on average less possible manipulators for each power relation, and thus has a lower probability of being actually manipulated by one of them.

Manipulating to be the best ranked. We analyse in the following the probability of becoming the best ranked one

Table 1: Percentage of manipulable power relations.

(ties are possible) thanks to a manipulation (see Figure 3).

Cross-simulation. We end our analysis by a cross simulation where for a given power relation we analyze the manipulability with respect to each social ranking rule (Table 1). Table 1 is coherent with our previous results (see Figure 1). Based on the results of simulations, it seems that if a power relation is manipulable by the Copeland-like solution, it is also by the KS-like solution. The most common case is to be manipulable by ordinal the Ordinal Banzhaf solution and the KS-like solution. For these reasons, our conjecture (suggested by the experimental results) is that the Copeland-like solution is not manipulable alone.

6 Conclusion

We have studied the problem of manipulating social ranking solutions. We have shown that lexcel is not manipulable and the manipulation of three other rules is NP-hard. Using simulation, we have remarked that Copeland-like is more resistant to manipulation than the Ordinal Banzhaf solution and the KS-like solution. Our study opens the way for many future works. We quote some of them : An axiomatic characterization of SRC rules taking into account strategy-proofness (like the one of Gibbard and Satterhwaite ([Gibbard, 1973] and [Satterthwaite, 1975])), analysis of the impact on the manipulability of some domain restrictions, study of coalitional manipulation or of simultaneous manipulation (game theoretical issues).