Vote and Aggregation in Combinatorial Domains with Structured Preferences

1 Introduction

Researchers in social choice have extensively studied the properties of voting rules and aggregation functions, up to an important detail: candidates are supposed to be listed explicitly (typically, they are individuals or lists of individuals), which assumes that they are not too numerous. In this paper, we consider the case where the set of candidates has a combinatorial structure, i.e., is a Cartesian product of finite value domains for each of a finite set of variables.

Since the number of possible alternatives is then exponential in the number of variables, it is not reasonable to ask voters to rank all alternatives explicitly. Consider for example that voters have to agree on a common menu to be composed of a first course, a main course, a dessert and a wine, with a choice of 6 items for each. This makes 64 candidates. This would not be a problem if each of the four items to be chosen were independent from the other ones: in this case, this vote over a set of 64 candidates would come down to four independent votes over sets of 6 candidates each, and any standard voting rule could be applied without difficulty. Things become more complicated if voters express dependencies between items, such as "if the main course is meat then I prefer red wine, otherwise I prefer white wine". Indeed, as soon as variables are not preferentially independent, it is generally a bad idea to decompose a vote problem with p variables into a set of p smaller problems, each one bearing on a single variable: "multiple election paradoxes" [Brams et al., 1998]

show that such a decomposition leads to suboptimal choices, and give real-life examples of such paradoxes, including simultaneous referenda on related issues. They argue that the only way of avoiding the paradox would consist in "voting for combinations [of values]", but they stress its practical difficulty without giving any hint for a practical solution.

Because the preference structure of each voter in such a case cannot reasonably be expressed by listing all candidates, what is needed is a compact preference representation language. Such languages have been developed within the Artificial Intelligence community so as to escape the combinatorial blow up of explicit representations. Many of these languages (including CP-nets and their extensions) are graphical: preferences are expressed locally (on small subsets of variables). The common feature of these languages is that they allow for a concise representation of the preference structure, while preserving a good readability (and hence a proximity with the way agents express their preferences in natural language).

Thus, AI gives a first answer to the problem pointed in [Brams et al., 1998]. However, another problem arises: once preferences have been elicited, and represented in some compact language, how is the voting rule computed? The prohibitive number of candidates makes it practically impossible to compute these rules in a straightforward way.

When domains are not too large, it may still be reasonable to first generate the whole preference relations from their compact representations and then compute the outcome by a direct implementation of the voting rule. However, when domains become bigger, this naive method becomes too greedy and then we need to find a more sophisticated way of computing the outcome of the vote. Two methods come to mind: either (1) give up optimality and compute an approximation of the voting or aggregation rule, or (2) assume that the voters' preferences enjoy specific structural properties that can be exploited so as to decompose the problem into smaller, local subproblems. Here we address (2), and we focus on a specific restriction of preference profiles where all voters have a preference relation enjoying conditional preferential independencies compatible with a common acyclic graph G. After giving some background on preference relations over combinatorial domains and vote in Section 2, we introduce and study sequential voting rules in Section 3. Section 4 then considers preference aggregation over combinatorial domains, and Section 5 concludes.

2 Background

2.1 Preferences on combinatorial domains

Let V = {x1, . . . , xp} be a set of variables. For each xi ∈ V , Di is the value domain of xi. A variable vi is binary if Di = {xi, xi}. Note the difference between the variable xi and the value xi. If X = {xi1 , . . . , xim } ⊆ V , with i1 < . . . < ip, then DX denotes Di1 × . . . × Dim .

X = D1 × ... ×Dp is the set of all alternatives, or candidates. Elements of X are denoted by ⃗x, ⃗x′ etc. and represented by concatenating the values of the variables: for instance, if V = {x1, x2, x3}, x1x2x3 assigns x1 to x1, x2 to x2 and x3 to x3. We allow concatenations of vectors of values: for instance, let V = {x1, x2, x3, x4, x5}, Y = {x1, x2}, Z = {x3, x4}, ⃗y = x1x2, ⃗z = x3x4, then ⃗y.⃗z.x5 denotes the alternative x1x2x3x4x5.

A (strict) preference relation on X is a strict order (an irreflexive, asymmetric and transitive binary relation). A linear preference relation is a complete strict order, i.e., for any ⃗x and ⃗y ̸= ⃗x, either ⃗x ≻ ⃗y or ⃗y ≻ ⃗x holds. If R is a preference relation, we generally note ⃗x ≻R ⃗x′ instead of R(⃗x, ⃗x′ ).

Let {X, Y,Z} be a partition of the set V of variables and ≻ a linear preference relation over DV . X is (conditionally) preferentially independent of Y given Z (w.r.t. ≻) if and only if for all ⃗x1, ⃗x2 ∈ DX, ⃗y1, ⃗y2 ∈ DY , ⃗z ∈ DZ,

Unlike probabilistic independence, preferential independence is a directed notion: X may be independent of Y given Z without Y being independent of X given Z.

A CP-net N [Boutilier et al., 2004] over V is a pair consisting of a directed graph G over V and a collection of conditional preference tables CPT(xi) for each xi ∈ V . Each conditional preference table CPT(xi) associates a total order 1 ≻i⃗u with each instanciation ⃗u of xi's parents Pa(xi) = U. For instance, let V = {x, y, z}, all three being binary, and assume that preference of a given agent over 2V can be defined by a CP-net whose structural part is the directed acyclic graph G = {(x, y), (y, z), (x, z)}; this means that the agent's preference over the values of x is unconditional, preference over the values of y (resp. z) is fully determined given the value of x (resp. the values of x and y).

The conditional preference statements contained in these tables are written with the usual notation, that is, x1x2 : x3 ≻ x3 means that when x1 is true and x2 is false then x3 = x3 is preferred to x3 = x3. In this paper we make the classical assumption that G is acyclic. A CP-net N induces a preference ranking on X: ⃗x ≻N ⃗y iff there is a sequence of improving flips from ⃗y to ⃗x, where an improving flip is the flip of a single variable ⃗xi "respecting" the preference table CPT (xi) (see [Boutilier et al., 2004]). Note that the preference relation induced from a CP-net is generally not complete.

Let G be a directed graph over V , and ≻ a linear preference relation. ≻ is said to be compatible with G iff for each x ∈ V , x is preferentially independent of V \ ({x} ∪ Par(x)) given Par(x). The following fact is obvious, but important:

1 More generally, the entries of conditional preference tables may contain partial orders over the domains of the variables (see [Boutilier et al., 2004]), but we don't need this here.

Observation 1 A linear preference relation ≻ is compatible with G if and only if there exists a CP-net N whose associated graph is G and such that ≻ extends ≻N .

Let G be an acyclic graph over V and let O = x1 > ... > xp be a linear order on V . G is said to follow O iff for every edge (xi, xj) in G we have i < j. A linear preference relation ≻ is said to follow O iff it is compatible with some acyclic graph G following O. Clearly, ≻ follows O = x1 > ... > xp if and only if for all i < p, xi is preferentially independent of {xi+1, ..., xp} given {x1, ..., xi-1} with respect to ≻. If ≻ follows O then the projection of ≻ on xi given (x1, . . . , xi-1) ∈ D1 × . . . × Di-1, denoted by ≻xi|x1=x1,...,xi-1=xi-1 , is the linear preference relation on Di defined by: for all xi, x′i ∈ Di, xi ≻xi|x1=x1,...,xi-1=xi-1 x′i iff x1...xi-1xixi+1...xp ≻ x1...xi-1x′ixi+1..xp holds for all (xi+1, . . . , xp) ∈ Di+1 × . . . ×Dp.

Due to the fact that ≻ follows O and that ≻ is a linear order, ≻xi|x1=x1,...,xi-1=xi-1 is a well-defined linear order as well. Note also that if ≻ follows both O = x1 > ... > xp and O′ = xσ(1) > ... > xσ(k-1) > xi(= xσ(k)) > ... > xσ(p), then ≻xi|x1=x1,...,xi-1=xi-1 and ≻xi|xσ(1)=xσ(1),...,xσ(k-1)=xσ(k-1) coincide. In other words, the local preference relation on xi depends only on the values of the variables that precede xi in O and in O′ .

Lastly, for any acyclic graph G over V , we say that two linear preference relations R1 and R2 are G-equivalent, denoted by R1 ∼G R2, if and only if R1 and R2 are both compatible with G and for any x ∈ V , for any ⃗y, ⃗y′ ∈ Dom(par(x)) we have Rx|par(x)=⃗y 1 = Rx|par(x)=⃗y 2 .

Observation 2 For any linear preference relations R and R′ , R ∼G R′ if and only if there exists a CP-net N whose associated graph is G and such that R and R′ both extend ≻N .

Example 1 Let V = {x, y, z}, all three being binary. and let R and R′ be the following linear preference relations:

R : xyz ≻ xy¯ z ≻ x¯ y¯ z ≻ x¯ yz ≻ ¯xy ¯ z ≻ ¯x¯ y¯ z ≻ ¯xyz ≻ ¯x¯ yz

R′ : xyz ≻ xy¯ z ≻ ¯xy ¯ z ≻ x¯ y¯ z ≻ ¯xyz ≻ ¯x¯ y¯ z ≻ x¯ yz ≻ ¯x¯ yz

Let G the graph over V whose set of edges is {(x, z), (y, z)}. R and R′ are both compatible with G. Moreover, R ∼G R′ , since all local preference relations coincide: x ≻xR ¯x and x ≻xR′ ¯x; z ≻z|x=x,y=y R ¯ z and z ≻z|x=x,y=y R′ ¯ z; etc. The CP-net N such that R and R′ both extend ≻N is defined by the following local conditional preferences: x ≻ ¯x; y ≻ ¯ y; xy : z ≻ ¯ z; x¯ y : ¯ z ≻ z; ¯xy : ¯ z ≻ z; ¯x¯ y : ¯ z ≻ z.

2.2 Voting rules and correspondences

Let A = {1, ..., N} be a finite set of voters and X a finite set of candidates. A (collective) preference profile w.r.t. A and X is a collection of N individual linear preference relations over X: P = (≻1, ..., ≻N) = (P1, ..., PN). Let PA,X be the set of all preference profiles for A and X .

A voting correspondence C : PA,X → 2X \{∅} maps each preference profile P of PA,X into a nonempty subset C(P) of X. A voting rule r : PA,X → X maps each preference profile P of PA,X into a single candidate r(P ). A rule can be obtained from a correspondence by prioritization over candidates (for more details see [Brams and Fishburn, 2004]).

To give an example, consider the well-known family of positional scoring rules and correspondences. A positional scoring correspondence is defined from a scoring vector, that is, a vector ⃗s = (s1, . . . , sm) of integers such that s1 ≥ s2 ≥ . . . ≥ sm and s1 > sm. Let ranki(x) be the rank of x in ≻i (1 if it is the favorite candidate for voter i, etc.). The score of x is defined by S(x) = ∑Ni=1 sranki(x). The correspondence defined from ⃗s selects all candidates maximizing S. A positional voting rule is defined as a positional scoring correspondence plus a tie-breaking mechanism. Well-known examples are the Borda rule, given by sk = m- k for all k, and the plurality rule, by s1 = 1, and sk = 0 for all k.

We also recall the definition of a Condorcet winner (CW). Given a profile P = (≻1, ..., ≻N), x ∈ X is a Condorcet winner iff it is preferred to any other candidate by a strict majority of voters, that is, for all y ̸= x, #{i, x ≻i y} > N2 . It is well-known that there are some profiles for which no CW exists. Obviously, when a CW exists then it is unique.

3 Sequential voting

Given a combinatorial set of alternatives and a compact representation (in some preference representation language R) of the voters' preferences, how can we compute the (set of) winner(s)? The naive way consisting in "unfolding" the compactly expressed preferences (that is, generating the whole preference relations on D1 × . . . ×Dp from the input), and then applying a given voting rule, is obviously unfeasible, except if the number of variables is really small. We can try to do better and design an algorithm for applying a given voting rule r on a succinctly described profile P without generating the preferences relations explicitly. However, we can't be too optimistic, because it is known that the latter problem is computationally hard, even for simple succinct representation languages and simple rules (see [Lang, 2004]).

A way of escaping this problem consists in restricting the set of admissible preference profiles in such a way that computationally simple voting rules can be applied. A very natural restriction (that we investigate in the next Section) consists in assuming that preferences enjoy some specific structural properties such as conditional preferential independencies.

3.1 Sequential voting rules and correspondences

Now comes the central assumption to the sequential approach: there exists an acyclic graph G such that the linear preference relation of every voter is compatible with G. This assumption is not as restrictive as it may appear at first look: suppose indeed that the linear preference relations (≻1, . . . ,≻N) are compatible with the acyclic graphs G1, . . . , GN , whose sets of edges are E1, . . . , EN . Then they are a fortiori compatible with the graph G∗ whose set of edges is E1 ∪ . . . ∪EN. Therefore, if G∗ is acyclic, then sequential voting will be applicable to (≻1, . . . ,≻N) (of course, this is no longer true if G∗ has cycles). Moreover, in many real-life domains it may be deemed reasonable to assume that preferential dependencies between variables coincide for all agents.

Sequential voting consists then in applying "local" voting rules or correspondences on single variables, one after the other, in such an order that the local vote on a given variable can be performed only when the local votes on all its parents in the graph G have been performed.

We define CompG as the set of all collective profiles P = (≻1, . . . ,≻N) such that each ≻i is compatible with G.

Definition 1 Let G be an acyclic graph on V ; let P = (P1, ..., PN) in CompG, O = x1 > ... > xp a linear order on V following G, and (r1, . . . , rp) a collection of deterministic voting rules (one for each variable xi). The sequential voting rule Seq(r1, . . . , rp) is defined as follows:

• x∗1 = r1(P x1 1 , . . . , P x1 N );

· . . .

Example 2 Let N = 12, V = {x, y} with Dom(x) = {x, ¯x} and Dom(y) = {y, ¯ y}, and P = 〈P1, . . . , P12〉 the following 12-voter profile:

All these linear preference relations are compatible with the graph G over {x, y} whose single edge is (x, y); equivalently, they follow the order x > y. Hence, P ∈ CompG. The corresponding conditional preference tables are:

voters 1,2,3,4 voters 5,6,7 voters 8,9,10 voters 11,12

Take rx and ry both equal to the majority rule, together with a tie-breaking mechanism which, in case of a tie between x and ¯x (resp. between y and ¯ y), elects x (resp. y). The projection of P on x is composed of 7 votes for x and 5 for ¯x, that is, P x i is equal to x ≻ ¯x for 1 ≤ i ≤ 7 and to ¯x ≻ x for 8 ≤ i ≤ 12. Therefore x∗ = rx(P x 1 , . . . , P x 12 ) = x: the xwinner is x∗ = x. Now, the projection of P on y given x = x is composed of 7 votes for y and 5 for ¯ y, therefore y∗ = y, and the sequential winner is now obtained by combining the x-winner and the conditional y-winner given x = x∗ = x, namely Seqrx,ry (P ) = xy.

In addition to sequential voting rules, we also define sequential voting correspondences in a similar way: if for each i, Ci is a correspondence on Di, then Seq(C1, . . . ,Cp)(P) is the set of all outcomes (x1, . . . , xp) such that x1 ∈ C1(P x1 1 , . . . , P x1 N ), and for all i ≥ 2, xi ∈ Ci(P xi|x1=x1,..,xi-1=xi-1 i , .., P xi|x1=x1,..,xi-1=xi-1 N ). Due to the lack of space, we give results for voting rules only.

An important property of such sequential voting rules and correspondences is that the outcome does not depend on O, provided that G follows O. This can be expressed formally:

Observation 3 Let O = (x1 > . . . > xp) and O′ = (xσ(1) > . . . > xσ(p)) be two linear orders on V such that G follows both O and O′ . Then

Seq(r1, . . . , rp)(P) = Seq(rσ(1), . . . , rσ(p))(P) and similarly for voting correspondences.

Note that when all variables are binary, all "reasonable" neutral voting rules (we have no space to comment on what "reasonable" means - and this has been debated extensively in the social choice literature) coincide with the majority rule when the number of candidates is 2 (plus a tie-breaking mechanism). Therefore, if all variables are binary and the number of voters is odd (in which case the tie-breaking mechanism is irrelevant), then the only "reasonable" sequential voting rule is Seq(r1, . . . , rn) where each ri is the majority rule.

It is important to remark that, in order to compute Seq(r1, . . . , rp)(P), we do not need to know the linear preference relations P1, . . . , PN entirely: everything we need is the local preference relations: for instance, if V = {x, y} and G contains the only edge (x, y), then we need first the unconditional linear preference relations on x and then the linear preference relations on y conditioned by the value of x. In other words, if we know the conditional preference tables (for all voters) associated with the graph G, then we have enough information to determine the sequential winner for this profile, even though some of the preference relations induced from these tables are incomplete. This is expressed more formally by the following fact (a similar result holds for correspondences):

Observation 4 Let V = {x1, . . . , xp}, G an acyclic graph over V , and P = (P1, . . . , PN), P ′ = (P ′1 , . . . , P ′N ) two complete preference profiles such that for all i = 1, . . . ,N we have Pi ∼G P ′ i . Then, for any collection of local voting rules (r1, . . . , rp), we have

This, together with Observation 2, means that applying sequential voting to two collections of linear preference relations corresponding to the same collection of CP-nets gives the same result. This is illustrated on the following example.

Example 3 Everything is as in Example 2, except that we don't know the voters' complete preference relations, but only their corresponding conditional preference tables. These conditional preferences contain strictly less information than P, because some of the preference relations they induce are not complete: for instance, the induced preference relation for the first 4 voters is xy ≻ ¯xy ≻ ¯x¯ y, xy ≻ x¯ y ≻ ¯x¯ y, with x¯ y and ¯xy being incomparable. However, we have enough information to determine the sequential winner for this profile, even though some of the preference relations are incomplete. For instance, taking again the majority rule for rx and ry, the sequential winner is xy for any complete profile P ′ = (P ′1 , . . . , P ′12 ) extending the incomplete preference relations induced by the 12 conditional preference tables above.

3.2 Sequential decomposability

We now consider the following question: given a voting rule r, is there a way of computing r sequentially when the linear preference relations enjoy common preferential independencies?

Definition 2 A voting rule r on X = D1 × . . . × Dp is decomposable if and only if there exist n voting rules r1, . . . , rp on D1, . . . , Dp such that for any linear order O = x1 > ... > xp on V and for any preference profile P = (P1, ..., PN) such that each Pi follows O, we have Seq(r1, . . . , rp)(P) = r(P). The definition is similar for correspondences.

An interesting question is the following: for which voting rules r does the sequential winner (obtained by sequential applications of r) and the "direct" winner (obtained by a direct application of r) coincide? The following result shows that this fails for the whole family of scoring rules (and similarly for correspondences).

Proposition 1 No positional scoring rule is decomposable.

Proof sketch: We give a proof sketch for the case of two binary variables (this generalizes easily to more variables, as well as to non-binary variables). Let r be a decomposable scoring rule on 2{x,y} : there exist two local rules rx and ry such that whenever P follow x > y, we have Seq(rx, ry)(P) = r(P). Then we show that rx and ry are both the majority rule (this follows easily from the fact that some properties of r, including monotonicity, carry on to rx and ry.) Now, consider the same preference profile P as in Example 3. P follows the order x > y. Now, let s1 ≥ s2 ≥ s3 ≥ s4 = 0 (with s1 > 0) the weights defining r. The score of xy is 4s1 +3s2 +3s3; the score of ¯xy is 5s1 +4s2 +3s3, which is strictly larger than the score of xy, therefore xy cannot be the winner for r, whatever the values of s1, s2, s3. ■

Such counterexamples can be found for many usual voting rules outside the family of scoring rules (we must omit the results due to the lack of space), including the whole family of voting rules based on the majority graph. Positive results, on the other hand, seem very hard to get. Obviously, dictatorial rules (electing the preferred candidate of some fixed voter) and constant rules (electing a fixed candidate whatever the voters' preferences) are decomposable. But the latter rules are of course not reasonable, and we conjecture that the answer to the above question is negative as soon as a few reasonable properties are required. .

A particular case of preferential independence is when all variables are preferentially independent from each other, which corresponds to a dependency graph G with no edges. In this case, the preference profile follows any order on the set of variables, and the sequential winner is better called a parallel winner, since the local votes on the single variables can be performed in any order. We might then consider the following property of separability:

Definition 3 A deterministic rule r is separable if and only if for any preference profile P = (≻1, ..., ≻N) such that the variables are pairwise conditionally preferentially independent, the parallel winner of r w.r.t. P is equal to r(P).

Obviously, any decomposable rule is separable. Are there any separable rules? Focusing on positional scoring rules, we find a rather intriguing result (the proof of which is omitted):

• if p = 2 and both variables are binary, exactly one positional scoring rule is separable: the rule associated with the weights s1 = 2s2 = 2s3 (and s4 = 0).
• in all other cases (p ≥ 3 or at least one variable has more than 2 possible values), then no positional scoring rule is separable.

3.3 Sequential Condorcet winners

We may now wonder whether a Condorcet winner (CW), when there exists one, can be computed sequentially. Sequential Condorcet winners (SCW) are defined similarly as for sequential winners for a given rule: the SCW is the sequential combination of "local" Condorcet winners.

Definition 4 Let G be an acyclic graph and P = (≻1, ..., ≻N) a profile in CompG. Let O = x1 > ... > xp be a linear order on V following G. (x∗1 , . . . , x∗p ) is a sequential Condorcet winner for P if and only if

• ∀x′1 ∈ D1, #{i, x∗1 ≻x1 i x′1 } > N2 ;
• for every k > 1 and ∀x′k ∈ Dk, #{i, x∗k ≻xk|x1=x∗1 ,...,xk-1=x∗k-1 i x′k } > N2 .

This definition is well-founded because we obtain the same set of SCWs for any O following G. The question is now, do SCWs and CWs coincide? Clearly, the existence of a SCW is no more guaranteed than that of a CW, and there cannot be more than one SCW. We have the following positive result, whose proof (which we omit) does not present any difficulty:

Proposition 3 Let G be an acyclic graph and P = (≻1, ..., ≻N) in CompG. If (x∗1 , x∗2 , . . . , x∗n ) is a Condorcet winner for P, then it is a sequential Condorcet winner for P.

The following example shows that the converse fails: 2 voters have the preference relation x¯ y ≻ ¯x¯ y ≻ xy ≻ ¯xy, one voter xy ≻ x¯ y ≻ ¯xy ≻ ¯x¯ y, and 2 voters ¯xy ≻ ¯x¯ y ≻ xy ≻ x¯ y. x and y are mutually preferentially independent in all relations, therefore the SCW is the combination of the locals CW for {x} and for {y}, provided they exist. Since 3 voters unconditionally prefer x to ¯x, x is the {x}-CW; similarly, 3 voters unconditionally prefer y to ¯ y and y is the {y}-CW. Therefore, xy is the SCW for the given profile; but xy is not a CW for this profile, because 4 voters prefer ¯x¯ y to xy.

Note that Proposition 3 extends to weak Condorcet winners (where strict majority is replaced by weak majority).

We now give a condition on the preference relations ensuring that SCWs and CWs coincide. Let O = x1 ▷ . . . ▷ xp be a linear order on V . We say that a linear preference relation ≻ on DX is conditionally lexicographic w.r.t. O if there exist p local conditional preference relations ≻xi|x1=x1,...,xi-1=xi-1 x′i for i = 1, .., p, such that ⃗x ≻ ⃗y if and only if there is a j ≤ p such that (a) for every k < j, xk = yk and (b) xj ≻xj|x1=x1,...,xj-1=xj-1 yj. A profile P = (≻1, . . . ,≻N) is conditionally lexicographic w.r.t. O if each ≻i is conditionally lexicographic w.r.t. O. Such preference relations can be represented by TCP-nets [Brafman et al., 2006] or conditional preference theories [Wilson, 2004].

Proposition 4 Let O be a linear strict order over V . If P = (≻1, . . . ,≻N) is conditionally lexicographic w.r.t. O, then ⃗x is a sequential Condorcet winner for P if and only if it is a Condorcet winner for P .

4 Arrow's theorem and structured domains

We end this paper by considering decomposable domains from the point of view of preference aggregation. A preference aggregation function maps a profile to an aggregated profile representing the preference of the group. Arrow's theorem [Arrow, 1963] states that any aggregation function defined on the set of all profiles and satisfying unanimity and independence of irrelevant alternatives (IIR) is dictatorial. An Arrow-consistent domain D is a subset of P allowing for unanimous, IIR and nondictatorial aggregation functions.

It is easy to see that for any acyclic graph G, Comp(G) is Arrow-consistent. Indeed, consider the preference aggregation function defined as follows:

• reorder the variables in an order compatible with G, i.e., w.l.o.g., assume that there is no edge (xi, xj) in G with i ≥ j. Such an order exists because G is acyclic.
• let h : V → A be a non-constant mapping from variables to voters (such a mapping exists because |V | ≥ 2 and |A| ≥ 2).
• for any ⃗x and ⃗y ̸= ⃗x, let k(⃗x, ⃗y) = min{j, xj ̸= yj}.
• for any collective profile 〈≻1, . . . ,≻N〉, define ≻∗= fh(≻1, . . . ,≻N) by: for all ⃗x and ⃗y, ⃗x ≻∗ ⃗y if xk ≻xk|x1=x1,...,xn=xn h(k) yk, where k = k(⃗x, ⃗y).

Proposition 5 fh is a nondictatorial aggregation function on Comp(G) satisfying unanimity and IIR.

Thus, restricting the set of admissible profiles to Comp(P ) is sufficient for escaping Arrow's theorem: in other terms, Comp(G) is Arrow-consistent 2 . fh is easier understood when it is turned into a voting rule: voter h(x1) first chooses his preferred value for variable x1, then voter h(x2) comes into play and chooses his preferred value for variable x2 given the value assigned to x1, and so forth. Note that fh is truly nondictatorial, because no agent imposes her own preference to the group; however fh however has p local dictators (one for each variable), since voter h(i) imposes his preference on the domain of xi. We now prove that there must exist such local dictators, provided that the following three properties are satisfies:

• (P1) preservation of the independence structure f is a mapping from Comp(G)N to Comp(G).
• (P2) independence of irrelevant values and variables For any xi ∈ V , ⃗z ∈ DPar(xi), and P = 〈P1, . . . , PN〉, Q = 〈Q1, . . . ,QN〉 in Comp(G)N such that for every j and all x, x′ ∈ Di, x ≻xi|⃗z Pj x′ iff x ≻xi|⃗z Qj x′ , we have x ≻xi|⃗z f(P) x′ if and only if x ≻xi|⃗z f(Q) x′ .

(P3) local unanimity

(P1) expresses that the preferential independencies expressed in the graph G should be transferred to the aggregated preference relation. Therefore, under (P1), for any preference relation ≻∗ resulting from the aggregation of N preferences relations in Comp(G) there exist p local conditional preference relations ≻xi|Par(xi) ∗ , for i = 1, . . . , p.

2 As a referee pointed out to me, this domain restriction does not preclude the existence of Condorcet triples, which suggests that it is not as strong as it may seem at first glance.

(P2) is a local version of independence of irrelevant alternatives: whether the society prefers a value xi to another value yi of xi given an assignment ⃗z of the parent variables of xi depends only on the voters' preferences between these two values given ⃗z (and not on their preferences on other values of xi nor on their preferences on other variables.)

(P3) tells that if all voters have the same local preference relation over the values of a variable xi given a fixed value ⃗z of its parents, then the local collective preference on Dxi given ⃗z should be equal to this local preference relation.

Importantly, note that the way (P2) and (P3) are written depends on the assumption that (P1) holds - otherwise we would not have been allowed to write ≻xi|⃗z f (P ) .

Proposition 6 Let G be an acyclic graph over a set of variables V = {x1, . . . , xp} with domains D1, . . . ,Dp, with |Di| ≥ 3 for each i. An aggregation function f on Comp(G) satisfies (P1), (P2) and (P3) if and only if there exists a local dictator d(xi, ⃗z) for each xi and each ⃗z ∈ DPar(xi), such

Proof sketch: The ⇐ direction is straightforward. For the ⇒ direction, let f satisfying (P1), (P2) and (P3). (P1) guarantees that for every xi and ⃗z ∈ DPar(xi), xi is independent of V \ (DPar(xi) ∪ {xi}) given ⃗z, therefore there exists a local collective preference relation ≻xi|⃗z ∗ such that for all ⃗t ∈ DV \(Par(xi) ∪ {xi}) and for all xi, x′i ∈ Dxi , xi ≻xi|⃗z ∗ x′i. (P2) implies that ≻xi|⃗z ∗ is fully determined by voters' preferences on the values of xi given ⃗z. Therefore, there exists a local aggregation function f xi|⃗z such that ≻xi|⃗z ∗ = f xi|⃗z (≻xi|⃗z 1 , . . . ,≻xi|⃗z N ). f xi|⃗z is easily shown to satisfy the conditions of Arrow' theorem. Applying Arrow's theorem to each f xi|⃗z enables us to conclude to the existence of a dictator d(xi, ⃗z) for each xi and each ⃗z ∈ DPar(xi), such that xi ≻f xi|⃗z (≻xi|⃗z 1 ,...,≻xi|⃗z N ) x′i ⇔ xi ≻xi|⃗z d(xi,⃗z) x′i. Now, the fact that ≻xi|⃗z ∗ = f xi|⃗z (≻xi|⃗z 1 , . . . ,≻xi|⃗z N ) allows us to conclude that xi ≻xi|⃗z d(xi,⃗z) x′i is equivalent to xi ≻xi|⃗z f(≻1,...,≻N) x′i , which in turn is equivalent to: for all ⃗t ∈ DV \(Par(xi)∪{xi}) and for all xi, x′i ∈ Dxi , ⃗z⃗txi ≻∗ ⃗z⃗tx′i, where ≻∗= f(≻1, . . . , ≻N). ■

Note that the local dictator for a given variable may depend on the values of its parents. For instance, with two variables x and y and a dependency graph with the edge (x, y), we have a single dictator for xi and up to |Dx| dictators for y.

Corollary 1 Let Sep(V ) be the domain of fully separable linear preference relations on DV . An aggregation function f on Sep(V ) satisfies (P1), (P2) and (P3) iff there exists p local dictators d(xi), . . . , d(xp) such that for each ⃗t ∈ DV \{xi},

Finally, note that knowing the local dictators does not fully determine f. For instance, let V = {x, y}, and G with no edge. Assume voter 1 prefers x1 to x2 and voter 2 prefers y1 to y2. ≻∗= f(≻1,≻2) satisfies x1 ≻⃗x∗ x2 and y1 ≻⃗y∗ y2, but this does not tell whether x1y2 ≻∗ x2y1 or x2y1 ≻∗ x1y2.

5 Conclusion

As far as we know, aggregating structured preferences on combinatorial domains exploiting preferential independence properties has never been considered neither in social choice nor in AI. [Rossi et al., 2004] define a multi-agent extension to CP-nets and propose various semantics for aggregating preferences; but they do not address computational issues.

This paper contains several negative results. But one important question is left unanswered: what are the sequentially decomposable voting rules? Answering this question (by finding a small set of properties implying that a rule cannot be decomposable) seems much more difficult than we thought, and this is of course an issue for further research.

Next, we identified a domain for which direct and sequential Condorcet winners coincide. Clearly, lexicographic preferences are very specific, so that we would like to find more reasonable restrictions for the latter property to hold.

Another important issue stems from the fact that in combinatorial domains with structural properties (independencies), direct (global) voting rules are generally not computable by a sequential application of local rules: so, what should we favor? Global voting rules, which are well studied in social choice but which take no advantage of preferential independencies, or sequential local rules, which are based on the dependency graph, thereby being more intuitive and easier to compute? A theoretical comparison between global voting and sequential local voting is a highly promising issue.

Acknowledgements

I wish to thank Christophe Gonzales, Martin Meier, Patrice Perny and Lirong Xia for many helpful discussions.