# aggregating_incomplete_pairwise_preferences_by_weight__66ae0900.pdf

Aggregating Incomplete Pairwise Preferences by Weight

Zoi Terzopoulou , Ulle Endriss Institute for Logic, Language and Computation, University of Amsterdam z.terzopoulou@uva.nl, u.endriss@uva.nl

We develop a model for the aggregation of preferences that do not need to be either complete or transitive. Our focus is on the normative characterisation of aggregation rules under which each agent has a weight that depends only on the size of her ballot, i.e., on the number of pairs of alternatives for which she chooses to report a relative ranking. We show that for rules that satisfy a restricted form of majoritarianism these weights in fact must be constant, while for rules that are invariant under agents with compatible preferences forming pre-election pacts it must be the case that an agent s weight is inversely proportional to the size of her ballot.

1 Introduction Modelling and aggregating the preferences of agents is relevant to various important applications of AI [Domshlak et al., 2011], ranging from online recommendation systems, to decision-theoretic planning engines, to the emerging topic of incorporating ethical principles into computer-supported decision making [Conitzer et al., 2017]. While it is acknowledged that decision makers cannot be expected to be perfectly rational and to always report transitive preferences regarding the full set of alternatives under consideration [Darmann et al., 2017; Hansson and Gr une-Yanoff, 2018], much existing work in computational social choice is still based on the classical model of preferences that presupposes completeness and transitivity [Brandt et al., 2016]. In this paper we propose a model of preference aggregation that does not make such assumptions. Instead, preferences are represented as merely acyclic sets of pairwise comparisons between alternatives. To illustrate the need for systems that can handle such nonstandard preferences, consider the following example. Example 1. Suppose you are asked in a poll to rank several apps in order of preference. You strictly prefer the New York Times app to Facebook for getting informed about the news and Facebook to Gmail when it comes to communicating with friends. But NYT and Gmail serve two completely distinct purposes for you, and you simply cannot rank them. The poll also includes apps you have never used, you are not

Contact Author

aware of their features, and hence do not hold any preference about them. So, you presumably would greatly appreciate the possibility of (i) expressing your preferences in a pairwise manner rather than as a list, and of (ii) leaving some of the apps unranked altogether.

We focus on a family of aggregation rules under which the weight assigned to agent i s ranking of two alternatives depends on how many other pairs of alternatives she ranks as well. For example, we may want to give an agent who only reports her preferences on a selected few pairs of alternatives more weight than an agent who expresses a view on all pairs. We consider different variants of these aggregation rules, concerning the type of output required: we may use a rule to obtain a consensus regarding the ranking of the alternatives, we may look for a single winner amongst the alternatives, or we may need to select a set of winners of a given size. Our new model is thus very ﬂexible both with respect to the individual preferences and the corresponding collective outcomes. Our main technical results concern the rules characterised by two normative principles (also known as axioms):1

Majoritarianism: Try to respect the will of the majority regarding the relative ranking of pairs of alternatives. We consider a highly restricted form of this principle that avoids majority cycles [de Condorcet, 1785].

Splitting: If several agents have mutually compatible preferences, it should be possible for them to form a preelection pact and all report the union of their individual preference sets without this change affecting the outcome. We consider different variants of this idea.

We concentrate our analysis on (restricted) majoritarianism and splitting because these axioms contrary to other wellknown ones are speciﬁcally relevant to scenarios with incomplete preferences. We ﬁnd that restricted majoritarianism characterises the rule with constant weights and that (certain) splitting axioms characterise the rule where an agent s weight is inversely proportional to the size of her reported preference set (we call this the even-and-equal-weight rule). These results are robust across all types of output requirements. We also simulate prominent rules of the standard voting framework with complete preferences and suggest new ones that

1Similar axioms have been discussed by Terzopoulou et al. [2018] in the context of judgment aggregation.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

(despite being very natural) have not been considered in the literature before. These proposals for new rules for standard voting are highlighted as Remarks 1 4. Finally, we spell out basic complexity results for all the rules introduced. The dominant approach to handling incomplete preferences in computational social choice so far has been the possible winner solution concept [Konczak and Lang, 2005; Boutilier and Rosenschein, 2016]. Given a proﬁle of incomplete preferences, the possible winners of a voting rule F are all the alternatives that win under F for some completion of the preferences. This is a reasonable solution concept when in fact the preferences of the agents are complete but we have not yet fully elicited them. Along similar lines, one could also assume that there is an underlying true ranking of the alternatives and that the agents incomplete preferences capture their partial knowledge about that ranking [Caragiannis et al., 2017]. Here, instead, we are interested in the aggregation of bona ﬁde incomplete preferences, i.e., in scenarios where it is the preferences themselves that are incomplete rather than our information about them. Of course, which approach is appropriate depends on context. Like us, Pini et al. [2008] and Endriss et al. [2009] have studied the aggregation of bona ﬁde incomplete preferences, but their proposals are less radical (they do not dispense with transitivity) and, in some sense, less ﬂexible (they do not have the notion of outcome type, which is prominent in our model). While Pini et al. extend a number of classical impossibility theorems in social choice theory to the case of incomplete preferences and while Endriss et al. investigate how forcing voters to report preferences that are either more or less complete than their true ones affects strategic behaviour, our focus is on the design and axiomatic characterisation of new aggregation rules. The main body of this paper is organised as follows. We introduce our model in Section 2, and each of the next three sections is dedicated to results for a speciﬁc type of output of aggregation rules: a collective ranking (Section 3), a single winner (Section 4), and a set of winners (Section 5).

2 The Model In this section we present our model of pairwise-preference aggregation and establish some of its elementary properties.

2.1 Basic Notation and Terminology The superpopulation N is an unbounded set of all potential agents that may participate in a preference aggregation scenario, and A is an unbounded set of all potential alternatives that agents in N may form preferences on.2 Any speciﬁc preference aggregation scenario concerns a ﬁnite group of agents N = {1, . . . , n} N and a ﬁnite subset A A, which we call the set of alternatives. Every agent i N performs pairwise comparisons over the alternatives in A and submits her ballot Ri, which is a set of strictly ordered pairs of alternatives:

Ri = {(a, b) A A | a is ranked above b by agent i}

2The notions of superpopulation and potential alternatives make explicit what is often left implicit in related models: that the number of agents and alternatives may vary across applications. In the proofs, they allow us to move between different scenarios.

We write ab as an abbreviation for (a, b) and use the terms ballot and (pairwise-)preference (set) interchangeably. We assume that for every agent i the set Ri is acyclic: if a1a2, a2a3, . . . , ak 1ak Ri, then aka1 / Ri, for every a1, a2, . . . , ak A.3 To talk about the transitive closure of a ballot {a1a2, a2a3, . . . , ak 1ak}, we sometimes write a1 a2 ak. Lastly, let us denote by R(A) the set of all acyclic pairwise preferences over a set of alternatives A. A proﬁle R = (R1, . . . , Rn) R(A)n captures the ballots of all agents in N. N R ab denotes the set of agents i for which ab Ri in R. A preference aggregation rule F is a function that maps any proﬁle R R(A)n for any set of alternatives A and group N to a nonempty set of preferences on the same alternatives, i.e., to a nonempty subset of 2R(A). Thus, the set F(R) may contain several, tied, outcomes.

2.2 Weight Rules and Types of Preferences In this paper we introduce a speciﬁc family of aggregation rules. The primary constituent of a weight rule for aggregating pairwise preferences is a weight function w : N R+. A weight function assigns to each natural number, representing a ballot size |Ri|, a positive real number w|Ri| = w(|Ri|), expressing how much any ordered pair ab Ri weighs, given the size of Ri. We may also think of w as an inﬁnite vector. For example, w = (1, 1

3, . . .) means that we distribute a total weight of 1 equally across all pairs in Ri, while w = (1, 1

M , 1 M 2 , ...), for a sufﬁciently large number M, weighs smaller ballots inﬁnitely more than larger ones. The concept of a weight function is essential for a number of applications. For example, in the context of peer-grading, suppose one grader submits a ranking of only three out of the twenty submissions, while another grader ranks all twenty of them. Should the same weight be assigned to those two rankings? Should the small ranking weigh less, or more? By the end of this paper we will be able answer these questions. We shall assume that any weight wλ for λ N is computable in polynomial time (polynomial in the length of the description of λ).4 We use the following notation to refer to the cumulative weight assigned to all the pairs in a preference set R A A from the perspective of holding Ri:

w Ri(R) = X

ab R w|Ri| 1ab Ri = w|Ri| |R Ri|

A second component of the deﬁnition of a weight rule is a type T , which is a function that maps every set of alternatives A A to a subset T (A) R(A) of preference sets. We focus on four speciﬁc types of immediate practical relevance. First, in the literature on preference aggregation both individual preferences and outcomes traditionally are complete rankings over the alternatives. So we consider the type of linear orders L, where L(A) contains all asymmetric, complete, and transitive relations over A. On the other hand, in voting theory we are mainly concerned with ﬁnding

3Acyclicity implies asymmetry (i.e., ab Ri ba / Ri for every a, b A). However, we stress that we do not assume that Ri needs to be transitive or complete; that is, there may exist alternatives a, b, c A such that ab, bc Ri, but ac / Ri. 4This is important for the (upper bounds in) complexity results.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

a (single) winner, that is, an alternative ranked higher than any other alternative [Zwicker, 2016]. Hence, we also deﬁne the type W, where W(A) includes all pairwise preferences of the form R = {aa | a A \ {a}}, for some a A. In multiwinner voting the outcome should be a given number of winning alternatives, constituting, for instance, a committee [Faliszewski et al., 2017]. So we deﬁne the type Wk, where Wk(A) consists of all pairwise preferences that designate a set of k winners (for some ﬁxed k > 1), i.e., that are of the form R = {(a1, a ), . . . , (ak, a ) | a A \ {a1, . . . , ak}}, for some a1, . . . , ak A with ai = aj for i = j. Finally, we deﬁne the type C of chains, which are linear orders over subsets of A, to model situations where agents rank part of the alternatives. Formally, C(A) consists of all pairwise preferences of the form R = (a1 a2 ak), for some k N and a1, . . . , ak A with ai = aj for i = j.5 In line with our existing notation R(A), we use the letter R to denote the type of all preference sets. Given a weight function w and a proﬁle R = (R1, . . . , Rn) for a speciﬁc set of alternatives A A and group of agents N N, a weight rule of type T , denoted by F T w , decides the outcome by selecting those preference sets in T (A) that maximise the total weight across all agents:

F T w (R) = argmax R T (A)

i N w Ri(R)

Note that for every weight rule F T w there are inﬁnitely many weight functions that induce it. For example, if we multiply all weights with some positive constant, then the rule being induced does not change. The following two weight rules will play a major role in this paper: Take any weight function w with wλ = wλ for all λ, λ N and any type T . We call the weight rule F T c induced by w the constant-weight rule of type T . Take any weight function w with wλ = w1

λ for all λ N and any type T . We call the weight rule F T ee induced by w the equal-and-even-weight rule of type T . The latter rule borrows its name from its counterpart for voting with approval ballots, the equal-and-even cumulative voting rule [Glasser, 1959; Alcalde-Unzu and Vorsatz, 2009].

2.3 Type Restrictions The restriction of a set of preferences S R(A) to a given type T is formally deﬁned as S|T = S T (A). Recall that, to compute F T w (R), we have to go through all preferences R of type T and select those that maximise total weight. An alternative deﬁnition would be to ﬁrst select all preferences R of any type that maximise total weight and to only then restrict the resulting set to T , i.e., to compute (argmax R R(A) P i N w Ri(R))|T , which we can also write as F R w (R)|T . Now the question arises: When do these two alternative approaches result in the same outcomes?

5Lang et al. [2017] deﬁne certain aggregation outcomes that include ours. For instance, their plain dominating 1-chain and plain dominating k-subset correspond to our single-winner and k-winner sets, respectively. But the model and the results they provide are restricted to complete input proﬁles.

To answer this question, we require some further terminology. Given two types T and T we say that T reﬁnes T if T (A) T (A) for all A A. We furthermore say that T extends T if for all A A and preferences R T (A) there exists a preference R T (A) with R R .

Proposition 1. If T simultaneously reﬁnes and extends T , then F T w (R) = F T w (R)|T for any w and R.

Proof. Since T (A) T (A), which holds as T reﬁnes T , we have that F T w (R) = argmax R T (A) P i N w Ri(R) T (A) argmax R T (A) P i N w Ri(R) = F T w (R)|T . For the other direction, we ﬁrst show that there exists at least one R T (A) with R F T w (R). Take any R F T w (R). Since T extends T , there exists an R T (A) with R R . Observe that w|Ri| |Ri R| w|Ri| |Ri R | for all i N and thus P i N w Ri(R) P i N w Ri(R ). Hence, we indeed get R F T w (R) as claimed. Now take any R F T w (R). By deﬁnition of the weight rule, this entails P i N w Ri(R ) P i N w Ri(R) for all R T (A), including the speciﬁc R we know to exist in F T w (R). As furthermore R T (A), which is due to T (A) T (A), we get R F T w (R) and thus also R F T w (R)|T . We conclude that F T w (R) F T w (R)|T .

Every type T reﬁnes R. But which types T also extend R? Certainly L extends R, as every pairwise-preference set can be extended to a linear order, and therefore so does every type T that includes all linear orders, answering our question.

Corollary 2. For any weight function w and type T that is reﬁned by L, it holds that F T w (R) = F R w (R)|T .

3 Obtaining a Collective Ranking

In this section we study the family of weight rules for outcomes that are complete rankings, i.e., outcomes of type L. Agents may still report incomplete preferences. But for the special case of complete proﬁles L L(A)n, all ballots are associated with the same weight (since their size is the same and their weight only depends on their size) and the choice of the weight function w is irrelevant. Hence, the induced weight rule for outcomes in L(A) for this particular case coincides with the well-known rule of Kemeny [1959].6,7

Proposition 3. For any proﬁle L L(A)n and weight function w, it holds that F L w (L) = Kemeny(L).

We now state the relative ranking problem for a weight rule F L w : Given a proﬁle R R(A)n and two distinguished alternatives a, b A, is a ranked above b in at least one ranking in F L w (R)? Proposition 4 clariﬁes that determining relative rankings under any weight rule of type L is complete

6In the interest of space, we omit a formal deﬁnition of this rule and refer to Brandt et al. [2016] for a modern exposition. 7It might be tempting to confuse the possible outcomes (as deﬁned by Konczak and Lang 2005) of the Kemeny rule with the outcomes induced by the constant-weight rule F L c . But in different aggregation situations possible outcomes may coincide with, include, or be included in the set of outcomes of F L c . For an example of the latter case, consider the proﬁle ({ab, bc, ac}, {ab, ca}, {ab, ca}).

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

for PNP || , i.e., for the class of problems solvable in polynomial time via parallel access to an NP oracle. We note that computing the outcome under such a rule is at least as hard. Proposition 4. The relative ranking determination problem for F L w is PNP || -complete, for any weight function w.

Proof sketch. By Proposition 3, PNP || -hardness follows from the corresponding result for the Kemeny rule [Hemaspaandra et al., 2005]. Proving membership in PNP || is routine.

Next, we wonder: what weights induce good rules? To answer, we adopt an axiomatic perspective [Arrow et al., 2002; Brandt et al., 2016]. For the sake of our deﬁnitions, we ﬁx a set of alternatives A A, a group of agents N N, and an aggregation rule F of type L, and say that F satisﬁes an axiom if the relevant deﬁnition holds for every A and N.

3.1 Majoritarianism Generating a collective ranking based on the pairwise preferences of the majority is commonly considered a desirable attribute of an aggregation rule. However, blindly following the majority s preferences easily leads to problematic cases of preference cycles [de Condorcet, 1785]. But there clearly are situations where some pairs of alternatives cannot cause a Condorcet-type paradox on a proﬁle. Such is the case when the alternatives a, b are independent of a proﬁle R, i.e., when for each ballot Ri in R, a and b might be compared to each other, but neither a nor b are compared to any other c (formally, ac, ca, bc, cb / Ri for all c A \ {a, b} and i N). The axiom of restricted majoritarianism expresses a fundamental normative principle (namely that more agents ranking a above b than b above a should imply collective preference of a to b), but limits its scope to cases of independence. As its name suggests, restricted majoritarianism is indeed very restrictive and this makes our ﬁndings all the more remarkable: Even by using only this weak (and hence indisputable) axiom, we get a characterisation of a very natural rule (Theorem 5). For a proﬁle R R(A)n, let us deﬁne the simple-majority set as m(R) = {(a, b) A A | |N R ab| > |N R ba|}. Axiom 1 (Restricted majoritarianism). A rule F is said to satisfy restricted majoritarianism if for all alternatives a, b A independent of a proﬁle R R(A)n, it holds that ab m(R) implies that ab R for all R F(R). Theorem 5. The only weight rule of type L satisfying restricted majoritarianism is the constant-weight rule F L c .

Proof. That the constant-weight rule F L c satisﬁes restricted majoritarianism is easy to verify. For the other direction, consider an arbitrary weight function w that induces a weight rule F L w and suppose that F L w satisﬁes restricted majoritarianism. To prove that F L w is the constant weight rule it sufﬁces to show that wλ = wλ for all λ, λ N. We ﬁrst show that F L w satisfying restricted majoritarianism for a group N N with odd n > 1 implies that wλ

2 n 1 for all λ, λ . Indeed, consider two arbitrary λ > λ and a set of alternatives A = {a1, b1, a 1, b 1, . . . , aλ, bλ, a λ, b λ} A (which is possible because A is unbounded). Then, take R = {a1b1, a2b2, . . . , aλbλ} R(A) and R =

{b1a1, a 2b 2, . . . , a λ b λ } R(A). We construct the following proﬁle R R(A)n for an odd n > 1:

R = (R, . . . , R | {z } (n 1)/2

, R , . . . , R | {z } (n+1)/2

Clearly, a1, b1 are independent of R, and b1a1 m(R). Hence, by restricted majoritarianism it must be the case that b1a1 R for all R F L w (R), implying that n 1

2 w|R| < n+1

2 w|R | and thus wλ

wλ < 1 + 2 n 1. To conclude, we know that if F L w satisﬁes restricted majoritarianism, then it does so for every group N N of odd cardinality. Thus, we must have that wλ

wλ < 1 + 2 n 1 for every odd n > 1 and for every wλ, wλ R+. Letting n go to inﬁnity, this implies that wλ = wλ for all λ, λ .

3.2 Splitting We now deﬁne a novel axiom tailored to the aggregation of bona ﬁde incomplete preferences. The basic idea is that when several agents have compatible and disjoint preference sets, they should be able to simply all report the union of their individual sets without affecting the outcome. This is useful in practice: If some members of a council meet before a vote and realise that they do not disagree on any of the relative rankings between alternatives, they could simply send a messenger to the main meeting to vote on their behalf. Alternatively, in a strategic setting, we may wish to disincentivise pre-election pacts between agents who care about different issues vote trading [Eldar, 2008] is a special case of this.

Axiom 2 (Splitting). A rule F is said to satisfy (arbitrary) splitting if for every proﬁle R R(A)n and subgroup N N of agents with pairwise disjoint ballots, it is the case that S i N Ri R(A) implies F(R) = F(R ), where R arises from R by replacing the ballot of each member of N by the union S i N Ri. F furthermore is said to satisfy equal splitting if the ballots of all agents in N are of equal size, and single splitting if they are all singletons.

We ﬁnd that the single-splitting axiom characterises the equal-and-even-weight rule, and so does the equal-splitting axiom. But interestingly, the arbitrary-splitting axiom proves to be too demanding: it is not satisﬁed by any weight rule.

Theorem 6. The only weight rule of type L satisfying the single-splitting axiom is the equal-and-even-weight rule F L ee.

Proof. We consider an arbitrary instance of the singlesplitting axiom and show that F L ee satisﬁes it. Take two proﬁles R, R , where R arises from R by replacing the preference set of each member of N by the union S i N Ri. By the deﬁnition of the weights for the rule F L ee, we know that every pair of alternatives in S i N Ri weighs exactly the same in R and in R , because |Ri| = 1 for every i N , and wλ = w1

λ for every λ. The same holds for all pairs that are not in S i N Ri too, since they trivially appear in exactly the same preference sets in both proﬁles R and R . This means that F L ee(R) = F L ee(R ). For the other direction, consider an arbitrary λ N, a set of alternatives A = {a1, b1, . . . , aλ, bλ} A, and

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

two proﬁles R = ({a1b1}, {b1a1}, {a2b2}, . . . , {aλbλ}) R(A)n and R = ({a1b1}, {b1a1, a2b2, . . . , aλbλ}, . . . , {b1a1, a2b2, . . . , aλbλ}) R(A)n (this can be done for a sufﬁciently large group N N). First, for any weight rule F L w we must have L, L F L w (R) for some {a1b1, a2b2, . . . , aλbλ} L and {b1a1, a2b2, . . . , aλbλ} L . Moreover, if F L w satisﬁes single splitting, it must be the case that F L w (R) = F L w (R ). So the weights of a1b1 and b1a1 should be the same in the proﬁle R , that is, w1 = λ wλ.

Theorem 7. The only weight rule of type L satisfying the equal-splitting axiom is the equal-and-even-weight rule F L ee.

Proof. If a weight rule satisﬁes equal splitting, then it satisﬁes single splitting too, so Theorem 6 implies that it must be the equal-and-even-scoring rule. The proof of the other direction, showing that F L ee satisﬁes equal splitting, proceeds exactly as the ﬁrst part of the proof of Theorem 6.

Proposition 8. No weight rule of type L satisﬁes the arbitrary-splitting axiom.

Proof. Every weight rule of type L that satisﬁes arbitrary splitting also satisﬁes single splitting, so by Theorem 6, the only candidate rule is F L ee. Then it remains to show that F L ee fails arbitrary splitting on at least one counterexample. Let A = {a1, b1, a2, b2, a3, b3} and consider the proﬁles R = ({b1a1}, {a1b1}, {a2b2, a3b3}) and R = ({b1a1}, {a1b1, a2b2, a3b3}, {a1b1, a2b2, a3b3}). Let w be the weight function associated with F L ee. Since both a1b1 and b1a1 weigh w1 in proﬁle R, there will exist two collective preference sets in F L ee(R) that each contain one of them. Now, note that w|{a1b1,a2b2,a3b3}| = w1

3 . So, a1b1 weighs 2w1

3 < w1 in R , while b1a1 still weighs w1. This means that for every preference set in F L ee(R ), only b1a1 but not a1b1 will belong to that set. Hence, F L ee(R) = F L ee(R ), which violates the arbitrary-splitting axiom.

4 Obtaining a Winner

In this section we study weight rules for outcomes of type W, indicating a single winner. To refer to a winning alternative of a preference set R, we deﬁne the set of the top alternatives in R: top(R) = {a A | (b, a) R for no b A}. For any set S R(A), we deﬁne top(S) = S R S top(R). For complete input proﬁles, the winners of any weight rule are exactly the winners according to the rule of Borda (1784): Given a linear order a1 a2 am, an alternative gets m 1 points for the ﬁrst place, m 2 points for the second place, and so forth. A winning alternative of Borda maximises the added score from all agents. Proposition 9 follows from Observation 4 of Lang et al. [2017].8

Proposition 9. For any proﬁle L L(A)n and weight function w, it holds that top(F W w (L)) = Borda(L).

Moreover, for any weight rule of type W, the outcome can be computed in polynomial time, generalising the well-known

8A similar result is also given by Endriss [2018], who simulates voting in the framework of judgment aggregation.

fact that the Borda winner can be found in polynomial time (the simple proof is omitted due to space constraints).9

Proposition 10. For any proﬁle R R(A)n and weight function w, F W w (R) can be computed in polynomial time.

We next wonder what kind of weights make sense when the outcome is of type W but some of the agents submit strictly incomplete preferences (as opposed to the complete input proﬁles we just examined).

4.1 Majoritarianism We observe that the axiom of restricted majoritarianism, as formulated earlier, does not apply to outcomes of type W, because these are incomplete. We therefore slightly modify it (and for complete outcomes the two versions coincide).

Axiom 3 (Weak restricted majoritarianism). A rule F satisﬁes weak restricted majoritarianism if for every proﬁle R R(A)n and alternatives a, b A that are independent of R, it holds that: if ab m(R), then ba / R for all R F(R).

We obtain a similar result as for rules of type L (Theorem 5).

Theorem 11. The only weight rule of type W satisfying weak restricted majoritarianism is the constant-weight rule F W c .

Proof. The proof matches that of Theorem 5, so we only explain here the part that differs, after the construction of the proﬁle R. Let Ra denote the preference set in W(A) corresponding to a being the winning alternative. We have P i N w Ri(Ra1) = P i N w Ri(Ra2) = = P i N w Ri(Raλ) = n 1

2 wλ and P i N w Ri(Rb1) = P i N w Ri(Ra 2) = = P i N w Ri(Ra λ ) = n+1

2 wλ . Thus, either each of a1, a2, . . . , aλ win in some proﬁle or none of them do, and the same is true for b1, a 2, . . . , a λ . This means that it cannot be the case that both a1b1 / R and b1a1 / R for all R F W w (R), because then F W w (R), which would be contrary to the deﬁnition of a weight rule. But a1, b1 are independent of R, and b1a1 m(R). Hence, by weak restricted majoritarianism, it must hold that b1a1 R for some R F W w (R). The remainder of the proof proceeds exactly as for Theorem 5.

Remark 1. To demonstrate how the constant-weight rule of winner type works, we inspect it on proﬁles of chains (i.e., on proﬁles C C(A)n), by ﬁrst deﬁning a variant of the Borda rule: For a chain a1 a2 ak, a1 gets k 1 points, a2 gets k 2 points, and so forth, with ak and all alternatives not appearing in the chain getting 0 points. Shortsighted Borda (s Borda) then maximises the collected points in a proﬁle.10

9So, there is a clear difference in complexity between using weight rules and computing possible winners: F W w , which generalises the Borda rule, can be evaluated in polynomial time yet, the possible-winner determination problem for Borda is NP-complete [Xia and Conitzer, 2008]. 10Shortsighted Borda differs from optimistic (or modiﬁed) and pessimistic Borda, which implictly take alternatives not included in a chain to be less preferred than those included [Baumeister et al., 2012]. Optimistic Borda (used also by Caragiannis et al. 2015) assigns k points to the most preferred alternative in a chain with k elements, k 1 points to the second most preferred, and so on, while

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Proposition 12. For any proﬁle C C(A)n, it holds that top(F W c (C)) = s Borda(C).

Proof sketch. For simplicity take wλ = 1 for all λ N. Then, for an outcome Ra corresponding to alternative a winning, we have w Ci(Ra) = |Ci Ra| = |{b A | ab Ci}|, which means that Ra gains as many points from the ballot of agent i as there are alternatives that i explicitly ranks below a. This is precisely how the s Borda score of a is deﬁned.

4.2 Splitting The splitting axioms for rules of type W can be (and thus are) deﬁned and operate exactly as for rules of type L. The proof of our next result is similar to the proofs of Theorems 6 and 7. Theorem 13. The only weight rule of type W satisfying the single-splitting (or the equal-splitting) axiom is the equaland-even-weight rule F W ee . Remark 2. When applied to proﬁles of chains, F W ee is reminiscent of a positional scoring rule, suggesting the deﬁnition of a new family of voting rules (the exploration of which is beyond the scope of this paper) that integrates positional scoring rules [Zwicker, 2016] and cumulative voting rules [Glasser, 1959]: Consider the rule that associates a chain a1 a2 ak 1 ak of length k with the scoring vector ( k 1 k(k 1)/2, k 2 k(k 1)/2, . . . , 1 k(k 1)/2, 0). Under this rule, every agent distributes a total weight of 1 across the alternatives in her chain in a Borda-like fashion.

5 Obtaining a Set of Winners This section is concerned with weight rules generating outcomes of type Wk, which designate k-sized sets of winners. Whenever the input proﬁle consists of complete preferences only, any weight rule simulates the k-Borda rule, returning the k alternatives with the highest Borda scores [Faliszewski et al., 2017]. Proposition 14 can be seen as a corollary of Observation 5 of Lang et al. [2017]. Proposition 14. For any proﬁle L L(A)n and weight function w, it holds that top(F Wk w (L)) = k-Borda(L). In analogy to Proposition 10, for any weight rule of type Wk, the set of winners is easy to compute. Proposition 15. For any proﬁle R R(A)n and weight function w, F Wk w (R) can be computed in polynomial time. Moving on to the investigation of multiwinner weight rules for incomplete ballots, we note that the deﬁnitions of weak restricted majoritarianism and splitting apply and the proofs of Theorems 11 and 13 carry over to the case of k winners. Theorem 16. The only weight rule of type Wk satisfying weak restr. majoritarianism is the constant-weight rule F Wk c . Theorem 17. The only weight rule of type Wk satisfying the single-splitting (or the equal-splitting) axiom is the equaland-even-weight rule F Wk ee .

the least preferred alternative in the chain gets 1 point and all others get 0 points. For an example where the two rules give different outcomes, consider the proﬁle (a b c, c d). However, s Borda coincides with the rule assigning as score to an alternative a based on the length of the longest path below a [Endriss et al., 2009].

Remark 3. For proﬁles of chains, the constant-weight kwinner rule is not k-s Borda,11 but it gives rise to a neat original deﬁnition of a multiwinner rule. Conceptually, when deciding for a set of k winners, one could regard the potential outcome (for instance, the committee) as a whole and compare the power of its members (based on the voters explicitly declared preferences) against its nonmembers: Consider the multiwinner voting rule that makes a set S A of ﬁxed size win when the alternatives in S are preferred over the alternatives outside S the maximum number of times.

Remark 4. The equal-and-even-weight k-winner rule closely follows the constant-weight rule of the same type; however, in this case, the power of a committee member over an alternative outside the committee hinges also on the sizes of the ballots that rank the member above the nonmember.

Overall, our results in Sections 3, 4, and 5 suggest that majoritarianism and splitting can never be satisﬁed together, by any weight rule; we thus formulate a principal impossibility:

Corollary 18. For any type T {L, W, Wk}, there is no weight rule F T w that satisﬁes weak restricted majoritarianism together with single, equal, or arbitrary splitting.

Corollary 18 sheds light on a fundamental theoretical fact that also has signiﬁcant practical implications. For instance, we now know that for an online recommendation system based on weight rules it is impossible to respect the opinion of the majority of the recommenders and at the same time disincentivise them to manipulate the outcome in groups.

6 Conclusion

We have introduced a model for the representation and aggregation of incomplete preferences, designing a family of rules based on the weight a pairwise ranking of two alternatives receives when reported within a preference set. Our model is relevant to multiagent scenarios where agents may satisfy minimal rationality requirements and violate not only completeness but also transitivity. We have examined two original normative principles restricted majoritarianism and splitting that tie in directly with the incompleteness of preferences and characterise two weight rules with particularly simple weight functions. These results are robust across aggregation scenarios with varying output types (full rankings, single winning alternatives, and sets of winners). Besides providing a basic complexity analysis, we have also shown that the rules thus characterised reduce to well-known rules for the special case of complete input proﬁles and suggest the deﬁnition of new ones in the standard voting framework. Our work opens up several opportunities for future research: not only to identify further axioms and the weight rules they characterise, but also to explore our model of aggregation rules for incomplete pairwise preference sets more broadly, beyond the class of weight rules we have focussed on in this ﬁrst paper on the topic. Finally, an experimental study to compare different aggregation rules in addition to our theoretical analysis could also be an interesting next step.

11For a counterexample, consider a proﬁle with three ballots that are chains: a b c d, c d a, and d a.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

References [Alcalde-Unzu and Vorsatz, 2009] Jorge Alcalde-Unzu and Marc Vorsatz. Size approval voting. Journal of Economic Theory, 144(3):1187 1210, 2009. [Arrow et al., 2002] Kenneth Arrow, Amartya Sen, and Kotaro Suzumura, editors. Handbook of Social Choice and Welfare. North-Holland, 2002. [Baumeister et al., 2012] Dorothea Baumeister, Piotr Faliszewski, J erˆome Lang, and J org Rothe. Campaigns for lazy voters: Truncated ballots. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012. [de Borda, 1784] Jean-Charles de Borda. Memoire sur les elections au scrutin. Histoire de l Academie Royale des Sciences, 1784. [Boutilier and Rosenschein, 2016] Craig Boutilier and Jeffrey S. Rosenschein. Incomplete information and communication in voting. In Handbook of Computational Social Choice. Cambridge University Press, 2016. [Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016. [Caragiannis et al., 2015] Ioannis Caragiannis, George Krimpas, and Alexandros Voudouris. Aggregating partial rankings with applications to peer grading in massive online open courses. In Proceedings of the 14th Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2015. [Caragiannis et al., 2017] Ioannis Caragiannis, Xenophon Chatzigeorgiou, George Krimpas, and Alexandros Voudouris. Optimizing positional scoring rules for rank aggregation. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI), 2017. [de Condorcet, 1785] Nicolas de Condorcet. Essai sur l application de l analyse a la probabilit e des d ecisions rendues a la pluralit e des voix, 1785. [Conitzer et al., 2017] Vincent Conitzer, Walter Sinnott Armstrong, Jana Schaich Borg, Yuan Deng, and Max Kramer. Moral decision making frameworks for artiﬁcial intelligence. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI), 2017. [Darmann et al., 2017] Andreas Darmann, Julia Grundner, and Christian Klamler. Election outcomes under different ways to announce preferences: An analysis of the 2015 parliament election in the Austrian federal state of Styria. Public Choice, 173(1 2):201 216, 2017. [Domshlak et al., 2011] Carmel Domshlak, Eyke H ullermeier, Souhila Kaci, and Henri Prade. Preferences in AI: An overview. Artiﬁcial Intelligence, 175(7 8):1037 1052, 2011. [Eldar, 2008] Ofer Eldar. Vote-trading in international institutions. European Journal of International Law, 19(1):3 41, 2008.

[Endriss et al., 2009] Ulle Endriss, Maria Silvia Pini, Francesca Rossi, and K. Brent Venable. Preference aggregation over restricted ballot languages: Sincerity and strategy-proofness. In Proceedings of the 21st International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2009. [Endriss, 2018] Ulle Endriss. Judgment aggregation with rationality and feasibility constraints. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018. [Faliszewski et al., 2017] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. In Trends in Computational Social Choice. AI Access, 2017. [Glasser, 1959] Gerald Glasser. Game theory and cumulative voting for corporate directors. Management Science, 5(2):151 156, 1959. [Hansson and Gr une-Yanoff, 2018] Sven Ove Hansson and Till Gr une-Yanoff. Preferences. In The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, 2018. [Hemaspaandra et al., 2005] Edith Hemaspaandra, Holger Spakowski, and J org Vogel. The complexity of Kemeny elections. Theoretical Computer Science, 349(3):382 391, 2005. [Kemeny, 1959] John Kemeny. Mathematics without numbers. Daedalus, 88:577 591, 1959. [Konczak and Lang, 2005] Kathrin Konczak and J erˆome Lang. Voting procedures with incomplete preferences. In Proceedings of the IJCAI Multidisciplinary Workshop on Advances in Preference Handling (MPREF), 2005. [Lang et al., 2017] J erˆome Lang, J erˆome Monnot, Arkadii Slinko, and William S. Zwicker. Beyond electing and ranking: Collective dominating chains, dominating subsets and dichotomies. In Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017. [Pini et al., 2008] Maria Silvia Pini, Francesca Rossi, K. Brent Venable, and Toby Walsh. Aggregating partially ordered preferences. Journal of Logic and Computation, 19(3):475 502, 2008. [Terzopoulou et al., 2018] Zoi Terzopoulou, Ulle Endriss, and Ronald de Haan. Aggregating incomplete judgments: Axiomatisations for scoring rules. In Proceedings of the 7th International Workshop on Computational Social Choice (COMSOC), 2018. [Xia and Conitzer, 2008] Lirong Xia and Vincent Conitzer. Determining possible and necessary winners under common voting rules given partial orders. In Proceedings of the 23rd AAAI Conference on Artiﬁcial Intelligence (AAAI), 2008. [Zwicker, 2016] William S. Zwicker. Introduction to the theory of voting. In Handbook of Computational Social Choice. Cambridge University Press, 2016.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)