DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections

1 Introduction

The problem of selecting a committee from a given set of candidates arises in multiple domains; it ranges from political sciences (e.g., selecting the parliament of a country) to recommendation systems (e.g., selecting the movies to show on Netflix). Formally, given a set C of m candidates (politicians and movies, respectively), a set V of n voters (citizens and Netflix subscribers, respectively) give their ordered preferences over all candidates c ∈ C to select a committee of size k. These preferences can be stated directly in case of parliamentary elections, or they can be derived based on input, such as when Netflix subscribers' viewing behavior is used to derive their preferences. In this paper 1 , we focus on selecting a committee using direct, ordered, and complete preferences.

∗This work was supported, in part, by Julia Stoyanovich's NSF grants No. 1916647, 1934464, and 1916505.

Which committee is selected depends on the committee selection rule, also called the multiwinner voting rule. Examples of commonly used families of rules when a complete ballot of each voter is given are Condorcet principle-based rules [Faliszewski et al., 2016], approval-based voting rules [Faliszewski et al., 2016; S´anchez-Fern´andez et al., 2017], and ordinal preference ballot-based voting rules like k-Borda and β-Chamberlin-Courant (β-CC) [Elkind et al., 2017; Faliszewski et al., 2017]. We refer readers to Section 2.2 of [Faliszewski et al., 2017] for further details. In this paper, we focus on ordinal preference-based rules.

However, these rules can create or propagate biases by systematically harming candidates coming from historically disadvantaged groups [Bredereck et al., 2018; Celis et al., 2018]. Hence, diversity constraints on candidate attributes were introduced to mitigate this. However, voters may be divided into predefined populations under one or more attributes, which may be different from candidate attributes. For example, voters in Figure 1b are divided into "California" and "Illinois" populations under the "state" attribute. The models that focus on candidate attributes alone may systematically under-represent smaller voter populations.

Example 1. An election E consists of m = 4 candidates (Figure 1a) and n = 4 voters giving complete, ordered preference (Figure 1b) to select a committee of size k = 2. Candidates and voters have one attribute each (gender and state, respectively). The k-Borda 2 winning committee for each voter population is {c1, c2} for California and {c4, c2} for Illinois.

1 An extended version of this paper is available at [Relia, 2021].

2 The Borda rule associates score m- i with the ith position, and k-Borda selects candidates with the k highest Borda scores.

Suppose that we impose a diversity constraint that requires the committee to have at least one candidate of each gender and a representation constraint that requires at least one candidate from the winning committee of each state. Observe that the highest-scoring committee consists of {c1, c2} (score = 17), which is representative but not diverse, since both candidates are male. Further, the highest-scoring diverse committee consisting of {c1, c3} (score = 13) is not representative because it does not include any winning candidates from Illinois, the smaller state. The highest-scoring diverse and representative committee is {c2, c3} (score = 12).

This example illustrates the inevitable utility cost due to enforcing additional constraints.

In contrast to prior work in computational social choice, we incorporate voter attributes that are separate from candidate attributes. Also, our work is different from "proportional representation" [S´anchez-Fern´andez et al., 2017; Brill et al., 2018; Monroe, 1995], where the number of candidates selected in the committee from each group is proportional to the number of voters preferring that group, and from its variants such as "fair" representation [Koriyama et al., 2013]. All these approaches dynamically divide the voters based on the cohesiveness of their preferences. Another related work, multi-attribute proportional representation [Lang and Skowron, 2018], couples candidate and voter attributes. An important observation we make here is that, even if the attributes of the candidates and of the voters coincide, it may still be important to treat them separately. This is because having a female candidate on the committee, for example, is different from having a candidate on the committee who is preferred by the female voters, and who themselves may or may not be female. This observation has implications on United Nations' sustainable development goals on equality.

Contributions. In this paper, we define a model that treats candidate and voter attributes separately during committee selection, and thus enables selection of the highest-scoring diverse and representative committee. We classify the computational complexity of using our model, study the limits of approximability, and develop a heuristic algorithm. Finally, we present an experimental evaluation using real and synthetic datasets, in which we show the efficiency of our algorithm, analyze the feasibility of committee selection and illustrate the utility trade-offs.

2 RelatedWork

Our work is motivated by the work on constrained multiwinner elections. Goalbase score functions, which specify an arbitrary set of logic constraints and let the score capture the number of constraints satisfied, could be used to ensure diversity [Uckelman et al., 2009]. Using diversity constraints over multiple attributes in single-winner elections is NP-hard [Lang and Skowron, 2018]. Also, using diversity constraints over multiple attributes in multiwinner elections and participatory budgeting is NP-hard, which has led to approximation algorithms and matching hardness of approximation results by Bredereck et al. [2018] and Celis et al. [2018]. Finally, due to the hardness of using diversity constraints over multiple attributes in approval-based multiwinner elections

[Brams, 1990], these have been formalized as integer linear programs (ILP) [Potthoff, 1990]. In contrast, Skowron et al. [2015] showed that ILP fails in the real world when using ranking-based proportional representation rules.

Overall, the work by Bredereck et al. [2018], Celis et al. [2018], and Lang and Skowron [2018] is closest to ours but we differ as we: (i) consider elections with predefined voter populations under one or more attributes, (ii) delineate voter and candidate attributes even when they coincide, and (iii) consider diversity and representation constraints.

3 Preliminaries and Notation

Multiwinner Elections. Let E = (C, V ) be an election consisting of a candidate set C = {c1, . . . , cm} and a voter set V = {v1, . . . , vn}, where each voter v ∈ V has a preference (ranked) list ≻v over m candidates. posv(c) denotes the position of candidate c ∈ C in the ranking of voter v ∈ V , where the most preferred candidate has position 1 and the least preferred has position m.

Given E = (C, V ) and k ∈ [m] (for k ∈ N+, [k] = {1, . . . , k}), a multiwinner election selects a k-sized subset of candidates (or committee) W using a multiwinner voting rule f (discussed later) such that the score of the committee f(W) is the highest. Ties are broken using a pre-decided order.

Candidate Groups. The candidates have µ attributes, A1, . . . ,Aµ : µ ∈ Z and µ ≥ 0. ∀ i ∈ [µ], Ai partitions the candidates into gi ∈ [m] groups, A(i,1), . . . , A(i,gi) ⊆ C. For example, candidates in Figure 1a have gender attribute (µ = 1) with disjoint groups, male and female (g1 = 2). Overall, the set G of all such arbitrary and potentially non-disjoint groups is A(1,1), . . . , A(µ,gµ) ⊆ C.

Voter Populations. The voters have π attributes, A′1 , . . . ,A′π : π ∈ Z and π ≥ 0, which may be different from the candidate attributes. ∀ i ∈ [π], A′i partitions the voters into pi ∈ [n] populations, P(i,1), . . . , P(i,pi) ⊆ V . For example, voters in Figure 1b have state attribute (π = 1), which has populations California and Illinois (p1 = 2). Overall, the set P of all such predefined and potentially non-disjoint populations will be P(1,1), . . . , P(π,pπ) ⊆ V .

Additionally, we are given WP , the winning committee ∀ P ∈ P. We limit the scope of WP to be a committee instead of a ranking of k candidates because using a committee selection rule such as CC rule does not return a complete ranking. Committee Selection Rules. In this paper, we focus on committee selection rules f that are based on single-winner positional voting rules and are monotone and submodular (∀A ⊆ B, f(A) ≤ f(B) and f(B) ≤ f(A) + f(B \ A)).

Definition 1. Chamberlin-Courant (CC) rule [1983]: The CC rule associates each voter with their most preferred candidate in the committee. The score of a committee is the sum of scores given by voters to their associated candidate. β-CC uses the Borda rule to assign scores to each voter's candidate.

Definition 2. Monroe rule: The Monroe rule [1995] dynamically divides the n voters into π populations based on the cohesiveness of their preferences where π = k (assuming k divides n). Then, each subpopulation's most preferred candidate is selected into the k-sized committee. Formally, ∀ P ∈ P, select c for P : maxc∈C(fP (c)).

A special case of submodular functions are separable functions: score of a committee W is the sum of the scores of individual candidates in the committee. Formally, f(W) = ∑c∈W f(c) [Bredereck et al., 2018]. Monotone and separable rules are natural and are considered good when the goal is to shortlist a set of individually excellent candidates:

Definition 3. k-Borda rule The k-Borda rule outputs committee of k candidates with the k highest Borda scores.

4 DiRe Committee Model

In this section, we formally define a model to select a diverse and representative committee, namely the DiRe committee, and compare our model to existing related models.

Definition 4. Unconstrained Committee Winner Determination (UCWD): We are given a set C of m candidates, a set V of n voters such that each voter v ∈ V has a preference list ≻v over m candidates, a committee selection rule f, and a committee size k ∈ [m]. Let W denote the family of all size-k committees. The goal of UCWD is to select a committee W ∈ W that maximizes f(W).

We introduce the diversity and representation constraints such that their minimum value is 1 as each candidate group and voter population deserve at least one candidate in the committee. This replicates real-world settings like the United Nations (UN) charter, which guarantees at least one representative to each member country in the UN General Assembly, independent of the country's population. Theoretically, all results in this paper hold even if the minimum value is 0.

DiversityConstraints. These constraints, denoted by ℓDG ∈ [min(k, |G|)] for each G ∈ G, enforce at least ℓDG candidates from the group G to be in the committee W. Formally, ∀ G ∈ G, |G∩W| ≥ ℓDG .

Representation Constraints. These constraints, denoted by ℓRP ∈ [1, k] for each voter population P ∈ P, enforce at least ℓRP candidates from the population P 's committee WP to be in the committee W. Formally, ∀ P ∈ P, |WP ∩W| ≥ ℓRP .

Definition 5. (µ, π)-DiRe Committee Feasibility ((µ, π)- DRCF): We are given an instance of E = (C, V ), k ∈ [m], G under µ attributes and ∀ G ∈ G, ℓDG , and P under π attributes and ∀ P ∈ P, ℓRP and WP . Let W denote the family of all size-k committees. The (µ, π)-DRCF problem selects committees W ∈ W such that |G ∩ W| ≥ ℓDG ∀ G ∈ G and |WP ∩W| ≥ ℓRP ∀ P ∈ P. These are called DiRe committees.

If a committee selection rule f is also an input to the feasibility problem, we get the (µ, π, f)-DRCWD problem:

Definition 6. (µ, π, f)-DiRe CommitteeWinner Determination ((µ, π, f)-DRCWD): Given (µ, π)-DRCF and f, the (µ, π, f)-DRCWD selects the highest scoring DiRe committee. Observation 1. (µ, π, f)-DRCWD is a generalized version of (µ, π)-DRCF and UCWD.

Finally, as our model provides the flexibility to specify the diversity and representation constraints and to select the voting rule, the diverse committee problem [Bredereck et al., 2018; Celis et al., 2018] and the apportionment problem [Brill et al., 2018; Hodge and Klima, 2018] are special cases of (µ, π, f)-DRCWD. See [Relia, 2021] for formal formulations.

5 Complexity Results

Selecting a committee using a submodular function such as the CC rule is NP-hard, known via reduction from exact 3cover [Procaccia et al., 2008]. Selecting a diverse committee when a candidate belongs to three groups is also NP-hard, known via reductions from 3-dimensional matching [Bredereck et al., 2018] and 3-hypergraph matching [Celis et al., 2018]. However, these hardness results are fragmented over several papers and they use reductions from several wellknown NP-hard problems. Next, we introduce representation constraints and hardness due to its use is unknown. Hence, we provide a complete computational classification 3 of (µ, π, f)- DRCWD using reductions from single well-known NP-hard problem, the vertex cover problem, in line with the approach used in [Chakraborty and Kolaitis, 2021]. All proofs can be found in the extended version of this paper [Relia, 2021].

Theorem 1. Let µ, π ∈ Z : µ, π ≥ 0 and f be a monotone committee selection rule, then (µ, π, f)-DRCWD is NP-hard.

Corollary 1. Classification of Complexity.

1. If ∀µ ∈ Z : µ ≥ 0, ∀π ∈ Z : π ≥ 0, and f is a submodular function, then (µ, π, f)-DRCWD is NP-hard.
2. If ∀µ ∈ [0, 2], π = 0, and f is a separable function, then (µ, π, f)-DRCWD is in P.
3. If ∀µ ∈ Z : µ ≥ 3, π = 0, and f is a separable function, then (µ, π, f)-DRCWD is NP-hard.
4. If ∀µ ∈ Z : µ ≥ 0, ∀π ∈ Z : π ≥ 1, and f is a separable function, then (µ, π, f)-DRCWD is NP-hard.

5.1 Tractable Case

Theorem 2. [Theorem 21, Corollary 22 in full-version of Celis et al. [2018]] The diverse committee feasibility problem can be solved in polynomial time when µ = 2.

Without loss of generality (W.l.o.g.), the above theorem holds when µ = 2. Hence, it holds for µ ∈ [0, 2]. Therefore, the following lemma and Corollary 1(2) follows:

Lemma 1. If µ ∈ [0, 2], π = 0, and f is a monotone, separable function, then (µ, π, f)-DRCWD is in P.

5.2 Hardness Results

NP-hard problem used. We reduce from the vertex cover problem on 3-regular, 2-uniform 4 hypergraphs [Garey and Johnson, 1979; Alimonti and Kann, 1997].

3 All hardness results are under the assumption P ̸= NP.

4 The size of hyperedges has implications on the inapproximability results. We use 2-uniform hypergraphs for the complexity results.

Definition 7. Vertex Cover (VC) problem: Given a graph H consisting of a set of m vertices X = {x1, x2, . . . , xm} and a set of n edges E = {e1, e2, . . . , en} where each e ∈ E connects two vertices in X, then VC S ⊆ H is where ∀ e ∈ E, e ∩ S ̸= ϕ. The VC problem is to find the minimum size S.

(µ, π, f)-DRCWD w.r.t. Diversity Constraints

When π = 0, (µ, π, f)-DRCWD is related to the diverse committee selection problem. However, the hardness of (µ, π, f)-DRCWD when µ ≥ 3 does not follow the hardness of the diverse committee selection problem.

More specifically, Theorem 9 of Bredereck et al. [2018] uses a reduction from 3-Dimensional Matching that only holds for instances when the number of groups that a candidate can belong to is exactly 3. Also, lower bound and upper bound is set to 1, which is mathematically different from our setting where we only allow lower bounds. On the other hand, Theorem 6 ("NP-hardness of feasibility: ∆ ≥ 3" 5 ) of Celis et al. [2018] uses two reductions: the first reduction from∆- hypergraph matching is indeed for the case when ∆ ≥ 3 but is limited to instances when the lower bound is 0 and the upper bound is 1, which is a trivial case in our setting. Moreover, the reduction from ∆-hypergraph matching uses a different problem as when ∆ ̸= ∆′ , the ∆-hypergraph matching and ∆′ -hypergraph matching are separate problems. The second reduction from 3-regular VC is for instances when ∆ = 3.

Hence, in this section, we give reductions such that our result holds ∀µ ∈ Z : µ ≥ 3, even when ∀G ∈ G, ℓDG = 1. The next two theorems help us prove Corollary 1(3).

Theorem 3. If ∀µ ∈ Z : µ ≥ 3 and µ is an odd number, π = 0, and f is a monotone, separable function, then (µ, π, f)-DRCWD is NP-hard, even when ∀G ∈ G, ℓDG = 1.

Proof Sketch. We create an instance such that |C| = |V | = m+(m·(2µ2 -7µ+3)) and |W| = k+mµ2 -3mµ. The reduction conforms to the real-world stipulations: (i) each candidate attribute Ai, ∀i ∈ [µ], partitions all the candidates into two or more groups and (ii) either no two attributes partition the candidates in the same way or if they do, the lower bounds for the two attributes are not the same. If any two attributes Ai and Aj : i ̸= j violates stipulation (ii), it implies that Ai and Aj are mathematically equivalent.

Theorem 4. If ∀µ ∈ Z : µ ≥ 3 and µ is an even number, π = 0, and f is a monotone, separable function, then (µ, π, f)-DRCWD is NP-hard, even when ∀G ∈ G, ℓDG = 1.

(µ, π, f)-DRCWD w.r.t. Representation Constraints

We now study the computational complexity of (µ, π, f)- DRCWD due to the presence of voter attributes. The following theorem helps us prove Corollary 1(4).

Theorem 5. If µ = 0, ∀π ∈ Z : π ≥ 1, and f is a monotone, separable function, then (µ, π, f)-DRCWD is NP-hard, even when ∀P ∈ P, ℓRP = 1.

Proof Sketch. Create an instance where |C| = m+ (n · m), |V | = n2 , and |W| = k. The reduction conforms to the stipulations analogous to the ones for candidate attributes.

5 In Celis et al. [2018], ∆ denotes "the maximum number of groups in which any candidate can be".

Corollary 2. If ∀µ ∈ Z : µ ≥ 0, ∀π ∈ Z : π ≥ 1, and f is a monotone, separable function, then (µ, π, f)-DRCWD is NP-hard, even when ∀G ∈ G, ℓDG = 1 and ∀P ∈ P, ℓRP = 1.

(µ, π, f)-DRCWD w.r.t. Submodular Scoring Function

Chamberlin-Courant (CC) rule is a well-known monotone, submodular scoring function [Celis et al., 2018], which we use for our proof. The novelty of our reduction is that it holds for determining the winning committee using CC rule that uses any positional scoring rule with scoring vector s = {s1, . . . , sm} such that s1 = s2, sm ≥ 0, and ∀i ∈ [3,m- 1], si ∈ Z : si ≥ si+1 and s2 > si.

The following statements prove Corollary 1(1).

Theorem 6. If f is a monotone, submodular function, then (µ, π, f)-DRCWD is NP-hard even when µ = 0 and π = 0.

Corollary 3. If ∀µ ∈ Z : µ ≥ 0, ∀π ∈ Z : π ≥ 0, and f is a monotone, submodular function, then (µ, π, f)-DRCWD is NP-hard, even when ∀G ∈ G, ℓDG = 1 and ∀P ∈ P, ℓRP = 1.

5.3 Inapproximability

The hardness of (µ, π, f)-DRCWD is mainly due to the hardness of (µ, π)-DRCF, even when constraints are set to 1. Hence, we now study the inapproximability of (µ, π)-DRCF.

We can try to reformulate representation constraints as diversity constraints. However, this is not possible as each candidate attribute partitions all m candidates into groups and ℓDG ∈ [min(k, |G|)], ∀ G ∈ G. However, for representation constraints, WP , ∀ P ∈ P, contains only k candidates and the remainder m - k candidates consisting of C \ WP , ∀ P ∈ P, may never be selected, thus making the reformulation non-trivial. Even if we relax range of ℓDG , ∀ G ∈ G, from [1,min(k, |G|)] to [0,min(k, |G|)], the following settings are different and we may not carry out reformulations:

Observation 2. ∀µ ∈ Z and ∀π ∈ Z, the following settings of the (µ, π)-DRCF problem are not equivalent: (i) µ=0 and π ≥ 1, (ii) µ ≥ 3 and π = 0, and (iii) µ ≥ 1 and π ≥ 1.

These settings differ as |G| and |WP | have implications. For instance, using both the constraints and using only representation constraints are mathematically as different as the vertex cover problem on hypergraphs and the vertex cover problem on k-uniform hypergraphs, respectively.

Definition 8. (µ, π)-DRCF-size-optimization: In the (µ, π)-DRCF-size-optimization problem, the aim is to find a minimum-size committee W ⊆ C such that W satisfies |G∩W| ≥ ℓDG ∀ G ∈ G and |WP ∩W| ≥ ℓRP ∀ P ∈ P.

Theorem 7. For ε > 0, ∀µ ∈ Z : µ ≥ 3, and π = 0, (µ, π)-DRCF-size-optimization problem is inapproximable within (1-ε)· (ln µ-O(ln ln µ)), even when ℓDG = 1 ∀ G ∈ G.

Theorem 8. For ε > 0, ∀µ ∈ Z : µ ≥ 1, and ∀π ∈ Z : π ≥ 1, (µ, π)-DRCF-size-optimization problem is inapproximable within a factor of (1 - ε)· ln (|G| + |P|), even when ℓDG = 1 ∀ G ∈ G and ℓRP = 1 ∀ P ∈ P.

Proof Sketch. We first give a reduction from hitting set (HS) to (1, 1)-DRCF. Next, as the HS problem is equivalent to the minimum set cover problem [Niedermeier and Rossmanith, 2003], the latter's inapproximability [Dinur and Steurer, 2014] holds for our problem.

Theorem 9. For ε > 0, µ = 0, and ∀π ∈ Z : π ≥ 1, (µ, π)-DRCF-size-optimization problem, assuming the UGC, is inapproximable within k - ε, even when ℓRP = 1 ∀ P ∈ P.

Proof Sketch. Assuming the Unique Games Conjecture (UGC) [Khot, 2002], vertex cover problem on k-uniform hypergraphs, for any integer k ≥ 2, is inapproximable within k - ε [Bansal and Khot, 2010], which we reduce from 6 .

6 Heuristic Algorithm

Our model is useful from the social choice theory perspective but it is computationally hard. Hence, we take a pragmatic approach to evaluate its efficiency in practice. We develop a two-stage heuristic algorithm motivated, in part, from distributed constraint satisfaction [Russell and Norvig, 2002].

6.1 DiReGraphs

We represent an instance of the (µ, π)-DRCF problem from Figure 1 as a DiReGraph (Figure 2). The quadrilaterals correspond to constraints and ellipses to candidates. Specifically, there is the global committee size constraint k (Level A), candidates (B), unary constraints ℓDG and ℓRP (C), and the DiRe committee (D). Edges connecting (B) and (C) depend on the candidate's membership in G or WP . The idea is to have a

6 For Theorem 9, we assume UGC holds as the result that showed pseudorandom sets in the Grassmann graph have near-perfect expansion completed the proof of 2-to-2 Games Conjecture [Khot et al., 2018], which is a significant evidence towards proving the UGC. Moreover, GapUG( 1 2 , ε) is NP-hard, i.e., a weaker version of the UGC holds with completeness 12 (See [Dinur et al., 2018] and "Evidence towards the Unique Games Conjecture" in [Khot et al., 2018]). Without assuming UGC, the result when µ = 0 and π ≥ 1 will change. For ε > 0, the problem is inapproximable within k - 1 - ε for k ≥ 3 [Dinur et al., 2005] and within √2 - ε for k = 2 [Khot et al., 2018].

Algorithm 1 DiRe Committee Algorithm

Input:

variables X = {X1, . . . , X|G|+|P|}

domain D = (D1, . . . ,D|G|+|P|) : each Di is G or WP

constraints S = {S1, . . . , S|G|+|P|} : each Si is ℓDG or ℓRP

Output: set W of committees : ∀W ∈ W, |W ∩Di| ≥ Si

• 1: Create DiReGraph DiReG
• 2: SG = subgraph of nodes on levels B & C of DiReG
• 3: SCC = strongly connected components of SG
• 4: for each scci, sccj ∈ SCC do
• 5: for each Xu = {Xi∪ Xj} : Xi ∈ scci, Xj ∈ sccj do
• 6: if !pairwise feasible(Xu, D, S) return false
• 7: end for
• 8: end for
• 9: for each scc in SCC do
• 10: XSCC = list of Xi for each Si at level C of scc
• 11: if !pairwise feasible(XSCC, D, S) return false
• 12: end for
• 13: Recreate DiReG using reduced D
• 14: return heuristic backtrack({}, DiReG, X, D, S)

"network flow" from A to D such that all nodes on level C are visited. Specifically, select k candidates (A) from m candidates (B) such that the in-flow τ at the unary constraint nodes (C) is at least ℓDG or ℓRP where τ = |W∩G| or τ = |W∩WP |. When τ ≥ ℓDG or τ ≥ ℓRP , there will be a DiRe committee (D). Example 2. DiReGraph: Consider the election instance in Figure 1. The candidate c2 is a male who is in winning committees of both the states, namely CA (California) and IL (Illinois). Hence, c2 in DiReGraph (Figure 2) is connected to three sets of constraints, one each for male and two states.

6.2 DiRe Committee Algorithm

The Algorithm 1 has two stages: (i) preprocessing reduces the search space used to satisfy the constraints and efficiently finds infeasible instances, and (ii) heuristic search of candidates decreases the number of steps needed either to find a feasible committee, or return infeasibility.

Preprocessing. Find the strongly connected components of the graph in time linear in m and n. We only do the pairwise feasibility as three-way (and higher) feasibility tests increase the computational time without improving the scope of finding infeasibility [Russell and Norvig, 2002].

Inter-component pairwise feasibility: Select Xi, Xj corresponding to Si, Sj on level C of DiReGraph, one each from different components of SCC. Do a pairwise feasibility check for each pair and return infeasibility if any one pair of variables can not return a valid committee. The correctness and completeness of this step are easy. If there are more constraints than the available candidates or if a pair of constraints are pairwise infeasible, then it is impossible to find a feasible solution. For intra-component pairwise feasibility, repeat the above procedure but within a component.

Reducing domain: If the algorithm reaches this stage, reduce the domain by removing candidates who, when selected, always return a pairwise infeasible solution.

100

50

0

(a) timed out instances

Heuristic Backtracking. Use depth-first search for backtracking. Specifically, choose one Xi at a time, and backtrack when Xi has no legal values left to satisfy the constraint. This technique repeatedly chooses an unassigned variable, and then tries all values in its domain, trying to find a solution. If an infeasibility is returned, traverse back by one step and move forward by trying another value.

Select unsatisfied variable: The "minimum-remainingvalues" heuristic chooses the variable having the fewest legal values. It picks a variable that is most likely to cause a failure, thereby pruning the search tree as infeasibility may be returned, in turn, avoiding additional searches.

Sort most favorite candidates: This heuristic sorts the candidates in decreasing order of its out-degree. For example, the ordering of candidates (Figure 2) will be c2 (out-degree = 3), c1, c4 (2), and c3 (1). This reduces the branching factor on future choices by selecting the candidate that is involved in the largest number of constraints, which means they help satisfy the highest proportion of constraints. Next, for completeness and to get multiple DiRe committees, do a "shift-left" such that the second candidate becomes the first and so on. (See [Relia, 2021] for an example explaining the algorithm.)

7 Empirical Analysis

We assess the efficiency of the algorithm and the effect of enforcing the constraints. [Code: https://github.com/KunalRelia/DiReCommittees]

Setup. We run experiments on a Macbook Pro(R) (Docker; 2.2 GHz 6-Core Intel(R) Core i7; 2.2GHz; 16 GB RAM; MacOS Big Sur (v11.1); Python 3.7). We use previously defined voting rules and set constraints at random.

Real Data: The United Nations Resolutions dataset [Voeten, 2014] consists of 193 countries voting for 81 resolutions presented in the UN General Assembly in 2014. We select a 12-sized DiRe committee. Each candidate has two attributes and the voter has one. The Eurovision dataset [Kaggle, 2019] consists of 26 countries ranking the songs performed by each of the 10 finalist countries. We select a 5-sized DiRe committee. Each candidate has two attributes and voter has one.

SynData 1: We set k = 6, n = 100, and m = 50. We generate complete preferences using Repeated Selection Model by setting selection probability Πi,j to replicate Mallows' [Mallows, 1957] model (ϕ = 0.5, random reference ranking σ) (Theorem 3, [Chakraborty et al., 2021]) and preference probability p(i) = 1, ∀i ∈ [m]. We randomly divide the can-

% timed out didates and voters into groups and populations, respectively. SynData 2: We use the same setting as SynData 1 except we fix µ and π to 2 and vary the cohesiveness by setting Πi,j to replicate Mallows' model's ϕ ∈ [0.1, 1], in increments of 0.1.

Efficiency of Heuristic Algorithm. All experiments in this section combine instances of k-Borda and β-CC (no significant difference in the running time; paired Student's t-test, p > 0.05). We present results for the Monroe rule separately. Algorithm is efficient: Only 18.90% of 525 instances timed out at 2000 sec (vs 93.71% using a brute-force algorithm). Among the instances that did not time out, the mean running time was 566.48 sec (standard deviation (sd) = 466.66) for k-Borda and β-CC, and 724.39 sec (sd = 575.31) for Monroe (Figure 3). Sparse DiReGraphs increased the efficiency.

Comparison with ILP: Our algorithm, which (i) handles constraints and any committee selection rule and (ii) terminated in (avg) 724 sec, has a clear edge over ILP [Skowron et al., 2015] as it scales linearly. Promisingly, the first committee returned by the algorithm in <120 sec was the winning DiRe committee among 63% of all instances.

Feasibility andCost of Fairness. All experiments consider each rule separately (paired Student's t-test, p < 0.05).

There was a negative correlation between the maximum proportion of unsatisfied constraints and ϕ, for all the three scoring rules (mean Pearson's ρ = -0.95, p <0.05). It was easier to satisfy the constraints when the cohesiveness (ϕ) was high, which led to lower infeasibility (Figure 4).

Real Datasets. The mean ratio of utilities of constrained to unconstrained committees was 0.93 (sd = 0.08). Importantly, the algorithm always terminated in under 102 sec.

8 Conclusion

With diversity in multiwinner elections becoming necessary, we showed that only diversity can do more harm than good as its cost may disproportionately be paid more by historically under-represented voter population. Hence, we developed (µ, π, f)-DRCWD model, which enforces diversity and representation constraints. We studied its computational properties theoretically and empirically. We also delineate the candidate and voter attributes even when they coincide as just like correlation does not imply causation, we observe that diversity does not imply representation and vice versa. This has relevance to equality-related United Nations' sustainable development goals. (See [Relia, 2021] for full acknowledgement.)