Multiwinner Voting with Fairness Constraints

1 Introduction

The problem of selecting a committee from a set of candidates given the preferences of voters is called multiwinner voting and arises in various social, political, and e-commerce settings; from electing a parliament, to choosing a committee, to selecting products to display. Formally, there is a set C of m "candidates" that can be selected (i.e., people, products, or other items) and a set A of n "voters" who have (possibly incomplete) preference list over the m candidates; we assume these lists are given. The goal is to select a subset of C of size k based on these preferences.

It remains to specify how the selection will be made. One common approach is to define a "total" score function scoreA : 2C → R≥0 which gives a score that depends on the voters' preferences to each potential committee. If the voter set A is clear from the context, we use score for short. This reduces the selection to an optimization problem: choose a committee of size k that maximizes the score. Different views on the desired properties of the selection process have led to a number of different scoring rules and, consequently, to a variety of different algorithmic problems. Prevalent examples include committee scoring rules [Aziz et al., 2017b; Elkind et al., 2014], approval-based rules [Aziz et al., 2017a], OWA-based rules [Skowron et al., 2015b], variants of the Monroe rule [Betzler et al., 2013; Monroe, 1995; Skowron et al., 2015a] and the goalbase rules [Uckelman et al., 2009].

However, it has been shown that voting rules, in the most general sense, can create or propagate biases; e.g., negatively affecting the fraction of women in the US legislature [Representation2020, 2017], and resulting in an electorate that under-represents minorities [Faliszewski et al., 2016]. Furthermore, such algorithmic biases have been shown to influence and reinforce human stereotypes [Kay et al., 2015]. An increasing awareness of such problems has led governments to generic [Bundy, 2017] and specific [Zealand, 1986] recommendations that aim to ensure sufficient representation of minority populations.

In response, "proportional representation" rules [Monroe, 1995], that represent the electorate proportionately in the elected body, have been developed. Formally, let P1, . . . , Pp ⊆ [m] be p disjoint groups of candidates where i ∈ {1, . . . , p} represents a given group. For any i ∈ [p], let fi be the fraction of voters who belong to (or, more generally, prefer) group i. Then, a voting rule achieving full proportionality would ensure that the selected committee S satisfies ⌊k·fi ⌋ ≤ |S∩Pi| ≤ ⌈k·fi ⌉; [Brill et al., , Definition 5]. Proportional representation schemes include the proportional approval voting rule [Brill et al., ] and the Chamberlain Courant rule [1983]. Other approaches consider different notions of "fairness" in representation; e.g., in degressive proportionality it is argued that minorities should have disproportionately many representatives.

We present the first algorithmic framework for multiwinner voting problems that can (1) incorporate general notions of fairness with respect to arbitrary group structures (e.g., satisfying fairness across multiple attributes simultaneously) and (2) outputs a subset that maximizes the given score function subject to these constraints. This requires the development of new approximate algorithms (Section 6) and hardness of approximation results (Section 5) which depend on both the score function and the structure of the fairness constraints. Empirically, we show that existing multiwinner voting rules may introduce bias and that our approach not only ensures fairness, but does so with a score that is close to the (unconstrained) optimal (see Section 7).

2 Our Contributions

Model. In a multiwinner voting setting, we are given m candidates, n voters that each has a (potentially incomplete and/or non-strict) preference list over the m candidates, a score function score : 2[m] → R≥0 defined by these lists, and a desired number k ∈ [m] of winners. In addition, to consider fair solutions, we are given arbitrary (potentially non-disjoint) groups of candidates P1, . . . , Pp ⊆ C, and fairness constraints on the selected winner set S of the form: ℓi ≤ |S ∩ Pi| ≤ ui, ∀i ∈ [p] for given numbers ℓ1, . . . , ℓp, u1, . . . , up ∈ Z≥0.

The goal of the constrained multiwinner voting problem is to select a committee of size k that maximizes score(S) and satisfies all fairness constraints. If the score function is monotone and submodular we call the problem the constrained MS multiwinner voting problem. This includes the well-studied Chamberlin-Courant (CC) rule, the Monroe rule, the OWAbased rules and the goalbase rules.

Results. The algorithmic problems that arise largely remain NP-hard, hence we focus on developing approximation algorithms. An important practical parameter, that also plays a role in the complexity of the constrained multiwinner voting problem, is the maximum number of groups to which a candidate can belong; we denote it by ∆. In real-world situations, we expect ∆ to be a small constant, i.e., each candidate only belongs to a few groups. Our main results (classified by the kind of fairness parameters) are summarized in Tables 1 and 2.

When ∆ = 1, e.g., when the groups partition the candidates, we present a (1 - 1/e)-approximation algorithm (Theorem 14) which is optimal given the (1-1/e-ε)-hardness of approximation result by [Nemhauser et al., 1978]. However, when ∆ ≥ 3, unlike the unconstrained case, even checking whether there is a feasible solution becomes NP-hard (Theorem 6). The problem of finding a solution that violates cardinality or fairness constraints up to any multiplicative constant factor remains NP-hard (Theorem 7 and 8). Moreover, even if the feasibility is guaranteed, the problem remains hard to approximate within a factor of Ω(log∆/∆) (Theorem 9).

To bypass this issue, we assume that the problem instance always has a feasible solution, and suggest natural sufficient conditions that guarantee feasibility. For instance, if the fraction of each group in the selected committee is allowed some slack as compared to their proportion in the set of candidates (ℓi ≤ k(|Pi|/m- 0.05) and ui ≥ k(|Pi|/m+ 0.05)), then a random committee of size k is feasible with high probability. When feasibility is guaranteed, for the class of MS voting rules we give a near-optimal bi-criterion approximation algorithm that only violates each fairness constraint by a small multiplicative factor (Theorem 11).

Techniques The algorithmic results combine two existing tools that have been extensively used in the monotone submodular maximization literature. The first, "multilinear extension" (Definition 10), extends the discrete MS score function to a continuous function over a relaxed domain. By applying a continuous greedy process via multilinear extension, a fractional solution with a high score can be computed efficiently. The second is to round the fractional solution to a committee of size k by "dependent rounding". In the case of ∆ ≥ 2 (Theorem 11), we use a swap randomized rounding procedure introduced by [Chekuri et al., 2010]. In the case of ∆ = 1 (Theorem 14) we design a two-layered dependent rounding procedure that runs in linear time. Some of the algorithmic results are achieved by reduction to wellstudied problems, like the monotone submodular maximization problem with ∆-extendible system (Theorem 12) and constrained set multi-cover (Theorem 13). The hardness results follow from reductions from well-known NP-hard problems, including ∆-hypergraph matching, 3-regular vertex cover, constrained set multi-cover and independent set, and borrow techniques from a recent work on fairness for ranking problems [Celis et al., 2018b].

We also study special cases; setting in which the fairness constraints involve only lower bounds (Theorem 13) or only upper bounds (Theorem 12). We further consider a certain specific MS score functions such as SNTV [Cox, 1994], or α-CC and β-CC [Chamberlin and Courant, 1983] where the unconstrained problem has recently received considerable attention. See Table 2 for a summary of these results, and natural corollaries which are described in the full version of the paper [Celis et al., 2017b].

Generality. This approach is general in that 1) it can handle arbitrary MS score functions, 2) multiple sensitive attributes which can take on arbitrary group structures, 3) interval constraints that need not specify exact probabilities of representations for each group, and in doing so 4) can satisfy many different existing notions of fairness.

Note that fairness can be simultaneously ensured across multiple sensitive attributes (e.g., ethnicity and political party) - the number of attributes a single candidate can have is captured by ∆. For example, in the New Zealand parliamentary election [Zealand, 1986] the parliament is required to include sufficient representation across 3 types of attributes: political parties, special interest groups, and Maori representation. Each candidate has an identity under each attribute, i.e., ∆ = 3.

This type of constraints generalize notions of proportionality that have arisen in the voting literature such as fully proportional representation [Monroe, 1995], by letting ℓi = ⌊k·ni/n⌋ and ui = ⌈k·ni/n⌉ for all i. (Here, ni is the number of voters who prefer type i.) Similarly, one can ensure other notions such as degressive proportionality [Koriyama et al., 2013] (e.g., satisfying Penrose's square root law [Penrose, 1946]) and flexible proportionality [Brill et al., ]. In particular, the percent of representation need not be exactly specified, rather one can input an allowable range.

This is also general enough to ensure the outcome satisfies existing notions of fairness, such as disparate impact, statistical parity, and risk difference. For example, consider the case of groups that form a partition, and let mi denote the number of voters that have type i. Given some ξi ∈ [0, 1], for each Pi, we say committee of size k satisfies ξ-statistical parity if ||S∩Pi|/k -mi/n| ≤ ξi (see [Dwork et al., 2012] for the original definition). We can set fairness constraints that guarantee ξ-statistical parity by setting ℓi and ui such that ξi ≥ 1 - max {|ℓi/k - mi/n| , |ui/k - mi/n|} for all i.

Finally, we note that the fair multiwinner voting rule that results after adding fairness constraints continues to satisfy many nice properties (e.g., consistency, monotonicity, and fair variants of weak unanimity or committee monotonicity; see [Elkind et al., 2014] for formal definitions) of the (unconstrained) voting rule. We refer the reader to the full version of this paper for the details [Celis et al., 2017b].

3 Preliminaries

Now we present the formal definition of our model and the definitions of three monotone submodular voting rules: SNTV, α-CC and β-CC, which we consider as special cases.

Definition 1 (Our model: constrained multiwinner voting) We are given a set C of m candidates, n voters together with R = {≻i}i∈[n] where ≻i is the preference list (potentially incomplete and/or non-strict) over the m candidates for voter i, and a score function scoreR : 2[m] → R≥0 with an evaluation oracle, a desired number k ∈ [m] of winners, arbitrary groups P1, . . . , Pp ⊆ C and integers ℓ1, . . . ℓp, u1, . . . up ∈ Z≥0. Given a size-k committee S, define the fairness constraints by ℓi ≤ |S ∩ Pi| ≤ ui, ∀i ∈ [p].

Let B ⊆ 2[m] denote the family of all size-k committees that satisfy all fairness constraints. The goal of the constrained multiwinner voting problem is to select an S ∈ B that maximizes scoreR(S). If the score function is monotone submodular, 1 we call the problem the constrained MS multiwinner voting problem.

If R is clear from the context, we denote scoreR by score. This succinct description of B and score allows us to design fast algorithms despite the fact that B can be exponentially.

For a preference order ≻ and a candidate c ∈ C, we write pos≻(c) to denote the position of c in ≻ (candidate ranked first has position 1 and ranked last has position m). Given a size-k committee S ⊆ C, we denote pos≻(S) := (i1, . . . , ik) to be the sequence of positions of the candidates in S sorted in increasing order with respect to ≻. Define [m]k to be the set of all size-k increasing sequences of elements from [m]. Definition 2 (CC) In the Chamberlin-Courant rule, there exists a positional score function γm : [m] → R satisfying that γm(i) ≥ γm(j) if 1 ≤ i < j ≤ m. Define γm,k(i1, . . . , ik) = maxj∈[k] γm(ij) = γm(i1) for any (i1, . . . , ik) ∈ [m]k. The total score function is defined by score(S) := ∑i∈[n] γm,k (pos≻i (S)).

1 Recall that a function f : 2[m] →R≥0 is a monotone submodular (MS) function if f(A ∪ B) + f(A ∩ B) ≤ f(A) + f(B) for all A, B ⊆ [m] and f(A) ≤ f(B) for all A ⊆ B.

Now we define three CC rules: SNTV, α-CC and β-CC.

Definition 3 The SNTV rule uses the following positional score function: γm(1) = 1 and γm(i) = 0 for i > 1. Observe that SNTV only requires that each ≻i includes the most preferred candidate of voter i.

Definition 4 The α-CC rule uses the following positional score function: γm(i) = 1 for i ≤ k and γm(i) = 0 for i > k. Observe that α-CC only requires that each ≻i includes the top k preferred candidates (without ordering) of voter i.

Definition 5 The β-CC rule uses the following positional score function: γm(i) = m- i.

4 RelatedWork

The study of total score functions and their resulting optimization problems have received much attention in recent years. Often the optimization problem turns out to be NP-hard; both α-CC and β-CC are NP-hard [Procaccia et al., 2008], 1 - 1/e is the best approximation ratio for αCC [Skowron et al., 2015a], the Monroe rule is computationally hard even if the voting parameters are small [Betzler et al., 2013], and the OWA-based rules are hard in general [Skowron et al., 2015b] as are the goalbase rules in various settings [Uckelman et al., 2009]. Hence, one must largely resort to developing approximation algorithms for these problems. Towards this, there has been a rich line of work [Lu and Boutilier, 2011; Skowron et al., 2015a; 2015a; 2015b]. The majority of score functions for multiwinner voting rules that have been studied are monotone submodular. Algorithm design for such score functions have benefitted from theoretical developments in the area of monotone submodular function maximization [Nemhauser et al., 1978; Calinescu et al., 2011].

Some recent work also considers aspects of fairness in voting. Goalbase score functions, which specify an arbitrary set of logic constraints and let the score capture the number constraints satisfied [Uckelman, 2010; Uckelman et al., 2009], could be used to ensure fairness. However, there are no known efficient algorithms to solve goalbase functions. Some recent literature studies single-winner voting in the multiattribute setting; see the survey of Lang and Xia [2016]. The bi-apportionment model can handle up to two attributes (often political party and district) [Serafini and Simeone, 2012; Lari et al., 2014]. Another related model is called constraint approval voting (CAP), with constraints on the numbers of winners from different categories of candidates, proposed by Brams [1990] and Potthoff [1990]. However, there is no efficient algorithm since the input in CAP is exponentially large in the number of attributes. Lang and Skowron [2016] also consider the problem of committee selection with multiple partitions; however, the goal is to produce a committee close to a given target composition of attributes as opposed to maximizing a score function.

More generally, our results contribute to the growing set of algorithms that incorporate fairness constraints to counter algorithmic bias in fundamental algorithmic problems such as classification [Dwork et al., 2012; Zemel et al., 2013; Zafar et al., 2017b; 2017a], sampling [Celis et al., 2016; 2017a; 2018a], ranking [Celis et al., 2018b; Yang and Stoyanovich, 2017] and personalization [Celis and Vishnoi, 2017]. Independently of this paper, [Bredereck et al., 2018] also propose a model for multiwinner voting with a type of fairness constraints (referred to as diversity constraints).

5 Hardness Results

Here we outline hardness results for the constrained multiwinner voting problem; we refer the reader to the full version of this paper for the formal proofs [Celis et al., 2017b]. We first address the complexity of the feasibility problem. Recall that ∆ is the maximum number of groups in which a candidate can be. When a candidate may be part of 3 or more groups, just the feasibility problem can become NPhard; even under mild feasibility conditions.

Theorem 6 (NP-hardness of feasibility: ∆ ≥ 3) The constrained multiwinner voting feasibility problem is NP-hard

for any ∆ ≥ 3, even if all ℓi = 0 or all ui = |Pi|.

The proof uses a reduction from two NP-hard problems ∆- hypergraph matching problem [Hazan et al., 2003] and the 3-regular vertex cover problem [Alimonti and Kann, 1997].

Furthermore, the next two theorems show that the feasibility problem remains hard even if one allows the size of the committee or the fairness constraints to be violated.

Theorem 7 (Hardness of feasibility with committee size violation) Let ui = |Pi| for all i ∈ [p]. For any ε > 0, the following gap version of the constrained multiwinner voting feasibility problem is NP-hard: 1) Output YES if the input instance is feasible. 2) Output NO if there is no feasible solution of size less than (1 - ε)k ln p.

The proof uses a reduction from the constrained set multicover problem, which is hard to approximate [Berman et al., 2004].

Theorem 8 (Hardness of feasibility with fairness violations) Assume ℓi = 0 for each i ∈ [p]. For every θ > 1, the following violation variant of the constrained multiwinner voting feasibility problem is NP-hard: 1) Output YES if the input instance is feasible. 2) Output NO if there is no solution S of size k such that |S ∩ Pi| ≤ θui for all i ∈ [p].

The proof relies on an inapproximability result for independent set [Zuckerman, 2006].

Lastly, we show that even if the constrained multiwinner voting instance is feasible, the hardness does not go away.

Theorem 9 (Inapproximability for feasible instances) A feasible constrained multiwinner voting problem that satisfies ℓi = 0 for each i ∈ [p] is NP-hard to approximate within a factor of Ω(log∆/∆).

The reduction is from maximum ∆-hypergraph matching, which is hard to approximate within a factor of Ω(log∆/∆) [Hazan et al., 2003] and works even when the scoring function is the SNTV rule.

6 Algorithmic Results

Here we present our algorithmic results for the constrained multiwinner voting problem and sketch the proofs; we refer the reader to the full version of this paper for the complete proofs [Celis et al., 2017b]. We first recall the notion of "multilinear extension".

Definition 10 (Multilinear extension) Given a monotone submodular function f : {0, 1}m → R≥0, the multilinear extension F : [0, 1]m → R≥0 is defined as follows: For y = (y1, . . . , ym) ∈ [0, 1]m, denote ˆ y to be a random vector in {0, 1}m where the jth coordinate is independently rounded to 1 with probability yj or 0 otherwise. Then we let F (y) = E [f (ˆ y)] = ∑R⊆[m] f (R) ∏i∈R yi ∏j /∈R(1 - yj ).

Define B ⊆ 2[m] as the family of all committees of size k that satisfy the fairness constraints. Denote the polytope B := {y ∈ [0, 1]m | ∑i∈[m] yi = k; ℓj ≤ ∑i∈Pj yi ≤ uj, ∀j ∈ [m]} to be the set of all vectors that satisfy the cardinality constraint and all fairness constraints. Let F : [0, 1]m → R≥0 denote the multilinear extension of the total score function score. Let OPT be the optimal score of the constrained MS multiwinner voting problem.

6.1 The Case of ∆≥ 2

Theorem 8 implies that it may be hard to find a committee only violating the fairness constraints by a small amount when ∆ ≥ 3. The following theorem shows that a constant approximation solution can be achieved that violates all fairness constraints by at most a multiplicative factor for feasible instances. By taking the violation factors into account, the desired fairness can be achieved by setting tighter constraints.

Theorem 11 (Bi-criterion algorithm when ∆ ≥ 2) Consider a feasible constrained MS multiwinner voting instance with OPT ≫ Ω(1). Let L := mini∈[p] ℓi and U := mini∈[p] ui. Assume 2√lnp/√U ≤ 1. There exists a randomized polynomial-time algorithm that outputs a committee S of size k with score at least (1-1/e-o(1))OPT with constant probability, and S satisfies the following for all i ∈ [p]:

The approximation ratio is 1 - o(1) for the SNTV rule.

Before presenting the proof sketch, we discuss the assumption and the consequences of Theorem 11. First, the assumption OPT ≫ Ω(1) is reasonable for several voting rules, such as the CC rule, the OWA-based rule, and the Monore rule. This is due to the fact that, if enough (e.g., at least n/10) voters have at least one representative in the optimal committee, then the total score of these rules is at least n/10.

Under reasonable assumptions, the violation in fairness constraints in the above theorem can be seen to be small. First, assume that no group is too small: |Pi| ≥ 0.15m ∀i ∈ [m]. Groups corresponding to gender, ethnicity and political opinions are often large. Combining this with the following conditions: k ≫ 100 lnp, and ℓi ≈ k (|Pi|/m- 0.05) , ui ≥ k (|Pi|/m + 0.05) for all i ∈ [p], we observe that 2√ln p/√L ≪ 0.66 is a small number. Similarly, we can check that 2√lnp/√U ≪ 0.45 = Ω(1) is also a small number. Thus, the violation of the group-fairness condition by Theorem 11 is small. We expect such algorithmic solutions to be deployed for the development of automated systems, such as movie selection on the airplane and news recommendation for websites, for which the above assumptions are natural.

Proof Sketch [of Theorem 11] We first obtain a fractional solution y ∈ B by the continuous greedy algorithm in [Calinescu et al., 2011, Section 3.1]. It follows that F(y) ≥ (1 - 1/e)OPT ≫ Ω(1) by [Calinescu et al., 2011, Appendix A]. Next, we run the randomized swap rounding algorithm in [Chekuri et al., 2010] and obtain a size-k committee S. By [Chekuri et al., 2010, Theorem 2.1], we have E [score(S)] ≥ F(y) ≥ (1 - 1/e)OPT, and for any i ∈ [p] and any δ1, δ2 > 0, Pr [|S ∩ Pi| ≤ (1 - δ1)ℓi] ≤ e-ℓiδ2 1 /2 , Pr [|S ∩ Pi| ≥ (1 + δ2)ui] ≤ (eδ2/(1+δ2)1+δ2 )ui .

Let δ1 = 2√ln p/√L and δ2 = 2√ln p/√U. Then by applying the union bound, we can show that S satisfies Equation (1) with probability at least 1-2/√p. On the other hand, we have for any δ > 0, Pr [score(S) ≤ (1- θ)F(y)] ≤ e-F(y)θ2 /8 by [Chekuri et al., 2010, Theorem 2.2]. Let θ = 0.01. Since F (y) ≫ Ω(1), we have score(S) ≥ (1 - 1/e - 0.01)OPT with probability 1 - o(1). ✷

We now present the algorithmic results when there are only upper/lower fairness constraints. We first consider the case that all ℓi = 0, i.e., each group is only required not to be over-represented. We call an algorithm (γ, θ)-approximation (γ ∈ [0, 1], θ ≥ 1) if the algorithm outputs a γ-approximate solution S such that |S ∩ Pi| ≤ θ · ui, ∀i ∈ [p].

Theorem 12 (Bi-criterion algorithm when ℓi = 0) Consider the constrained MS multiwinner voting problem satisfying ℓi = 0 for all i ∈ [p]. Suppose we have a feasible solution ˆ S in advance. For any 0 < ε < 1, the following claims hold: 1) There exists a (1/∆+1, 2)-approximation algorithm that runs in O(mk/∆) time. 2) Suppose ui ≥ 6 log p/ε2 and k ≥ 6 log p/ε2 . There exists a polynomialtime (1 - 1/e - O(ε), 2)-approximation algorithm.

The assumption that we have a feasible solution ˆ S is often satisfied and does not add computational overhead under natural conditions on the data. For instance, let ai denote the number of candidates that belong exclusively to group i. Then, if ai > ℓi for all i and ∑i min{ai, ui} > k, a feasible solution exists and can be found in linear time via a greedy algorithm.

Proof Sketch [of Theorem 12] Define B′ to be the collection of committees that have at most k candidates and satisfy all fairness constraints. For the first claim, we can prove that (C, B′ ) is a ∆-extendible system Since score is monotone submodular, we reduce the problem of finding argmaxS∈B′ score(S) to the monotone submodular maximization problem with ∆-extendible system, which has a (1/∆+1)-approximation algorithm in O(mk/∆) time by [Feldman et al., 2017, Theorem 1]. Therefore, we can compute a committee S1 ∈ B′ with score(S1) ≥ (1/∆+1)OPT in O(mk/∆) time by [Feldman et al., 2017, Theorem 1]. Then from ˆ S \ S1, we arbitrarily select a set S2 ⊆ ˆ S of k - |S1| candidates. We can verify that S1 ∪ S2 is a (1/∆+1, 2)-approximation solution.

For the second claim, we compute y ∈ (1 - ε)B′ :=

{S ⊆ C : |S| ≤ (1 - ε)k; |S ∩ Pi| ≤ (1 - ε)ui, ∀i ∈ [p]}. Then we round y to a committee S1 using the swap randomized rounding procedure in [Chekuri et al., 2010]. By [Chekuri et al., 2010, Theorem 5.2], S1 can be guaranteed to be in B′ , and score(S1) ≥ (1 - 1/e - O(ε))OPT . Then by the same argument as in the first claim, we can obtain a (1 - 1/e - O(ε), 2)-approximation solution. ✷ We now present the result for the case when we only have lower bound constraints, i.e., the upper bound constraints ui = |Pi| for all i ∈ [p]. Further, we assume that a committee of size o(k/ ln∆) satisfying all fairness constraints exists, which is reasonable since, in practice, ∆ roughly represents the number of attributes, like gender and ethnicity. Though there may exist many groups, the number of attributes is usually limited.

Theorem 13 (Approximation algorithm when ui = |Pi|) Given a constrained multiwinner voting instance satisfying ui = |Pi| for all i ∈ [p] with a promise that a size-o(k/ ln∆) committee satisfying all fairness constraints exists, there exists a (1 - 1/e - o(1))-approximation algorithm.

6.2 The Case of ∆= 1

In this section, we consider the case ∆ = 1, i.e., Pi ∩ Pj = ∅ for all 1 ≤ i < j ≤ p and prove the following theorem.

Theorem 14 (Algorithm for ∆ = 1) Given a feasible constrained MS multiwinner voting instance with ∆ = 1, there exists a randomized polynomial-time (1 - 1/e)- approximation algorithm.

Algorithm DegreeOne.

1. Compute a fractional solution y ∈ B by the continuous greedy algorithm in [Calinescu et al., 2011, Section 3.1].
2. For j ∈ [p], iteratively do the following until Pj has at most 1 non-integral coordinate: Arbitrarily select two candidates ci, ci′ ∈ Pj with fractional coordinates yi, yi′ . Let δ1 = min{1- yi, yi′} and δ2 = min{yi, 1- yi′}. Let ei = (0, . . . , 0, 1, 0, . . . , 0) ∈ {0, 1}m. Construct two vectors y1 = y+δ1(ei-ei′ ) and y2 = y+δ2(ei′ -ei). Let y ← y1 with probability δ2/δ1+δ2 and y ← y2 otherwise.

1. W.l.o.g., assume y1, . . . , yγ are the remaining fractional coordinates. Iteratively do the same procedure as in Step 2 until y becomes an integral solution.
2. Output S whose indicator vector is y = 1S.

Proof Sketch [of Theorem 14] It is not hard to verify the feasibility of S and the running time. For the approximation ratio, we have F(y) ≥ (1 - 1/e)OPT in Step 1 by [Calinescu et al., 2011, Appendix A]. Then by [Calinescu et al., 2011, Section 2.1], we can prove that E [F(y)] ≥ F(y) for each iteration of Step 2 and 3. Thus, we conclude that E[score(S)] ≥ F (y) ≥ (1 - 1/e)OP T . ✷

7 Empirical Results

We compare the performance of winning committees without fairness constraints and with fairness constraints, under several commonly used MS multiwinner voting rules. We assume that the voter preferences are generated according to a twodimensional Euclidean model as in [Schofield, 2007] which suggests that voters' political opinions can be described sufficiently well in two dimensions. Multiwinner voting rules may introduce or exacerbate bias in such preference models. We show that the fairness constraints can prevent this, and moreover, the score attained by the fair result is close to the score attained by the optimal unconstrained (and hence, biased) committee.

7.1 Setup

Voting Rules. We consider five MS multiwinner voting rules: SNTV, Bloc, k-Borda, α-CC and β-CC. The definitions of SNTV, α-CC and β-CC appear in Section 3. Bloc outputs the k candidates that have the most voters listing them in the top k of their list. k-Borda outputs the k candidates with the largest sum of the Borda scores (Definition 5) that she receives from all voters. As a baseline, we also consider the Random voting rule that simply selects a committee uniformly at random. In all cases, we let k = 12 be the size of the desired committee.

Sampling Candidates, Voters and Preferences. We generate 400 voters and 120 candidates where each voter and candidate is represented by a point in the [-3, 3] × [-3, 3] square. 1/4 of the voters are sampled uniformly at random from each quadrant, and 1/3 of the candidates are sampled uniformly from the first quadrant, 1/4 the second quadrant, 1/6 the third quadrant, and 1/4 the fourth quadrant. As in [Elkind et al., 2017], we use Euclidean preferences; given a pair of candidates ci, cj ∈ R2 , a voter a ∈ R2 prefers ci to cj if d (ci, a) < d (cj , a) where d (·, ·) is the Euclidean distance.

Groups and Fairness Constraints. We consider each quadrant to be a different group, and let Pi be the collection of candidates in the i-th quadrant. We compare the performance of three different types of constraints to the unconstrained optimal solution and the random baseline.

• Proportional w.r.t. voters: the number of winners is proportional to the number of voters in each quadrant.
• Proportional w.r.t. candidates: The number of winners is proportional to the number of candidates in each quadrant.
• Relax: The number of winners in each quadrant is allowed to be anywhere in the range between what would be proportional to voters and proportional to candidates.

Metrics. As ametic of fairness, we consider the Gini index, a well-studied metric for inequality: Let p be the total number of groups, and let ni be the number of winners in each group Pi, then the Gini index is defined to be ∑pi=1 ∑pj=1 |ni-nj | 2p ∑pi=1 nj . This measures, on a scale from 0 to 1, how disproportionate the distribution of winners is amongst the groups (here, quadrants), with 1 meaning complete inequality and 0 meaning complete equality. In this context, the Gini index should be interpreted relationally, observing how different methods and constraints change the index up or down, as opposed to thinking of it as prescribing a correct outcome.

In addition, for each voting method we measure the price of fairness, i.e., the ratio between its score and the optimal unconstrained score. A ratio close to 100% indicates that despite adding fairness constraints the method attains close to an optimal score.

7.2 Results

We report the mean and the standard deviation of the Gini index, and the mean of the score ratio of 1000 repetitions in Table 3, and, as an example, depict the outcome of 1000 repetitions for the Bloc rule in Figure 1.

Unconstrained rules introduce bias. We observe that there can be bias in the unconstrained voting rules as the Gini index is large; in particular, for several rules, the inequality is larger than that of a random set of candidates suggesting that underlying disproportionalities in the set of candidates can be exacerbated by certain rules. The intuition is that having many candidates in the same quadrant thins their supporters due to competition, leading to disproportionately fewer representatives as winners.

For α-CC and β-CC, the unconstrained Gini index is close to that the Gini index when constraints are placed to be proportional with respect to candidates. However, the standard deviation in both cases is 0.06, which suggests that there can be significant bias in some outcomes of this process. The constrained process, on the other hand, will always satisfy the corresponding Gini index exactly.

The fairness constraints allow us to fix a particular distribution of winners (and hence corresponding Gini index), in this case either proportional with respect to voters or candidates, and hence allows us to de-bias the result in any desired manner. The result of the relaxed constraints, which allow the distribution of winners within these ranges vary with some rules tending towards proportionality with respect to voters and others with respect to candidates.

The price of fairness is small. Because the feasible space of committees becomes smaller in the constrained settings, the optimal constrained score may be less than its unconstrained counterpart. However, in Table 3 we observe that the fairness constraints do not decrease the score by much; in fact for the α-CC or β-CC rules the score does not decrease at all. 2 This is not just a matter of there being many good committees; indeed a random committee in these settings does not performwell in comparison. Hence, the "price of fairness" is small in this setting; understanding this quantity more generally remains an important direction for future work.

8 Conclusion

In this paper, we propose a general model for multiwinner voting that can handle arbitrary MS score functions, can simultaneously ensure fairness across multiple sensitive attributes and can satisfy many different existing notions of fairness. We also develop efficient approximation algorithms for our model in different settings. The empirical results show that our model indeed eliminates bias compared to unconstrained voting, with a controlled price of fairness.