Aggregating Incomplete Pairwise Preferences by Weight

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 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.

∗Contact Author

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 flexible 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 specifically relevant to scenarios with incomplete preferences. We find 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

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

(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 profile 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 fide 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 fide incomplete preferences, but their proposals are less radical (they do not dispense with transitivity) and, in some sense, less flexible (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 specific 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 specific preference aggregation scenario concerns a finite group of agents N = {1, . . . , n} ⊆ N and a finite 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:

2 The 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 profile 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 profile 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 specific 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 infinite vector. For example, w = (1, 1 2 , 13 , . . .) means that we distribute a total weight of 1 equally across all pairs in Ri, whilew = (1, 1M , 1 M2 , ...), for a sufficiently large number M, weighs smaller ballots "infinitely" 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:

A second component of the definition 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 specific 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 finding a (single) winner, that is, an alternative ranked higher than any other alternative [Zwicker, 2016]. Hence, we also define 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 define the type Wk, where Wk(A) consists of all pairwise preferences that designate a set of k winners (for some fixed 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 define 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

3 Acyclicity 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.

4 This is important for the (upper bounds in) complexity results.

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 profile R = (R1, . . . , Rn) for a specific 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:

Note that for every weight rule F T w there are infinitely 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 defined 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 definition would be to first 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 (argmaxR∈R(A) ∑i∈N wRi (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?

5 Lang et al. [2017] define 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 profiles.

To answer this question, we require some further terminology. Given two types T and T ′ we say that T refines 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 refines 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 refines T ′ , we have that F T w (R) = argmaxR∈T (A) ∑i∈N wRi (R) ⊇ T (A) ∩ argmaxR∈T ′ (A) ∑i∈N wRi (R) = F T ′ w (R)|T .

For the other direction, we first 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 ∑i∈N wRi (R) ≥ ∑i∈N wRi (R′ ). Hence, we indeed get R ∈ F T ′ w (R) as claimed.

Now take any R∗ ∈ F T w (R). By definition of the weight rule, this entails ∑i∈N wRi (R∗ ) ≥ ∑i∈N wRi (R) for all R ∈ T (A), including the specific 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 refines 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 refined 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 profiles 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 profile 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 profile 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 clarifies that determining relative rankings under any weight rule of type L is complete for P NP || , 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.

6 In the interest of space, we omit a formal definition of this rule and refer to Brandt et al. [2016] for a modern exposition.

7 It might be tempting to confuse the possible outcomes (as defined 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 profile ({ab, bc, ac}, {ab, ca}, {ab, ca}).

Proposition 4. The relative ranking determination problem for F L w is P NP || -complete, for any weight function w.

Proof sketch. By Proposition 3, P NP || -hardness follows from the corresponding result for the Kemeny rule [Hemaspaandra et al., 2005]. Proving membership in P NP || 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 definitions, we fix a set of alternatives A ⊆ A, a group of agents N ⊆ N, and an aggregation rule F of type L, and say that F satisfies an axiom if the relevant definition 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 profile. Such is the case when the alternatives a, b are independent of a profile 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 findings 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 profile R ∈ R(A)n , let us define 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 profile 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 satisfies 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 satisfies restrictedmajoritarianism. To prove that F L w is the constant weight rule it suffices to show that wλ = wλ′ for all λ, λ′ ∈ N.

We first show that F L w satisfying restricted majoritarianism for a group N ⊆ N with odd n > 1 implies that wλ wλ′ < 1 + 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′2 b′2 , . . . , a′λ′b′λ′} ∈ R(A). We construct the following profile R ∈ R(A)n for an odd n > 1:

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 satisfies 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 infinity, this implies that wλ = wλ′ for all λ, λ′ .

3.2 Splitting

We now define a novel axiom tailored to the aggregation of bona fide 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 profile R ∈ R(A)n and subgroup N ′ ⊆ N of agents with pairwise disjoint ballots, it is the case that ⋃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 ⋃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 find 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 satisfied 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 satisfies it. Take two profiles R, R′ , where R′ arises from R by replacing the preference set of each member of N ′ by the union ⋃i∈N ′ Ri. By the definition of the weights for the rule F L ee , we know that every pair of alternatives in ⋃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 ⋃i∈N ′ Ri too, since they trivially appear in exactly the same preference sets in both profiles 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 two profiles 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 sufficiently 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 satisfies 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 profile 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 satisfies equal splitting, then it satisfies 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 satisfies equal splitting, proceeds exactly as the first part of the proof of Theorem 6.

Proposition 8. No weight rule of type L satisfies the arbitrary-splitting axiom.

Proof. Every weight rule of type L that satisfies arbitrary splitting also satisfies 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 profiles 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 profile 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 aWinner

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 define 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 define top(S) = ⋃R∈S top(R).

For complete input profiles, 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 first 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 profile 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 fact that the Borda winner can be found in polynomial time (the simple proof is omitted due to space constraints). 9

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

Proposition 10. For any profile 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 profiles 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 satisfies weak restricted majoritarianism if for every profile 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 profile R. Let Ra denote the preference set in W(A) corresponding to a being the winning alternative. We have ∑i∈N wRi (Ra1 ) = ∑i∈N wRi (Ra2 ) = · · · = ∑i∈N wRi (Raλ ) = n-1 2 wλ and ∑i∈N wRi (Rb1 ) = ∑i∈N wRi (Ra′2) = · · · = ∑i∈N wRi (Ra′λ′ ) = n+1 2 wλ′ . Thus, either each of a1, a2, . . . , aλ win in some profile 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 definition 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 profiles of chains (i.e., on profiles C ∈ C(A)n ), by first defining 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 (sBorda) then maximises the collected points in a profile. 10

9 So, 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].

10 Shortsighted Borda differs from optimistic (or modified) 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

Proposition 12. For any profile C ∈ C(A)n , it holds that top(F W c (C)) = sBorda(C).

Proof sketch. For simplicity take wλ = 1 for all λ ∈ N. Then, for an outcome Ra corresponding to alternative a winning, we have wCi (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 sBorda score of a is defined.

4.2 Splitting

The splitting axioms for rules of type W can be (and thus are) defined 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 profiles of chains, F W ee is reminiscent of a positional scoring rule, suggesting the definition 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 profile 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 profile 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 profile 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 definitions 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 profile (a ≻ b ≻ c, c ≻ d). However, sBorda 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 profiles of chains, the constant-weight kwinner rule is not k-sBorda, 11 but it gives rise to a neat original definition 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 fixed 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 satisfied 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 satisfies weak restricted majoritarianism together with single, equal, or arbitrary splitting.

Corollary 18 sheds light on a fundamental theoretical fact that also has significant 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 profiles and suggest the definition 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 first 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.

11 For a counterexample, consider a profile with three ballots that are chains: a ≻ b ≻ c ≻ d, c ≻ d ≻ a, and d ≻ a.