Multi-Agent Soft Constraint Aggregation via Sequential Voting

1 Introduction

We consider scenarios where a set of agents needs to select a common decision from a set of possible decisions, over which they express their preferences. We also assume that such a decision set has a combinatorial structure, that is, that each decision can be seen as the combination of certain features, where each feature has a set of possible instances. This occurs in several AI applications, such as combinatorial auctions, web recommender systems, and configuration systems. Even if the number of features and instances is small, the number of possible decisions can be very large. Fortunately, in the presence of such a combinatorial structure, agents may describe their preference in a compact and efficient way, using one of the several formalisms available in the literature, such as soft constraints [8], CP-nets [3], and graphical utility models [2]. The goal is to aggregate such preferences and to select the most preferred decision. While such compact preference formalisms are suitable for aggregating the preferences of a single agent, they may lead to undesirable results if used for multi-agent preference aggregation. For example, in soft constraints, the negative opinion of an agent over a specific instance of a feature would impact negatively on any decision containing such an instance, even if all other agents like it. An alternative could be to search for a decision belonging to the Pareto frontier of the multi-agent preferences, as it is done in [6] for preferences expressed via GAI utility functions. Another option, that we study in this paper, is to aggregate the preferences via voting rules.

Voting theory [1] is a wide research area that considers similar scenarios: in an election, voters (called agents) vote by expressing their preferences over a set of candidates (called objects or decisions), and a voting rule decides who the winner candidate is. Voting theory provides many rules to aggregate preferences, each taking as input (a part of) the preference orderings of the agents and giving as output the"winner" object, that is, the object that is considered to be the best according to the rule. In our context, it may take exponential time just to provide a voting rule with what it needs of the preference orderings of the agents. A valid alternative is to use a voting rule several times, on each feature of the object set (possibly using a different voting rule for each feature). That is, the voting rule asks the agents to provide their preferences on each feature at a time, and at each step a winner instance for a certain feature will be returned. At the end, all the winner instances will constitute the winning object.

This approach is certainly more attractive computationally, since usually the number of instances of each feature is small. However, when features are interdependent, it is not clear if the result of this sequential approach is useful at all. In this paper we consider this issue, assuming agents express their preferences via soft constraints.

As an example of the setting we consider, in a combinatorial auction, the features are the various items to be sold, and each bid consists of the agent's preferences over single items or combinations of them. In this context, a sequential approach would consider one item at a time, and at each step it would exploit the bids to allocate this item.

A similar approach has been considered for CP-nets in [7] and partially investigated for soft constraints in [9]. With respect to CP-nets, soft constraints allow one to avoid imposing many restrictions on the agents' preferences, since they are not directional, and thus information can flow from one variable of a constraint to another one without a predefined ordering between them. This allows one to not tie the variable ordering used by the sequential procedure to the topology of the constraint graph of each agent. Moreover, soft constraints can model also strict requirements, which are often necessary in multi-issue settings where one needs to rule out some combinations of feature instances.

In this paper we study some desirable properties of the considered voting rules, namely independence of irrelevant alternatives (IIA), non-dictatorship, and strategy-proofness. We prove that IIA of the sequential procedure implies IIA of all the voting rules used in for the features (also called 'local rules'), while the opposite does not hold. The same results hold for strategy-proofness. On the other hand, non-dictatoriality of the sequential procedure implies nondictatoriality of at least one local rule, and viceversa. We also consider the computational complexity of deciding if a coalition of agents can manipulate the result by forcing the selection of a certain object (aka coalitional constructive manipulation): if it is easy to do this for all local rules, then it is also easy for the sequential procedure, and if it is NPcomplete for at least one local rule, then it is so also for the sequential procedure.

We also show experimentally that the sequential approach is convenient in terms of computation time, while satisfying the agents just as much as the non-sequential approach. Also, the quality of the returned solution is not affected by the ordering of the features, nor by the presence of coalitions of voters (i.e., voters who vote in the same way) in the profile.

2 Background

Soft Constraints. A soft constraint [8] involves a set of variables and associates a value from a (partially ordered) set to each instantiation of its variables. Such a value is taken from a c-semiring, which is defined by 〈A, +, ×, 0, 1〉, where A is the set of preference values, + induces an ordering over A (where a ≤ b iff a + b = b), × is used to combine preference values, and 0 and 1 are respectively the worst and best element. A Soft Constraint Satisfaction Problem (SCSP) is a tuple 〈V, D, C, A〉 where V is a set of variables, D is the domain of the variables and C is a set of soft constraints (each one involving a subset of V ) associating values from A.

An instance of the SCSP framework is obtained by choosing a specific c-semiring. For instance, choosing SFCSP = 〈[0, 1], max,min, 0, 1〉 means that preference are in [0,1] and we want to maximize the minimum preference. This is the setting of fuzzy CSPs (FCSPs) [8], that we will use in the examples of this paper. Consider the following figure, which shows the constraint graph of an FCSP where V = {x, y, z}, D = {a, b} and C = {cx, cy, cz, cxy, cyz}. Each node models a variable and each arc models a binary constraint, while unary constraints define variables' domains. For example, cy associates preference 0.4 to y = a and 0.7 to y = b. Default constraints such as cx and cz will often be omitted in the following examples.

Solving an SCSP means finding the ordering induced by the constraints over the set of all complete variable assignments. In the case of FCSPs, such an ordering is a total order with ties. In the example above, the induced ordering has (x = a, y = b, z = b) and (x = b, y = b, z = b) at the top with a preference of 0.5, (x = a, y = a, z = a) and (x = b, y = a, z = a) just below with 0.4, and all others tied at the bottom with preference 0.2. An optimal solution, say s, of an SCSP is then a complete assignment with an undominated preference (thus (x = a, y = b, z = b) or (x = b, y = b, z = b) in this example). Given a variable x, we write s ↓ x to denote the value of x in s. Finding an optimal solution is an NP-hard problem, unless certain restrictions are imposed, such as a tree-shaped constraint graph.

Constraint propagation may improve the search for an optimal solution. Given a variable ordering o, a FCSP is directional arc-consistent (DAC) if, for any two variables x and y linked by a fuzzy constraint, such that x precedes y in the ordering o, we have that, for each a in the domain of x, fx(a) = maxb∈D(y)(min(fx(a), fxy(a, b), fy(b))), where fx, fy, and fxy are the preference functions of cx, cy and cxy. This definition can be generalized to any instance of the SCSP approach by replacing max with + and min with ×.

DAC is enough to find the preference level of an optimal solution when the problem has a tree-shape and the variable ordering is compatible with the father-child relation of the tree [8]. In fact, such an optimum preference level is the best preference level in the domain of the root variable. To find an optimal solution, it is then enough to perform a backtrack-free search which instantiates variables in the same order used for DAC (thus, from the root of the tree to its leaves). In our running example, if we choose the variable ordering 〈x, y, z〉, achieving DAC means first enforcing the property over y and z and then over x and y. The first phase modifies the preference of y = b to 0.5, while the second phase sets the preferences of both x = a and x = b to 0.5. We note that, by achieving DAC w.r.t. ordering o, we obtain a total order with ties over the values of the first variable in o, where each value is associated to the preference of the best solution having such a variable instantiated to such a value. In our running example, achieving DAC brings both values of x to 0.5 that is the preference of an optimal solution.

Voting Rules. A voting rule allows a set of voters to choose one among a set of candidates. Voters need to submit their vote, that is, their preference ordering over the set of candidates (or part of it), and the voting rule aggregates such votes to yield a final result, usually called the winner. In the classical setting [1], given a set of candidates C, a profile is a collection of total orderings over the set of candidates, one for each voter. Given a profile, a voting rule maps it onto a single winning candidate (if necessary, ties are broken appropriately). In this paper, we will often use a terminology which is more familiar to multi-agent settings: we will sometimes call"agents" the voters,"solutions" the candidates, and "decision" or "best solution" the winning candidate. Some examples of widely used voting rules are: Plurality, where each voter states who the preferred candidate is, and the candidate who is preferred by the largest number of voters wins; Borda, where, given m candidates, each voter gives a ranking of all candidates, the ith ranked candidate scores m-i, and the candidate with the greatest sum of scores wins; Approval, where each voter approves between 1 and m - 1 candidates of m total candidates, and the candidate with most votes of approval wins; Copeland, where the winner is the candidate who wins the most pairwise competitions against all the other candidates.

Voting theory has considered many desirable properties of voting rules. In this paper we will focus on independence of irrelevant alternatives (IIA), non-dictatorship, and strategyproofness. A voting rule is IIA [10] if, whenever a candidate y loses to some winner x, and the relative ranking of x and y does not change in the profile, then y cannot win (independently of any possible change w.r.t. other irrelevant alternatives). A voting rule is non-dictatorial if there is no voter such that the winner is always a top-ranked alternative of this voter (the dictator). A voting rule is strategy proof if it is not manipulable, that is, no voter can get better off by lying on its preference ordering. All the above rules are non-dictatorial and manipulable in general, while only Approval is IIA.

Recently, the computational complexity of several kinds of manipulation has been studied. Coalitional constructive manipulation, denoted by CCM(d,C, r, p), is the problem of deciding if coalition C can make d win in profile p via rule r, and it has been shown, for example, to be in P for Copeland with three candidates and Plurality [4], and NP-complete for Copeland [5].

Sequential preference aggregation. Assume to have a set of agents, each one expressing its preferences over a common set of objects via an SCSP whose variable assignments correspond to the objects. Since the objects are common to all agents, this means that all the SCSPs have the same set of variables and the same variable domains but they may have different constraints, as well as different preferences over the variable domains. In [9] this is the notion of soft profile, which is formally defined as a triple (V,D, P) where V is a set of variables (also called issues), D is a sequence of |V | lexicographically ordered finite domains, and P a sequence of m SCSPs over variables in V with domains in D1 . A fuzzy profile is a soft profile with fuzzy soft constraints. An example of a fuzzy profile where V = {x, y}, Dx = Dy = {a, b, c, d, e, f, g}), and P is a sequence of seven FCSPs, is shown in Fig. 1.

The idea proposed in [9] is to sequentially vote on each variable via a voting rule, possibly using a different rule for each variable. Given a soft profile (V,D, P), assume |V | = n, and consider an ordering of such variables O = 〈v1, . . . , vn〉, and a corresponding sequence of voting rules R = 〈r1, . . . , rn〉 (that will be called "local"). The sequential procedure is a sequence of n steps, where at each step i,

1. All agents are first asked for their preference ordering over the domain of variable vi, yielding profile pi over

1 Notice that a soft profile consists of a collection of SCSPs over the same set of variables, while a profile (as in the classical social choice setting) is a collection of total orderings over a set of candidates.

P6

P7

Figure 1: A fuzzy profile.

such a domain. To do this, the agents will achieve DAC on their SCSP, considering the ordering O2 .

1. Then, the voting rule ri is applied to profile pi, returning a winning assignment for variable vi, say di. If there are ties, the first one following the given lexicographical order will be taken.
2. Finally, the constraint vi = di is added to the preferences of each agent and DAC is applied to propagate its effect considering the reverse order of O.

After all n steps have been executed, the winning assignments are collected in the tuple 〈d1, . . . , dn〉, i.e., the winner of the election. This is denoted by SeqO,R(V,D, P). In the soft profile above, assume the variable ordering is 〈x, y〉 and ri = Approval for all i = 1, ..., n. In step 1, agents apply DAC. This changes the preferences of the agents over x. For example, in P1 and P2, x = a maintains preference 1, x = b gets preferences 0.9, and all other domain values get preference 0, while in P3, x = a and x = c maintain preference 1, x = b gets preference 0.9, while all others get preference 0. Then, Approval is applied over the domain of x where the sets of approved values are: {a} for the first two voters and respectively {c, a}, {d, a}, {e, a}, {f, b}, and {g, b} for the others. Thus, x = a is chosen and the constraint x = a added to all SCSPs, and its effect is propagated via DAC on the domain of y. In step 2, DAC does not modify any preference (since y is the last variable) and the sets of approved values for y are all equal and contain only b. Thus the elected solution with the sequential procedure is s = (x = a, y = b), which has preference 0.7 for P1 and P2, 1 for P3, P4, and P5, and 0.9 for P6 and P7.

An alternative to this sequential procedure would be to generate the preference orderings for each voter from their FCSPs, and then to aggregate them in one step via Approval. In our example, (x = a, y = b) gets 3 votes, (x = a, y = a) and (x = b, y = a) each gets 2 votes, (x = f, y = f), (x = d, y = d), (x = e, y = c), (x = c, y = e), and (x = g, y = g) each gets 1 vote, while all other solutions get no vote. Thus the winner is (x = a, y = b).

The variable ordering which is used in the sequential procedure, is assumed to be given in this paper 3 . In practice, the variable ordering is chosen by the chair of the preference aggregation process, for example by using priority arguments (one may vote first on the most important features), or by aggregating the agents's preferences on such orderings (if the number of features is small, this voting process is feasible).

2 Ties are broken lexicographically if needed (for example, when using Plurality and there are ties at the top level). Also, Approval is given the sets of optimal solutions.

3 In general, different variable orderings may lead to different results. However, some orderings will produce the same result. Intu-

In [9] it is shown that if the sequential procedure is Condorcet consistent, or anonymous, or neutral, or (strongly) monotonic, or consistent, or efficient, or participative, then all the local rules are so. On the other hand, the opposite holds only for anonymity, (strongly) monotonicity, and consistency. In the following sections we will presents results about other important properties: IIA, non-dictatorship, and strategy-proofness.

3 Theoretical results

3.1 Independence of Irrelevant Alternatives

The sequential procedure may be not IIA, even starting from IIA local rules.

Theorem 1 If all the local rules are IIA, the sequential procedure may be non-IIA.

Proof: Consider the fuzzy profile (V,D, P) in Fig. 1, with the variable ordering 〈x, y〉 and where ri = Approval (which is IIA) for each i. In such a scenario the elected solution is s = (x = a, y = b).

Consider now a different profile, where the winner is s′ = (x = b, y = a), which differs from the current profile only on the relationship between assignments other than s′ . The new soft profile is (V,D, P ′ ) where P ′ is obtained from P by swapping the preferences of (x = a, y = a) and (x = b, y = b) in P1 and P2. If we run the sequential election on P ′ , the sets of approved values for x are: {b} for the first two voters and as in P for the other voters. Thus, b is chosen for variable x and, given this, the sets of approved values for y are: {b} for the first two voters and {a} for the remaining five voters. Thus the winning solution is s′ = (x = b, y = a). Thus, despite the fact of using IIA local rules on all variables, the sequential procedure is not IIA. □

On the other hand, if the sequential procedure is IIA, then all local rules are IIA.

Theorem 2 If one of the local rules is not IIA, then the sequential procedure is not IIA as well.

Before proving this theorem, we introduce a notion that will be used, in this proof and in other proofs in this paper, to lift at the sequential procedure level a property that belongs to one of the voting rules used for a variable. In the context of a set of variables V with domain D, and a set of m voters, given a profile pi over a variable vi, we define a soft profile over V , Ext(pi) = (V,D, P), such that for any sequential procedure SeqO,R, where ri is the i-th component of R, SeqO,R(Ext(pi)) ↓ vi = ri(pi), and, in each SCSP in P, the preference of any solution coincides with the preference of its projection on vi. To achieve this, P consists of SCSPs with only unary constraints: the constraint over vi respects

itively, these are orderings that differ just for the relative position of variables that are independent on each other, according to all agents (we omit details for lack of space).

the ordering in pi, all other unary constraints are the same for all voters and associate preference 1 to exactly one value per variable and 0 to all other values. Also, all voting rules are assumed to be unanimous. Intuitively, Ext(pi) extends the orderings over variable vi given by pi to a soft profile over all variables.

Proof: Assume a local rule, say ri, is not IIA. This means that there is a profile over the values of variable vi, say pi, a value for vi, say d ̸= ri(pi), and another profile p′i on values of vi, such that d = ri(p′i ) and the relationship between ri(pi) and d is the same in pi and p′i . Let us now consider the two soft profiles Ext(pi) = (V,D, P) and Ext(p′i ) = (V, D, P ′ ). By definition, we have SeqO,R(Ext(pi)) ↓ vi = ri(pi) and SeqO,R(Ext(p′i )) ↓ vi = ri(p′i ) = d and thus SeqO,R(Ext(pi)) ̸= SeqO,R(Ext(p′i )). Moreover, since the preference for any assignment coincides with the preference of its projection over variable vi, the relationship between SeqO,R(Ext(pi)) and SeqO,R(Ext(p′i )) in each SCSP in P is the same as the one in each corresponding SCSP in P ′ . Thus the sequential approach is not IIA. □

3.2 Non-dictatorship

It is sufficient for one of the local rules to be non-dictatorial in order for the sequential approach to be non-dictatorial as well. The converse holds as well if a specific voter is considered.

Theorem 3 If a local rule is non-dictatorial, then the sequential procedure is non-dictatorial.

Proof: Assume rule ri is non-dictatorial. Thus, for each voter j there exists a profile over variable vi, say pij, such that ri(pij) is not a top element for j. Let us now consider the soft profile Ext(pij). Since SeqO,R(Ext(pij)) ↓ vi = ri(pij), it is not one of j's top candidates. □

Theorem 4 If the sequential procedure is non-dictatorial w.r.t. a given voter, then at least one of the local rules is non-dictatorial w.r.t. the same voter.

Proof: If the sequential procedure is non-dictatorial, then, for each agent j, there exists a soft profile (V,D, Pj) such that SeqO,R(V,D, Pj) is a not an optimal solution of the SCSP of j. If SeqO,R(V,D, Pj) ↓ v1 is not a top element for j on the profile p1 on values of v1 obtained applying DAC, then r1 is non-dictatorial. Otherwise, if SeqO,R(V,D, Pj) ↓ v1 is a top element for j on the profile p1 on values of v1 obtained applying DAC, then we repeat the reasoning for the next local rule. Since SeqO,R(V,D, Pj) is not optimal for j, there must exist a variable vk such that SeqO,R(V,D, Pj) ↓ vk is not a top element for j on the profile p1 on values of vk obtained applying DAC. Thus rk is non-dictatorial. □

3.3 Strategy-proofness

The presence of a local rule that is manipulable jeopardizes the strategy-proofness of the sequential approach. Moreover, the strategy-proofness of all local rules is not sufficient for ensuring the strategy-proofness of the sequential procedure.

Theorem 5 If one of the local rules is not strategy proof, the sequential procedure is not strategy proof.

Proof: Assume a voting rule ri is not strategy proof. Thus, there is an agent j and two profiles over variable vi, say pi and p′i , that differ only because, in p′i , j misreports his preferences which are ri(p′i ) is preferred to ri(pi). Consider now the two soft profiles Ext(pi) and Ext(p′i ). Since SeqO,R(Ext(pi)) ↓ vi = ri(pi) and SeqO,R(Ext(p′i )) ↓ vi = ri(p′i ), agent j prefers SeqO,R(Ext(p′i )) to SeqO,R(Ext(pi)) and has thus succeeded in manipulating the sequential procedure. □

Theorem 6 If all the local rules are strategy proof, the sequential procedure may be non-strategy proof.

Proof: Consider the fuzzy profile with V = {x, y}, D = {a, b}, and P = {P1, P2, P3}, as shown below.

Consider the sequential procedure where O = 〈x, y〉 and ri=Plurality for i = 1, 2 (Plurality over two candidates is strategy proof). The sequential winner is (x = a, y = b). However, if the first voter lies by swapping the preferences of (x = a, y = a) and (x = b, y = a) in P1, then in the first step x = b wins, and the final winner is (x = b, y = a), which is better for him. Thus, the sequential procedure is not strategy proof. □

Turning our attention to the complexity of manipulation, if CCM (coalitional constructive manipulation) is easy for all the local rules, it remains so for the sequential approach. Actually, when obtaining the desired manipulation is easy at the local level, our result gives also a polynomial algorithm to set the preferences of the coalition in order to manipulate at the sequential level. Conversely, if CCM is difficult for at least one of the local rules, then it is so for the sequential procedure.

Theorem 7 If CCM is in P for all the local rules, then it is in P also for the sequential procedure.

Proof: Consider a DAC soft profile (V,D, P) with n variables and m voters such that all the SCSPs, except those of agents in the coalition, have been specified. The goal of the coalition C is to make candidate d = (d1, d2, . . . , dn) win. The sequential procedure SeqO,R used is such that CCM(di,C, ri, P) is in P for every ri in R.

We consider the rules one at a time, following O. It is possible to determine in polynomial time if d1 can win the election on the domain of v1 and, if so, how the coalition should vote on the domain values of v1 to achieve this. If d1 cannot win the local election, then candidate d cannot win the sequential election. If instead d1 can win on v1, then we add for each agent in the coalition a unary constraint on v1 to his SCSP simulating the ordering that that agent in the coalition must give in order to manipulate successfully. In order to so, the best elements in the ordering are given preference 1 and the following values are given any preference that respects the ordering. Then, v1 = d1 is fixed in the SCSPs of all the agents not in the coalition, the result is propagated, and DAC is restored.

Next, in polynomial time the possibility of a constructive manipulation for d2 given r2 is checked, and we proceed as above, until all the variables have been considered. After (at most) n polynomial steps, we will either have determined that d cannot win, or we will have defined the SCSPs of the agents in the coalition so that d does win. We notice that such SCSPs have only unary constraints and thus can be solved in polynomial time. □

Theorem 8 If all the local rules are polynomially computable and CCM is NP-complete for one of the local rules, then it is so also for the sequential procedure.

Proof: We reduce polynomially an instance of CCM for a voting rule r to an instance of CCM for the sequential procedure where one of the local rules is r. An instance of CCM for r consists of a candidate d, a coalition C, and a profile p, written as CCM(d, C, r, p). From such an instance, we construct an instance of CCM for the sequential procedure SeqO,R where R is any finite sequence of voting rules (r1, . . . , rn) including r, say in the i-th position, and O is any ordering of variables v1, . . . , vn, all having the same domain, containing all the candidates appearing in p. Also, the soft profile considered for such an instance is Ext(p), the coalition remains C, and the candidate is E(d) = (d1, . . . , dn) where di = d and dj for j ̸= i has preference 1 in the SCSPs of Ext(p). We will write it CCM(E(d), C, SeqO,R, Ext(p)).

If CCM(d,C, r, p) = true, then, in the sequential instance, coalition C can set its preferences in profile Ext(p) to make E(d) win. In fact, such agents can modify their preferences over the domain of vi in the same way as needed to make d win in the non-sequential instance. Conversely, if CCM(E(d), C, SeqO,R, Ext(p)) = true, then we compute the orderings over the domain of vi when v1 = d1, . . . vi-1 = di-1 (via DAC). By using such orderings, the coalition can make d win in the non-sequential instance. □

4 Experimental results

If r is a voting rule, we denote by seq(r) the sequential procedure where r is applied at each step. We will compare r and seq(r) for several voting rules r in terms of computational cost, satisfaction of voters and sensitivity to coalitions.

To perform the experiments, we have randomly generated profiles with tree-shaped FCSPs based on the following parameters: the number of voters m, the number of variables n, the number of domain elements d, and the tightness t (the percentage of tuples with preference 0 in each fuzzy constraint). Given values to such parameters, we generate a profile with m tree-shaped FCSPs defined over n variables, with d elements in the domain of each variable, and where each fuzzy constraint involves two variables and has a number of tuples with preference 0 which is t% of the maximum number of tuples (that is, d2 ). For the other tuples, we randomly generate preference values in (0, 1]. In each set of tests, we fix all parameters except one, and let this last parameter vary. When a parameter is fixed, we use the following values: m = 25, n = 5, d = 6 and t = 20%. Also, each result is the average over 50 fuzzy profiles with the same parameters' values. The experiments were conducted on a machine with an Intel Core2 Solo 1.40GHz, with

3GB of RAM. We show detailed results only for Borda, since all other rules we considered (Plurality, Approval, and Copeland) have shown the same trends. We have also run experiments that show that the variable ordering does not influence the computation time nor the satisfaction of the agents. Such results are omitted due to lack of space.

Computation time. As it can be seen in Fig. 2, the sequential procedure substantially outperforms the nonsequential rule in terms of the time needed to find the winner. An increase in the values of all the parameters, except tightness, causes a non-trivial growth in the computation time of the non-sequential approach, while leaving the time for the sequential approach practically unchanged.

Solution quality. We measure the error as the distance, for each voter, of his preference for the winner from the preference of his optimal solutions, averaged over all voters. Quite surprisingly, for all rules, the agents are on average almost equally satisfied with the winner elected by the two approaches (see Figure 3). When the number of values in the domains, or the number of variables, grows, the error grows as well. The reason for this is that an increase in the number of solutions makes it less likely for the winner to have a high preference in each SCSP. The same trend can be observed when the number of voters grows. In this case, however, the higher error is due to an increased amount of disagreement among the larger number of voters. This is supported also by the fact that the preference decreases. When tightness grows, instead, the error decreases. In fact, the less solutions with a non-zero preference each FCSP has, the more likely it is that the winner has a preference close to the optimal one for each voter.

Coalitions. Since each agent's SCSP is generated randomly, the probability that two voters vote equally is very small and thus there is a large amount of disagreement among the agents. To check also instances with some amount of consensus among agents, we considered several partitions of a set of 30 voters into subsets, where all the voters in a subset have exactly the same FCSP. The cardinality of the partitions we have considered are 2, 3, 6, 15, and 30. Our experiments

(omitted for lack of space) show that the error decreases as consensus increases. Thus the error shown in Fig. 3 is an upper bound w.r.t. to cases with coalitions. This holds for both the sequential and the non-sequential approach. For example, for the Borda rule, the error of the sequential approach ranges from 0.14 with 2 subsets to 0.31 with 30 subsets and for the non-sequential approach from 0.1 with 2 subsets to 0.3 with 30 subsets.

5 FutureWork

We plan to consider the complexity of other kinds of manipulation, the presence of feasibility constraints over the decision set, and agents' preferences expressed via a combination of compact preference formalisms.