Even More Effort Towards Improved Bounds and Fixed-Parameter Tractability for Multiwinner Rules

1 Introduction

Given the numerous applications of multiwinner voting, the research on multiwinner elections is quite dense by now [Faliszewski et al., 2017b]. In such elections there is a set of m candidates, a set of n voters, and an integer k, and the task of a multiwinner voting rule is to aggregate the preferences of the voters and identify a committee, namely a set of k candidates. In particular, much research has been done on designing multiwinner voting rules, including offering various general classes of such rules.

One particularly popular class of multiwinner voting rules is the class of Committee Scoring Rules (CSRs) [Elkind et al., 2017; Faliszewski et al., 2018; Faliszewski et al., 2019]. This class of multiwinner voting rules is very rich and contains a variety of voting rules; see, e.g., [Faliszewski et al., 2017a].

Much of the research is concentrated on the computational complexity of computing winners under various multiwinner voting rules (including under various CSRs), because for many applications it is crucial to be able to efficiently compute exact winners. As might be expected, computing winners under some CSRs can be done in polynomial-time (e.g., k-Borda [Faliszewski et al., 2017b]), while for others the corresponding decision problem is NP-hard.

As with other NP-hard problems, it is natural to aim at circumventing the computational intractability of those CSRs for which winner determination is NP-hard. Such endeavors have led to applying the framework of parameterized complexity by identifying parameters that allow for exact algorithms that are efficient whenever those parameters are small. Some of the commonly studied parameters are the committee size k and the number of voters, n. Indeed, this line of research has proven to be rather successful (see, e.g., [Bredereck et al., 2017; Bredereck et al., 2020; Faliszewski et al., 2017a; Faliszewski et al., 2019; Faliszewski et al., 2018; Aziz et al., 2018; Betzler et al., 2013; Betzler et al., 2012; Faliszewski et al., 2017c; Yang and Wang, 2018; Zhou et al., 2019; Liu and Guo, 2016; Aziz et al., 2014; Misra et al., 2015]). In this article, we further advance this line of research.

Before we describe our specific contributions, we first provide some preliminaries regarding multiwinner elections, concentrating on CSRs, OWA rules, and the specific rules we consider in this paper, and parameterized complexity.

1.1 Multiwinner Elections

An ordinal multiwinner election consists of a set of m candidates, a set of n voters, each providing a linear order over the candidates, and an integer k. The goal of a multiwinner voting rule is, given a multiwnner election, to output a set of k candidates, referred to as a winning committee. 1

An important class of multiwinner voting rules is the class of Committee Scoring Rules (CSRs). These rules operate by defining the satisfaction of a voter from a committee as a function that considers only the positions of the committee in the ranking (or preference list) of the voter. In particular, for a voter v, let posv(c) denote the position of candidate c in the ranking of v; e.g., if v : a ≻ b ≻ c ≻ d then posv(b) = 2, as b is ranked second by v. Then, given a voter v and a committee S, it implies a position vector, denoted by posv(S), which is a sorted vector of the positions of the candidates in the committee, in the ranking of v; e.g., if v : a ≻ b ≻ c ≻ d, then the position vector of the committee {c, b} is [2, 3], as b is ranked second by v and c is ranked third. Now, a committee scoring function, f, is a function that takes a position vector and outputs a score (equivalently, a satisfaction value). Formally, f : {0, . . . ,m-1}k →Z≥0.

1 Indeed, there might be several co-winning committees; we ignore such issues of tie-breaking here as they only clutter the technical presentation.

Some scoring functions that we will use throughout the paper are described next:

• Median scoring function: Given a value of λ ≤ k, the median scoring function is defined to be f(p1, . . . , pk) = m- pλ. That is, it is the Borda score of the committee member ranked λ by the corresponding voter. E.g., for λ = 1, the satisfaction of a voter v : a ≻ b ≻ c ≻ d from a committee {b, c}, by the median scoring function, would be 2, as b is the committee member ranked the highest by v among all committee members, and it is ranked second by v. Similarly, for λ = 2, the satisfaction of v would be 1, as c is the second highest committee member of v.
• Best scoring function: Given a value of λ ≤ k, the best scoring function is defined to be f(p1, . . . , pk) = ∑i∈[λ] (m-pi). That is, it is the sumof the Borda scores of the committee member ranked in first λ positions by the corresponding voter. E.g., for λ = 2, the satisfaction of a voter v : a ≻ b ≻ c ≻ d from a committee {b, c, d}, by the best scoring function, would be 3.

We wish to mention here that these scoring functions are referred as λ-median and λ-mean in the literature [Skowron et al., 2016]. Note that such terminology fixes the value of λ, however we allow λ to be even function of k, e.g., when λ = k, k-mean is same as k-Borda and k-median is same as Pessimist. So to avoid such inconsistencies we consider λ as a part of the input.

Given some specific committee scoring function f , one can define various voting rules; two natural possibilities are to consider the voting rule that aims at finding a committee that maximizes the sum (over the voters) of the satisfaction from the committee [Skowron et al., 2016], and the voting rule that aims at finding a committee that maximizes the min (over the voters) of the satisfaction from the committee [Aziz et al., 2018]. Formally, we have the following:

• Given a committee scoring function f, by UTILf we refer to the voting rule that selects the committee that maximizes the sum of voter satisfaction; i.e., UTILf selects argmaxS ∑v∈V f(posv(S)).
• Given a committee scoring function f, by EGALf we refer to the voting rule that selects the committee that maximizes the satisfaction of the least satisfied voter; i.e., EGALf selects argmaxS minv∈V f(posv(S)). The study of egalitarian committee scoring rules was initiated by Aziz et al. [2018] and remained unstudied for various scoring functions so far.

When f is a median scoring function and λ = 1, the voting rule UTILf is the prominent multiwinner voting rule Chamberlin Courant (CC), which was proposed by Chamberlin and Courant [1983]. For λ = k under the same scoring function, the voting rule UTILf is known as Pessimist. For median scoring function f, we call the voting rule EGALf as Egalitarian-Median, and for the best scoring function, we call it as Egalitarian-Best.

Throughout the paper, we use βv(c) to denote the Borda score of the candidate c from the voter v, and Borda(X, c) to denote ∑v∈X βv(c), the sum of the Borda scores of the candidate c from the voters in X. For a set X, we use 〈X〉 to denote an arbitrary ordering of X.

1.2 Parameterized Complexity

A central notion in parameterized complexity is fixedparameter tractability (FPT), which means, for a given instance (x, k), decidability in time f(k) · poly(|x|), where f(·) is an arbitrary computable function and poly(·) is a polynomial function. However, all problems are not FPT. Contrastingly, W[1] or W[2]-hardness captures the intractability in parameterized complexity. We refer the reader to books [Downey and Fellows, 2013; Cygan et al., 2015; Niedermeier, 2006].

1.3 Our Contributions

Here, we list our contributions, Table 1 summarizes our results. The notation O⋆ (f(k)) suppresses poly(n,m) factors.

• For the voting rule CC, we give an algorithm that runs in O⋆ (2n ) time, and this exponential dependence on n is optimal (assuming Set Cover Conjecture). This is an improvement over known O⋆ (nn )-time algorithm proposed by Betzler et al. [Betzler et al., 2013].
• For the voting rule Pessimist, we show that it is W[1]-hard wrt. k and XP wrt. n (i.e., polynomial time solvable for constant number of voters). The NP-hardness of Pessimist was established in [Skowron et al., 2016], however the same reduction does not give W-hardness.
• For the voting rule Egalitarian-Median, we have following:
• We first show that it is NP-hard for all the values of λ < k. Note that for λ = 1, the problem is known as Egalitarian-CC [Aziz et al., 2018] and also referred as MiniMax CC [Betzler et al., 2013], for which NPhardness, W[2]-hardness wrt. k, and an O⋆ (nn )-time algorithm was established by Betzler et al. [Betzler et al., 2013]. For λ = k, the problem is known as Egalitarian Pessimist which is known to be polynomial time solvable [Aziz et al., 2018].
• Next, we study the parameterized complexity wrt. the parameter k. We show that the problem is W-hard wrt. k when either λ or k - λ is a constant or λ = ϵk, where 0 < ϵ < 1. Despite of these intractable results, we have an FPT wrt. k when the required satisfaction is at most m- g(k), where g is some computable function.
• Next, we give an algorithm that runs in O⋆ (2n log(λ+1) ) time. Note that this algorithm gives O⋆ (2n )-time algorithm for Egalitarian-CC, and this exponential dependence on n is optimal (assuming Set Cover Conjecture).

Note that this is an improvement over known O⋆ (nn )- time algorithm proposed by Betzler et al. [Betzler et al., 2013]. The same algorithm gives an FPT algorithms wrt. n that runs in O⋆ (2n2 ) time for all the value of λ.

• Next, we give an algorithm that runs in O⋆ (2n log(k-λ+1) ) time. Note that for λ = k - 1, this gives an O⋆ (2n )-time algorithm.
• For the voting rule Egalitarian-Best, we show that it is NPhard and W-hard wrt. k when either λ or k - λ is a constant or λ = ϵk, where 0 < ϵ < 1. Note that for λ = k, it is known as Egalitarian-k-Borda which is known to be NP-hard and W-hard wrt. k [Aziz et al., 2018]. Moreover, it can be solved in polynomial time when n and λ are constants.

All the missing and formal proofs will be presented in the journal version.

2 Chamberlin-Courant (CC)

We give an optimal algorithm for CC that runs in O⋆ (2n ) time, which is an improvement over the known O⋆ (nn )-time algorithm proposed in [Betzler et al., 2013]. Furthermore, the exponential dependence on n is optimal, assuming the Set Cover Conjecture (SCC), that says that we cannot have an algorithm that runs in O⋆ ((2 - ϵ)n ) time, where 0 < ϵ ≤ 1 and n is the size of the universe; we can infer the same about CC. This follows due to the reduction from HITTING SET to CC by Betzler et al., where the universe and the family of sets is mapped to the candidates and the voters, resp. The lower bound for HITTING SET follows from its linear size reducibility from SET COVER for which we have the Set Cover Conjecture. In that canonical reduction, the universe in the instance of SET COVER corresponds to the set family in the instance of HITTING SET. So unless the SCC fails, HITTING SET cannot have an algorithm that runs in time O⋆ ((2-ϵ)m), where m is the family size. The lower bound for CC holds due to its reduction from HITTING SET.

Theorem 1. CC is solvable in O⋆ (2n ) time.

We begin our discussion with an observation about CC: any committee of size k, denoted by S, yields a k-partition of the voter set, denoted by V1, . . . , Vk (i.e pairwise disjoint sets that cover V = ∪i∈[k]Vi) such that for each i ∈ [k] voters in district Vi are represented by a unique candidate in S, the one they rank above all others in S. We say that this partition is induced by S. Thus, in order to find the optimal CC committee it is enough to find a k-partition of the voters that yields the maximum CC score for the given instance.

In this exposition we have an instance I = (V , C , k, η); the goal is to decide if there exists a k-sized committee S ⊆C such that if {Vi : i ∈ [k]} is the partition induced by S, then η ≥ ∑i∈[k] Borda(Vi, ci). A trivial k-partition algorithm for a voter set of size n requires O(kn ) time, but by reducing our problem to polynomial multiplication involving polynomialmany multiplicands, representing pairwise disjoint subsets of V , each with degree at most O(2n ) we can find the desired partition in time 2nmO(1) . The trick is that while multiplying, the degree allows us to keep track of the combined score if the multiplicands constitute different districts of a partition. Before we dive into the details, we will discuss the main idea and some terminologies used in the algorithm.

Big picture. Any subset X ⊆ V can be viewed as a subset of [n]. Let χ(X) denote the characteristic vector of X, defined as an n-length vector whose ith bit is 1 iff i ∈ X. We view χ(X) as an n-digit binary number. A crucial observation guiding our algorithm is that two sets X1 and X2

are disjoint iff the number of 1s in χ(X1) + χ(X2) (binary sum/modulo 2) is equal to |X1| + |X2|. So, for each subset X ⊆ V of size t for which there exists a candidate c ∈ C such that α = Borda(X, c) we make a polynomial P 1 t,α(x) that contains the monomial xχ(X) . This type of representation allows us to succinctly capture the property of disjointness between the subsets of V , as well as allowing us to test at the end if all the k disjoint subsets taken together also "cover" V . To see this let us consider disjoint subsets X1,X2 ⊆V . Then, the polynomial xχ(X1) ×xχ(X2) = xχ(X1)+χ(X2) follows from normal polynomial multiplication. Due to the disjointness of the sets, their characteristic vectors are as well, i.e., none of the n positions have 1 in both χ(X1) and χ(X2). Consequently, χ(X1) + χ(X2) is also an n-length binary string that contains exactly |X1| + |X2| many 1s. We only construct polynomials that result from multiplying at most k monomials representing subsets of V . Moreover, when multiplying monomials we keep track of each one's contribution to the score of a potential committee for which the set corresponding to the monomial will form a district. For this purpose, we create a family of polynomials representing the various scores that such a district may contribute based on which candidate is representing it.

In the final step, we look for a polynomial that contains a monomial whose degree is (1)n , the string of n ones. This is because this monomial was generated by multiplying k monomials that constitute a k-partition of V . The fact that we never go beyond an n-length string as the degree ensures that the actual degree of the monomial in terms of decimal is at most 2n . This allows us to use the O(d log d) algorithm to multiply two polynomials of degree d (in decimal) in no more that O⋆ (2n ) time, [Moenck, 1976]. Thus, in this manner we can obtain an algorithm that runs in time O⋆ (2n ).

Before we discuss our algorithm, we have to introduce some notations and terminologies. Let V be a set of size n. Two binary strings of length n are said to be disjoint if for each i ∈ [n], the ith bits in the two strings are different. The Hamming weight of a binary string S, denoted by H(S), is defined to be the number of 1s in the string S. A monomial xi is said to have Hamming weight h, if the binary representation of i has Hamming weight h. The following result is used crucially in our algorithm.

Corollary 1. Subsets X1,X2 ⊆V are disjoint if and only if Hamming weight of the string χ(X1)+χ(X2) is |X1|+|X2|.

The Hamming projection of a polynomial P(x) to h, denoted by Hh(P(x)), is the sum of all the monomials of P(x) which have Hamming weight h. We define the representative polynomial of P(x), denoted by R(P(x)), as the sum of all the monomials that have non-zero coefficient in P(x) but have coefficient 1 inR(P(x)), i.e, it ignores the actual coefficients and only remembers whether the coefficient of is nonzero. We say that a polynomial P(x) contains a monomial xi if the coefficient of xi is non-zero. The zero polynomial is one in which the coefficient of each monomial is 0.

Proof. Nowwe are ready to present the algorithm.

Algorithm. For the instance I = (C , V , k, η), we will define k types of polynomials iteratively. We start with type 1. For any s ∈ [n] and α ∈ [(m- 1)n], we define

Thus, a polynomial of type 1 contains information about all subsets of V of a fixed size and for whom there exists a candidate whose Borda score from that subset is a fixed value. All the polynomials of type 1 taken together contain information about all possible subsets of V .

For any s ∈ [n] and α ∈ [(m- 1)n], we define the polynomials of type j ∈ [k] \{1} as follows

A j-type polynomial is defined by multiplying polynomials of type j - 1 and 1. The use of the H(·) operator ensures that the only monomials that survive are those that are formed by multiplying monomials with degrees that represent disjoint characteristic vectors (see Corollary 1). Thus, a j-type polynomial contains information about all sets that are formed by the disjoint union of j pairwise disjoint sets that yield a certain score. Each polynomial represents a set of voters of specific size who give a specific Borda score to a j-sized committee. The R(·) operator keeps coefficients to at most 1.

After defining these polynomials, the algorithm checks among the polynomials of type k, if for some α ≥ η, the polynomial P k n,α(x) is non-zero. If so, then it returns "yes", else it returns "no".

3 Pessimist

We resolve the complexity of PESSIMIST (find a committee under Pessimist rule).

Theorem 2. PESSIMIST is W[1]-hard wrt. k.

The proof is via a parameterized reduction from the INDEPENDENT SET problem on regular graphs. We begin by discussing the main idea behind our reduction

Proof Sketch. In our reduction, we associate the vertex set of the ∆-regular graph G = (V,E) of the instance of INDEPENDENT SET with both the set of voters and the set of candidates of the instance of PESSIMIST. Additionally, we have a large set of dummy candidates, whose role and number is strategically chosen to identify "no"-instances. For each voter v ∈ V , we create a large separation between the set of candidates that represent his neighbors in G, N(v), and those that are not his neighbors, N(v). This is done by placing a block of dummy candidates in between these two sets in that voter's preference list. The preference list of voter v is

where cv denotes the "clone" of v, the candidate corresponding to the vertex v, Dv denotes the set of dummies corresponding to voter v, and the suffix denoted by . . . contains the sets of dummies corresponding to other voters.

The affect of this arrangement is that an independent set of size k, say S, when viewed as a k-sized committee of candidates, call it ˆ S, induces a partition of the voter set: voters whose clone is in the committee, those whose one neighbor is in the committee, and those whose neighbors are not in the committee. Since the committee defines an independent set in G, we know that if vertex v ∈ S, then its neighbors cannot be in ˆ S, thus voter v's score for ˆ S is due to a candidate in N(v). If v /∈ S, then its neighbor(s) may or may not be in S. All those vertices whose neighbors are not in S contribute a similarly high score towards ˆ S. Those whose neighbor belongs to S contribute a lower score towards ˆ S. These precise contributions lead us to set the target score to be η = (2n3 + ∆)n - (2n2 + ∆) · min{n - k, k∆}, where the termmin{n-k, k∆} comes into play because that is the upper bound on the number of neighbors a k-sized subset of vertices can have outside the set. Specifically, it upper bounds |N(S)|. Additionally, we remark that |Dv| = 2n2 , and so the total number of dummies is exactly 2n3 . The choice of these numbers is driven by our calculation in the reverse direction.

In the reverse direction, suppose that we have a k-sized committee, call it ˆ S, whose score is at least η. First, we note that ˆ S does not contain any dummy candidate, because it appears in the suffix of n - 1 voters and thus the contribution from them will be so low that ˆ S cannot achieve η. Next we argue that if there is even a pair of candidates in ˆ S that share an edge in G, then the score of ˆ S is strictly less than η. This calculation dictates the size of Dv, described above.

Next, we show that the problem can be solved in polynomial time when the number of voters is a constant. The idea is that for each voter, we can guess the last candidate (representative) who is in the committee. Then, we know that any candidate who is ranked lower than the representative is not part of the committee, and so delete all those candidates. Next, we choose any k-sized set of candidates from the remaining set to obtain the desired committee.

Theorem3. PESSIMIST is solvable in polynomial time, when n is constant.

4 Egalitarian-Median

In this section, we study the computational and parameterized complexity of EGAL-MED (finding a winning committee under the Egalitarian-Median rule). We first define some terminologies that will be used throughout the section. Let (C , V , λ, k, η) be an instance of EGAL-MED. For a voter v and integer ℓ, prefixv (ℓ) denote the set of top ℓ candidates in the preference list of v, i.e., prefixv (ℓ) = {c ∈ C : βv(c) ≥ m-ℓ}. Similarly, suffixv(ℓ) denote the set of last ℓ candidates or the set of candidates whose Borda score is less than ℓ in the preference list of v, i.e., suffixv(ℓ) = {c ∈ C : βv(c) < ℓ}.

We begin with the intractability results. To prove NPhardness, we give a polynomial-time reduction from EHITTING SET, in which given a universe U, integers s, ˜ k, and a family, F, of subsets of U such that the size of every set in F is s; we shall find a ˜ k-sized set S ⊆ U such that for any set F ∈ F, F ∩ S ̸= ∅. This is a variant of the well-known HITTING SET problem, where the size of every set in the family is same. E-HITTING SET is known to be NP-hard for all s ≥ 2 [Garey and Johnson, 1979]. Towards giving reduction, we first note that in a winning committee, for every voter, we can have at most k - λ candidates whose score is less than the required score. So, we create a voter corresponding to every set in the family F and a candidate corresponding to elements of the universe U. Then, we encode that the winning committee has the candidates corresponding to elements that are not in the hitting set. So, a voter vF corresponding to the set F ranks all the candidates corresponding to elements in F at the end. Clearly, we do not want all these candidates in the committee, otherwise we will not get a hitting set. So, we set the required satisfaction as s and λ as k - (s - 1), so that s candidates from the suffixv(s) cannot be in the winning committee. Below, we prove it formally.

Theorem 4. EGAL-MED is NP-hard for all λ ∈ [k - 1].

Proof Sketch. Let (U,F, s, ˜ k) be an instance of E-HITTING SET. Let |U| = ˜n and |F| = ˜m. Without loss of generality, we assume that ˜n ≥ ˜ k + s. We construct an instance (C , V , λ, k, η) of EGAL-MED as follows. For every element u ∈ U, we add a candidate cu in C . For every F ∈ F, we add a voter vF in F. For a subset X ⊆ U, let CX denote the set of all the candidates corresponding to the elements in the set X. Next, we define the preference list of every voter, vF , as follows: vF : 〈C \ CF 〉 ≻ 〈CF 〉. Let k = ˜n - ˜ k, λ = k -(s-1), and η = s. This completes the construction. Intuitively, we capture that if S is a solution to (U,F, s, ˜ k), then the set of candidates corresponding to the elements in U\S form a desired committee, and vice-versa. Since η = s and λ = k - (s - 1), we ensure that for every voter vF at most k - λ =s - 1 candidates from suffixvF (s) are in the committee. Thus, we ensure that for any voter vF , CF is not a subset of the committee as |CF | = s. Hence, if S has score η, then the subset of elements of U whose corresponding candidates are not in the committee is a hitting set.

Next, we prove that EGAL-MED is W[2]-hard wrt. k, when either λ is a constant or λ = ϵk, where 0 < ϵ < 1. Towards that we again give a polynomial-time reduction from E-HITTING SET, which is known to be W[2]-hard wrt. solution size [Downey and Fellows, 1995]. Note that the above reduction (Theorem 4) is not parameter preserving. To prove the following theorem, in the reduction, we capture that for every voter, we shall choose at least λ candidates from top m - η candidates, in the winning committee. Note that in the above reduction, we captured the opposite of this, i.e., the winning committee can have at most k - λ candidates from the last η candidates in the preference list of a voter.

Theorem 5. EGAL-MED is W[2]-hard wrt. k for constant λ.

Next, we show that the problem is even hard when λ = ϵk, where 0 < ϵ < 1.

Corollary 2. EGAL-MED is W[2]-hard wrt. k, when λ = ϵk, where 0 < ϵ < 1.

Next, we prove that EGAL-MED is W[1]-hard wrt. k when k - λ is a non-zero constant. Towards that we give a polynomial time reduction from the s-RED/BLUE NONBLOCKER problem, in which given a graphG = (V,E), where V is partitioned into two color classes Vred and Vblue and every vertex in Vblue has s neighbors in Vred, and an integer k; we have to decide the existence of a k-sized set S ⊆ Vred such that every vertex in Vblue has at least one neighbor that is not in S. This problem is known to be W[1]-hard wrt. k for s ≥ 2 [Downey and Fellows, 2013]. We view this problem as hitting neighborhood of every vertex of Vblue in the set Vred at most s - 1 times. So, for every vertex in Vred, we create a candidate, and for every vertex in Vblue, we create a voter. Now, for every voter vx, where x is a vertex in Vblue, the candidates corresponding to the neighbors of x in Vred are lowest ranked candidates. We set λ and η so that any winning committee takes at most s - 1 of these lower ranked candidates.

Theorem 6. EGAL-MED is W[1]-hard wrt. k, even when kλ and η are non-zero constants.

Next, we identify a tractable case wrt. the parameter k. The idea of the following algorithm is also based on the fact that for every voter, we shall choose at least λ candidates from the top m- η candidates, which we view as hitting the sets prefixv (m- η) for every voter v at least λ times. Thus, if prefixv (m- η) = g(k), then we can use known algorithm in [Mellor et al., 2010] for this variant of the HITTING SET problem to obtain an algorithm for our problem. There the algorithm is for d-sized sets, but it gives us FPT wrt. k as in our case the size of these sets is g(k).

Theorem 7. EGAL-MED is FPT wrt. k when η = m-g(k), where g(k) is any computable function of k.

Next, we show that the problem is tractable wrt. n, the number of voters. Towards that we first give an algorithm that runs in O⋆ (2n log(λ+1) ) time. Note that this algorithm gives an O⋆ (2n )-time algorithm for Egalitarian CC (λ = 1 in EGAL-MED), which is an improvement over known O⋆ (2n log n ) algorithm in [Betzler et al., 2013]. Furthermore, this running time is tight under Set Cover Conjecture due to the reduction from the HITTING SET problem in [Betzler et al., 2013].

So far, we view the problem as hitting the prefix of a voter λ times. Next, we visualise this problem as covering a voter λ times using the candidates in the prefix. Using this idea, we reduce the problem to SET MULTICOVER, where given a universe U, a family of subsets, F, of U, and integers k, ℓ, we shall decide the existence of a subset F ′ ⊆ F, where |F ′ | ≤ k, such that for every element u ∈ U, there are at least ℓ sets in F ′ that contains u; and then use the known exact algorithm in [Hua et al., 2010] for SET MULTICOVER to obtain the desired result.

Theorem8. EGAL-MED is solvable inO⋆ (2n log(λ+1) ) time.

Proof Sketch. Given an instance (C , V , λ, k, η) of EGALMED, we create an instance (U,F, ℓ, k′ ) of the SET MULTICOVER problem as follows. For every voter v ∈ V , we add an element ev in U. Let C ′ ⊆ C be a subset of candidates that belongs to top |C | - η candidates for any voter v ∈ V , that is C ′ = ∪v∈V prefixv (|C | - η). For every c ∈ C ′ , we add a set Fc = {ev ∈ U : βv(c) ≥ η} to the set F. We set ℓ = λ and k′ = k. Next, we use the exact algorithm for SET MULTICOVER in [Hua et al., 2010] that runs in O⋆ (2|U| log(ℓ+1) ) time. Note that λ = ℓ and |U| = |V |. Thus, we obtain an algorithm for EGAL-MED that runs in O(2n log(λ+1) ).

Note that in the instance (U,F, ℓ, k′ ) of SET MULTICOVER, ℓ ≤ 2|U| . Thus, we have the following result.

Corollary 3. EGAL-MED is solvable in O⋆ (2n2 ) time.

Next, we give an algorithm for EGAL-MED that runs in O(2n log(k-λ+1) ) time. Note that if k - λ is constant, we have an algorithm with running time 2O(n) . Here, we again use the idea that from the suffix part of every voter, we shall pick at most k - λ candidates in the winning committee, and devise a dynamic programming algorithm. The intuitive idea is as follows. Given an instance (C , V , λ, k, η) of EGAL-MED, we partition C into two parts C1 and C2 such that C1 = ∪v∈V suffixv(η) and C2 = C \ C1. We guess the number of candidates, say k1 ≤ k, in the winning committee from the set C1, i.e., for a winning committee S, |S ∩ C1| = k1. Next, using DP, we find a k1-sized committee which is a subset of C that has the following property: for every voter v, the committee contains at most k - λ candidates from suffixv(η). Then, we add any k - k1 candidates from the candidate set C2 to obtain a winning committee.

Theorem 9. EGAL-MED is solvable in O⋆ (2n log(k-λ+1) ).

5 Egalitarian-Best

Here, we study the computational and parameterized complexities of EGAL-BEST (finding a winning committee under the Egalitarian-Best rule). The idea behind the following reduction is same as in Theorem 5. By setting η = ˜n + λ˜n + sλ + (λ-1)(λ-2) 2 in the proof of Theorem 5, we obtain the following:

Theorem 10. EGAL-BEST is NP-hard and W[2]-hard wrt. k, when λ is a constant.

As argued for Corollary 2, we have the following:

Theorem 11. EGAL-BEST is NP-hard and W[2]-hard wrt. k even when λ = ϵk, where 0 < ϵ < 1.

Fortunately, we have the following tractable case. The idea is that for every voter we can guess the set of λ candidates whose Borda score will be counted in the score.

Theorem 12. EGAL-BEST can be solved in polynomial time for constant n and λ.

Acknowledgments

The authors were supported by the following grants. S. Gupta by SERB-Starting Research Grant (SRG/2019/001870). S. Saurabh by European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant no. 819416), and Swarnajayanti Fellowship grant (DST/SJF/MSA- 01/2017-18). N. Talmon by the Israel Science Foundation (ISF; GrantNo.630/19)