# approvalbased_committee_voting_under_incomplete_information__b14d9c2d.pdf

Approval-Based Committee Voting under Incomplete Information

Aviram Imber,1 Jonas Israel,2 Markus Brill,2 Benny Kimelfeld1

1 Technion Israel Institute of Technology, Haifa, Israel 2 Research Group Efﬁcient Algorithms, TU Berlin, Germany aviram.imber@campus.technion.ac.il, j.israel@tu-berlin.de, brill@tu-berlin.de, bennyk@cs.technion.ac.il

We investigate approval-based committee voting with incomplete information about the approval preferences of voters. We consider several models of incompleteness where each voter partitions the set of candidates into approved, disapproved, and unknown candidates, possibly with ordinal preference constraints among candidates in the latter category. This captures scenarios where voters have not evaluated all candidates and/or it is unknown where voters draw the threshold between approved and disapproved candidates. We study the complexity of some fundamental computational problems for a number of classic approval-based committee voting rules including Proportional Approval Voting and Chamberlin Courant. These problems include that of determining whether a given set of candidates is a possible or necessary winning committee and whether it forms a committee that possibly or necessarily satisﬁes representation axioms. We also consider the problem whether a given candidate is possibly or necessarily a member of the winning committee.

1 Introduction

Approval-based committee (ABC) voting represents a wellstudied multiwinner election setting, where a subset of candidates of a predetermined size, a so-called committee, needs to be chosen based on the approval preferences of a set of voters (Lackner and Skowron 2021). Traditionally, ABC voting is studied in the context where we know, for each voter and each candidate, whether the voter approves the candidate or not. In this paper, we investigate the situation where the approval information is incomplete. Speciﬁcally, we assume that each voter is associated with a set of approved candidates, a set of disapproved candidates, and a set of candidates where the voter s stand is unknown, hereafter referred to as the unknown candidates. Moreover, we may have (partial) ordinal information on voters preferences among the unknown candidates, restricting the valid completions of voters approval sets. When the number of candidates is large, unknown candidates are likely to exist because voters are not aware of or not familiar with, and therefore cannot evaluate, all candidates. In particular, this holds in scenarios where candidates join

Copyright c 2022, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

the election over time, and voter preferences over new candidates have not been elicited (Chevaleyre et al. 2012). Distinguishing between disapproved and unknown candidates accounts for two fundamentally different reasons for nonapprovals: either the voter has evaluated the candidate and judged him or her not worth approving (in which case the candidate counts as disapproved), or the voter has not evaluated the candidate (in which case the candidate counts as unknown). Furthermore, incorporating (partial) ordinal preferences among unknown candidates allows us to model situations in which we (partially) know how a voter rank-orders the candidates, but we do not know where the voter draws his or her approval threshold. Scenarios involving incomplete knowledge about approval preferences arise naturally in a variety of practical settings. For example, in a scenario where we retrieve information from indirect sources such as social media (say, for the sake of prediction), we may get only sparse information about approval ( Vote for X ) and disapproval ( Deﬁnitely not Y ), and possibly pairwise preferences due to explicit statements (e.g., X is at least better than Y ). As another example, in shortlisting scenarios (such as faculty hiring) some voters may know with sufﬁcient conﬁdence that they support or oppose some candidates (e.g., the ones from their own ﬁeld of expertise) but have no clear opinion on others. This situation also naturally arises when labeling documents for information retrieval, where the committee corresponds to the page of search results: some documents are clearly relevant, some clearly irrelevant, and some are unclear. For the unclear ones, it may be way easier to rank the documents (totally or partially) by relevance rather than to insist on a complete classiﬁcation into relevant and irrelevant; in fact, this is the motivation behind some successful methodologies for learning ranking functions (learning to rank) such as the pairwise and listwise approaches (Cao et al. 2007). Our basic model of incompleteness is the poset approval model that is illustrated in Figure 1(a). This model is a rather direct generalization of the voter model in the seminal work of Konczak and Lang (2005), who study problems of winner determination with incomplete preferences under rankingbased single-winner rules (such as plurality and Borda). For each voter, we are given a set of approved candidates and a set of disapproved candidates, together with a partial order over the remaining ( unknown ) candidates that con-

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

strains the possible approval ballots of the voter: if an unknown candidate is preferred to another unknown candidate, then the former needs to be approved by the voter whenever the latter is approved. In other words, each possible world is obtained by selecting a linear extension of the partial order and determining a cutoff point every candidate before the cutoff is approved, and every candidate after the cutoff is disapproved (in addition to the known approvals and disapprovals, respectively). We study in depth two special cases of this model that correspond to the two extremes of posets: zero information (3VA) and full information (linear). In the three-valued approval (3VA) model,1 illustrated in Figure 1(b), the partial order of the poset is empty. Hence, every subset of unknown candidates determines a valid possible world where this set is approved and its complement is disapproved. In the linear model, illustrated in Figure 1(c), the unknown candidates are ordered linearly. Hence, every preﬁx of this order determines a possible world where the candidates in this preﬁx are approved and the ones in the remaining sufﬁx are disapproved. From the computational perspective, the models are fundamentally different. For instance, a voter can have an exponential number of possible worlds (or completions) in one case, but only a linear number in the other. Of course, when a problem is tractable in the poset approval model, then it is also tractable in the 3VA and linear models. On the contrapositive, whenever a problem is intractable (e.g., NP-hard) in one of these two models, it is also intractable for the general poset approval model. However, as we illustrate later, a problem may be tractable in 3VA and intractable in the linear model, and vice versa. We investigate the computational complexity of fundamental problems that arise in ABC voting with incomplete approval proﬁles. In the ﬁrst problem, the goal is to determine whether a given set W of candidates is a possible winning committee. In the second problem, the goal is to determine whether such given W is a necessary winning committee. More formally, a possible committee (respectively, necessary committee) is a set of candidates that is a winning committee in some completion (respectively, all completions) of the incomplete approval proﬁle. We also achieve some results on the problem where we are given a candidate and the goal is to determine whether the candidate is possibly or necessarily a member of a winning committee. In the applications described earlier it is often enough to ﬁnd only one winning committee, e.g., because we only want to have one set of top search results and do not care about there being other, equally good such sets. Thus ﬁnding a necessary winning committee is enough and we do not need to elicit any more information. Conversely, if for example in a hiring process we know that some candidates are not in any possible committee any more, we can already inform them that they will deﬁnitely not get the position and we can stop eliciting preferences over those candidates.

1The term is analogous to Three-Valued Logic (3VL) that is adapted, e.g., in SQL (Libkin 2016), where the three values are true, false and unknown.

We consider a class of voting rules that was introduced by Thiele (1895). This broad class of approval-based committee voting rules contains several classic rules such as Approval Voting (AV), Chamberlin Courant (CC), and Proportional Approval Voting (PAV). For all Thiele rules except AV, the problem of determining winning committees is intractable even before we allow for incompleteness (Lackner and Skowron 2021). Consequently, computing either possible or necessary committees is intractable as well, under each of our models of incompleteness. Therefore, we focus on the case where the committee size is small (i.e., constant). In this case, winning committees can be computed in polynomial time for all considered rules. In addition, we study a problem of fair representation of voters given incomplete approvals. In particular, we focus on justiﬁed representation (JR) (Aziz et al. 2017), which requires that all voter groups that are large enough and cohesive enough are represented in the committee. We investigate the complexity of deciding whether a given set of candidates possibly or necessarily forms a committee that satisﬁes JR given an incomplete approval proﬁle. We also brieﬂy discuss stronger notions of proportional representation.

Related work Collective decision making under incomplete knowledge has been extensively studied; we refer to Lang (2020) for a recent survey. Most of that work focuses on single-winner elections (e.g., Xia and Conitzer 2011), with the paper by Lu and Boutilier (2013) representing a notable exception. To the best of our knowledge, there are only two papers that deal with incomplete information in the context of approval voting: First, Barrot et al. (2013) study single-winner approval voting and multiwinner approval voting (which we refer to as AV) given incomplete information. In the terminology of our paper, their incompleteness model corresponds to the special case of the linear model in which all candidates (except the most preferred one) belong to the unknown category. We discuss speciﬁc relationships between their work and ours in Section 4. Second, Terzopoulou, Karpov, and Obraztsova (2021) consider restricted domains for approval voting under uncertainty using a model of incompleteness corresponding to our 3VA model. Allowing voters to not only specify which candidates they approve and disapprove but also for which they are undecided can be seen as eliciting trichotomous preferences (without uncertainty). In this vein, our work relates to Felsenthal (1989), Alcantud and Laruelle (2014), Baumeister and Dennisen (2015), and Zhou, Yang, and Guo (2019).

2 Preliminaries We consider a voting setting where a ﬁnite set V of voters has preferences over a ﬁnite set C of candidates. We usually use n for the number of voters and we enumerate voters as v1, v2, . . . , vn. The number of candidates is denoted by m. An approval proﬁle A = (A(v1), . . . , A(vn)) lists the approval sets of the voters, where A(vi) C denotes the set of candidates that are approved by voter vi. The concatenation of two approval proﬁles A1 = (A1(v1), . . . , A1(vp)) and A2 = (A2(v 1), . . . , A2(v q)) is denoted by A1 A2 := (A1(v1), . . . , A1(vp), A2(v 1), . . . , A2(v q)). An approval-

Unknown Disapproved Approved

(a) Poset approval

Unknown Disapproved Approved

(b) Three-valued approval (3VA)

Approved Unknown Disapproved (c) Linear incomplete approval

Figure 1: Models of incomplete approval preferences: Poset approval and the special cases of 3VA and linear incomplete approval. Dashed frames depict candidates that are approved in a valid completion.

based committee (ABC) rule takes an approval proﬁle as input and outputs one or more size-k subsets of candidates, so called committees, for a given parameter k N. Most of our work is focused on a class of ABC rules known as Thiele rules (Thiele 1895). These rules are parameterized by a weight function w, i.e., a non-decreasing function w: N Q 0 with w(0) = 0. The score that a voter v contributes to a subset S C is deﬁned as w(|S A(v)|) and the score of S is P v V w(|S A(v)|). The rule w Thiele then outputs the subset(s) of size k with the highest score. Two of the most famous examples of Thiele rules are Approval Voting (AV),2 where w(x) = x, and Proportional Approval Voting (PAV), where w(x) = Px i=1 1/i. We assume that w(x) is computable in polynomial time in x, and that there exists an integer x with w(x) = 0 (otherwise, all subsets of voters have the same score). Observe that for every ﬁxed number k, we can ﬁnd the committee(s) under w Thiele in polynomial time by computing the score of every subset W C of size k. Without loss of generality, we assume that weight functions are normalized such that w(x) = 1 for the smallest x with w(x) > 0. We call a Thiele rule binary if w(x) {0, 1} for all x N. Since w is non-decreasing, binary Thiele rules are characterized by an integer t such that w(x) = 0 for every x < t and w(x) = 1 for all x t. The most prominent binary Thiele rule is Chamberlin Courant (CC), with w(x) = 1 for all x 1.

2We can also deﬁne this rule using scores of individual candidates: For a candidate c, the approval score of c is deﬁned as | {v V : c A(v)} |. AV selects committees consisting of the k candidates with highest approval scores.

3 Models of Incompleteness In this section, we formally introduce the three models of incomplete information that we investigate. We ﬁrst deﬁne poset approval as a general model, and then two models constituting special cases. In all models, a partial proﬁle P = (P(v1), . . . , P(vn)) consists of n partial votes.

Poset approval. For each voter v, the partial vote P(v) consists of a partition (Top(v), Middle(v), Bottom(v)) of C into three sets and a partial order3 v over the candidates in Middle(v). Top(v) represents the candidates that v approves in any case, Bottom(v) represents the candidates that v approves in no case. The partial order v represents approval constraints on the candidates in Middle(v), whose approval is open. Speciﬁcally, if c v c and v approves c , then v also approves c. A completion of P = (P(v1), . . . , P(vn)) is an approval proﬁle A = (A(v1), . . . , A(vn)) where each A(v) completes P(v). Namely, Top(v) A(v), Bottom(v) A(v) = , and for every pair c, c Middle(v) with c v c , it holds that c A(v) whenever c A(v). Equivalently, we can describe A in the following way: For each voter v select a subset Middle A(v) Middle(v) which respects v (i.e., c v c and c Middle A(v) imply c Middle A(v)) and v approves exactly A(v) = Top(v) Middle A(v).

Three-valued approval (3VA). This model is a special case of poset approval where for every voter v, the partial order v over the candidates in Middle(v) is empty (except for the reﬂexive part). In other words, v might approve any subset of candidates in Middle(v). Hence, a completion of P = (P(v1), . . . , P(vn)) is a complete approval proﬁle A = (A(v1), . . . , A(vn)) such that for every voter v we have Top(v) A(v) and Bottom(v) A(v) = .

Linear incomplete approval. This model is a special case of poset approval where for every voter v, v is a complete linear order ci1 v. . . v ciq on the candidates in Middle(v). To construct a completion A, for every voter v we select a j |Middle(v)| such that Middle A(v) = ci1, . . . , cij .

In the linear model of incompleteness, every partial vote has at most m completions, as opposed to the previous two models where even a single partial vote can have 2m completions. In all three models, the number of completions for a partial proﬁle can be exponential in the number of voters n. In order to deﬁne possible and necessary committees, ﬁx an ABC voting rule r. Given a committee size k and a partial proﬁle P, a set W C of k candidates is a possible committee if there exists a completion A of P where W is a winning committee (under r), and a necessary committee if W is a winning committee for every completion A of P. In the following sections, we investigate the computational complexity of deciding whether a given set of candidates is a possible or necessary committee, for different rules r.

4 Computing Possible Committees The ﬁrst decision problem we study concerns possible committees. For an ABC rule r and committee size k, con-

3Recall that a partial order is a reﬂexive, antisymmetric, and transitive binary relation.

sider the following decision problem that we denote by Pos Com k : Given a partial proﬁle P and a subset W C of candidates of size k, decide whether W is a possible committee. As mentioned earlier, we parameterize the decision problem by k since otherwise winner determination even in the case of no uncertainty is known to be NP-hard for almost all Thiele rules (Lackner and Skowron 2021). Observe that Pos Com k is in NP under all Thiele rules, for every ﬁxed k, in all three models of uncertainty that we study. This is because, given a complete proﬁle, we can ﬁnd the winning committees of a ﬁxed size k under Thiele rules in polynomial time. Our results concerning the complexity of deciding Pos Com k under different models of uncertainty are summarized in Table 1. In particular, we show that under the model of poset approval, Pos Com k is NP-complete for all Thiele rules. To obtain this result, we study the complexity of Pos Com k in the models of three-valued approval and linear incomplete approval in Sections 4.1 and 4.2, respectively. Then, we prove our main result in Section 4.3. We ﬁrst introduce a useful lemma that holds in all three models of uncertainty. The complete proofs of all results can be found in the full version of the paper (Imber et al. 2021).

Lemma 1. Let w1, w2 be a pair of weight functions. Assume there are two integers k, t 0 and a strictly increasing linear function f such that w2(x + t) = f(w1(x)) for every x {0, 1, . . . , k}. Then, in each of the three models of uncertainty, there is a polynomial-time reduction from Pos Com k under w1-Thiele to Pos Com k + t under w2Thiele.

Proof sketch. Let P1 = (P1(v1), . . . , P1(vn)) and W C1 of size k be an instance of Pos Com k under w1-Thiele. Deﬁne an instance of Pos Com k + t under w2-Thiele where the candidates are C2 = C1 D for D = {d1, . . . , dt}. The proﬁle is P2 = (P2(v1), . . . , P2(vn)), where for every voter v, P2(v) is the same as P1(v) except that v always approves the candidates of D. Formally, we add the candidates of D to Top(v), and the rest is unchanged. It can be shown that W is a possible committee (of size k) for P1 under w1-Thiele if and only if W D is a possible committee (of size k + t) for P2 under w2-Thiele.

4.1 Three-Valued Approval

We now discuss the complexity of Pos Com k in the 3VA model for different Thiele rules. We start with Approval Voting and Chamberlin Courant.

Theorem 1. In the 3VA model, Pos Com k is solvable in polynomial time under Approval Voting, for all ﬁxed k 1.

Proof sketch. Given P = (P(v1), . . . , P(vn)) and a subset W C of |W| = k candidates, deﬁne a completion A = (A(v1), . . . , A(vn)) where for every voter v, Middle A(v) = Middle(v) W; that is, except for Top(v), voters only approve candidates in W. It can be shown that W is a possible committee for P if and only if W is a winning committee in A.

Theorem 2. In the 3VA model, Pos Com 2 is NP-complete under Chamberlin Courant.

Proof sketch. We show NP-hardness by a reduction from one-in-three positive 3SAT, which is the following decision problem: Let X = {x1, . . . , xn} be a set of elements. Given sets S1, . . . , Sm X, where |Si| = 3 for every i, is there a subset B X such that for each i, |B Si| = 1? This problem is NP-complete (Garey and Johnson 1979). Given X and S = {S1, . . . , Sm}, we deﬁne an instance of Pos Com 2 under Chamberlin Courant. The candidates are C = S {w1, w2}. The partial proﬁle P = P1 A2 consists of two parts that we describe next. The ﬁrst part, P1, consists of a voter for every element in X. Let x X, and let S(x) = {Si S : x Si} be the sets of S that contain x. Deﬁne a voter vx with Top(vx) = S \ S(x), Middle(vx) = {w1, w2} and Bottom(vx) = S(x). The decision whether to approve w1 or w2 represents the decision whether to include x in the subset B X. The second part, A2, consists of six voters without uncertainty (voters with Middle(v) = ). We add three voters approving S, two voters approving {w1}, and a single voter approving {w2}. It can be shown that {w1, w2} is a possible committee if and only if there is a solution to the instance of one-in-three positive 3SAT.

Next, we use Lemma 1 and Theorem 2 to obtain another hardness result.

Theorem 3. Let w be a weight function such that w(k 2) < w(k 1) = w(k) for some k 2. Then, in the 3VA model, Pos Com k is NP-complete under w-Thiele.

Whereas the condition in Theorem 3 does not hold for PAV (for which the complexity of Pos Com k in the 3VA model remains open), it clearly holds for binary Thiele rules.

Corollary 1. For every binary Thiele rule, there exists k 2 such that Pos Com k is NP-complete in the 3VA model.

4.2 Linear Incomplete Approval Next, we discuss the complexity of Pos Com k in the linear model. We start with binary Thiele rules.

Theorem 4. In the linear model, Pos Com k is solvable in polynomial time for binary Thiele rules, for all ﬁxed k 1.

Proof sketch. Consider a binary Thiele rule and let t be such that w(x) = 0 for all x < t and w(x) = 1 for all x t. Without loss of generality, we can assume that k t. Given P = (P(v1), . . . , P(vn)) and a subset W C of k candidates we construct a completion A as follows. Let ci1 v v ciq be the linear order of voter v over the candidates in Middle(v). If |Top(v) W| t, then v always contributes a score of 1 to W. Since approving more candidates cannot increase the score of W, we select Middle A(v) = . If |(Top(v) Middle(v)) W| < t, then v always contributes a score of 0 to W, and we select Middle A(v) = again. Finally, assume that |Top(v) W| < t and |(Top(v) Middle(v)) W| t. Let j be minimal with |(Top(v) ci1, . . . , cij ) W| t and Middle A(v) = ci1, . . . , cij . It can be shown that W is a possible committee if and only if W is a winning committee in A.

Model AV CC PAV w-Thiele

Three-Valued Approval P [Thm. 1] NP-c [Thm. 2] ? NP-c for every binary w [Cor. 1]

Linear Incomplete Approval NP-c [Cor. 2]

(for all k 2) P [Thm. 4] NP-c [Cor. 2] (for all k 2) P for every binary w [Thm. 4]; NP-c for every strictly increasing w [Cor. 2] (for all k 2)

Poset Approval NP-c [Thm. 7] NP-c [Thm. 7] NP-c [Thm. 7] NP-c for every w [Thm. 7]

Table 1: Overview of our complexity results for Pos Com k . NP-c means that Pos Com k is NP-complete for at least one k, unless otherwise stated. P means that Pos Com k is solvable in polynomial time for all k. The result marked with also follows from Barrot et al. (2013).

We now turn to the complexity of Pos Com k under non-binary w-Thiele rules. The next theorem states that Pos Com 2 is NP-complete under w-Thiele for every function w whose ﬁrst three values are pairwise distinct.

Theorem 5. Let w be a weight function with w(2) > w(1) > 0. Then, in the linear model, Pos Com 2 is NPcomplete under w-Thiele.

Proof sketch. Without loss of generality we have w(1) = 1 and w(2) = 1 + x where x > 0. We show two reductions, depending on whether x (0, 1] or x > 1, from exact cover by 3-sets (X3C), which is the following decision problem: Given a set U = {u1, . . . , u3q} and a collection E = {e1, . . . , em} of 3-element subsets of U, can we cover all the elements of U using q pairwise disjoint sets from E? This problem is NP-complete (Garey and Johnson 1979). We start with the case where x (0, 1]. Given U and E, we construct an instance of Pos Com 2 under w-Thiele. The candidate set is C = U {c, d, z}. The partial proﬁle P = P1 A2 is the concatenation of the following two parts. The ﬁrst part, P1, consists of a voter for every set in E. For every e E, voter ve has Top(ve) = , Middle(ve) = e {c}, and Bottom(ve) = (U \ e) {d, z}. The linear order on Middle(ve) is an arbitrary order that ranks c last. This means that if ve approves c, then it also approves the candidates of e. The idea is that approving c indicates that e is in the cover, and disapproving c indicates that e is not in the cover. The second part, A2, consists of 2q + 1 voters without uncertainty (voters with Middle(v) = ). Assume w.l.o.g. that q is even. We add q/2 voters approving {z}, q/2 voters approving {z} U, q/2 voters approving {d}, q/2 voters approving {d} U, and a single voter approving {c, d, z}. It can be shown that {c, d} is a possible committee for P if and only if there exists an exact cover. For the case x > 1 a similar reduction is possible.

Next, we use Lemma 1 in order to generalize Theorem 5 to every function with three consecutive different values.

Theorem 6. Let w be a weight function such that w(k 2) < w(k 1) < w(k) for some k 2. Then, in the linear model, Pos Com k is NP-complete under w-Thiele.

Clearly, Theorem 6 applies to all Thiele rules with strictly increasing weight functions (such as AV and PAV).

Corollary 2. Let w be a strictly increasing weight function. Then, in the linear model, Pos Com k is NP-complete under w-Thiele for every k 2.

As a special case, Corollary 2 reasserts the result of Barrot et al. (2013) that Pos Com k is NP-complete for the AV rule. (The hardness result by Barrot et al. (2013) even applies to the special case in which all candidates are unknown.)

4.3 Poset Approval Combining the results from the previous two sections, we can now formulate the main result of this paper.

Theorem 7. In the poset approval model, for every weight function w there exists an integer k such that Pos Com k is NP-complete under w-Thiele.

Proof. Let w be a weight function, and let j be the minimal index such that w(j) > 0. Since w is non-decreasing, either w(j + 1) = w(j) > w(j 1) or w(j + 1) > w(j) > w(j 1). In the ﬁrst case, by Theorem 3, Pos Com j + 1 is NPcomplete under w-Thiele in the 3VA model. In the second case, by Theorem 6, Pos Com j + 1 is NP-complete under w-Thiele in the linear model. The result follows since 3VA and the linear model are special cases of poset approval.

4.4 Possible Committee Members We now consider a different decision problem where we do not focus on whole committees but rather on individual candidates. We say candidate c is a possible committee member if there exists a completion A of P such that there exists a winning committee W with c W. For an ABC rule r and a committee size k, we consider the computational problem Pos Mem k , where the input consists of a partial proﬁle P and a candidate c, and the goal is to determine whether c is a possible committee member under r. Note that for every voting rule, if Pos Com k is solvable in polynomial time, then we can also solve Pos Mem k efﬁciently: given a candidate c, test whether {c, d1, . . . , dk 1} is a possible committee for all other k 1 candidates d1, . . . , dk 1. Since k is ﬁxed, this can be done efﬁciently. By Theorems 1 and 4 we can deduce the following.

Corollary 3. For all ﬁxed k 1, Pos Mem k is solvable in polynomial time:

1. In the 3VA model under approval voting;

2. In the linear model under every binary Thiele rule. We also obtain a tractability result in a setting for which the corresponding Pos Com k problem is intractable. Theorem 8. In the linear model, Pos Mem k is solvable in polynomial time under Approval Voting, for all ﬁxed k 1.

Proof sketch. Given a candidate c and a partial proﬁle P = (P(v1), . . . , P(vn)), we construct a completion A of P as follows. For all voters v with c Top(v) or c Bottom(v), we let Middle A(v) = . Otherwise, c Middle(v) and we deﬁne Middle A(v) to be the smallest preﬁx of the linear order over Middle(v) that includes c. It can be shown that c is a possible committee member if and only if c is a member of a committee in A.

5 Computing Necessary Committees The next decision problem we study concerns necessary winning committees. For an ABC rule r and a committee size k, we consider the following decision problem, which we refer to as Nec Com k : Given a partial proﬁle P and a subset W C of candidates of size |W| = k, determine whether W is a necessary committee under r. As above, we parametrize the problem by the committee size k to evade hardness even in the case of complete information. We show that Nec Com k is solvable in polynomial time for a large family of ABC rules that includes all Thiele rules. Each member of the family of ABC scoring rules is associated with a scoring function f : N N R satisfying f(x, y) f(x , y) for x x . The score s of a subset S C given approval set A(v) is

s(A(v), S) = f(|A(v) S|, |A(v)|),

and the total score is s(A, S) = P v V s(A(v), S). The rule deﬁned by f outputs the subset(s) of size k with the highest score. Observe that Thiele rules are a special case of ABC scoring rules, where the score s(A(v), S) that v assigns to S depends only on |A(v) S|. An example for an ABC scoring rule which is not a Thiele rule is Satisfaction Approval Voting (Brams and Kilgour 2014), where the score a voter v contributes to a S C is s(A(v), S) = |S A(v)|/|A(v)|. When we discuss scoring rules, we assume that f(x, y) is computable in polynomial time given x and y. The following positive result covers all ABC scoring rules and all considered models of incompleteness. Theorem 9. Let r be an ABC scoring rule. Then, in the model of poset approval, for all ﬁxed k 1, Nec Com k is solvable in polynomial time under r. In order to prove Theorem 9, observe that a subset W C of size k is not a necessary committee if and only if there exists a completion where another size-k subset has a score strictly greater than the score of W. Formally, let P be a partial proﬁle and let Wk = {W C : |W | = k} be the set of subsets of size k. For a completion A of P and W, W Wk, deﬁne the score difference as

A(W, W ) = s(A, W ) s(A, W).

When A consists of a single set A(v) we write A(v)(W, W ) instead of A(W, W ).

Let C(P) be the set of completions of P. Again, when the proﬁle consists of a single voter v, we write C(P(v)) instead of C(P). Deﬁne the maximal score difference as

P(W) := max A C(P),W Wk A(W, W ).

Observe that W is not a necessary committee if and only if P(W) > 0. To compute P(W), we iterate over all sets W Wk, and for every W we compute P(W, W ) := max A C(P) A(W, W ). Once we compute P(W, W ) for every W Wk we are done, since P(W) = max W Wk P(W, W ). Now, let W Wk. Since r is an ABC scoring rule, the score of W in a completion A is s(A, W ) = P v V s(A(v), W ), therefore

P(W, W ) = max A C(P)

v V A(v)(W, W )

v V max A(v) C(P (v)) A(v)(W, W ) = X

P (v)(W, W ) .

The following lemma completes the proof of Theorem 9 by showing that P (v)(W, W ) can be computed in polynomial time for each voter v V .

Lemma 2. Let r be an ABC scoring rule and k a ﬁxed natural number. Computing P (v)(W, W ) is possible in polynomial time given a partial vote P(v) over a set C of candidates, and a pair of sets W, W Wk.

Proof sketch. Set S = Middle(v) (W W ). We call a subset R S feasible if there exists a completion A(v) of P(v) where Middle A(v) S = R. For feasible R S, set

R P (v)(W, W ) = max A(v) C(P (v)): Middle A(v) S=R (W, W , A(v)) .

Otherwise, deﬁne R P (v)(W, W ) = . We get that

P (v)(W, W ) = max R S R P (v)(W, W ). Since |S| 2k, there is a constant number of subsets of S. It can be shown that we can compute R P (v)(W, W ) in polynomial time for every R S.

Necessary Committee Members. A candidate c is a necessary committee member if for every completion A of P there exists a winning committee W for which c W. For an ABC rule r and a committee size k, we consider the computational problem Nec Mem k , where the input consists of a partial proﬁle P and a candidate c, and the goal is to determine whether c is a necessary committee member. Note that a necessary committee member can be a member of different winning committees in different completions. Thus, in contrast to Pos Com and Pos Mem, being able to solve Nec Com does not help deciding Nec Mem, because a candidate could be a necessary committee member without being a member of a necessary committee. We show that in the 3VA model we can ﬁnd the necessary members in polynomial time under approval voting.

Theorem 10. In the 3VA model, Nec Mem k is solvable in polynomial time under Approval Voting, for all ﬁxed k 1. In the linear model, Nec Mem k is solvable in polynomial time under AV and under binary Thiele rules. Theorem 11. In the linear model, Nec Mem k is solvable in polynomial time under Approval Voting and under every binary Thiele rule, for all ﬁxed k 1.

6 Representation under Incompleteness An important goal in committee voting concerns the representation of voters. Sufﬁciently large and cohesive groups of voters should be adequately represented in the committee. In this section, we investigate the problem of representation under incomplete preference information: Given a committee W and partial proﬁle P, does W possibly or necessarily provide some form of representation? We mainly focus on justiﬁed representation (Aziz et al. 2017), and discuss stronger representation axioms at the end of this section. For a (complete) approval proﬁle A and committee size k, a committee W C of size |W| = k satisﬁes justiﬁed representation (JR) w.r.t. A if for all G V with |G| n

k and | T v G A(v)| = , it holds that |W S v G A(v)| = . Aziz et al. (2017) show that it can be tested in polynomial time whether a given committee provides JR w.r.t. a given approval proﬁle (without incompleteness). Given a partial proﬁle P and a committee W, we consider two decision problems. In Pos JR, we ask whether there exists a completion A of P such that W satisﬁes JR w.r.t. A. In Nec JR we ask whether W satisﬁes JR w.r.t. every completion of P. In contrast to the decision problems we considered earlier, the committee size k is part of the input for both problems. We ﬁrst prove that a committee satisfying JR w.r.t. a given approval proﬁle A also satisﬁes JR w.r.t. a new approval proﬁle A that results from modifying A in certain ways. Lemma 3. Let W C be a committee satisfying JR with respect to a given approval proﬁle A. Then, W satisﬁes JR with respect to a modiﬁed approval proﬁle A if A is constructed in one of the following two ways: (i) a voter v V stops to approve a candidate not in W, i.e., A (v) = A(v) \ {c} for some c / W and A (u) = A(u) for all u = v; or (ii) a voter v V changes her approval set such that the modiﬁed approval set contains a candidate in W, i.e., A (v) W = and A (u) = A(u) for all u = v. Using this, we show tractability of Pos JR and Nec JR by proving that for each problem it is sufﬁcient to check whether W satisﬁes JR for one carefully chosen completion. Theorem 12. In the poset approval model, Pos JR and Nec JR are both solvable in polynomial time.

Proof sketch. We prove only Nec JR (and omit Pos JR for lack of space). Assume we are given a partial proﬁle P and a committee W of size k. For each voter v V , let Sv be the inclusion-maximal subset of candidates in Middle(v) satisfying Sv W = while respecting the partial order v over Middle(v). We set A(v) = Top(v) Sv for each voter v V . It can be shown that if W satisﬁes JR in A, then it also satisﬁes JR in any other completion A of P.

Note that if we treat k as a constant, we can use Theorem 12 to also check whether a given candidate is a possible member of a JR committee. This is because, for ﬁxed k, we can enumerate all size-k subsets containing c. We now turn our attention to two stronger representation axioms: proportional justiﬁed representation (PJR) and extended justiﬁed representation (EJR) require that cohesive groups of voters are represented proportionally to their size (Aziz et al. 2017; S anchez-Fern andez et al. 2017). Informally, if a group G V of voters satisﬁes both |G| ℓ n

k and | T v G A(v)| ℓfor some integer ℓ, then PJR and EJR require that G is represented ℓtimes by the committee. The axioms differ in the way that they deﬁne representation. (For formal deﬁnitions, refer to the full version of the paper.) Even for a complete approval proﬁle A, it is co NPcomplete to decide whether a given committee provides PJR or EJR w.r.t. A (Aziz et al. 2017, 2018). However, we show that this problem becomes tractable if we assume the committee size k to be ﬁxed. Our proof is based on a proof by Aziz et al. (2018), who show an analogous result for a ﬁxed number of candidates (instead of a ﬁxed committee size). Theorem 13. Given a committee W and a (complete) approval proﬁle A, testing whether W satisﬁes PJR or EJR is possible in time O(mk+2 n k). If the committee size is assumed to be ﬁxed, Theorem 13 implies that PJR and EJR can be veriﬁed efﬁciently in the case of complete information. This observation gives rise to computational questions regarding PJR and EJR under incompleteness: Given a committee W and a partial approval proﬁle P and assuming k is ﬁxed, can we decide in polynomial time whether W satisﬁes PJR or EJR for any or all of the completions of P? We leave this open for future work.

7 Concluding Remarks We studied computational aspects of approval-based committee voting under incomplete approval information. We adopted poset approval as a general model of incompleteness, along with the 3VA and linear special cases, and we focused on committees of a ﬁxed size. We established a quite broad picture of complexity for the problems of determining whether a given set of candidates is a possible or necessary committee for large classes of ABC rules. We also proved several results on the problems of possible and necessary committee members, albeit leaving some cases open for future work. Finally, we investigated the question of whether a given committee satisﬁes, possibly or necessarily, the representation axiom justiﬁed representation. The problem remains open for the stronger axioms of proportional and extended justiﬁed representation; we established that if the committee size is ﬁxed the potential source of hardness can only be the incompleteness. It seems promising to study the problem of possible and necessary committees also for other ABC rules such as sequential Phragm en or Rule X (Peters and Skowron 2020). Additional directions for future research include other models of incompleteness, and uncertainty in general, such as a model where voter attendance to the ballot is uncertain.

Acknowledgments

We thank J erˆome Lang for helpful discussions as well as Phokion Kolaitis and Julia Stoyanovich for insightful suggestions on modeling voter incompleteness. We also thank the anonymous reviewers for their helpful comments. The work of Jonas Israel and Markus Brill was supported by the Deutsche Forschungsgemeinschaft (DFG) under Grant BR 4744/2-1. The work of Aviram Imber and Benny Kimelfeld was supported by the US-Israel Binational Science Foundation (BSF) under Grant 2017753.

References Alcantud, J. C. R.; and Laruelle, A. 2014. Dis&Approval Voting: A Characterization. Social Choice and Welfare, 43(1): 1 10. Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justiﬁed Representation in Approval Based Committee Voting. Social Choice and Welfare, 48(2): 461 485. Aziz, H.; Elkind, E.; Huang, S.; Lackner, M.; S anchez Fern andez, L.; and Skowron, P. 2018. On the Complexity of Extended and Proportional Justiﬁed Representation. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI), 902 909. AAAI Press. Barrot, N.; Gourv es, L.; Lang, J.; Monnot, J.; and Ries, B. 2013. Possible Winners in Approval Voting. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT), 57 70. Springer-Verlag. Baumeister, D.; and Dennisen, S. 2015. Voter Dissatisfaction in Committee Elections. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1707 1708. IFAAMAS. Brams, S. J.; and Kilgour, D. M. 2014. Satisfaction Approval Voting. In Voting Power and Procedures, Studies in Choice and Welfare, 323 346. Springer. Cao, Z.; Qin, T.; Liu, T.; Tsai, M.; and Li, H. 2007. Learning to Rank: From Pairwise Approach to Listwise Approach. In ICML, volume 227 of ACM International Conference Proceeding Series, 129 136. ACM. Chevaleyre, Y.; Lang, J.; Maudet, N.; Monnot, J.; and Xia, L. 2012. New Candidates Welcome! Possible Winners with Eespect to the Addition of new Candidates. Mathematical Social Sciences, 64(1): 74 88. Felsenthal, D. S. 1989. On Combining Approval with Disapproval Voting. Behavioral Science, 34: 53 60. Garey, M. R.; and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Imber, A.; Israel, J.; Brill, M.; and Kimelfeld, B. 2021. Committee Voting with Incomplete Approvals. Technical report, arxiv:2103.14847 [cs.GT]. Konczak, K.; and Lang, J. 2005. Voting procedures with incomplete preferences. In Proceedings of the Multidisciplinary Workshop on Advances in Preference Handling (MPREF), 124 129.

Lackner, M.; and Skowron, P. 2021. Multi-Winner Voting with Approval Preferences. Technical report, ar Xiv:2007.01795 [cs.GT]. Lang, J. 2020. Collective Decision Making under Incomplete Knowledge: Possible and Necessary Solutions. In Proceedings of the 29th International Joint Conference on Artiﬁcial Intelligence (IJCAI) Survey Track, 4885 4891. IJCAI. Libkin, L. 2016. SQL s Three-Valued Logic and Certain Answers. ACM Transactions on Database Systems, 41(1): 1:1 1:28. Lu, T.; and Boutilier, C. 2013. Multiwinner Social Choice with Incomplete Preferences. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI), 263 270. AAAI Press. Peters, D.; and Skowron, P. 2020. Proportionality and the Limits of Welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (ACM-EC), 793 794. ACM Press. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Basanta Val, P.; and Skowron, P. 2017. Proportional Justiﬁed Representation. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI), 670 676. AAAI Press. Terzopoulou, Z.; Karpov, A.; and Obraztsova, S. 2021. Restricted Domains of Dichotomous Preferences with Possibly Incomplete Information. In Proceedings of the 35th AAAI Conference on Artiﬁcial Intelligence (AAAI), 5726 5733. AAAI Press. Thiele, T. N. 1895. Om Flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, 415 441. Xia, L.; and Conitzer, V. 2011. Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders. Journal of Artiﬁcial Intelligence Research, 41: 25 67. Zhou, A.; Yang, Y.; and Guo, J. 2019. Parameterized Complexity of Committee Elections with Dichotomous and Trichotomous Votes. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 503 510. IFAAMAS.