A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes

1 Introduction

Voting plays a key role for decision making in modern societies and multiagent systems. Classically, a vote one-to-one corresponds to a linear order of the given set of candidates. In many situations, however, only partial information about the voters' preferences is available. For instance, in multiagent systems the agents often must make a joint decision based on their individual preferences concerning a (potentially large) set of alternatives (synonymously, candidates). Sometimes, however, an agent has not enough information or time to provide a linear order on all alternatives and thus only may provide a partial ordering of the alternatives. Then, a vote corresponds to a partial order of the set of candidates. In this context, two central questions arise.

1. Given a set of partial orders, does a distinguished candidate c win for each extension of the partial orders into linear ones? This is the NECESSARY WINNER problem.
2. Given a set of partial orders, can a distinguished candidate c win for at least one extension of the partial orders into linear ones? This is the POSSIBLE WINNER problem.

In this paper, we focus on the POSSIBLE WINNER problem for several voting systems-in particular, we consider the common voting rules k-approval and, following Xia and

Susanne Hemmann

Institut f¨ur Informatik FSU Jena D-07743 Jena, Germany

Rolf Niedermeier

Institut f¨ur Informatik Friedrich-Schiller-Universit¨at Jena D-07743 Jena, Germany rolf.niedermeier@uni-jena.de

Conitzer [2008], Borda, Bucklin, Copeland, maximin, and ranked pairs. Some of our results also hold for broader classes of voting rules.

POSSIBLE WINNER is a well-studied problem [Konczak and Lang, 2005; Lang et al., 2007; Pini et al., 2007; Walsh, 2007; Xia and Conitzer, 2008]. Correcting Konczak and Lang [2005] claiming polynomial-time solvability for scoring rules, it has been recently shown that POSSIBLE WINNER is NP-complete for Borda, many other scoring rules, Bucklin, Copeland, maximin, and ranked pairs [Xia and Conitzer, 2008]. In contrast, NECESSARY WINNER is coNP-complete only for Copeland and ranked pairs but polynomial-time solvable for Bucklin, maximin, and scoring rules [Xia and Conitzer, 2008]. Interestingly, the NPcompleteness results for POSSIBLE WINNER even hold when there is only a constant number of candidate pairs per vote for which the relative order is open. In contrast, if the number of candidates is constant, then POSSIBLE WINNER can be solved in polynomial time provided that the voting rule can be executed in polynomial time [Walsh, 2007]. An extensively studied special case of POSSIBLE WINNER is "constructive manipulation" (see, e.g., [Conitzer et al., 2007]). Here, the given set of partial orders consists of two subsets; one subset contains linearly ordered votes and the other one completely unordered votes. Refer to [Walsh, 2007; Xia and Conitzer, 2008] for nice overviews.

The fundamental goal of parameterized algorithmics [Niedermeier, 2006] is to find out whether the seemingly unavoidable combinatorial explosion occurring in algorithms to solve NP-hard problems can be confined to certain problemspecific parameters. The idea is that when such a parameter has only small values in applications, then an algorithmwith a running time that is exponential exclusively with respect to the parameter may be efficient and practical. Formally, a given parameterized problem (I, p) with input instance I and parameter p is called fixed-parameter tractable (FPT) with respect to the parameter p if it can be solved within running time f(p) · |I|O(1) for some computable function f. In other words, the running time is polynomial for constant parameter values and the degree of the polynomial in the running time is independent of the parameter.

The statement that POSSIBLE WINNER can be solved in polynomial time when the number of candidates is bounded by a constant k [Walsh, 2007] is a starting point for our work.

The decisive question is how k influences the degree of the polynomial that upper-bounds the running time. In the stated polynomial-time algorithm, k determines the degree in the way "nk ", where n denotes the input size. Such algorithms become impractical even for modest values of k. We partially answer this question by showing that POSSIBLE WINNER is fixed-parameter tractable with respect to the parameter k (number of candidates) for all of the above mentioned voting rules. Moreover, we initiate a broader algorithmic study of POSSIBLE WINNER by pursuing a multivariate complexity analysis based on further parameterizations. More specifically, we additionally analyze how the parameters "number of votes" and "total number of undetermined pairs" influence the problem complexity. We achieve (parameterized) intractability results in the first case and fixed-parameter tractability results in the second case. More precisely, first we prove that POSSIBLE WINNER for Borda, Bucklin, and k-approval remains NP-complete even in case of a constant number of votes (which excludes any hope for fixed-parameter tractability with respect to this parameter). Second, we prove that with respect to the parameter "total number of undetermined pairs" POSSIBLE WINNER becomes fixed-parameter tractable for all voting rules where in case of linearly ordered votes the winner can be determined in polynomial time. For the special case Borda, we further identify an interesting special case that is solvable in polynomial time and that can be used to improve the running time of the fixed-parameter algorithm.

Due to the lack of space, several details had to be deferred to a full version of the paper.

Preliminaries. Let C = {c1, . . . , cm} be the set of candidates. Classically, a vote is a linear order (a transitive, antisymmetric, and total relation) on C. An n-voter profile P on C consists of n votes on C. The set of all profiles on C is denoted by P (C).

A voting rule r is a function from P(C) to 2C ; the resulting image set is called the set of co-winners. Throughout this paper we cast our proofs for the case of uniquely determined co-winners (that is, one-element co-winner sets), just referring to these as winners. All our results hold for the cowinner case as well.

The most frequently used voting rules in this work are Borda and k-approval. Both are (positional) scoring rules. Scoring rules are defined by scoring vectors (α0, α1, . . . , αm-1) with integers α0 ≥ α1 ≥ · · · ≥ αm-1 ≥ 0. More specifically, a scoring rule r consists of a sequence of scoring vectors s1, s2, . . . such that for any i ∈ there is a scoring vector for i candidates. For a vote v and a candidate c ∈ C, let the score s(v, c) := αj where j is the number of candidates that are better than c in v. For any profile P = {v1, . . . , vn}, let s(P, c) := ∑ni=1 s(vi, c). A scoring rule will output c as a co-winner if it maximizes s(P, c). For example, the following three voting rules with their corresponding scoring vectors are common: H11934

• plurality with (1, 0, . . . ),
• Borda with (m - 1, m- 2, . . . , 0), and
• k-approval with (1, 1, 1, . . . , 0, 0) starting with k 1's.

Due to the lack of space, we refer to [Xia and Conitzer, 2008] for the definitions and an overview of the other voting systems studied in this work.

A partial order is a transitive, antisymmetric, and reflexive relation. Sometimes, a partial order specifies a whole subset of candidates, e.g., e ≻ D. This notation means that e ≻ d for all d ∈ D and there is no specified order among the candidates in D. A linear order V extends a partial order O if O ⊆ V , that is, for any i, j ≤ m, one has ci ≻O cj ⇒ ci ≻V cj. For a voting rule r and a profile of partial orders PO = (O1, . . . ,On) on C, a candidate c ∈ C is a possible winner if there exists a P = (V1, . . . , Vn) such that, for each i, Vi extends Oi into a linear order and c ∈ r(P ).

POSSIBLE WINNER

Input: A voting rule r, a set of candidates C, a profile of partial orders PO = (O1, . . . , On) on C, and a distinguished candidate c ∈ C.

Question: Is there an extension profile P = (V1, . . . , Vn) where Vi extends Oi for all 1 ≤ i ≤ n and c ∈ r(P)?

2 Number of candidates

To assess the parameterized complexity with respect to the parameter "number of candidates", we employ Lenstra's famous algorithm for bounded-variable-cardinality integer linear programming (see [Niedermeier, 2006, Chapter 11]) which has shown usefulness for proving fixed-parameter tractability for control in elections as well [Faliszewski et al., 2007]. Lenstra's result says that it is fixed-parameter tractable with respect to the number of variables to check whether all inequalities of an integer linear program can be fulfilled at the same time (the so-called feasibility problem). By expressing POSSIBLE WINNER as the feasibility problem for an integer linear program with a number of variables bounded by a function solely depending on the parameter "number of candidates", one can obtain the following.

Theorem 1. For all positional scoring rules, Bucklin, Copeland, ranked pairs, and maximin POSSIBLE WINNER is fixed-parameter tractable with respect to the parameter "number of candidates".

3 Number of votes

A well-studied scenario in voting systems is constructive manipulation with a bounded number of unspecified votes, that is, bounded coalition size [Faliszewski et al., 2008; Xia et al., 2008]. Since constructive manipulation is a special case of POSSIBLE WINNER, this motivates the consideration of the parameter "number of partial votes". An overview of results for this parameterization is given in Table 1. In the following, we show the NP-completeness of POSSIBLE WINNER for a constant total number of votes for k-approval, Bucklin, and Borda.

k-approval. The NP-complete INDEPENDENT SET (IS) problem asks, given an undirected graph G = (V,E) and a positive integer t, whether there is a size-t vertex subset V ′ ⊆ V such that there is no edge between any two vertices of V ′ .

Theorem 2. For k-approval, POSSIBLE WINNER is NPcomplete for a partial profile that consists of two partial orders when k is part of the input.

Proof. (Sketch) We give a many-one reduction from INDEPENDENT SET to POSSIBLE WINNER for k-approval. Given an IS-instance ((V,E), t) with V = {v1, . . . , vn}, we construct a 2-voter partial profile PO over a set of candidates C in which the distinguished candidate c ∈ C is a possible winner according to k-approval with k := |n+(n2 )+|E|-tn+( t2)+1| iff (G, t) is a yes-instance. The set of candidates is C := CV ⊎ CE ⊎ {c} ⊎ D with a candidate for every vertex, that is, CV := {ci | vi ∈ V }, and candidates that are related to pairs of vertices, that is, for 1 ≤ i < j ≤ n, if {vi, vj} ∈ E, then there are two candidates eij and e′ij in CE; otherwise, there is one candidate eij in CE. Further, D consists of |d| dummy candidates with d := n-t+ (n2 ) +|E|-tn+ ( t2). In the following, we describe the construction for the case that d ≥ 0. The case d < 0 can be handled similarly. The two partial orders O1 and O2 of PO are specified as follows:

O1 : c ≻ D ≻ CV ≻ CE. O2 : c ≻ CV ∪CE ≻D, and for 1 ≤ i < j ≤ n, if {vi, vj} ∈ E, then ci ≻ eij and cj ≻ e′ij ; otherwise, ci ≻ eij and cj ≻ eij.

The distinguished candidate c has a total score of two. If there is an extension in which all other candidates have a total score of at most one, then c is a possible winner. This is equivalent to the demand that every other candidate must assume at least one "zero-position". Since we have 1+|CV |+|CE|+ |D| = 1+n+(n2 )+|E|+n-t+(n2 )+|E|-tn+(t2) candidates and consider k-approval with k = n+(n2 )+|E|-tn+(t2)+1, there are (n2 ) + |E| + n - t zero-positions per vote.

In O1, the candidates of CE are beaten by all other candidates, and thus assume zero-positions in every extension. Hence, |CE| = (n2 )+|E| zero-positions are already occupied. The remaining n - t zero-positions can only be assigned to candidates of CV . In an extension in which c wins, those t candidates from CV with a one-position in O1 must assume a zero-position in O2. According to the definition of O2, every candidate from CV is placed before n - 1 candidates from CE. Hence, placing a candidate from CV at a zeroposition in O2 implies that n - 1 candidates from CE must also assume zero-positions. Since every candidate of CE has a zero-position in O1, assigning zero-positions to candidates from CE in an extension of O2 is not necessary to make c the possible winner. The basic idea of the construction is that two candidates ci, cj ∈ CV that assume zero-positions in O2 can "share" a candidate from CE if {vi, vj} /∈ E. In this case, both candidates enforce a zero-position for the same candidate eij whereas otherwise the two candidates eij and e′ij must assume zero-positions. As we argue in the following, the construction ensures that for no pair of "selected" candidates from CV there are two corresponding candidates from CE that are forced to a zero-position. Otherwise, the number of remaining zero-positions would not be sufficient for the selected candidates from CV and c would not win.

Since all candidates fromD assume zero-positions in O2, it is easy to verify that there are exactly tn- ( t2) zero-positions left over (and c beats all candidates of D). Now, suppose that the candidates fromCV that must assume a zero-position in O2 correspond to an independent set. Then, the number of candidates of CE that are forced to assume a zero-position is t · (n - 1) minus the number of candidates that are counted twice. For all pairs of candidates that correspond to nonadjacent vertices a candidate of CE is counted twice. Since the t candidates correspond to an independent set, there are ( t2) such candidates and the number of zero-positions is sufficient. Hence, extending O2 by placing the CV -candidates that correspond to an independent set (and all "enforced" candidates) to zero-positions and extending O1 by placing the remaining candidates of CV to zero-positions yields an extension in which c is the winner.

We omit the argument for the reverse direction.

Bucklin. The Bucklin score of a candidate is the smallest position s such that the candidate takes position s or smaller in more than half of the votes. The candidate with the smallest Bucklin score wins. The reduction from IS used in Theorem 2 for k-approval can be adapted to work for Bucklin. We sketch the basic idea: Additionally to the two partial orders, the modified profile contains three linear orders ensuring the following. The Bucklin score of the distinguished candidate is set to a certain value s. All other candidates have Bucklin score at most s if they do not assume a position greater than s in one of the partial votes, and have Bucklin score higher than s, otherwise. Now, a position higher than s is equivalent to a "zero-position", that is a position greater than k, in the proof of Theorem 2. Hence, one can argue in analogy to there. Regarding the construction of the linear votes, the Bucklin score of the distinguished candidate can be fixed by setting it to position s in all three linear votes. All other candidates are set to a position smaller than s in one of the linear orders and to a position higher than s in the two other linear orders. This idea can be used to show the following.

Theorem 3. For Bucklin, POSSIBLE WINNER is NPcomplete for a partial profile consisting of two partial and three linear orders.

Borda. The 3-PARTITION problem is defined as follows. Given a multi-set A = {a1, . . . , an} of positive integers and B := (3/n) · ∑ai∈A ai, it asks whether there is a partition of A into size-3 subsets A1, . . . ,An/3 such that ∑ai∈Aj ai = B for all j ∈ {1, . . . , n/3}. The 3-PARTITION problem is strongly NP-complete [Garey and Johnson, 1979].

Informally, this means that the NP-hardness still holds when the integers of A have values polynomially bounded in n. We denote the special case that each integer ai ∈ A must be a multiple of n as 3-n-PARTITION. It is not hard to verify that the 3-n-PARTITION problem is strongly NP-hard since every 3-PARTITION instance can be reduced to 3-n-PARTITION by multiplying all input integers with n.

Theorem 4. For Borda, POSSIBLE WINNER is NP-complete for a partial profile consisting of three partial and three linear orders.

Proof. Let A = {a1, . . . , an} denote a 3-n-PARTITION instance with B := (3/n) · ∑ai∈A ai. To ease the presentation, we assume that ai < ai+1 for i = 1, . . . , n - 1 and a1 = n. It is not hard to modify the following manyone reduction to work for general instances. We construct a partial profile PO over a set C of candidates in which the distinguished candidate c ∈ C can become a winner iff A is a yes-instance for 3-n-PARTITION. The set of candidates is C := {c} ⊎ E ⊎ T ⊎ D, with one candidate for every member of A, that is, E := {ei | ai ∈ A}, candidates representing the subsets resulting from the partition into 3sets, that is T := {t1, . . . , tn/3}, and a set of dummy candidates D := ⊎ni=1 Di only needed to "fill" positions (specified later). The partial profile PO consists of three linear orders and three identical partial orders. Every partial order Oq, q ∈ {1, 2, 3}, of PO is given by c ≻ T and

with |D1| = a1 - 1 and |Di| = ai - ai-1 - 1 for i ∈ {2, . . . , n}. This definition fixes the number of dummy candidates; more precisely, |D| = ∑Di∈D |Di| = a1 - 1 + ∑ni=2 (ai - ai-1 - 1) = an - n. Thus, the total number of candidates is m = 1+|E|+|T |+|D| = 1+n+n/3+an-n = an+n/3+1. Since 3-n-PARTITION is strongly NP-complete, we can assume that an and, thus, m is polynomial in n. This also allows that the integers from A are presented by the candidates as follows. For every candidate ei ∈ E, there are exactly ai - 1 candidates s ∈ D ∪ E with c ≻ s and s ≻ ei in Oq, q ∈ {1, 2, 3}. Further, note that the position and thus the total score of the distinguished candidate c is already fixed. In contrast, every subset candidate tj ∈ T can be "inserted" at any position behind c in the three partial votes. The basic idea of this construction is that the "choice" of the positions for tj in the three partial orders corresponds to the choice of three numbers from A into the corresponding subset Aj. For example, inserting tj directly before the candidate ei in one of the partial votes means that ai ∈ Aj . More specifically, we would like to ensure the following two points for every possible extension in which c wins:

1. Every number of A is selected exactly once, that is, for every candidate ei ∈ E\{e1} there is exactly one candidate tj ∈ T with ei-1 ≻ tj and tj ≻ ei in one of the three partial votes, and one candidate tj ∈ T with tj ≻ e1.

2. For all tj ∈ T , the sum corresponding to the three "number candidates" fromE selected by tj is B.

The two points can be realized by setting the linear orders of PO appropriately. To this end, for c′ ∈ C\{c} let the maximum partial score smax p (c′ ) denote the maximum score that c′ may get within the three partial votes without beating c. Then, it is not hard to construct three linear orders of PO such that the following conditions hold. (We defer the description of the linear orders to the full version of this work.)

• smax p (ei) = 3(m-1) -3ai - i for all ei ∈ E,
• smax p (tj) = 3(m-1) -B for all tj ∈ T , and
• smax p (d) ≥ 3m for all d ∈ D.

By construction, c will make 3(m-1) points in any extension. Hence, the last condition implies that a candidate d ∈ D can never beat c. Further, every ei ∈ E must "loose" at least 3ai + i points against c and every tj ∈ T must loose at least B points against c.

Now, we show that there is a solution for 3-n-PARTITION iff there is an extension of PO such that c wins.

"⇒" Let {A1, . . . ,An/3} with Aj = {aj1 , aj2 , aj3 } denote a solution of 3-n-PARTITION for A. Then, extend Oq, q ∈ {1, 2, 3}, such that tj ≻ ejq and Djq ≻ tj. This extension is unambiguous since all ajq ∈ A are pairwise distinct. As explained before, in every partial vote, for every ei ∈ E, there are exactly ai - 1 candidates s ∈ D ∪ E with c ≻ s and s ≻ ei. Thus, without inserting any tj ∈ T before ei, ei "looses" 3ai points against c. For q ∈ {1, 2, 3}, let τi,q denote the number of candidates from T that are inserted before ei to extend Oq. Then, for every ei, we have τi,1 + τi,2 + τi,3 = i since for all z ≤ i a candidate from T is inserted directly before ez in one of the three partial votes. Thus, ei looses 3ai + i points in this extension and c beats ei. It remains to show that c beats tj. Since aj1 + aj2 + aj3 = B, due to the construction the number of candidates that are "better" than tj in the three partial votes is at least |{s ∈ (D ∪ E) : s ≻O1 ej1 }| + |{s ∈ (D ∪ E) : s ≻O2 ej2 }| + |{s ∈ (D∪E) : s ≻O3 ej3 }| = B-3. Thus, smax p (tj) ≤ 3(m-1) -B and c will beat tj.

"⇐" Let V1, V2, V3 denote an extension of PO in which c is a winner. As explained before, without inserting any ti ∈ T before ei, ei "looses" 3ai points against c. Hence, ei must loose further i points. This can only be achieved by inserting candidates of T . Hence, at least i times a candidate of T must be inserted before ei, that is, ti1 + ti2 + ti3 ≥ i. We denote this as property (I). In the following, we show first that for a candidate tj ∈ T that selects ej1 , ej2 , ej3 , one must have ∑3q=1 ajq = B and, second that every ei ∈ E, that is, every number of A, is selected exactly once.

First, we show by contradiction that for a candidate tj ∈ T that selects ej1 , ej2 , ej3 , one can neither have ∑3q=1 ajq < B nor ∑3q=1 ajq > B. Assume that there is a tj with ∑3q=1 ajq < B. Then, the minimum number of points that tj will make in any extension is as follows: In Vq, q ∈ {1, 2, 3}, there are at most ajq - 1 candidates of D ∪ E with d > tj. Thus, tj can loose at most ∑3q=1 ajq points by candidates from D ∪ E. Since |T| = n/3, in every partial vote at most n/3 - 1 candidates of T can be inserted before tj. Thus, the score of tj in V1, V2, V3 is at least 3(m - 1) - ∑3q=1 ajq - n + 3. By assumption, ∑3q=1 ajq < B and since all ajq ∈ A are multiples of n,

∑3q=1 ajq ≤ B - n. Then, in total tj will make at least 3(m - 1) - B + n - n + 3 = 3(m - 1) - B + 3 > smax p (tj) points in the partial votes, and tj thus beats c.

Now, assume that there is a tj with ∑3q=1 ajq > B. We consider the amount of points all remaining candidates of T\{tj} together can loose against c by candidates fromD∪E. Recall that i candidates of T must be inserted before any ei (property (I)). Clearly, inserting all candidates as far right as possible maximizes the amount of points the candidates of T\{tj} can loose. Due to property (I) this amount is at most ∑ni=1 ai - ∑3q=1 ajq = (n/3) · B - ∑3q=1 ajq < (n/3 - 1) · B. Further, this amount can be "contributed" to the candidates only in multiples of n since ai differs from aj at least by n. Then at least one candidate t ∈ T\{tj} can only loose less than the average amount of points. More precisely, t must loose less than B points and, thus, can loose at most B-n points by candidates fromD∪E. Again, we have that t can loose at most n - 3 additional points by inserting candidates of T . Thus, the minimum score that t will make in V1, V2, and V3 is 3(m- 1) -B + n - n + 3 > smax p (t) and t will beat c.

Second, it remains to show that every number in A is selected exactly once. We cannot select en twice without violating property (I). For i < n, assume that a candidate ei is selected twice. Due to property (I), we must have selected at least i + 1 candidates corresponding to as, s ≤ i < n. Hence, in total, the sum of the numbers corresponding to the selected candidates is at most ∑is=1 ai + ai + ∑ns=i+2 ai < ∑ns=1 ai = (n/3)·B. Since we have shown before that every candidate tj selects candidates that sum up exactly to B and we have |T | = n/3, this is a contradiction.

Summarizing, in any extension where c wins, the selected candidates of T correspond to a solution for 3-n-PARTITION.

4 Total number of undetermined pairs

Xia and Conitzer [2008] showed for five common voting rules that the POSSIBLE WINNER problem is NP-complete even if each partial order only contains a constant number of undetermined pairs of candidates. As a consequence, there is no hope for showing fixed-parameter tractability with respect to this parameter. To chart the border of tractability, we consider the parameter k denoting the "total number of undetermined pairs". More precisely, let PO be a partial profile over C. For O ∈ PO, let u(O) denote the number of undetermined pairs in O, that is, u(O) := |{{c1, c2} ∈ C : (c1 ≻ c2) /∈ O and (c2 ≻ c1) /∈ O}|. Then, k := ∑O∈PO u(O).

A general search tree approach. Consider a partial order where the candidates c1 and c2 form an undetermined pair. To extend this partial order into a linear order, one has to decide whether either c1 ≻ c2 or c2 ≻ c1. Clearly, it may happen that not each of these options is compatible with already fixed pairwise rankings within the given partial orders. Then, this option can be discarded. However, in the worst case, one faces a branching into two valid cases, in each branch decreasing the parameter denoting the total number of undetermined pairs by one. Clearly, this yields a search tree of size O(2k ). For an arbitrary voting rule r, let fr(n,m) denote the running time needed to compute a winner when given linear orders. Then, for every leaf one can check whether c is a winner for the corresponding extension in fr(n,m) time, giving the following theorem.

Theorem 5. For a partial n-voter profile over m candidates and a voting rule r, POSSIBLE WINNER can be decided in O(2k · (m + fr(n,m)) + nm2 ) time, where k denotes the total number of undetermined pairs.

Theorem 5 is based on a pure worst-case analysis. Significant practical improvements are conceivable. For instance, it is promising to select the order in which the undetermined pairs are processed in a more clever way. Subsequently, for the Borda rule we demonstrate that a provable improvement over the straightforward search tree size of O(2k ) is possible by using a refined search strategy.

An improved search tree for Borda's rule. A central observation concerning Borda for getting a search tree asymptotically smaller than O(2k ) lies in the detection of a polynomialtime solvable special case. To this end, for a partial order O, we define an isolated undetermined pair of candidates to be an undetermined pair where both candidates do not form an undetermined pair in O with any other candidate.

Theorem 6. For k being the total number of undetermined pairs, in case of Borda POSSIBLE WINNER can be decided in O(nm2 + k2 ) time if all undetermined pairs are isolated.

Proof. If the distinguished candidate c is contained in an undetermined pair, then, in the linear order, c is always placed in front of the second candidate of the pair. After that, one can assume that none of the undetermined pairs contains c. For an isolated undetermined pair {c1, c2} of candidates, the relative order of c1 and c2 with respect to all other candidates is already determined. More precisely, it is not hard to see that c1 and c2 must have the same relative order with respect to each of the remaining candidates, and, thus, they must be direct neighbors in the final linear order. Then, their scores in this final order will differ by exactly one point. Thus, for every candidate c′ ̸= c being in at least one undetermined pair, one can compute the minimum number of points l(c′ ) that c′ will make in every possible extension. That is, l(c′ ) is the sum over the scores for c′ obtained by choosing c′′ ≻ c′ in all undetermined pairs {c′ , c′′ } that contain c′ . Note that the score s(c) for the distinguished candidate c is already fixed. Clearly, if l(c′ ) ≥ s(c) for some c′ , then c cannot become possible winner. Otherwise, let b(c′ ) := s(c) - l(c′ ) - 1 ≥ 0 denote the balance of c′ with respect to c. The balance counts the number of partial orders where c′ may be placed better than the other candidate in an undetermined pair without defeating c.

Using the balance b(c′ ) for all candidates c′ ∈ C\{c}, one can decide POSSIBLE WINNER with the help of a maximum flow computation as follows. Consider a four-level directed, arc-weighted s-t-network with distinguished vertices s and t (see Figure 1). The first level only consists of vertex s. The second level consists of vertices one-to-one representing all undetermined pairs. Note that the same two candidates may induce more than one undetermined pair because they may occur in more than one partial order. The vertex s is connected by arcs of weight one to all level-two vertices. The third level of vertices one-to-one represents all candidates occurring in at least one undetermined pair. Every level-two vertex representing an undetermined pair is connected by two weight-one arcs to the two vertices corresponding to the two candidates contained in the undetermined pair. The fourth level only consists of vertex t. Every level-three vertex representing a candidate c′ is connected by one arc to t which is assigned the weight b(c′ ).

The central claim now is as follows (proof omitted): The constructed flow network allows for an integer flow of value k iff the distinguished candidate c is a possible winner of the corresponding Borda instance with k undetermined pairs.

Altogether, we arrive at the overall running time O(nm2 + k2 ). To this end, note that the flow network can be constructed in O(nm2 ) time. Further, the number of arcs of the flow network is linear in k. The Ford-Fulkerson algorithm can compute a maximum integer flow in O(|A| · f) time, where |A| denotes the number of arcs and f denotes the value of a maximum flow. Since the value of the maximum flow is bounded by k, the claimed running time follows.

The basic idea for an improved search tree algorithm for Borda in the general case is as follows. Three candidates {c1, c2, c3} ⊆ C form an undetermined triple with respect to some partial order O ∈ PO if there are at least two undetermined pairs in O, each formed by two candidates from {c1, c2, c3}. Now, one branches on undetermined triples instead of undetermined pairs. This leads to a search tree of size 1.82k . Once there are no more undetermined triples, then one can show that all remaining undetermined pairs must be isolated. Hence, in the leaves of the refined search tree the algorithm from Theorem 6 can be applied.

Theorem 7. For the Borda rule, POSSIBLE WINNER can be decided in O(1.82k (nm2 + k2 )) time, where k denotes the total number of undetermined pairs.

5 Conclusion

With our multivariate complexity analysis for the POSSIBLE WINNER problem we complement previous work [Walsh, 2007; Xia and Conitzer, 2008]. We studied parameterizations based on the number of candidates, the number of votes, and the total number of undetermined candidate pairs. It is conceivable that further parameterizations are worth investigation. Moreover, whereas we only dealt with two-dimensional (that is, one parameter at a time) complexity analysis, it also seems prospective to study the dependence on parameter pairs (three-dimensional) or even higher-dimensional parameterizations. All our results also hold for the possible co-winner case. We conclude with a few concrete challenges for future work: Make the fixed-parameter tractability results from Section 2 more practical by replacing integer linear programming with combinatorial algorithms. Concerning the efficient enumeration of extensions, study in how many of all possible extensions a distinguished candidate is a winner. Consider the case where one does not allow all possible extensions of partial orders but restricts these to "CP-nets", see [Xia and Conitzer, 2008].