A Maximum Likelihood Approach towards Aggregating Partial Orders

1 Introduction

In traditional voting theory, it is usually assumed that each agent reports her preferences as a linear order. However, in computational social choice and the associated multiagent applications, it is often desirable to allow for partial orders. There are at least two important reasons for this. First, sometimes an agent is simply unable to decide which of two alternatives should be ranked higher (that is, the two alternatives are incomparable [14]). Second, sometimes the number of alternatives is extremely large, so that it is infeasible from a computation/communication standpoint for the agents to fully report their preferences over the whole set of alternatives (that is, the agents' preferences are incomplete [14]).

Vincent Conitzer

Department of Computer Science

Duke University Durham, NC 27708, USA conitzer@cs.duke.edu

For example, in multi-issue domains, the set of alternatives is exponentially large. In this context, researchers have investigated voting methods that are based on the agents representing their preferences by CP-nets [4; 17; 14; 13; 23]. A CP-net corresponds to a specific type of partial order over the alternatives. As another example, perhaps only parts of the agents' preferences have been revealed so far, perhaps through an incremental elicitation process, and in this case the currently available information can be represented by a partial order for each agent. In such a situation, it is useful to knowwhether a given alternative can still / must certainly win the election at this point (the possible / necessary winner problem) [12; 20; 3; 2; 21].

Perhaps because these issues have not been central in the traditional social choice literature, there has not been much research on designing good voting rules that take partial orders as input. It is not difficult to make up such a rule in an adhoc fashion. For example, Rademaker and De Baets [16] proposed a computationally tractable method to aggregate partial orders. Their method in some sense extends a common voting rule called ranked pairs [18]. However, we feel that a more principled approach is desirable. For example, we may follow the axiomatic approach. This approach reigns supreme in social choice theory, with for example the celebrated example of Arrow's impossibility theorem [1]. Some desirable properties (axioms) of a voting rule are specified, and then the corresponding class of voting rules is characterized. Pini et al. [15] applied the axiomatic approach to voting with partial orders and obtained some significant impossibility theorems.

Much older, and arguably more constructive, is the maximum likelihood approach, which was first introduced more than two hundred years ago by Condorcet [7], and has recently been adopted in economics [8; 19], as well as in the artificial intelligence and computational social choice literatures [6; 5; 23]. The idea is to imagine that there is a "correct" outcome, and each voter's preferences constitute a noisy perception of this absolute truth. In Condorcet's model, given the "correct" ranking V , for each pair of alternatives c and c′ where c ≻V c′ , with probability p > 1/2 the voter also prefers c to c′ (and with probability 1 -p, she prefers c′ to c). This "pairwise independence" assumption might result in intransitive preferences, e.g. a ≻ b, b ≻ c, and c ≻ a. However, this does not cause a problem. We can simply conceptually allow for the possibility that a voter has a vote that violates transitivity.

This gives us a voting rule that is defined on a larger domain that allows for intransitivity, which can then still be applied to the subdomain where transitivity holds. Given a profile, a winning full ranking is defined to be one that maximizes the likelihood of the agents' votes. Condorcet's original MLE model results in Kemeny's rule [26]. It was later shown that some, but not all, other commonly used voting rules are MLEs for some noise models [6]. MLE rules have been characterized as a class of voting rules called ranking scoring rules [5]. The MLE approach has also been pursued for voting in multiissue domains [23].

In this paper, we pursue the MLE approach in the context of voting with partial orders. An illustrative example is as follows. We have a set of candidates for k ≥ 1 positions (for example, Ph.D. applicants), and a committee that evaluates these candidates. A committee member will generally not give a linear order of all candidates, being both time-constrained and not always comfortable comparing a given pair of candidates (perhaps due to area mismatch). In this context, it is not unreasonable to suppose that some candidates are, in some sense, truly better than others, but of course there is noise in the process. Our goal may be to get an aggregate ranking of all candidates, or to designate the top k alternatives.

2 Preliminaries

Let X = {c1, . . . , cm} be a finite set of alternatives (or candidates) and O be a finite set of outcomes. Despite being finite, the size of X or O is not constrained. In traditional voting systems, a vote V is a linear order over X, i.e., a transitive, antisymmetric, and total relation over X. The set of all linear orders on X is denoted by L(X ). In this paper, we allow a vote to be a partial order over X, i.e., a transitive and antisymmetric relation over X. The set of all partial orders on X is denoted by PO(X ). For any pair of alternatives c, c′ and any partial order W, we write c ∼W c′ if c and c′ are not comparable in the partial order W. We note that L(X ) ⊆ PO(X ). An n-voter profile P over L(X ) (respectively, PO(X )) can be written as P = (V1, . . . , Vn), where Vj ∈ L(X ) (respectively, Vj ∈ PO(X )) for every j ≤ n. The set of all profiles over L(X ) (respectively, PO(X )) is denoted by FL(X ) (respectively, FPO(X )). In this paper, a (voting) rule r maps any profile to a subset of outcomes. Two example outcome spaces are X , the set of all alternatives, and L(X ), the set of all linear orders. 1 A voting rule rPO over profiles of partial orders is an extension of a voting rule rL over profiles of linear orders, if for any P ∈ FL(X ), we have rPO(P ) = rL(P ). In this case rL is called the restriction of rPO on FL(X ). The following common voting rules over FL(X ) play a role in our paper.

· Positional scoring rules. Here we let O = X. Given a scoring vector ⃗v = (v1, . . . , vm) of m integers, for any vote V ∈ L(X ) and any c ∈ X, let PS⃗v(V, c) = vi, where i is the rank of c in V . For any profile P = (V1, . . . , Vn), let PS⃗v(P, c) = ∑nj=1 PS⃗v(Vj, c). The rule will select all alternatives c∗ ∈ X so that PS⃗v(P, c∗ ) is maximized. One important positional scoring rule is Borda, for which the scoring vector is (m1, m - 2, . . . , 0).

1 The former type of mapping is also known as a voting correspondence, and the latter as a preference function. In this paper, we simply call them voting rules for convenience.

· Kemeny. Here we let O = L(X ). For any pair of linear orders V and V ′ and any pair of different alternatives c, c′ , let δc,c′ (V, V ′ ) equal 1 if V and V ′ agree on which of c and c′ is ranked higher. The Kemeny rule will select all linear orders V ∗ so that ∑V ∈P ∑c̸=c′ δc,c′ (V, V ∗ ) is maximized.

For any profile P composed of linear orders, we let WMG(P ) denote the weighted majority graph of P , defined as follows. WMG(P ) is a directed graph whose vertices are the alternatives. For i ̸= j, let DP (ci, cj) denote the total number of votes in P where ci ≻ cj minus the total number of votes in P where cj ≻ ci. If DP(ci, cj) > 0, then there is an edge (ci, cj) with weight wij = DP(ci, cj). Also, for i < j, if DP(ci, cj) = 0, then there is an edge (ci, cj) with weight wij = 0.

We say a voting rule r (defined over FL(X )) is based on the WMG if for any pair of profiles P1, P2 such that WMG(P1) = WMG(P2), we have r(P1) = r(P2). We say a voting r satisfies non-imposition if for any alternative c and any natural number n, there exists an n-profile P such that r(P ) = c. A voting rule r satisfies neutrality if r treats the alternatives symmetrically. More precisely, for any permutation M over X and any profile P , we have r(M (P )) = M (r(P )).

Maximum Likelihood Approach to Voting

In the maximum likelihood approach to voting, it is assumed that there is an unobserved correct outcome o+ ∈ Ofor example, a correct ranking V + ∈ L(X ) or a correct winner c+ ∈ X-and each vote V is drawn conditionally independently given o+, according to a conditional probability distribution π(V |o+). The independence structure of the noise model is illustrated by the Bayesian network in Figure 1. 2

Under this independence assumption, the probability of a profile P = (V1, . . . , Vn) given the correct outcome o+ is π(P|o+) = ∏nj=1 π(Vj|o+). Then, the maximum likelihood estimate of the correct winner is MLEπ(P ) = argmaxo∈O π(P|o). MLEπ is set-valued, as there may be several outcomes o∗ that maximize π(P|o∗ ). In this paper, we require all the conditional probabilities to be strictly positive, for technical reasons.

Under the model where outcomes are rankings, it has been shown that a neutral voting rule is an MLE for some noise model if and only if it is a neutral ranking scoring rule [5]. More generally, we define an outcome scoring rule rs∗ to be a voting rule defined by a scoring function s∗ : L(X ) × O → R, as follows: for any profile P, rs∗ (P ) = argmaxo∈O ∑V∈P s∗ (V, o). If O = L(X ), we obtain ranking scoring rules, and if O = X , we obtain candidate scoring rules. An outcome scoring rule is weakly neutral if for any pair of outcomes o and o′ , there exists a permutation M over X such that for any linear order V ∈ L(X ), we have s∗ (V, o) = s∗ (M (V ), o′ ).

2 The use of this independence structure is standard. Moreover, if conditional independence among votes is not required, then any voting rule can be represented by an MLE for some noise model [6], which trivializes the question.

3 MLEs and Pairwise Scoring Rules

We now move on to the contributions of this paper. We recall that the objective of this paper is to study noise models and the associated MLE voting rules for voting with partial orders. Ideally, in the special case where the profiles consist of linear orders, the MLE of such a noise model coincides with a commonly used voting rule. We will mainly study three types of outcome space: (1) an outcome is an alternative (O = X); (2) an outcome is a linear order (O = L(X )); and (3) an outcome is a subset of k alternatives (O = {S ⊆ X : |S| = k}).

The model that we are about to introduce is similar to Condorcet's noise model, but it is much more general, in terms of both the input profiles and the outcome space. For any outcome o ∈ O and any pair of alternatives ci, cj, let π(ci ≻ cj|o) denote the probability that ci ≻ cj in a vote given correct outcome o, and let π(ci ∼ cj |o) denote the probability that ci and cj are incomparable given correct outcome o. We have π(ci ≻ cj |o) + π(cj ≻ ci|o) + π(ci ∼ cj |o) = 1 because these events are disjoint and exhaustive.

We assume that conditional on the correct outcome o ∈ O, for any voter, all the pairwise comparisons are drawn independently according to the conditional probability distribution π(·|o). That is, for any partial order W over X and any pair of alternatives ci, cj (i ̸= j), we define:

Then, for any partial order W over X and any outcome o ∈ O, we let π(W|o) = ∏1≤i<j≤m π(Wci,cj |o) be the probability of W given correct outcome o. For any profile P = (W1, . . . ,Wn) of partial orders, we obtain that the probability of this profile given correct outcome o is π(P|o) = ∏nj=1 π(Wj|o) (using the standard assumption of independence across voters). We call such a noise model π a pairwiseindependent model. For any pairwise-independent model π and any profile P of partial orders, we let MLEπ(P ) = argmaxo∈O π(P |o). MLEπ is a voting rule defined over profiles of partial orders.

We say that a pairwise-independent model is weakly neutral if for any pair of outcomes o, o′ ∈ O, there exists a permutation M over X such that for any ci, cj ∈ X, π(ci ≻ cj|o) = π(M (ci) ≻ M (cj )|o′ ).

Next, we define pairwise scoring rules, which are voting rules defined by pairwise scoring functions. We introduce pairwise scoring rules mainly because they are defined in a similar way as ranking/candidate scoring rules [5], and the relationship between pairwise scoring rules and MLEs of pairwise independence models is similar to the relationship between ranking/candidate scoring rules and MLEs in the linearorders setting.

Definition 1 A pairwise scoring function is a function s : X × X × O → R, where for any c ∈ X and any o ∈ O, s(c, c, o) = 0. We overload s as follows. For any partial order W ∈ PO(X ) and any outcome o ∈ O, we let s(W, o) = ∑(ci,cj)∈W s(ci, cj, o). For any profile P = (W1, . . . ,Wn) of partial orders over X and any outcome o ∈ O, we let s(P, o) = ∑nj=1 s(Wj, o). The pairwise scoring rule rs over profiles of partial orders is defined by rs(P ) = arg maxo∈O s(P, o).

For notational convenience, we write s(c ≻ c′ , o) instead of s(c, c′ , o).

Definition 2 A pairwise scoring function s is weakly neutral if for any pair of outcomes o, o′ ∈ O, there exists a permutation M over X such that for any ci, cj ∈ X, s(ci ≻ cj, o) = s(M (ci) ≻ M (cj ), o′ ).

Theorem 1 A voting rule is a pairwise scoring rule with a weakly neutral pairwise scoring function if and only if it is the MLE of a weakly neutral pairwise-independent model.

Proof: For any weakly neutral pairwise-independent model π, we define a pairwise scoring function s as follows. For any o ∈ O and any pair of different alternatives (ci, cj), we let s(ci ≻ cj, o) = logπ(ci ≻ cj|o) - logπ(ci ∼ cj|o). It follows that for any partial order W, s(W, o) = ∑(ci,cj)∈W logπ(ci ≻ cj|o) - ∑(ci,cj)∈W logπ(ci ∼ cj|o) = ∑i<j logπ(Wci,cj |o) - ∑i<j logπ(ci ∼ cj|o) = log π(W |o) - ∑i<j logπ(ci ∼ cj|o). Because π is weakly neutral, for any pair of outcomes o, o′ ∈ O, ∑i<j logπ(ci ∼ cj|o) = ∑i<j logπ(ci ∼ cj|o′ ). Hence, argmaxo∈O π(P|o) = argmaxo∈O ∑j logπ(Wj|o) = arg maxo∈O ∑j s(Wj , o) = arg maxo∈O s(P, o). Therefore, rs is equivalent to MLEπ. It is easy to verify that s is weakly neutral (using the weak neutrality of π).

Conversely, let rs be a pairwise scoring rule, where s is weakly neutral. Let O = {o1, . . . , ot}. For any 2 ≤ h ≤ t, let Mh denote the permutation over X such that for any pair of different alternatives ci, cj, s(ci ≻ cj, o1) = s(Mh(ci) ≻ Mh(cj), oh). For any alternative c, let M1(c) = c. For any i < j ≤ m, we let bi,j be a constant such that 2s(ci≻cj ,o)+bi,j + 2s(cj≻ci,o)+bi,j + 2bi,j = 1. The existence of such a bi,j is guaranteed by the intermediate value theorem (when bi,j = ∞, the left-hand side is ∞ > 1, and when bi,j =

-∞, the left-hand side is 0 < 1). Now, we define a pairwiseindependent model π as follows: for any h ≤ t and any i < j, π(Mh(ci) ≻ Mh(cj)|oh) = 2s(Mh(ci)≻Mh(cj),oh)+bi,j , π(Mh(cj) ≻ Mh(ci)|oh) = 2s(Mh(cj)≻Mh(ci),oh)+bi,j , and π(Mh(ci) ∼ Mh(cj)|oh) = 2bi,j . Because s is weakly neutral, it follows that π is weakly neutral. We note that for any oh ∈ O and any partial order W, logπ(W|oh) = ∑i<j logπ(Wci,cj |o) = s(W, o) + ∑i<j bi,j, implying that MLEπ = rs. □

We now give some examples of pairwise scoring rules with weakly neutral scoring functions. The first family of pairwise scoring rules consists of extensions of Borda, and the second family consists of extensions of Kemeny.

Proposition 1 (Borda extensions) Let O = X and fix some a and b, with a > b and a ≥ 0 ≥ b. For any c ∈ O and any pair of alternatives ci, cj (i ̸= j), we define the weakly neutral pairwise scoring function as follows.

For any profile P of linear orders, rs(P ) = Borda(P ).

Proposition 2 (Kemeny extensions) Let O = L(X ) and fix some a and b, with a > b and a ≥ 0 ≥ b. For any l ∈ O and any pair of alternatives ci, cj (i ̸= j), we define the weakly neutral pairwise scoring function as follows.

For any profile P of linear orders, rs(P ) = Kemeny(P

While the various Borda extensions are indeed different from each other-for example, a candidate that is compared to others very often benefits if |a| > |b|-the Kemeny extensions in fact all correspond to the same rule. This is because the sum of the number of a's and the number of b's that l ∈ L(X ) receives does not depend on l: it is equal to the total number of pairwise comparisons made by voters.

4 Properties of Pairwise Scoring Rules

In this section, we study some basic properties of pairwise scoring rules. A voting rule is anonymous if it treats the voters symmetrically. A voting rule r is consistent if for any pair of profiles P1, P2 of partial orders, if r(P1) ∩ r(P2) ̸= ∅, then r(P1 ∪ P2) = r(P1) ∩ r(P2). For any profile P of partial orders, we define the generalized weighted majority graph (GWMG), denoted by GWMG(P ), as follows. GWMG(P ) is a directed graph whose vertices are the alternatives, and for each ordered pair of different alternatives ci, cj, there is an edge ci → cj whose weight wi,j is the proportion of agents voting ci ≻ cj in P. That is, wi,j = |{W ∈ P : ci ≻W cj}|/|P|. We say a voting rule r defined over profiles of partial orders is based on the GWMG if for any pair of profiles P1, P2 of partial orders such that |P1| = |P2| and GWMG(P1) = GWMG(P2), we have r(P1) = r(P2). GWMG-based voting rules over profiles of linear orders are defined similarly by requiring that both P1 and P2 are profiles of linear orders in the above definition. We note that any WMG-based voting rule (defined over profiles over linear orders) is GWMG-based. The following is straightforward to verify:

Proposition 3 Any pairwise scoring rule rs satisfies anonymity and consistency, and is based on GWMG.

The next proposition characterizes all pairwise scoring rules that, when we consider their restriction on profiles of linear orders, are based on the WMG.

Proposition 4 For any pairwise scoring rule rs, its restriction on profiles of linear orders is based on the WMG if and only if for any o1, o2 ∈ O, ∑i̸=j s(ci ≻ cj, o1) = ∑i̸=j s(ci ≻ cj , o2).

When the set of outcomes is the set of all alternatives, the next theorem characterizes all pairwise scoring rules whose restriction on profiles of linear orders is neutral.

Theorem 2 Let O = X. For any pairwise scoring rule rs, its restriction r′s on profiles of linear orders satisfies neutrality if and only if r′s is Borda.

Proof: By Proposition 3, rs satisfies anonymity and consistency. Therefore, r′s also satisfies anonymity and consistency. By Young's axiomatic characterization of positional scoring rules [25], a voting rule with O = X satisfies continuity (which is satisfied by all pairwise scoring rules), anonymity, neutrality, and consistency if and only if it is a positional scoring rule. Therefore, r′s is a positional scoring rule. Let (v1, . . . , vm) denote the scoring vector. It suffices to prove that for any 2 ≤ i′ ≤ m1, v1 - v2 = vi′ - vi′+1 (it should be noted that shifting the Borda score vector by a constant does not change the rule).

For the sake of contradiction, suppose that 2 ≤ i′ ≤ m is such that v1-v2 ̸= vi′ -vi′+1. We next derive a contradiction for the case where v1 -v2 > vi′ -vi′+1; the case where v1 - v2 < vi′ - vi′ +1 can be handled similarly. Let Mm-2 denote the cyclic permutation among {c3, . . . , cm}. That is, Mm-2 : c3 → c4 → · · · → cm → c3. For any permutation M and any natural number k, we let M k denote the permutation such that M k (x) = M (M k-1 (x)) (whereM 1 = M). Let M2 denote the cyclic permutation among {c1, c2}. Let V = [c1 ≻ c2 ≻ · · · ≻ cm]. We define a profile P1 as follows. P1 = (V,M2(V ),Mm-2(V ),Mm-2(M2(V )), . . . ,M m-3 m-2 (V ), M m-3 m-2 (M2(V ))). It follows that for any c ∈ X \ {c1, c2}, PS(P1, c1) = PS(P1, c2) > PS(P1, c), which means that r′s (P1) = {c1, c2} and s(P1, c1) = s(P1, c2) > s(P1, c).

Let V ′ be an arbitrary linear order where c1 is ranked in the i′ th position and c2 is ranked in the (i′ + 1)th position. Let P2 = (V,M2(V ), V ′ ,M2(V ′ )). We have PS(P2, c1) = PS(P2, c2). Hence, there exists a natural number k such that r′s (kP1 ∪ P2) = {c1, c2}, where kP1 represents a profile that is composed of k copies of the votes in P1. Let P ′2 = (V, V,M2(V ′ ),M2(V ′ )). Because v1 - v2 > vi′ - vi′ +1, PS(kP1 ∪ P ′2 , c1) > PS(kP1 ∪ P2, c1) = PS(kP1 ∪ P2, c2) > PS(kP1 ∪ P ′2, c2). Moreover, for any alternative c ∈ X \ {c1, c2}, we have PS(kP1 ∪ P ′2 , c1) > PS(kP1 ∪ P2, c1) > PS(kP1 ∪ P2, c) = PS(kP1 ∪ P ′2 , c). Hence, r′s(kP1 ∪ P ′2) = {c1}. However, because GWMG(kP1 ∪ P ′2) = GWMG(kP1∪P2) and rs is based on GWMG (Proposition 3), r′s (kP1 ∪P ′2 ) = r′s (kP1 ∪P2), which is a contradiction. □

We recall that Borda can indeed be represented as a pairwise scoring rule with a weakly neutral pairwise scoring function (Proposition 1), which means that it can be naturally extended to profiles of partial orders by our MLE approach. On the other hand, Theorem 2 suggests that, when O = X , no other neutral voting rules can be extended to profiles of partial orders by our MLE approach. (In Section 5, we will see an example where O ̸= X.) We note that there is other work on desirable and axiomatizing properties of Borda [10; 24].

We now investigate the relationship between pairwise scoring rules and outcome scoring rules (incl. ranking/candidate scoring rules).

Proposition 5 For any pairwise scoring rule rs, there exists a GWMG-based outcome scoring rule rs∗ such that for any profile P of linear orders, rs(P ) = rs∗ (P ). Moreover, if s is weakly neutral, then s∗ is also weakly neutral.

The next theorem states that any WMG-based outcome scoring rule rs∗ can be extended to a pairwise scoring rule rs. This is more difficult to prove.

Theorem 3 For any WMG-based outcome scoring rule rs∗ that satisfies non-imposition, there exists a pairwise scoring rule rs that is an extension of rs∗. Moreover, if s∗ is weakly neutral, then s is also weakly neutral.

Proof: Let O = {o1, . . . , ot}. For any linear order V , we let f(V ) = (0, s∗ (V, o2) - s∗ (V, o1), . . . , s∗ (V, ot) - s∗ (V, o1)). For any profile P of linear orders, we let f(P ) = ∑V ∈P f(V ). We first show the following claim whose proof is omitted.

Claim 1 For any profile P of linear orders, if the weight of every edge in WMG(P ) is zero, then f(P ) = ⃗0.

Next, for any pair of alternatives ci, cj (i ̸= j), we define the following two votes.

Here the alternatives in X \ {ci, cj} are ranked in an arbitrary way, and in rev(X \ {ci, cj}), the alternatives in X \ {ci, cj} are ranked in the reversed order. Let M-{i,j} denote the set of all permutations over X \ {ci, cj}. We note that |M-{i,j}| = (m2)!. Let Pi,j = {M (Vi,j ), M (V ′ i,j ) : M ∈ M-{i,j}}.

Next, we prove that for any linear order V , f(V ) = ∑ci≻V cj f(Pi,j)/(2(m2)!). Let P1 = ⋃ci≻V cj Pi,j . Let P2 = rev(P1). We note that the WMG of 2(m - 2)!V is the same as the WMG of P1, and the weight of each edge in the WMG of P1 ∪ P2 is 0. Using Claim 1, we obtain f(P1 ∪ P2) = f(P1) + f(P2) = ⃗0 and f({2(m - 2)!V } ∪ P2) = 2(m - 2)!f(V ) + f(P2) = ⃗0. Therefore, f (P1) = 2(m - 2)!f (V ).

For any h ≤ t, we let s(ci ≻ cj, oh) = s∗ (Pi,j , oh). It follows that f(V ) = ∑ci≻V cj f(Pi,j)/(2(m - 2)!) = ∑ci≻V cj [(s(ci ≻ cj, o1), s(ci ≻ cj, o2), . . . , s(ci ≻ cj , ot)) - s(ci ≻ cj, o1) · ⃗1]/(2(m - 2)!) = [(s(V, o1), s(V, o2), . . . , s(V, ot)) -s(V, o1) · ⃗1]/(2(m2)!). Therefore, for any h ≤ t and any linear order V , s∗ (V, oh) - s∗ (V, o1) = (s(V, oh) - s(V, o1))/(2(m - 2)!). Hence, for any profile P of linear orders and any h1, h2 ≤ t, s∗ (P, oh1 ) ≥ s∗ (P, oh2 ) if and only if s(P, oh1 ) ≥ s(P, oh2 ). It follows that rs is an extension of rs∗ .

Suppose s∗ is weakly neutral. Let M1, . . . ,Mt denote the permutations for the pairs of outcomes (o1, o1), (o1, o2), . . . , (o1, ot), respectively. For any i ̸= j and any h ≤ t, Mh(Pi,j ) = {Mh(M (Vi,j )), Mh(M (V ′ i,j )) : M ∈ M-{i,j}} = {M ′ (VMh(i),Mh(j)), M ′ (V ′Mh(i),Mh(j) ) : M ′ ∈ M-{Mh(i),Mh(j)}}= PMh(i),Mh(j). Therefore, s(Mh(ci) ≻ Mh(cj), oh) = 2(m - 2)!s∗ (PMh(i),Mh(j), oh) = 2(m - 2)!s∗ (Mh(Pi,j ), oh) = 2(m - 2)!s∗ (Pi,j , o1) = s(Pi,j , o1), which means that s is also weakly neutral. □

Putting Proposition 5 and Theorem 3 together, we obtain an almost complete characterization of the voting rules that can be extended to pairwise scoring rules. The necessary condition (Proposition 5) states that it must be an outcome scoring rule r that is based on the GWMG, and the sufficient condition (Theorem 3) states that if r is based on the WMG (and to satisfy non-imposition), then r can be extended to a pairwise scoring rule. How to close the gap between the GWMG condition and the WGM condition is left as an open question.

5 Selecting a Set of k Winning Alternatives

In this section, we propose a pairwise-independent probability model πk for the case where the outcome space is composed of all sets of k alternatives (for a given natural number k). For instance, perhaps our goal is to select k candidates to admit/hire based on partial orders given by a committee. We now present the MLE model πk formally. For any k ≤ m, let Ok = {S ⊆ X : |S| = k} denote the outcome space. The main idea behind this model is that, given one of the winners and one of the losers in the correct outcome, a voter is more likely to rank the former above the latter than vice versa.

Definition 3 Let 0 < ¯ p, p1, p2 < 1 and (1 - ¯ p)/2 < p < 1 - ¯ p. For any o ∈ Ok, the conditional probabilities in πk are defined as follows.

(a) For any pair of alternatives ci, cj such that ci, cj ∈ o, πk(ci ∼ cj|o) = p1 and πk(ci ≻ cj|o) = πk(cj ≻ ci|o) = (1 - p1)/2.

(b) For any pair of alternatives ci, cj such that ci, cj ∈ X \ o, πk(ci ∼ cj |o) = p2 and πk(ci ≻ cj |o) = πk(cj ≻ ci|o) = (1 - p2)/2.

By Theorem 1, MLEπk is a pairwise scoring rule rs whose scoring function is defined as follows. The base of all logarithms is 2.

We now define (the decision variant of) the problem of maximizing the likelihood under πk. In the LIKELIHOODEVALUATION problem (L-EVALUATION for short), we are given a natural number k, a positive number t, and a profile P consisting of partial orders; we are asked whether there exists o ∈ Ok such that πk(P |o) ≥ t.

Theorem 4 The L-EVALUATION problem is NP-complete.

Proof sketch: Given an outcome o and a profile P, it is straightforward to check that it takes polynomial time to compute πk(P|o). Therefore, L-EVALUATION is in NP. We prove NP-hardness by a reduction from the decision variant of MAXCUT, which is known to be NP-complete [11]. We are given an undirected graph G = (V, E) and a natural number t′ . We are asked whether there exists a partition of V into two sets, V1 and V2, such that the number of edges across V1 and V2 is at least t′ .

We construct an instance of L-EVALUATION as follows. Let V ′ be a set of dummy alternatives with |V ′ | = |V|. Let X = V ∪ V ′ and k = |V|. None of the dummy alternatives will ever be compared by a voter to another alternative; the point of these dummy alternatives is merely to make sure that any partition S1 ∪ S2 = V corresponds to a partition S ′1 ∪ S ′2 = V ∪V ′ such that |S ′1 | = |S ′2 | = |V| = k. In πk, let p1 = p2 = 1/3, ¯ p = 1/4, and p = 1/2.

For each undirected edge {ci, cj} ∈ E, we define two votes: Wi,j , which contains only one pairwise comparison, ci ≻ cj; and Wj,i, which contains only one pairwise comparison, cj ≻ ci. Let P be the profile that consists of all these votes Wi,j,Wj,i for all {ci, cj} ∈ E. Let C = (log 1/3)|P|(k(k - 1) + (m - k)(m - k - 1))/2 + (log1/4)|P|k(m- k), that is, C = ∑ci̸=cj logπ(ci ∼ cj|o) for any o ∈ Ok; let t = 2t′+C .

For any o ∈ Ok, let CUT(o) denote the number of edges in E across o and V \ o. We can show that the likelihood of o is 2 CUT(o)+C , which is at least t = 2t′+C if and only if CUT(o) ≥ t′-that is, if and only if (o ∩ V, V \ o) is a cut of V whose size is at least t′ . □

We can also show that choosing an outcome to maximize the log-likelihood is APX-hard and MAXSNP-hard, by a PTAS-reduction and an L-reduction, both from the MAX-CUT problem. The reductions are similar to the reduction in the proof of Theorem 4. It is also possible to give a simple integer program with binary variables for computing outcomes of MLEπk . We omit all this due to the space constraint.

6 Future Work

One direction for future research is to use these techniques in applications. The example from the introduction of committee members giving partial orders of Ph.D. applicants was not fictitious: with the help of an integer program solver, we have already used the extension of the Kemeny rule to partial orders (Proposition 2) to help us rank Ph.D. applicants to our department. There are also open technical questions. For example, what is the exact complexity of computing an arbitrary winning outcome under MLEπk ? (We conjecture it is ΘP2 -complete.) Can we close the gap between the WMG and GWMG conditions described at the end of Section 4? Do the voting rules proposed in this paper satisfy other properties for voting with partial orders [15]? Can we extend other classes of voting rules to partial orders, for example generalized scoring rules [22] or distance rationalizable models [9]?

Acknowledgements

Lirong Xia is supported by a James B. Duke Fellowship. We acknowledge NSF CAREER 0953756 and IIS-0812113, and an Alfred P. Sloan fellowship for support. We thank all IJCAI11 reviewers for their helpful comments and suggestions.