Incompleteness and Incomparability in Preference Aggregation

1 Introduction

We consider a multi-agent setting where each agent specifies their preferences by means of an ordering over the possible outcomes. A pair of outcomes can be ordered, incomparable, in a tie, or the relationship between them may not yet be specified. Incomparability and incompleteness represent very different concepts. Outcomes may be incomparable because the agent does not wish very dissimilar outcomes to be compared. For example, we might not want to compare a biography with a novel since the criteria along which we judge them are just too different. Outcomes can also be incomparable because the agent has multiple criteria to optimize. For example, we might not wish to compare a faster but more expensive laptop with a slower and cheaper one. Incompleteness, on the other hand, represents simply an absence of knowledge about the relationship between certain pairs of outcomes. Incompleteness arises when we have not fully elicited an agent's preferences or when agents have privacy concerns which prevent them from revealing their complete preference ordering.

∗This work has been supported by Italian MIUR PRIN project "Constraints and Preferences" (n. 2005015491).

Since we wish to aggregate together the agents' preferences into a single preference ordering, we must modify preference aggregation functions to deal with incompleteness. One possibility is to consider all possible ways in which the incomplete preference orders can be consistently completed. In each possible completion, preference aggregation may give different optimal elements (or winners). This leads to the idea of the possible winners (those outcomes which are winners in at least one possible completion) and the necessary winners (those outcomes which are winners in all possible completions) [Konczak and Lang, 2005].

While voting theory has been mainly interested in the fairness of social choice or social welfare functions, there has been recent interest in computational properties of preference aggregation [Rossi et al., 2004; Lang, 2004; Konczak and Lang, 2005; Conitzer and Sandholm, 2002b]. It has also been noted that the complexity of manipulating an election is closely related to the complexity of computing possible winners [Konczak and Lang, 2005; Conitzer and Sandholm, 2002a].

In this paper we start by considering the complexity of computing the necessary and the possible winners. We show that both tasks are hard in general, even to approximate. Then we identify sufficient conditions that assure tractability. Such conditions concern properties of the preference aggregation function, such as monotonicity and independence to irrelevant alternatives (IIA) [Arrow et al., 2002].

Possible and necessary winners are useful in many scenarios including preference elicitation [Chen and Pu, 2004]. For example, elicitation is over when the set of possible winners coincides with that of the necessary winners [Conitzer and Sandholm, 2002b]. However, recognizing when such a condition is satisfied is hard in general. In the last part of the paper we show that, if the preference aggregation function is IIA, preference elicitation can focus just on the incompleteness concerning those outcomes which are possible and necessary winners, allowing us to ignore all other outcomes and to complete preference elicitation in polynomial time.

2 Basic notions

Preferences. We assume that each agent's preferences are specified via a (possibly incomplete) partial order with ties

(IPO) over the set of possible outcomes, that we will denote by Ω. An incomplete partial order is a partial order where some relation between pairs of outcomes is unknown. Given two outcomes A and B, an agent will specify exactly one of the following: A < B, A > B, A = B, A ∼ B, or A?B, where A ∼ B means that A and B are incomparable, and A?B that the relation between A and B is unknown, this means that it can be any element of {=,>,<, ∼}.

Example 1. Given outcomes A, B, and C, an agent may state preferences such as A > B, B ∼ C, and A > C, or also just A > B and B ∼ C. However, an agent cannot state preferences such as A > B, B > C, C > A, or also A > B, B > C, A ∼ C since neither are POs.

Profiles. A profile is a sequence of n partial orders p1, . . . , pn over outcomes, one for each agent i ∈ {1, . . . , n}, describing the preferences of the agents. An incomplete profile is a sequence in which one or more of the partial orders is incomplete.

Social welfare and preference aggregation. Social welfare functions [Arrow et al., 2002] are functions from profiles to partial orders with ties. Given a social welfare function f, we define a corresponding preference aggregation function, written paf , which is a function from incomplete profiles to sets of partial orders with ties (POs). Precisely, given an incomplete profile ip = (ip1, . . . , ipn), where the ipi's are IPOs, consider all the profiles, say p1, . . . , pk, obtained from ip by replacing any occurrence of ? in the ipi's with either <,>, =, or ∼ which is consistent with a partial order. Let us then set paf(ip) = {f(p1), . . . , f(pk)}. This set will be called the set of results of f on profile ip.

Example 2. Consider the Pareto social welfare function f defined as follows [Arrow et al., 2002]: given a profile p, for any two outcomes A and B, if all agents say A > B or A = B and at least one says A > B in p, then A > B ∈ f (p); if all agents say A = B in p, then A = B ∈ f(p); otherwise, A ∼ B ∈ f(p). In Figure 1 we show an example with three agents and three outcomes A, B, and C.

Necessary and possible winners. We extend to the case of partial orders the notions of possible and necessary winners presented in [Konczak and Lang, 2005] in the case of total orders. Given a social welfare function f and an incomplete profile ip, we define necessary winners of f given ip to be all those outcomes which are maximal elements in all POs in paf(ip) . A necessary winner must be a winner, no matter how incompleteness is resolved in the incomplete profile. Analogously, the possible winners are all those outcomes which are maximal elements in at least one of the POs in paf(ip). A possible winner is a winner in at least one possible completion of the incomplete profile. We will write NW(f, ip) and PW(f, ip) for the set of necessary and possible winners of f on profile ip. We will sometimes omit f and/or ip, and just write NW and PW when they will be obvious or irrelevant.

Example 3. In Example 2, A and B are the necessary winners, since they are top elements in all POs f(pi), for all i = 1, 2. C is a possible winner since it wins in f(p2).

Combined result. Unfortunately, the set of results can be exponentially large. We will therefore also consider a compact representation that is polynomial in size. This may throw away information by compacting together results into a single combined result. Given a social welfare function f and an incomplete profile ip, consider a graph, whose nodes are the outcomes, and whose arcs are labeled by non-empty subsets of {<, >, =, ∼}. Label l is on the arc between outcomes A and B if there exists a PO in paf (ip) where A and B are related by l. This graph will be called the combined result of f on ip, and will be denoted by cr(f, ip). If an arc is labeled by set {<,>, =, ∼}, we will say that it is fully incomplete. Otherwise, we say that it is partially incomplete. The set of labels on the arc between A and B will be called rel(A, B).

Example 4. The combined result for Example 2 is shown in Figure 1.

3 Possible and NecessaryWinners

In this section we show that computing the set of necessary and possible winners of a social welfare function is, in general, NP-hard even if we restrict ourselves to incomplete but total orders. We will consider the following, well known, voting rule.

Single Transferable Vote. In the STV rule each voter provides a total order on candidates and, initially, an individual's vote is allocated to their most preferred candidate. The quota of the election is the minimum number of votes necessary to get elected. If only one candidate is to be elected then the quota is ⌊n/2⌋ + 1, where n is the number of voters. If no candidate exceeds the quota, then, the candidate with the fewest votes is eliminated, and his votes are equally distributed among the second choices of the voters who had selected him as first choice. In what follows we consider STV

elections in which some total orders, provided by the voters, are incomplete.

In general, given an incomplete profile and a candidate a, we say POSSIBLEWINNER holds iff a is a possible winner of the election.

Theorem 1 PossibleWinner is NP-complete.

Proof: In fact, membership in NP follows by giving a completion of the profile in which a wins. Completeness follows from the result that EFFECTIVE PREFERENCE (determining if a particular candidate can win an election with one vote unknown) for STV is NP-complete [Bartholdi and Orlin., 1991] Q.E.D.

This result allows us to conclude that, in general, finding possible winners of an election is difficult. However, it should be noticed that for many rules used in practice including some positional scoring rules [Konczak and Lang, 2005], answering PossibleWinner is polynomial. The complexity of computing possible winners is related to the complexity of manipulating an election [Konczak and Lang, 2005]. For instance, it is NP-complete to determine for the Borda, Copeland, Maximin and STV rules if a coalition can cast weighted votes to ensure a given winner [Conitzer and Sandholm, 2002a]. It follows therefore that with weighted votes, PossibleWinner is NP-hard for these rules.

Given an incomplete profile and a candidate a, we say NECESSARYWINNER holds iff a is a necessary winner of the election.

Theorem 2 NecessaryWinner is coNP-complete.

Proof: The complement problem is in NP since we can show membership by giving a completion of the profile in which some b different to a wins. To show completeness, we give a reduction from EFFECTIVE PREFERENCE with STV in which a appears at least once in first place in one vote. This restricted form of EFFECTIVE PREFERENCE is NP-complete [Bartholdi and Orlin., 1991]. Consider an incomplete profile Π in which n + 1 votes have been cast, a has at least one first place vote, one vote remains unknown, and we wish to decide if a can win. We construct a new election from Π with n new additional votes, and one new candidate b. We put b at the top of each of these new votes, and rank the other candidates in any order within these n votes. We place b in last place in the original n + 1 votes, except for one vote where a is in first place (by assumption, one such vote must exist) where we place b in second place and shift all other candidates down. We observe that b will survive till the last round as b has at least n votes and no other candidate can have as many till the last round. We also observe that if a remains in the election, then the score given to each candidate by STV remains the same as in the original election so the candidates are eliminated in the same order up till the point a is eliminated. If a is eliminated before the last round, the second choice vote for b is transferred. Since b now has n + 1 votes, b is unbeatable and must win the election. If a survives, on the other hand, to the last round, we can assume b is ranked at the bottom of the unknown vote. All the other candidates but a and b have been eliminated so a has n + 1

votes and is unbeatable. Hence, if a is not a possible winner in the original election, b is the necessary winner of this new election. Thus determining the necessary winner of this new election decides if a is a possible winner of the original election. Q.E.D.

Given these results, we might wonder if it is easy to compute a reasonable approximation of the sets of possible and necessary winners. Unfortunately this is not the case. The reduction described in the proof of previous theorem shows that we cannot approximate the set of possible winners within a factor of two. In fact, we can show that we cannot approximate efficiently the set of possible winners within any constant factor.

Theorem 3 It is NP-hard to return a superset of the possible winners, PW ∗ in which we guarantee |PW ∗ | < k|PW| for some given positive integer k.

Proof: We again give a reduction from EFFECTIVE PREFERENCE for STV in which a appears at least once in first place in one vote. Consider an incomplete profile Π in which n + 1 votes have been cast, a has at least one first place vote, one vote remains unknown, and we wish to decide if a can win. We construct a new election from Π. We make k copies of Π. In the ith copy Πi, we subscript each candidate with the integer i. We add n new additional votes, and one new candidate b. We put b at the top of each of these new votes, and rank all the other candidates except ai in any order within these n votes. The ranking of the candidates ai is left unknown but beneath b. In each Πi, we place b in last place except for one vote where ai is in first place (by assumption, one such vote must exist) where we place b in second place and shift all other candidates down. Finally, for each candidate in Πj not in Πi except for aj, we rank then in any order at the bottom of the the votes in Πi. The ranking of the candidates ai is again left unknown but beneath b. We observe that b will survive till all but one candidate has been eliminated from one of the Πi. We also observe that if ai remains in the election, then the score given to each candidate by STV remains the same as in the original election so the candidates in Πi are eliminated in the same order up till the point ai is eliminated. Suppose a cannot win the original election. Then ai will always be eliminated before the final round. The second choice vote for b is transferred. Since b now has at least n + 1 votes, b is unbeatable and must win the election. Suppose, on the other hand, that a can win the original election. Then ai can survive to be the last remaining candidate in Πi. We can assume b is ranked at the bottom of the unknown votes of all the candidates with an index i and above all the candidates with an index j different to i. Thus ai has n + 1 votes. If we have the corresponding ranking in the other unknown votes, aj for j ̸= i will also survive. Since b has only n votes, b will be eliminated. It is now possible for any of the candidates, ai where 1 ≤ i ≤ k to win depending on how exactly the ai are ranked in the different votes. Thus the set of possible winners is {ai | 1 ≤ i ≤ k} plus b if a is not a necessary winner in the original election. Hence, if a is a possible winner in the original election, the size of the set of possible winners is greater than or equal to k, whilst if it is not, the set is of size 1. If we know that |PW ∗ | < k|PW|, then |PW ∗ | < k guarantees that |PW| = 1, b is the necessary winner and hence that a is not a possible winner in the original election. Q.E.D.

Similarly, we cannot approximate efficiently the set of necessary winners within some fixed ratio.

Theorem 4 It is NP-hard to return a subset of the necessary winners, NW ∗ in which we guarantee |NW ∗ | > 1k |NW| whenever |NW| > 0 for any given positive integer k.

Proof: In the reduction used in the last proof, |NW| = 1 if a is a possible winner in the original election and 0 otherwise. Suppose a is a possible winner. Then in the new election, |NW| = 1. As |NW ∗ | > 1k |NW|, it follows that |NW ∗ | = 1. Thus, the size of NW ∗ will determine if a is possible winner. Q.E.D.

4 Combined result

We now consider the problem of computing the combined result. We show that, while in general it is difficult, there are some restrictions which allow us to compute an approximation of the combined result in polynomial time. In the next section, we will show how it is possible to compute the set of possible and necessary winners starting from this approximation to the combined result.

Theorem 5 Given an incomplete profile, determining if a label is in the combined result for STV is NP-complete.

Proof: In fact, a polynomial witness is a completion of the incomplete profile. To show completeness, we use a polynomial number of calls to this problem to determine if a given candidate is a possible winner. Q.E.D.

From this result we immediately get the following corollary.

Corollary 5.1 Given an incomplete profile and a social welfare function, computing the combined result is NP-hard.

We now introduce some properties of preference aggregation functions which allow us to compute an upper approximation to the combined result in polynomial time. We recall that the set of labels of an arc between A and B in the combined result is called rel(A,B).

The first property we consider is independence to irrelevant alternatives (IIA). A social welfare function is said to be IIA when, for any pair of outcomes A and B, the ordering between A and B in the result depends only on the relation between A and B given by the agents [Arrow et al., 2002]. Many preference aggregation functions are IIA, and this is a property which is related to the notion of fairness in voting theory [Arrow et al., 2002]. Given a function which is IIA, to compute the set rel(A,B), we just need to ask each agent their preference over the pair A and B, and then use f to compute all possible results between A and B. However, if agents have incompleteness between A and B, f has to consider all the possible completions, which is exponential in the number of such agents.

Assume now that f is also monotonic. We say that an outcome B improves with respect to another outcome A if the relationship between A and B does not move left along the following sequence: >,≥, (∼ or =), ≤,<. For example, B improves with respect to A if we pass from A ≥ B to A ∼ B. A social welfare function f is monotonic if for any two profiles p and p′ and any two outcomes A and B passing from p to p′ B improves with respect to A in one agent i and pj = p′j for all j ̸= i, then passing from f(p) to f(p′ ) B improves with respect to A.

Consider now any two outcomes A and B. To compute rel(A,B) under IIA and monotonicity, again, since f is IIA, we just need to consider the agents' preferences over the pair A and B. However, now we don't need to consider all possible completions for all agents with incompleteness between A and B, but just two completions: A < B and A > B. Notice that, since f is IIA, we don't need to consider complete profiles, but just the part of the profile concerning A and B. This means that transitivity issues do not arise.

Function f will return a result for each of these two completions, say AxB and AyB, where x, y ∈ {<,>, =, ∼}. Since f is monotonic, the results of all the other completions will necessarily be between x and y in the ordering >, ≥, (∼ or =), ≤, <. By taking all such relations, we obtain a superset of rel(A, B), that we call rel∗ (A, B). In fact, monotonicity of f assures that, if we consider profile A < B and we get a certain result, then considering profiles where A is in a better position w.r.t. B (that is, A > B, A = B, or A ∼ B), will give an equal or better situation for A in the result. Thus we have obtained an approximation of the combined result, that we call cr∗ (f, ip). We will now give a characterization of this approximation of the combined result.

Theorem 6 Given two outcomes A and B, rel∗ (A,B) ⊇ rel(A,B). Moreover, if rel∗ (A,B) = {<,>, ∼, =}, then either rel∗ (A, B) = rel(A, B) or rel∗ (A, B)-rel(A, B) = {∼, =}.

Example 5. Consider the Lex rule [Arrow et al., 2002], in which agents are ordered and, given any two outcomes A and B, the relation between A and B in the result is the relation given by the first agent in the order that does not declare a tie between A and B. Consider the incomplete profile ip = (ip1 = (A > C,B > C,A?B), ip2 = (A > B > C)). Then rel∗ (A,B) = {<, =, ∼, >}, whereas rel(A, B) = {<, ∼, >}.

By following the procedure described above, this approximation of the combined result can be computed polynomially, since we only need to consider two completions.

Theorem 7 Given a preference aggregation function f which is IIA and monotonic, and an incomplete profile ip, computing cr∗ (f, ip) is polynomial in the number of agents.

5 Computing possible and necessary winners

We will now show how to determine the possible and necessary winners, given cr∗ (f, ip). Consider the arc between an outcome A and an outcome C in cr∗ (f, ip). Then, if this arc has the label A < C, then A is not a necessary winner, since there is an outcome C which is better than A in some result. If this arc only has the label A < C, then A is not a possible winner since we must have A < C in all results. Moreover, consider all the arcs between A and every other outcome C. Then, if no such arc has label which includes A < C, then A is a necessary winner. Notice, however, that in general, even if there are no arcs connecting A to every other outcome C with the unique label A < C, A could not be possible winner. A could be better than some outcomes in every completion, but there might be no completion where it is better than all of them. We will show that this is not the case if f is IIA and monotonic.

We now define Algorithm 1, which, given cr∗ (f, ip), computes NW and PW, in polynomial time.

Algorithm 1: Computing NW and PW

Input: cr∗ (f, ip), where f: IIA and monotonic

preference aggregation function and ip: incomplete profile; Output: P, N: sets of outcomes; P ← Ω; N ← Ω; foreach A ∈ Ω do if ∃ C ∈ Ω such that {<} ⊆ rel∗ (A, C) then N ← N - A; if ∃ C ∈ Ω such that {<} = rel∗ (A, C) then P ← P - A;

return P , N;

Theorem 8 Given cr∗ (f, ip), Algorithm 1 terminates in O(m2 ) time, where m = |Ω|, returning N = NW and P = PW.

Proof: Algorithm 1 considers, in the worst case, each arc exactly once, thus we have O(m2 ).

N=NW. By construction of cr∗ (f, ip), ≮∈ rel∗ (A,C) iff ≮∈ rel(A,C). By Algorithm 1, A ∈ N iff ∀C,≮∈ rel{A,C}, and this implies that there is no result in which there exists an outcome C that beats A. Thus, A ∈ NW. On the contrary, A ∈ NW iff A ̸< C, ∀C ∈ Ω, for all results, from which, A ∈ N .

P = PW. An outcome A is in PW if there is no other outcome which beats it in all results. Thus, there cannot exist any other outcome C such that < is the only label in rel{A,C} and, thus by construction, also in rel∗{A,C}. Thus, PW ⊆ P. To show the other inclusion we consider A ∈ P and we construct a completion of ip such that A wins in its result. First, let us point out that for any outcome A, A ∈ P iff ̸ ∃C ∈ Ω, rel∗ (A,C) = {<}. If ∀C ∈ Ω, ≮∈ rel∗ (A, C), then A is never beaten by any other outcome C and A is NW and, thus, a PW. Secondly, let us consider the case in which A is such that whenever <∈ rel∗ (A,C), either ∼ or > (or both) are also in rel∗ (A,C) and let us denote with X such set of outcomes. Then for every outcome in C ∈ X we choose > whenever available and ∼ otherwise. This corresponds to replacing A?C with A > C in the incomplete profile. Such choice on AC arcs cannot cause a transitivity inconsistency and thus can be completed to a result in which A is a winner. Finally, let us consider the case in which there is at least a C such that rel∗ (A, C) = {<, =}. If for every other outcome C′ , rel∗ (A, C′ ) contains exactly one label from the set: {>, ∼, =} then we can safely set AC to = since there is, for sure, a result with that labeling. Moreover, in such a result A is a winner. Assume, instead, that there is at least an outcome C′ such that |rel∗ (A,C′ ) > 1|. This means that there is at least an agent which has not declared his preference on AC′ and that such preference cannot be induced by transitivity closure. We replace A?C′ with A > C′ everywhere in the profile, we perform the transitive closure of all the modified IPOs, and we apply f. We will prove that such transitive closure does not force label < on AC. After the procedure, due to monotonicity, rel(A,C′ ) will contain exactly one label from the set: {>, ∼, =}. Let us assume that, after the procedure, A = C′ and let us now consider rel(C′ ,C). Had it been rel∗ (C′ ,C) = {<} from the start, this would have forced rel(A,C) = {<}. However, this is not possible since A ∈ P. This allows us to conclude that (rel∗ (C′ , C) ∩ {>, ∼, =}) ̸= ∅ and any of such additional labels together with A = C′ can never force A < C. Clearly, if A > C′ or A ∼ C′ , there is no labeling of C′C which can force A < C. It should be noticed that any available choice on C′C can always be made safely due to the fact that the function is IIA and that the transitive closure of the profiles has already ruled out inconsistent choices. By iterating the procedure until every ? in the incomplete profile is replaced, we can construct a result of the function in which A is a winner. Q.E.D.

An example of a preference aggregation function which is both IIA and monotonic is the Pareto rule, described in Example 2. Another example is the Lex rule, described in Example 5. A third example is the approval voting rule, for which a tractability result for computing NW and PW is given in [Konczak and Lang, 2005] since it is a positional scoring rule.

6 Preference elicitation

One use of necessary and possible winners is in eliciting preferences [Chen and Pu, 2004]. Preference elicitation is the process of asking queries to agents in order to determine their preferences over outcomes. At each stage in eliciting agents' preferences, there is a set of possible and necessary winners. When NW = PW, preference elicitation can be stopped since we have enough information to declare the winners, no matter how the remaining incompleteness is resolved [Conitzer and Sandholm, 2002b]. At the beginning, NW is empty and PW contains all outcomes. As preferences are declared, NW grows and PW shrinks. At each step, an outcome in PW can either pass to NW or become a loser. When PW is larger than NW, we can use these two sets to guide preference elicitation and avoid useless work.

If the preference aggregation function is IIA, then to determine if an outcome A ∈ PW -NW is a loser or a necessary winner, it is enough to ask agents to declare their preferences over all pairs involving A and another outcome, say B, in PW. Moreover, IIA allows us to consider just one profile when computing the relations between A and B in the result, and guarantees that the result is a precise relation, that is, either <, or >, or =, or ∼. To determine all the winners, we thus need to know the relations between A and B for all A ∈ PW - NW and B ∈ PW. There are examples where all such pairs must be considered. Algorithm 2, in O(|PW|2 ) steps eliminates enough incompleteness to determine the winners. At each step, the algorithm asks each agent to express their preferences on a pair of outcomes (via procedure ask(A,B)) and aggregates such preferences via function f. If function f is polynomially computable, the whole computation is polynomial in the number of agents and outcomes.

Theorem 9 If f is IIA and polynomially computable, then determining the set of winners via preference elicitation is polynomial in the number of agents and outcomes.

Using the results of the previous sections, under certain conditions we know how to compute efficiently the necessary winners and the possible winners. Thus Algorithm 2 can be given as input the outputs of Algorithm 1.

Algorithm 2: Winner determination

Input: PW, NW: sets of outcomes; f: preference

aggregation function; Output: W: set of outcomes; wins: bool; P ← PW; N ← NW; while P ̸= N do choose A ∈ P - N; wins ← true; PA ← P - {A}; repeat choose B ∈ PA; if ∃ an agent such that A?B then ask(A,B); compute f (A,B); if f(A, B) = (A > B) then P ← P - {B}; if f(A, B) = (A < B) then P ← P - {A}; wins ← false; PA ← PA - {B}; until f(A, B) = (A < B) or PA = ∅ ; if wins = true then N ← N ∪ {A}; W ←N; return W ;

It should be noticed that deciding when elicitation is over, that is checking if P = N, is hard in general since, in [Conitzer and Sandholm, 2002b] such a result has been proven for STV.

7 Related and future work

In [Konczak and Lang, 2005] preference aggregation functions for combining incomplete total orders are considered. Compared to our work, we permit both incompleteness and incomparability, while they allow only for incompleteness. Second, they consider social choice functions which return the (non-empty) set of winners. Instead, we consider social welfare functions which return a complete partial order. Social welfare functions give a finer grained view of the result. Third, they consider specific voting rules like the Borda procedure whilst we have focused on general properties that ensure tractability.

Some of our results use IIA which is a strong assumption. However, we use it just to show intractability is not inevitable on incomplete partial orders. We plan to find other cases where IIA can be relaxed. We also plan to consider the addition of constraints to agents' preferences. This means that preference aggregation must take into account the feasibility of the outcomes. Thus possible and necessary winners must now be feasible. It is also important to consider compact knowledge representation formalisms to express agents' preferences, such as CP-nets and soft constraints. Possible and necessary winners should then be defined directly from such compact representations, and preference elicitation should concern statements allowed in the representation language. Finally, a possibility or a probability distribution over the completions of an incomplete preference relation can be used to provide additional information when computing possible and necessary winners.