A Dichotomy Theorem on the Existence of Efficient or Neutral Sequential Voting Correspondences

1 Introduction

In many real-life group decision making problems, the space of alternatives has a multi-issue (or combinatorial) structure. For instance, in multiple referenda [Brams et al., 1998], the inhabitants of some local community are asked to make a common decision on several related issues of local interest, such as building a public facility. As another example, the members of an association may have to elect a steering committee, composed of a president, a vice-president and a treasurer [Benoit and Kornhauser, 1991].

When voting is used in Artificial Intelligence contexts, these situations become even more pronounced. For example, agents may have to vote over a joint plan or an allocation of tasks or resources. These alternative spaces are also combinatorial, and they are generally much larger than those considered in human domains. This is one of the problems that is driving the burgeoning field of computational social choice (for an introduction, see [Chevaleyre et al., 2007]).

J´erˆome Lang

LAMSADE Universit´e Paris-Dauphine 75775 Paris Cedex 16, France

lang@irit.fr

In classical social choice theory, voters are supposed to submit their preferences as linear orders over the set of alternatives, and then a voting rule (voting correspondence) is applied to select one alternative (multiple alternatives) as the winner. However, problems emerge when the set of alternatives has a multi-issue structure: the number of alternatives becomes exponentially large, so it is unrealistic to ask voters to specify their preferences as (explicit) linear orders; hence, traditional voting rules or correspondences cannot be applied in a straightforward way. A simple idea to cope with this problem consists in decomposing an election into a set of independent elections, each of which bears on a single issue. This process gives rise to a seat-by-seat 1 voting rule. It works to some extent when the preferences of voters are separable (that is, if voters' preferences on each issue are independent from the values of other issues), but it is impractical when they are not, because in this case a voter cannot specify her preferences on a single issue without knowing the values of the other issues.

Instead of decomposing the election in parallel, it was proposed in [Lang, 2007] to compose local voting rules (or correspondences) sequentially: given a fixed linear order O (without loss of generality, O = x1 > . . . > xp) on the set of issues, these rules work by holding an election for each issue according to a local voting rule, following O - that is, the election on issue issue xi takes place after the outcome of the elections on x1, . . . ,xi-1 has been decided. For this sequential procedure to be applied, it is sufficient that each voter expresses, for each issue xi, her local preference relation over the values of xi, given any vector of values of issues x1, . . . ,xi-1, That is, the voters' preferences are modeled by acyclic CP-nets [Boutilier et al., 2004] whose structural part is an acyclic graph respecting O. The voting rules obtained in this way is called sequential compositions of local voting rules, or for short, sequential voting rules. There are also other approaches for making group decisions over multi-issue domains, including extensions of sequential voting rules [Xia et al., 2007b; 2008], mCP-nets [Rossi et al., 2004], and a method to aggregate numerical preferences over multi-issue domains, represented compactly by GAI-networks [Gonzales et al., 2008].

1 We keep this terminology "seat by seat" used in [Benoit and Kornhauser, 2006] even though our notions and results apply to any kind of voting context on a multi-issue domain, such as multiple referenda.

Sequential voting rules are elicitation-friendly, because they can be executed with an elicitation protocol which asks each voter only polynomially many queries, and easy to compute (provided that the local voting rules are easy to compute). When the preferences of all voters are separable, the outcome of a sequential voting rule is independent on the choice of the order O and the rule thus obtained is a seatby-seat rule in the sense of [Benoit and Kornhauser, 2006]. Therefore, sequential voting rules are a generalization of seatby-seat voting rules.

As local voting rules, local voting correspondences can also be composed in a similar way, giving rise to sequential voting correspondences. One of the most important questions for seat-by-seat voting rules and correspondences, and more generally for sequential voting rules and correspondences, is the following: are there any efficient or neutral seat-by-seat voting rules (or correspondences) other than dictatorships? Three recent papers partly answer this question. When the multi-issue domain is composed of two binary issues, two positive results are proved-one in [Xia et al., 2007a], in which we showed that the sequential composition of two majority correspondences satisfies many good properties, including neutrality; another in [ ¨Ozkal-Sanver and Sanver, 2006], in which the authors proved that when there is an odd number of voters, the seat-by-seat voting rule composed of majority rules is efficient. On the other hand, it was also proved in [ ¨Ozkal-Sanver and Sanver, 2006] that when the domain is composed of at least three issues, or two issues and the number of voters is even, no anonymous seatby-seat voting rule is efficient. Remarkably, Benoit and Kornhauser [2006] proved the following two elegant impossibility theorems: (a) when the multi-issue domain is not composed of two binary issues, the only efficient seat-by-seat voting rules are dictatorships; (b) when the multi-issue domain is composed of three or more issues, the only neutral and locally efficient seat-by-seat voting rules are dictatorships. We note that any non-existence result about seat-by-seat voting rules (correspondences) can be easily extended to the case of sequential composition of local rules (correspondences), because the latter are an extension of the former. Similarly, any existence result about sequential composition of local rules (correspondences) can be easily extended to the case of seatby-seat voting rules (correspondences).

However, when the multi-issue domain is composed of two issues, at least one of which is non-binary, the neutrality of seat-by-seat voting rules is still not clear. Furthermore, it seems that the technique used to prove the impossibility theorems (a) and (b) cannot be fully extended to the case of voting correspondences. We argue that correspondences are very important, because of the following reasons. First, commonly studied voting rules are defined by voting correspondences plus tie-breaking mechanisms, and the voting correspondence part is the major part from a theoretical point of view; second, voting correspondences can have more good properties than voting rules. For example, many common voting correspondences satisfy symmetry, that is, both neutrality (all alternatives are treated equally) and anonymity (all voters are treated equally), but no voting rule satisfies symmetry. Third, there are many situations in which the agents want more options, that is, they want a set of "best alternatives" rather than just one winning alternative. In these situations, voting correspondences are better choices than voting rules. Specifically, sequential voting correspondences are extremely interesting for preference aggregation on multi-issue domains, because even though the set of alternatives is exponentially large, the output of a sequential voting correspondences can always be represented in a compact way, making it computationally feasible to output a set of winning alternatives.

In this paper, we prove that except in the case where the multi-issue domain is composed of two binary issues, the only efficient or neutral seat-by-seat voting correspondences are dictatorships, anti-dictatorships, and the trivial correspondence that always outputs the whole set of alternatives. We note that since it is a non-existence result, it can be easily generalized to the case of sequential voting rules and correspondences. We also show that the sequential composition of two majority correspondences is efficient. Finally, combining these results with previous work, we obtain dichotomy theorems on the existence of neutral or efficient sequential (seatby-seat) voting rules and correspondences. Our dichotomy theorems completely answer the question on the existence of non-dictatorial and non-trivial sequential (seat-by-seat) voting rules and correspondences that are either efficient or neutral.

2 Preliminaries

Basics of voting. Let X be a finite set of alternatives. A vote V is a linear preference relation on X , that is, a transitive, antisymmetric, and complete relation. We write x ≻V x′ if an alternative x is preferred to another alternative x′ in vote V. In this paper, we assume that the set of alternatives has a multiissue (a.k.a. multiattribute or combinatorial) structure. That is, let A = {x1, . . . ,xp} be a set of issues, where each issue xi takes values in a local domain Di, with |Di| ≥ 2. An alternative is uniquely identified by the combination of values of its issues, that is, X = D1 ×. . .×Dp. A profile is a collection of individual linear preference relations over X. A voting rule maps each profile to a unique winning alternative, and a voting correspondence maps each profile to a non-empty set of winning alternatives. For example, the plurality correspondence selects the alternatives that are ranked at the top the most number of times; when there are only two alternatives {x,y}, the majority correspondence ma j is defined by ma j(P) = {x} (resp. {y}) if more voters in P prefer x to y (resp. y to x), and ma j(P) = {x,y} in case of a tie. A voting correspondenceC is a dictatorship (resp. anti-dictatorship) if there exists a voter j such that for any profile P= (V1, . . . ,VN), C(P) = {top(Vj)} (resp. C(P) = {bot(Vj)}, where top(Vj) (bot(Vj)) is the alternative that is ranked at the top (bottom) place in Vj. We note that a voting rule can be seen as a voting correspondence that always output one winner. Therefore, all definitions and results for correspondences a fortiori apply to rules, but the reverse does not always holds. For example, no voting rule satisfies both neutrality and anonymity, but many common voting correspondences (e.g. the plurality correspondence) satisfy both of them.

Preferences represented as CP-nets. A CP-net N over X consists of two parts: (a) a directed graph G= (A,E) and (b) a set of conditional linear preferences ⪰i⃗u over Di, for any assignment ⃗u of the parents of xi in G. Let CPT(xi) be the set of all conditional linear preferences on Di, called a conditional preference table (CPT). When G is acyclic, N is said to be an acyclic CP-net. N induces a partial preorder ⪰N in the following way: for any ai,bi ∈ Di, any assignment ⃗u of the parents of xi (denoted by ParG(xi)), and any assignment ⃗z of A-ParG(xi)-{xi}, (ai,⃗u,⃗z) ⪰N (bi,⃗u,⃗z) if and only if ai ⪰i⃗u bi. That is, given the values of all parents of xi, the preference over xi is independent of the values of all issues that are neither the parents of xi nor xi itself. When N is acyclic, ⪰N is transitive and asymmetric, that is, a strict partial order.

A linear order V extends a CP-net N , denoted by V ∼ N , if it extends the partial order induced by N . V is separable if it extends a CP-net whose directed graph has no edge. For any assignment ⃗u of ParG(xi), let V|xi:⃗u be the restriction of V to xi, given⃗u. That is, V|xi:⃗u is the linear order ⪰i⃗u over Di. Given a DAG G on A, a CP-net N is compatible with G if its graph GN is compatible with G, which means that GN ⊆ G; V is compatible with G if there exists a CP-net N such that V ∼N and N is compatible with G. If V is compatible with G, we also say that V is G-legal; we say V is legal, if it is G-legal for some acyclic graph G. The set of all G-legal votes is denoted by Legal(G). A profile is G-legal if all of its votes are G-legal. For any linear order O on A, we define GO to be the graph induced by O-that is, there is an edge (xi,xj) in GO if and only if xi >O xj. We note that for any DAG G, a linear order O can be found such that G ⊆ GO , which means that any G-legal profile is also GO-legal.

Sequential voting rules and correspondences. Given an order O = x1 > . . . > xp and a set of local correspondences {c1, . . . ,cp} (that is, for any i ≤ p, ci is a voting correspondence on Di), the sequential composition of local correspondences c1, . . . ,cp w.r.t. O, denoted by Seq(c1, . . . ,cp), is defined for all GO-legal profiles as follows: Seq(c1, . . . ,cp)(P) is characterized by the set of alternatives (d1, . . . ,dp) ∈ X, so that for any i ≤ p, we have di ∈ ci(P|xi:d1...di-1 ). We note that Seq(c1, . . . ,cp) is well-defined, because for any Glegal profile, the set of winners is the same for all O such that G ⊆ GO (see [Lang, 2007]). When G has no edge, Seq(c1, . . . ,cp) becomes a seat-by-seat correspondence, denoted by Sbs(c1, . . . ,cp). It follows that for any separable profile Ps, Sbs(c1, . . . , cp)(Ps) =W1 × . . .×Wp, where for any i ≤ p, Wi = ci(Ps|xi ).

Example 1 Let A = {x, y} with Dx = {x1, x2, x3} and Dy = {y, ¯ y}, and P = (V1, . . . ,V6) be the following 6-voter profile:

All these 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 ∈ Legal(G). The corresponding conditional preference tables are shown in Table 1.

Take cx to be the plurality rule, and cy to be the majority rule. The projection of P on x, namely P|x = (V1|x, . . . ,V6|x), contains three votes x1 ≻ x2 ≻ x3, two votes x2 ≻ x3 ≻ x1, and one vote x2 ≻ x1 ≻ x3. Therefore, the plurality winners for P|x are cx(P|x) = {x1,x2}. Now, the projection of P on y given x = x1, namely P|y:x=x1 = (V1|y:x=x1 , . . . ,V6|y:x=x1 ), is composed of 4 votes for ¯ y and 2 for y, therefore cy(P|y:x=x1 ) ={¯ y}; P|y:x=x2 is composed of 3 votes for y and 3 votes for ¯ y, therefore cy(P|y:x=x2 ) = {y, ¯ y}. The sequential winners are now obtained by combining the x-winners and the conditional y-winners given any x-winner, namely Seq(cx, cy)(P) = {x1 ¯ y, x2y, x2 ¯ y}.

A sequential voting correspondence C = Seq(c1, . . . , cp) is neutral, if for any legal profile P and any permutation M on X such that M(P) is legal, we have C(M(P)) =M(C(P)). C is efficient (resp. anti-efficient), if for any legal profile P, any y ∈C(P), any x ∈ X, if x ≻V y (resp. y ≻V x) for all V ∈ P, then, x ∈C(P).

¨Ozkal-Sanver and Sanver [2006] proved that if there are at least three binary issues (or two binary issues and an even number of voters), then the seat-by-seat voting rule composed of majority rules is not efficient. Within the same line of research, two impossibility theorems were proved on the neutrality and efficiency of seat-by-seat voting rules [Benoit and Kornhauser, 2006].

Theorem 1 ([Benoit and Kornhauser, 2006]) When the multi-issue domain is not composed of two binary issues, the only efficient seat-by-seat voting rules are dictatorships.

Theorem 2 ([Benoit and Kornhauser, 2006]) When the multi-issue domain is composed of at least three issues, and each local rule is efficient, the only neutral seat-by-seat voting rules are dictatorships.

When the domain is composed of two binary issues, there are possibility results on the existence of seat-by-seat (sequential) voting rules or correspondences that are efficient, neutral, and nondictatorial. In [Xia et al., 2007a], we proved that the sequential correspondence that is composed of two majority correspondences is neutral. It was also shown in [ ¨OzkalSanver and Sanver, 2006] that when there is an odd number of voters, the seat-by-seat voting rule that is composed of two majority rules is efficient.

3 Dichotomy theorems

We note that Theorem 2 does not cover the case in which the domain is composed of two issues, where at least one of the issues is not binary. Moreover, both Theorem 1 and Theorem 2 apply only to voting rules (but not correspondences), and the requirement that there is a unique winner plays an important role in their proofs. Therefore, it seems that these impossibility theorems cannot be easily extended to the case of voting correspondences. In this section, we first show that similar impossibility results hold for voting correspondences. Our results also cover the case of voting rules that is not covered in Theorem 2. Then, we show that the sequential composition of two majority correspondences is efficient. Finally, we obtain a dichotomy theorem on the existence of efficient or neutral seat-by-seat voting correspondence. Similar dichotomy theorems hold for sequential voting rules and correspondences.

Theorem 3 If X is not composed of two binary issues, then the only efficient or neutral seat-by-seat voting correspondences on X are dictatorships, anti-dictatorships, and the trivial correspondence that always outputs the whole set of alternatives X .

Proof: The theorem is proved for two cases. Case 1: X is composed of three or more issues (Lemma 17). Case 2: X is composed of two issues, and at least one of the issues is not binary (Lemma 18). Statements and proofs of the lemmas are in the appendix. Due to space constraints, some proofs are omitted. ✷

Theorem 4 Let X = {x, ¯ x}×{y, ¯ y}. Seq(ma j,ma j) is efficient, where O = x > y.

Proof: For the sake of contradiction we assume that the theorem does not hold. Then, there exists a profile P such that ⃗a = (a1, a2) ∈ Seq(ma j,ma j)(P), ⃗b = (b1, b2) ≻V ⃗a for any V ∈ P, and ⃗b ̸∈ Seq(ma j,ma j)(P). If a2 = b2, then b1 ≻V |x a1 for all V ∈ P, which means that ma j(P|x) = {b1}, ⃗a ̸∈ Seq(ma j,ma j)(P), contradiction. Therefore, a2 ̸= b2. Similarly, a1 ̸= b1. Without loss of generality, we let ⃗a = (x, y),⃗b = ( ¯ x, ¯ y). For any V ∈ P, because ( ¯ x, ¯ y) ≻V (x,y), either [V|x = ¯ x ≻ x], or [V|x = x ≻ ¯ x, V|y:x = ¯ y ≻ y, and V |y: ¯ x = ¯ y ≻ y]. Let n1 (resp. n2) be the number of votes of the former (resp. latter) type in P. It follows from x ∈ ma j(P|x) that n2 ≥ n1; from y ∈ ma j(P|y:x) we must have that n1 ≥ n2. Hence n1 = n2. Then, we have that ( ¯ x, ¯ y) ∈ Seq(ma j,ma j)(P), contradiction. ✷

Combining Theorem 3, Theorem 4, and the Theorem 5.3 in [Xia et al., 2007a], we obtain the following dichotomy theorem on the existence of efficient or neutral seat-by-seat correspondences and sequential voting correspondences.

Theorem 5 Except in the case where the domain is composed of two binary issues, the only efficient or neutral seatby-seat (sequential) correspondences are dictatorships, antidictatorships 2 , and the trivial correspondence that always outputs the whole set of alternatives; when the domain is composed of two binary issues, and the local correspondences are majority correspondences, the seat-by-seat (sequential) voting correspondence is neutral and efficient.

The restriction of Theorem 6 to seat-by-seat voting rules, combined with the results in [ ¨Ozkal-Sanver and Sanver, 2006]), gives a dichotomy theorem that generalizes Theorem 1 and Theorem 2.

Theorem 6 Except in the case where the domain is composed of two binary issues, the only efficient or neutral seatby-seat (sequential) voting rules are dictatorships and antidictatorships 3 ; when the domain is composed of two binary issues, a non-dictatorial anonymous voting rule can be efficient or neutral if and only if the number of voters is odd.

2 Not possible if the voting correspondence is efficient.

3 Again, not possible if the voting rule is efficient.

4 Conclusion

In this paper we focus on characterizing the existence of efficient or neutral sequential (seat-by-seat) voting correspondences by the structure of the multi-issue domain. Our main results are the extensions of the two impossibility theorems in [Benoit and Kornhauser, 2006] to the case of voting correspondences. Based on our impossibility theorems, we obtain dichotomy theorems on the existence of efficient or neutral sequential (seat-by-seat) voting rules and correspondences.

These results have a strong impact in many classes of practical collective decision making situations. Every time a vote on several issues is organized sequentially or in parallel (which typically happens in recruiting committees, when several positions of different kinds are open, or in interest groups on the Internet which often make such decisions by conducting a parallel vote on several issues), there is no way of ensuring efficiency, nor neutrality, as soon as there are more than two issues, or as soon as there are two issues, one of which is not binary. If one wants neutrality and/or efficiency to hold, one has to find different methods for collective decision making, such as asking voters to report their preferences at once in a compact representation language, and then aggregate the individuals' inputs; but then the price to be paid is likely to be a very high communicational and computational cost.

Acknowledgements

The authors want to thank Vincent Conitzer, Patrick Girard, Yoav Shoham, and anonymous reviewers for helpful comments and suggestions. Lirong Xia was supported by a James B. Duke Fellowship and a National Natural Science Foundation of China under grant number 60505011. J´erˆome Lang was supported by the project ANR-05-BLAN-0384 "Preference Handling and Aggregation in Combinatorial Domains".