# On the Complexity of Finding a Diverse and Representative Committee using a
Monotone, Separable Positional Multiwinner Voting Rule

Kunal Relia
New York University, USA
<EMAIL_ADDRESS>This work was supported, in part, by Julia Stoyanovich’s NSF
grants No. 1934464 and 1916505.

###### Abstract

Fairness in multiwinner elections, a growing line of research in computational
social choice, primarily concerns the use of constraints to ensure fairness.
Recent work proposed a model to find a diverse _and_ representative committee
and studied the model’s computational aspects. However, the work gave
complexity results under major assumptions on how the candidates and the
voters are grouped. Here, we close this gap and classify the complexity of
finding a diverse and representative committee using a monotone, separable
positional multiwinner voting rule, conditioned _only_ on the assumption that
P $\neq$ NP.

##  1 Introduction

Fairness has recently received particular attention from the computer science
research community. For context, the number of papers that contain the words
“fair” or “fairness” in their titles and are published at top-tier computer
science conferences like NeurIPS and AAAI grew at an average of 38% year on
year since 2018. Moreover, the conference ACM FAccT, formerly known as FAT*,
was established in 2018 to “bring together researchers and practitioners
interested in fairness, accountability, and transparency in socio-technical
systems”. Similarly, there is a growing trend in the Computational Social
Choice (COMSOC) community towards the use of “fairness”111We do not consider
the research on Fair Resource Allocation due to the specificity in the use of
the word “fair”.) (Bredereck et al. 2018; Celis, Huang, and Vishnoi 2018;
Cheng et al. 2019; Hershkowitz et al. 2021; Shrestha and Yang 2019).

However, the term “fairness” is used in varying contexts. For example,
Bredereck _et al._ (2018) and Celis _et al._ (2018) call diversity of
candidates in committee elections as fairness, while Cheng _et al._ (2019)
call representation of voters in committee elections as fairness. Such
context-specific use of the term narrates an incomplete story. Hence, Relia
(2022) unified the framework using the DiRe Committee model that combines the
use of diversity and representation constraints.

In line with the conceptual difference, the use of constraints leads to setups
of multiwinner elections that are technically different. For instance,
diversity constraint is a property of candidates and representation constraint
is a property of voters. The use of these constraints are mathematically as
different as the regularity and uniformity properties of hypergraphs222The
mathematical differences between, say, the vertex cover problem on $d$-regular
hypergraphs and $k$-uniform hypergraphs are well-known (Bansal and Khot 2010;
Feige 2003). Hence, it is important to mathematically delineate the two
notions.

A starting step towards understanding the difference between diversity and
representation is having a classification of complexity of using diversity and
representation constraints in multiwinner elections. The classification of
complexity, while technically interesting and important in itself, enables a
detailed understanding of the nuances that delineate the two notions. Our main
contributions are the complexity results that are based on a singular
assumption that P$\neq$NP.

##  2 Related Work

###  2.1 COMSOC and Classification of Complexity

Computational Social Choice research has particularly focused on classifying
the complexity of a known social choice problem. For instance, Konzcac and
Lang (2005) introduced the problem of voting under partial information. This
led to line of research that aimed to classify the complexity of the problem
of possible winners (candidate is a winner in at least one completion) and
necessary winners (candidate is a winner in all completions) over all pure
positional scoring rules (Baumeister and Rothe 2012; Betzler and Dorn 2010;
Chakraborty and Kolaitis 2021; Kenig 2019; Xia and Conitzer 2011).

###  2.2 Multiwinner Elections, Fairness, and Complexity

Our work primarily builds upon the literature on constrained multiwinner
elections. Fairness from candidate’s perspective is discussed via the use of
diversity constraints over multiple attributes and its use is known to be NP-
hard, which has led to approximation algorithms and matching hardness of
approximation results by Bredereck _et al._ (2018) and Celis _et al._ (2018).
Additionally, 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). On the
other hand, the study of fairness from voters’ perspective pertains the use of
representation constraints (Cheng et al. 2019). 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).

Overall, our work is at the intersection of the interest COMSOC researchers
have on classifying the complexity and fairness in multiwinner elections.
Specifically, our work is the closest to the work by Bredereck _et al._
(2018), Celis _et al._ (2018), Cheng _et al._ (2019) and Relia (2022) but we
differ as we: (i) provide a complete classification of complexity of using
finding a diverse and representative committee using a monotone, separable
positional multiwinner voting rule, (ii) our NP-hardness results hold for
_all_ integer values of attributes, and (iii) our NP-hardness results are
conditioned _only_ on the assumption that P$\neq$NP.

##  3 Preliminaries and Notation

#### Multiwinner Elections.

Let $E=(C,V)$ be an election consisting of a candidate set
$C=\\{c_{1},\dots,c_{m}\\}$ and a voter set $V=\\{v_{1},\dots,v_{n}\\}$, where
each voter $v\in V$ has a preference list $\succ_{v}$ over $m$ candidates,
ranking all of the candidates from the most to the least desired.
$\operatorname{pos}_{v}(c)$ denotes the position of candidate $c\in C$ in the
ranking of voter $v\in V$, where the most preferred candidate has position 1
and the least preferred has position $m$.

Given an election $E=(C,V)$ and a positive integer $k\in[m]$ (for
$k\in\mathbb{N}$, $[k]=\\{1,\dots,k\\}$), a multiwinner election selects a
$k$-sized subset of candidates (or a committee) $W$ using a multiwinner voting
rule $\mathtt{f}$ (discussed later) such that the score of the committee
$\mathtt{f}(W)$ is the highest. We assume ties are broken using a pre-decided
priority order.

#### Candidate Groups.

The candidates have $\mu$ attributes, $A_{1},...,A_{\mu}$, such that
$\mu\in\mathbb{Z}$ and $\mu\geq 0$. Each attribute $A_{i}$, $\forall$
$i\in[\mu]$, partitions the candidates into $g_{i}\in[m]$ groups,
$A_{(i,1)},...,A_{(i,g_{i})}\subseteq C$. Formally, $A_{(i,j)}\cap
A_{(i,j^{\prime})}=\emptyset$, $\forall j,j^{\prime}\in[g_{i}],j\neq
j^{\prime}$. For example, candidates may have race and gender attribute ($\mu$
= 2) with disjoint groups per attribute, male and female ($g_{1}$ = 2) and
Caucasian and African-American ($g_{2}$ = 2). Overall, the set $\mathcal{G}$
of _all_ such arbitrary and potentially non-disjoint groups is
$A_{(1,1)},...,A_{(\mu,g_{\mu})}\subseteq C$.

#### Voter Populations.

The voters have $\pi$ attributes, $A^{\prime}_{1},...,A^{\prime}_{\pi}$, such
that $\pi\in\mathbb{Z}$ and $\pi\geq 0$. The voter attributes may be different
from the candidate attributes. Each attribute $A^{\prime}_{i}$, $\forall$
$i\in[\pi]$, partitions the voters into $p_{i}\in[n]$ populations,
$P_{(i,1)},...,P_{(i,p_{i})}\subseteq V$. Formally, $P_{(i,j)}\cap
P_{(i,j^{\prime})}=\emptyset$, $\forall j,j^{\prime}\in[p_{i}],j\neq
j^{\prime}$. For example, voters may have state attribute ($\pi$ = 1), which
has populations California and Illinois ($p_{1}$ = 2). Overall, the set
$\mathcal{P}$ of _all_ such predefined and potentially non-disjoint
populations will be $P_{(1,1)},...,P_{(\pi,p_{\pi})}\subseteq V$.

Additionally, we are given $W_{P}$, the winning committee $\forall$
$P\in\mathcal{P}$. We limit the scope of $W_{P}$ to be a committee instead of
a ranking of $k$ candidates because when a committee selection rule such as CC
rule is used to determine each population’s winning committee $W_{P}$, then a
complete ranking of each population’s collective preferences is not possible.

#### Multiwinner Voting Rules.

There are multiple types of multiwinner voting rules, also called committee
selection rules. In this paper, we focus on committee selection rules
$\mathtt{f}$ that are based on single-winner positional voting rules, and are
monotone and submodular ($\forall A\subseteq B,f(A)\leq f(B)$ and $f(B)\leq
f(A)+f(B\setminus A)$), and specifically separable. (Bredereck et al. 2018;
Celis, Huang, and Vishnoi 2018). Specifically, 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, $\mathtt{f}$ is
separable if it is submodular and $\mathtt{f}(W)=\sum_{c\in W}\mathtt{f}(c)$
(Bredereck et al. 2018). Monotone and separable selection rules are natural
and are considered good when the goal of an election is to shortlist a set of
individually excellent candidates:

######  Definition 1.

$k$-Borda rule The $k$-Borda rule outputs committees of $k$ candidates with
the highest Borda scores.

##  4 Classification of Complexity

We now study the computational complexity of DRCWD due to the presence of
candidate attributes _and_ voter attributes. Specifically, we establish the
NP-hardness of DRCWD for various settings of $\mu$, $\pi$, and $\mathtt{f}$
via reductions from a single well known NP-hard problem, namely, the vertex
cover problem on 3-regular333A 3-regular graph stipulates that each vertex is
connected to exactly three other vertices, each one with an edge, i.e., each
vertex has a degree of 3. The VC problem on 3-regular graphs is NP-hard.,
2-uniform444A 2-uniform hypergraph stipulates that each edge connects exactly
two vertices. hypergraphs (Garey and Johnson 1979; Alimonti and Kann 1997).

Note that the reductions are designed to conform to the real-world
stipulations of candidate attributes such that (i) each candidate attribute
$A_{i},\forall i\in[\mu]$, _partitions_ all the $m$ 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 across groups of the two attributes
are not the same. For stipulation (ii), note that if two attributes partition
the candidates in the same way and if the lower bounds across groups of the
two attributes are also the same, then mathematically they are identical
attributes that can be combined into one attribute. We use the same
stipulations for voter attributes.

Finally, all our results are based _only_ on the assumption that P$\neq$NP.

######  Theorem 1.

If $\mu=1$, $\forall\pi\in\mathbb{Z}:\pi\geq 1$, and $\mathtt{f}$ is the
monotone, separable function arising from an arbitrary single-winner
positional scoring rule, then DRCWD is NP-hard.

###### Proof Sketch.

The proof extends from the reduction used in the proof of Theorem 5 in (Relia
2022) (full-version). Specifically, we have $m+(n\cdot m)+1$ candidates such
that $m+(n\cdot m)$ from the previous reduction are in one group and we have a
dummy candidate $a$ in the second group. The diversity constraints are set to
1 for both the groups. The voters, voter populations, and rankings are the
same as before except candidate $a$ is ranked first by all the voters. The
representation constraints are set to 2 for all voter populations. The
committee size is set to $k+1$. It is easy to see that the proof of
correctness follows the proof of correctness of Theorem 5 (Relia 2022) (full-
version) with an addition of always selecting the candidate $a$. ∎

######  Theorem 2.

If $\mu=2$, $\forall\pi\in\mathbb{Z}:\pi\geq 1$, and $\mathtt{f}$ is the
monotone, separable function arising from an arbitrary single-winner
positional scoring rule, then DRCWD is NP-hard.

###### Proof Sketch.

We now build upon the reduction used in the proof of Corollary 1. The only
change in the reduction is the addition of the second candidate attribute. In
addition two groups already present under one attribute, we create two more
groups under the second attribute such that the first group contains the $m$
candidates from $C$ and the second group contains $(n\cdot m)+1$ candidates
($(n\cdot m)$ dummy candidates $D$ and 1 dummy candidate $a$). The diversity
constraints are set to 1 for both the groups. The voters, voter populations,
rankings, and the representation constraints are the same as before. The
committee size is again set to $k+1$. It is easy to see that the proof of
correctness follows the proof of correctness of Corollary 1. ∎

######  Theorem 3.

If $\forall\mu\in\mathbb{Z}:\mu\geq 3$ and $\mu$ is an odd number,
$\forall\pi\in\mathbb{Z}:\pi\geq 1$, and $\mathtt{f}$ is the monotone,
separable function arising from an arbitrary single-winner positional scoring
rule, then DRCWD is NP-hard.

###### Proof.

We reduce an instance of vertex cover (VC) problem to an instance of DRCWD.

#### PART I: Construction

#### Candidates:

We have one candidate $c_{i}$ for each vertex $x_{i}\in X$, and
$2\mu^{2}m-7\mu m+2\mu mn+2mn+3m$ dummy candidates $d\in D$ where $m$
corresponds to the number of vertices in the graph $H$, $n$ corresponds to the
number of edges in the graph $H$, and $\mu$ is a positive, odd integer (hint:
the number of candidate attributes). Specifically, we divide the dummy
candidates into two types of blocks:

  * •

Block type $B_{1}$ consists of $m\mu-3m$ blocks and each block consists of
three sets of candidates:

    * –

Set $T_{1}$ consists of single dummy candidate, $d_{i,1}^{T_{1}}\in T_{1}$,
$\forall$ $i\in[1,$ $m\mu-3m]$.

    * –

Set $T_{2}$ consists of $\mu-1$ dummy candidates, $d_{i,j}^{T_{2}}\in T_{2}$,
$\forall$ $i\in[1,$ $m\mu-3m]$, $j\in[1,$ $\mu-1]$.

    * –

Set $T_{3}$ consists of $\mu-1$ dummy candidates, $d_{i,j}^{T_{3}}\in T_{3}$,
$\forall$ $i\in[1,$ $m\mu-3m]$, $j\in[1,$ $\mu-1]$.

  * •

Block type $B_{2}$ consists of $2mn$ blocks and each block consists of one set
of candidates:

    * –

Set $T_{4}$ consists of $\mu+1$ dummy candidates, $d_{i,j}^{T_{4}}\in T_{4}$,
$\forall$ $i\in[1,$ $2mn]$, $j\in[1,$ $\mu+1]$.

Hence, there are $(m\mu-3m)\cdot(1+\mu-1+\mu-1)$ dummy candidates in blocks of
type $B_{1}$ and $(2mn)\cdot(\mu+1)$ dummy candidates in blocks of type
$B_{2}$. This results in a total of $2\mu^{2}m-7\mu m+3m$ dummy candidates of
type $B_{1}$ and $2\mu mn+2mn$ dummy candidates of type $B_{2}$. Thus, $|D|$ =
$2\mu^{2}m-7\mu m+2\mu mn+2mn+3m$. Note that the types of blocks and sets
discussed above are different and independent from the candidate groups
(discussed later) that are used to enforce diversity constraints.

Overall, we set $A$ = {$c_{1},\dots,c_{m}$} and the dummy candidate set $D$ =
{$d_{1},\dots,d_{2\mu^{2}m-7\mu m+2\mu mn+2mn+3m}$}. Hence, the candidate set
$C$ = $A\cup D$ is of size $|C|=$ $2\mu^{2}m-7\mu m+2\mu mn+2mn+4m$
candidates.

#### Committee Size:

We set the target committee size to be $k+m\mu^{2}+2mn\mu-3m\mu$.

#### Candidate Groups:

We now divide the candidates in $C$ into groups such that each candidate is
part of $\mu$ groups as there are $\mu$ candidate attributes.

Candidates in $A$: Each edge $e\in E$ that connects vertices $x_{i}$ and
$x_{j}$ correspond to a candidate group $G\in\mathcal{G}$ that contains two
candidates $c_{i}$ and $c_{j}$. As our reduction proceeds from a 3-regular
graph, each vertex is connected to three edges. This corresponds to each
candidate $c\in A$ having three attributes and thus, belonging to three
groups.

Additionally, each candidate $c\in A$ is part of $\mu-3$ groups where each
group is with the one candidate from Set $T_{1}$ of block type $B_{1}$.
Specifically, candidate $c_{i}$ forms a group each with $d_{j,1}^{T_{1}}\in
T_{1}$ : $j\in[1+(i-1)(\mu-3),$ $i(\mu-3)]$. Hence, as each one of the $m$
candidates form $\mu-3$ groups, we have a total of $m(\mu-3)=m\mu-3m$ blocks
of type $B_{1}$ consisting of $m(\mu-3)$ candidates in Set $T_{1}$. Overall,
each candidate $c\in A$ has $\mu$ attributes and is part of $\mu$ groups.

$v_{1}^{1}$, …, $v_{1}^{n}$ | $c_{i_{1}}\succ c_{j_{1}}$ | $\succ$ | $U_{2}$ | $\succ$ | $U_{3}$ | $\succ$ | $U_{4}^{v_{1}}$ | $\succ$ | $U_{5}^{v_{1}}$ | $\succ$ | $U_{6}^{v_{1}}$ | $\succ$ | $U_{7}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$v_{2}^{1}$, …, $v_{2}^{n}$ | $c_{j_{1}}\succ c_{i_{1}}$ | $\succ$ | $U_{2}$ | $\succ$ | $U_{3}$ | $\succ$ | $U_{4}^{v_{2}}$ | $\succ$ | $U_{5}^{v_{2}}$ | $\succ$ | $U_{6}^{v_{2}}$ | $\succ$ | $U_{7}$
$v_{3}^{1}$, …, $v_{3}^{n}$ | $c_{i_{2}}\succ c_{j_{2}}$ | $\succ$ | $U_{2}$ | $\succ$ | $U_{3}$ | $\succ$ | $U_{4}^{v_{3}}$ | $\succ$ | $U_{5}^{v_{3}}$ | $\succ$ | $U_{6}^{v_{3}}$ | $\succ$ | $U_{7}$
$v_{4}^{1}$, …, $v_{4}^{n}$ | $c_{j_{2}}\succ c_{i_{2}}$ | $\succ$ | $U_{2}$ | $\succ$ | $U_{3}$ | $\succ$ | $U_{4}^{v_{4}}$ | $\succ$ | $U_{5}^{v_{4}}$ | $\succ$ | $U_{6}^{v_{4}}$ | $\succ$ | $U_{7}$
⋮ |  |  |  |  |  |  |  |  |  |  |  |  |
$v_{2n-1}^{1}$, …, $v_{2n-1}^{n}$ | $c_{i_{n}}\succ c_{j_{n}}$ | $\succ$ | $U_{2}$ | $\succ$ | $U_{3}$ | $\succ$ | $U_{4}^{v_{2n-1}}$ | $\succ$ | $U_{5}^{v_{2n-1}}$ | $\succ$ | $U_{6}^{v_{2n-1}}$ | $\succ$ | $U_{7}$
$v_{2n}^{1}$, …, $v_{2n}^{n}$ | $c_{j_{n}}\succ c_{i_{n}}$ | $\succ$ | $U_{2}$ | $\succ$ | $U_{3}$ | $\succ$ | $U_{4}^{v_{2n}}$ | $\succ$ | $U_{5}^{v_{2n}}$ | $\succ$ | $U_{6}^{v_{2n}}$ | $\succ$ | $U_{7}$

Table 1: An instance of preferences of voters created in the reduction for the
proof of Theorem 3.

Candidates of Block type $B_{1}$: Each candidate in the block type $B_{1}$ has
$\mu$ attributes and are grouped as follows:

  * •

Each dummy candidate $d_{j,1}^{T_{1}}\in T_{1}$ : $j\in[1+(i-1)(\mu-3),$
$i(\mu-3)]$ is in the same group as candidate $c_{i}\in A$. Additionally, it
is also in $\mu-1$ groups, individually with each of $\mu-1$ dummy candidates,
$d_{j,o}^{T_{2}}\in T_{2}$, $\forall o\in[1,$ $\mu-1]$. Thus, the each dummy
candidate $d_{j,1}^{T_{1}}\in T_{1}$ has $\mu$ attributes and is part of $\mu$
groups.

  * •

For each dummy candidate $d_{j,i}^{T_{2}}\in T_{2}$ : $j\in[1+(i-1)(\mu-3),$
$i(\mu-3)]$ and $\forall i\in[1,$ $\mu-1]$, it is in the same group as
$d_{j,1}^{T_{1}}$ as described in the previous point. It is also in $\mu-1$
groups, individually with each of $\mu-1$ dummy candidates,
$d_{j,i}^{T_{3}}\in T_{3}$. Thus, each dummy candidate $d_{j,i}^{T_{2}}\in
T_{2}$ has $\mu$ attributes and is part of $\mu$ groups.

  * •

For each dummy candidate $d_{j,i}^{T_{3}}\in T_{3}$ : $j\in[1+(i-1)(\mu-3),$
$i(\mu-3)]$ and $\forall i\in[1,$ $\mu-1]$, it is in $\mu-1$ groups,
individually with each of $\mu-1$ dummy candidates, $d_{j,i}^{T_{2}}\in
T_{2}$, as described in the previous point. Next, note that when $\mu$ is an
odd number, $\mu-1$ is an even number, which means Set $T_{3}$ of each block
has an even number of candidates. We randomly divide $\mu-1$ candidates into
two partitions. Then, we create $\frac{\mu-1}{2}$ groups over one attribute
where each group contains two candidates from Set $T_{3}$ such that one
candidate is selected from each of the two partitions without replacement.
Thus, each pair of groups is mutually disjoint. Thus, each dummy candidate
$d_{j,i}^{T_{3}}\in T_{3}$ is part of exactly one group that is shared with
exactly one another dummy candidate $d_{j^{\prime},i}^{T_{3}}\in T_{3}$ where
$j\neq j^{\prime}$. Overall, this construction results in one attribute and
one group for each dummy candidate $d_{j,i}^{T_{3}}\in T_{3}$. Hence, each
dummy candidate $d_{j,i}^{T_{3}}\in T_{3}$ has $\mu$ attributes and is part of
$\mu$ groups.

Candidates of Block type $B_{2}$: Finally, we assign candidates from the Block
type $B_{2}$ to groups. Each of the dummy candidate in Set $T_{4}$ of each of
the $2mn$ blocks is grouped individually with each of the remaining $\mu$
dummy candidates in Set $T_{4}$ of a block. Formally, $\forall i\in[1,$
$2mn]$, $\forall j\in[1,$ $\mu+1]$, $d_{i,j}^{T_{4}}\in T_{4}$ and $\forall
o\in[1,$ $\mu+1]$, $d_{i,o}^{T_{4}}\in T_{4}$ such that $j\neq o$,
$d_{i,j}^{T_{4}}$ and $d_{i,o}^{T_{4}}$ are in the same group. Hence, each
block consists of $\mu+1$ candidates and each candidate is grouped pairwise
with each of the remaining $\mu$ candidates. This means that each dummy
candidate $d_{i,j}^{T_{4}}\in T_{4}$ has $\mu$ attributes and is part of $\mu$
groups555This setup of Block type $B_{2}$ is analogous to creating $2mn$
$K_{\mu+1}$ graphs, i.e., a total of $2mn$ complete (2-uniform, $\mu$-regular)
(hyper-)graphs, each with $\mu+1$ vertices..

#### Diversity Constraints:

We set the lower bound for each candidate group as follows:

  * •

$l^{D}_{G}=1$ for all $G\in\mathcal{G}$ : $G\cap A\neq\phi$, which corresponds
that each vertex in the vertex cover should be covered by some chosen edge.

  * •

$l^{D}_{G}=1$ for all $G\in\mathcal{G}$ such that at least one of the
following holds:

    * –

$\forall i\in[1,$ $m\mu-3m]$, $G\cap d_{i,1}^{T_{1}}\neq\phi$.

    * –

$\forall i\in[1,$ $m\mu-3m]$, $\forall j\in[1,$ $\mu-1]$, $G\cap
d_{i,j}^{T_{2}}\neq\phi$.

    * –

$\forall i\in[1,$ $m\mu-3m]$, $\forall j\in[1,$ $\mu-1]$, $G\cap
d_{i,j}^{T_{3}}\neq\phi$.

  * •

$l^{D}_{G}=2$ for all $G\in\mathcal{G}$ such that $\forall i\in[1,$ $2mn]$,
$\forall j\in[1,$ $\mu+1]$, $G\cap d_{i,j}^{T_{4}}\neq\phi$ and $\forall
i\in[1,$ $2mn]$, $G\cap d_{i,\mu+1}^{T_{4}}=\phi$.

  * •

$l^{D}_{G}=1$ for all $G\in\mathcal{G}$ such that $\forall i\in[1,$ $2mn]$,
$\forall j\in[1,$ $\mu+1]$, $G\cap d_{i,j}^{T_{4}}\neq\phi$.

In summary, $\forall$ $G\in\mathcal{G}$,

$l^{D}_{G}=\begin{cases}2,&\text{if }\forall i\in[1,2mn],\forall
j\in[1,\mu],G\cap d_{i,j}^{T_{4}}\neq\phi\text{ and }\\\ &\forall
i\in[1,2mn],G\cap d_{i,\mu+1}^{T_{4}}=\phi\\\ 1,&\text{otherwise}\end{cases}$

#### Voters and Preferences:

We now introduce $2n^{2}$ voters, $2n$ voters for each edge $e\in E$. More
specifically, an edge $e\in E$ connects vertices $x_{i}$ and $x_{j}$. Then,
the corresponding $2n^{2}$ voters $v\in V$ rank the candidates as follows:

  * •

First $2$ positions \- Set $U_{1}$ : The top two positions are occupied by
candidates $c_{i}$ and $c_{j}$ that correspond to vertices $x_{i}$ and
$x_{j}$. For voter $v^{b}_{a}$ where $a\in[2n]$ and $b\in[n]$, we denote the
candidates $c_{i}$ and $c_{j}$ as $c_{i_{a}}$ and $c_{j_{a}}$. Note that we
have two voters that correspond to each edge and hence, two voters $v^{b}_{a}$
and $v^{b}_{a-1}$ $\forall a\in[2n]_{\text{even}}$, rank the same two
candidates in the top two positions. Specifically, voter $v^{b}_{a}$ ranks the
two candidates based on the non-increasing order of their indices. Voter
$v^{b}_{a-1}$ ranks the two candidates based on the non-decreasing order of
their indices.

  * •

Next $m\mu^{2}-3m\mu$ positions \- Set $U_{2}$ : All of the $m\mu-3m$ dummy
candidates from Set $T_{1}$ and all of the $m\mu^{2}-4m\mu+3m$ dummy
candidates from Set $T_{3}$ are ranked based on non-decreasing order of their
indices. Note that $m\mu-3m+m\mu^{2}-4m\mu+3m$ = $m\mu^{2}-3m\mu$.

  * •

Next $2mn\mu$ positions \- Set $U_{3}$ : $2mn\mu$ of the $2mn\mu+2mn$ dummy
candidates from Set $T_{4}$ are ranked based on non-decreasing order of their
indices. Specifically, a dummy candidate $d_{o,j}^{T_{4}}$ from Set $T_{4}$ is
selected $\forall o\in[1,$ $2mn]$ and $\forall j\in[1,$ $\mu]$. Note that
dummy candidate from Set $T_{4}$ of the kind $d_{o,\mu+1}^{T_{4}}$, for all
$\forall o\in[1,$ $2mn]$, is not ranked in these positions.

  * •

Next $m$ positions \- Set $U_{4}$ : $m$ out of $2mn$ unranked dummy candidates
from Set $T_{4}$ of the kind $d_{o,\mu+1}^{T_{4}}$, for all $\forall o\in[1,$
$2mn]$, are ranked in the next $m$ positions based on non-decreasing order of
their indices. Specifically, the $m$ candidates that are ranked satisfy
$(o\mod 2n)+1=a$. Note that for each type of voter of the kind $v_{i}$, these
$m$ candidates are distinct as shown below. Hence, for all pairs of voters of
the kind $v_{i},v_{j}\in V:v_{i}\neq v_{j}$, we know that $U_{4}^{v_{i}}\cap
U_{4}^{v_{j}}=\phi$.

  * •

Next $m-2$ positions \- Set $U_{5}$ : The $m-2$ candidates from $A$, which are
not ranked in the top two positions, are ranked based on non-decreasing order
of their indices. Formally, $U_{5}=A\setminus\\{c_{i_{a}},c_{j_{a}}\\}$.

  * •

Next $2mn-m$ positions \- Set $U_{6}$ : $2mn-m$ out of $2mn$ unranked dummy
candidates from Set $T_{4}$ of the kind $d_{o,\mu+1}^{T_{4}}$, for all
$\forall o\in[1,$ $2mn]$, are ranked based on non-decreasing order of their
indices. Specifically, the candidates that are ranked satisfy $(o\mod
2n)+1\neq a$.

  * •

Next $m\mu^{2}-4m\mu+3m$ positions \- Set $U_{7}$ : All of the
$m\mu^{2}-4m\mu+3m$ dummy candidates from Set $T_{2}$ are ranked based on non-
decreasing order of their indices.

More specifically, the voters rank the candidates as shown in Table 1. The
sets without a superscript (e.g., $U_{2}$) denote the candidate rankings that
are the same for all voters.

#### Voter Populations:

We now divide the voters in $V$ into populations such that each voter is part
of $\pi$ populations as there are $\pi$ voter attributes. Specifically, the
voters are divided into disjoint population over one or more attributes when
$\forall\pi\in\mathbb{Z},\pi\geq 1$. The voters are divided into populations
as follows: $\forall x\in[\pi]$, $\forall y\in[2n]$, $\forall z\in[n]$, voter
$v_{y}^{z}\in V$ is part of a population $P\in\mathcal{P}$ such that $P$
contains all voters with the same ($z\mod x$) and $y$. Each voter is part of
$\pi$ populations.

#### Representation Constraints:

We set the lower bound for each voter population as follows: $\forall
P\in\mathcal{P}$, $l^{R}_{P}$ = $1+m\mu^{2}-3m\mu+2mn\mu$.

This completes our construction for the reduction, which is a polynomial time
reduction in the size of $n$ and $m$.

#### PART II: Proof of Correctness

######  Claim 1.

We have a vertex cover $S$ of size at most $k$ that satisfies $e\cap
S\neq\phi$ $\forall$ $e\in E$ if and only if we have a committee $W$ of size
at most $k+m\mu^{2}+2mn\mu-3m\mu$ such that $\forall$ $G\in\mathcal{G}$,
$|G\cap W|\geq l^{D}_{G}$, $\forall$ $P\in\mathcal{P}$, $|W_{P}\cap W|\geq
l^{R}_{P}$, and
$\mathtt{f}(W)=\max_{W^{\prime}\in\mathcal{W}}\mathtt{f}(W^{\prime})$666The
ties are broken based on rankings of the candidate such that higher ranked
candidates are chosen over the lower ranked candidates. Note that with some
trivial changes in voter preferences, we can ensure that there are no ties.
Specifically, we create enough copies of each voter to ensure that each
candidate not in the top $k+m\mu^{2}+2mn\mu-3m\mu$ positions occupy the last
position once. where $\mathcal{W}$ is a set of committees that satisfy all
constraints.

($\Rightarrow$) If the instance of the VC problem is a yes instance, then the
corresponding instance of DRCWD is a yes instance.

#### Diversity constraints are satisfied:

Firstly, each and every candidate group will have at least one of their
members in the winning committee $W$, i.e., $|G\cap W|\geq l^{D}_{G}$ for all
$G\in\mathcal{G}$.

More specifically, for each of the $m\mu-3m$ blocks of type $B_{1}$ of
candidates, we select:

  * •

one dummy candidate from Set $T_{1}$

  * •

all $\mu-1$ dummy candidates from Set $T_{3}$

This helps to satisfy the condition $l^{D}_{G}=1$ for all $G\in\mathcal{G}$
such that at least one of the following holds:

  * •

$\forall i\in[1,$ $m\mu-3m]$, $G\cap d_{i,1}^{T_{1}}\neq\phi$.

  * •

$\forall i\in[1,$ $m\mu-3m]$, $\forall j\in[1,$ $\mu-1]$, $G\cap
d_{i,j}^{T_{2}}\neq\phi$.

  * •

$\forall i\in[1,$ $m\mu-3m]$, $\forall j\in[1,$ $\mu-1]$, $G\cap
d_{i,j}^{T_{3}}\neq\phi$.

Thus, we select $\mu$ candidates from $\mu-3$ blocks for each of the $m$
candidates that correspond to vertices in the vertex cover. This results in
$(\mu\cdot(\mu-3)\cdot m)=m\mu^{2}-3m\mu$ candidates in the committee.

Next, for each of the $2mn$ blocks of type $B_{2}$ of candidates, we select:

  * •

$\mu$ dummy candidates $d_{i,j}^{T_{4}}$ from Set $T_{4}$ such that $i\in[1,$
$2mn]$ and $j\in[1,$ $\mu]$.

This helps to satisfy the conditions : $l^{D}_{G}=2$ for all $G\in\mathcal{G}$
such that $\forall i\in[1,$ $2mn]$, $\forall j\in[1,$ $\mu+1]$, $G\cap
d_{i,j}^{T_{4}}\neq\phi$ and $\forall i\in[1,$ $2mn]$, $G\cap
d_{i,\mu+1}^{T_{4}}=\phi$ and $l^{D}_{G}=1$ for all $G\in\mathcal{G}$ such
that $\forall i\in[1,$ $2mn]$, $\forall j\in[1,$ $\mu+1]$, $G\cap
d_{i,j}^{T_{4}}\neq\phi$. Overall, we select $\mu$ candidates from $2mn$
blocks. This results in additional $2mn\mu$ candidates in the committee.

Finally, for groups that do not contain any dummy candidates, select $k$
candidates $c\in A$ that correspond to $k$ vertices $x\in X$ that form the
vertex cover. These candidates satisfy the remainder of the constraints.
Specifically, these $k$ candidates satisfy $|G\cap W|\geq 1$ for all the
candidate groups that do not contain any dummy candidates. Hence, we have a
committee of size $k+m\mu^{2}+2mn\mu-3m\mu$.

#### Representation constraints are satisfied:

Next, if the instance of the VC problem is a yes instance, then we have a
winning committee $W$ of size $k+m\mu^{2}+2mn\mu-3m\mu$ that consists of $k$
candidates corresponding to the VC and $m\mu^{2}+2mn\mu-3m\mu$ candidates from
Sets $U_{2}$ and $U_{3}$. Also, each and every population’s winning committee,
$W_{P}$ for all $P\in\mathcal{P}$, will have at least
$1+m\mu^{2}-3m\mu+2mn\mu$ of their members in the winning committee $W$ such
that $|W_{P}\cap W|\geq 1+m\mu^{2}-3m\mu+2mn\mu$, for all $P\in\mathcal{P}$,
because:

  * •

as we have a yes instance of the VC problem, one of the two corresponding
candidates occupying the first two positions of the ranking will be on the
committee.

  * •

each of the $m\mu^{2}-3m\mu$ candidates from Set $U_{2}$ will be on the
committee

  * •

each of the $2mn\mu$ candidates from Set $U_{3}$ will be on the committee

By construction, candidates in Set $U_{2}$ and candidates in Set $U_{3}$ will
always be the part of each population’s winning committee. Additionally,
candidates in Set $U_{2}$ are the $\mu$ candidates selected from each of the
$m\mu-3m$ blocks of the type $B_{1}$ and these candidates are the same across
all voter populations. Also, the candidates in Set $U_{3}$ are the $\mu$
candidates selected from each of the $2mn$ blocks of the type $B_{2}$ and
these candidates are the same across all voter populations. Thus, $|W_{P}\cap
W|\geq 1+m\mu^{2}-3m\mu+2mn\mu$, for all $P\in\mathcal{P}$, and the _same_
winning committee $W$ satisfy the diversity constraints _and_ the
representation constraints.

#### Highest scoring committee:

It remains to be shown that $W$ is the highest scoring committee among all the
committees that satisfy the given constraints.

Note that for a given population $P\in\mathcal{P}$, $\forall c\in C$ :
$\operatorname{pos}_{P}(c)=1$ or $\operatorname{pos}_{P}(c)=2$, $\forall
d_{i,j}^{T_{4}}\in$ Set $U_{4}^{P}$, $\forall v\in V$,
$\operatorname{pos}_{v}(c)$ $\succ$ $\operatorname{pos}_{v}(d_{i,j}^{T_{4}})$.
This holds based on the prerequisite condition that we are interested in
committees that satisfy the constraints. Additionally, Set $U_{2}$ $\succ$ Set
$U_{3}$ $\succ$ $d_{i,j}^{T_{4}}$, $\forall d_{i,j}^{T_{4}}\in$ Set $T_{4}$.
This holds because $d_{i,j}^{T_{4}}$ is either in Set $U_{4}$ or Set $U_{6}$,
and even after accounting for varying preferences of these two sets, Sets
$U_{2}$ and $U_{3}$ are always ranked higher. Thus, the contribution of each
candidate in Sets $U_{2}$ and $U_{3}$ to the total score will be greater than
equal to a candidate $d_{i,j}^{T_{4}}$. As noted earlier, the ties are broken
based on ranking. Hence, $W$ will be the highest scoring committee.

Overall, a yes instance of the VC problem implies a yes instance of the DRCWD
problem such that the committee $W$ s of size at most
$k+m\mu^{2}+2mn\mu-3m\mu$, $\forall$ $G\in\mathcal{G}$, $|G\cap W|\geq
l^{D}_{G}$, $\forall$ $P\in\mathcal{P}$, $|W_{P}\cap W|\geq l^{R}_{P}$, and
$\mathtt{f}(W)=\max_{W^{\prime}\in\mathcal{W}}\mathtt{f}(W^{\prime})$.

($\Leftarrow$) The instance of the DRCWD is a yes instance when we have
$k+m\mu^{2}+2mn\mu-3m\mu$ candidates in the committee. This means that each
and every group will have at least one of their members in the winning
committee $W$, i.e., $|G\cap W|\geq l^{D}_{G}$ for all $G\in\mathcal{G}$. Then
the corresponding instance of the VC problem is a yes instance as well. This
is because the $k$ vertices $x\in X$ that form the vertex cover correspond to
the $k$ candidates $c\in A$ that satisfy $|G\cap W|\geq 1$ for all the
candidate groups that do not contain any dummy candidates.

Next, by construction, we know that as a yes instance of the DRCWD problem
satisfies the diversity constraints, each population’s winning committee,
$W_{P}$ for all $P\in\mathcal{P}$, will have at least $l^{R}_{P}$ of their
members in the winning committee $W$, i.e., $|W_{P}\cap W|\geq l^{R}_{P}$ for
all $P\in\mathcal{P}$. Importantly, as the $k+m\mu^{2}+2mn\mu-3m\mu$-sized
committee $W$ also satisfies the diversity constraints, we know that all
candidates from Set $U_{2}$ and Set $U_{3}$ are selected. Additionally, no
candidate from Set $U_{4}$ of each voter population is selected and _at least
one_ of the top 2 ranked candidates from each voter population is selected.
Hence, this means that the corresponding instance of the VC problem is a yes
instance as well. Finally, this committee will be the highest scoring
committee among all the committees that satisfy the constraints. This
completes the other direction of the proof of correctness.

We note that as we are using a separable committee selection rule, computing
scores of candidates takes polynomial time. This completes the overall proof.

∎

The hardness holds even when either all diversity constraints are set to zero
($\forall G\in\mathcal{G}$, $l_{G}^{D}=0$) or all representation constraints
are set to zero ($\forall P\in\mathcal{P}$, $l_{P}^{R}=0$).Finally, we now
show that DRCWD is NP-hard even when either all diversity constraints are set
to zero ($\forall G\in\mathcal{G}$, $l_{G}^{D}=0$) _or_ all representation
constraints are set to zero ($\forall P\in\mathcal{P}$, $l_{P}^{R}=0$).

######  Theorem 4.

If $\forall\mu\in\mathbb{Z}:\mu\geq 3$ and $\mu$ is an even number,
$\forall\pi\in\mathbb{Z}:\pi\geq 1$, and $\mathtt{f}$ is the monotone,
separable function arising from an arbitrary single-winner positional scoring
rule, then DRCWD is NP-hard.

###### Proof Sketch.

The proof follows from the proof of Theorem 3. Hence, we only discuss the
major changes in the construction of the proof.

#### PART I: Construction

#### Candidates:

We have two candidates $c_{i}$ and $c_{m+i}$ for each vertex $x_{i}\in X$, and
$2\cdot(2\mu^{2}m-7\mu m+2\mu mn+2mn+3m)$ dummy candidates $d\in D$ where $m$
corresponds to the number of vertices in the graph $H$, $n$ corresponds to the
number of edges in the graph $H$, and $\mu$ is a positive, even integer (hint:
the number of candidate attributes). We divide the dummy candidates into two
types of blocks in line with the proof of Theorem 3 but there twice the number
of blocks and hence, by transitivity, twice the number of candidates.

#### Committee Size:

We set the target committee size to be $2\cdot(k+m\mu^{2}+2mn\mu-3m\mu)$.

#### Candidate Groups:

We divide the candidates in $C$ into groups such that each candidate is part
of $\mu$ groups as there are $\mu$ candidate attributes. The division is in
line with the proof of Theorem 3 but each set contains twice the number of
candidates and there is one exception. For candidates in Block Type $B_{2}$:

  * •

For each dummy candidate $d_{j}^{T_{3}}\in T_{3}$, it is in $\mu-1$ groups,
individually with each of $\mu-1$ dummy candidates, $d_{i}^{T_{2}}\in T_{2}$,
as described in the previous point. Next, note that when $\mu$ is an even
number, $\mu-1$ is an odd number, which means Set $T_{3}$ has an _odd_ number
of candidates. We randomly divide $\mu-2$ candidates into two partitions.
Then, we create $\frac{\mu-2}{2}$ groups over one attribute where each group
contains two candidates from Set $T_{3}$ such that one candidate is selected
from each of the two partitions without replacement. Thus, each pair of groups
is mutually disjoint. Hence, each dummy candidate $d_{j}^{T_{3}}\in T_{3}$ is
part of exactly one group that is shared with exactly one another dummy
candidate $d_{j^{\prime}}^{T_{3}}\in T_{3}$ where $j\neq j^{\prime}$. Overall,
this construction results in one attribute and one group for all but one dummy
candidate $d_{j}^{T_{3}}\in T_{3}$, which results into a total of $\mu$
attributes and $\mu$ groups for these $\mu-2$ candidates. This is because
$\frac{\mu-2}{2}$ groups can hold $\mu-2$ candidates. Hence, one candidate
still has $\mu-1$ attributes and is part of $\mu-1$ groups. If this block of
dummy candidates is for candidate $c_{i}\in A$, then another corresponding
block of dummy candidates for candidate $c_{m+i}\in A$ will also have one
candidate $d_{z}^{T^{\prime}_{3}}\in T^{\prime}_{3}$ who will have $\mu-1$
attributes and is part of $\mu-1$ groups. We group these two candidates from
separate blocks. Hence, now that one remaining candidate also has $\mu$
attributes and is part of $\mu$ groups. As there is always an even number of
candidates in set $A$ ($|A|=2m$), such cross-block grouping of candidates
among a total of $(\mu-3)\cdot 2m$ blocks, also an even number, is always
possible.

#### Diversity Constraints:

We set the lower bound for each candidate group in line with the proof of
Theorem 3.

#### Voters and Preferences:

We now introduce $4n^{2}$ voters, $4n$ voters for each edge $e\in E$. More
specifically, an edge $e\in E$ connects vertices $x_{i}$ and $x_{j}$. Then,
the corresponding $4n^{2}$ voters $v\in V$ rank the candidates in line with
the proof of Theorem 3 but each set now consists of twice the number of
candidates. Specifically, the major change is in Set $U_{1}$ as it now
consists of $c_{i}$, $c_{j}$, $c_{i+m}$, and $c_{j+m}$.

#### Voter Populations:

We divide the voters into populations in line with the proof of Theorem 3.

#### Representation Constraints:

We set the lower bound for each voter population as follows: $\forall
P\in\mathcal{P}$, $l^{R}_{P}$ = $2\cdot(1+m\mu^{2}-3m\mu+2mn\mu)$.

This completes our construction for the reduction, which is a polynomial time
reduction in the size of $n$ and $m$ in line with the proof of Theorem 3.

#### PART II: Proof of Correctness

######  Claim 2.

We have a vertex cover $S$ of size at most $k$ that satisfies $e\cap
S\neq\phi$ $\forall$ $e\in E$ if and only if we have a committee $W$ of size
at most $2\cdot(k+m\mu^{2}+2mn\mu-3m\mu)$ such that $\forall$
$G\in\mathcal{G}$, $|G\cap W|\geq l^{D}_{G}$, $\forall$ $P\in\mathcal{P}$,
$|W_{P}\cap W|\geq l^{R}_{P}$, and
$\mathtt{f}(W)=\max_{W^{\prime}\in\mathcal{W}}\mathtt{f}(W^{\prime})$777The
ties are broken based on rankings of the candidate such that higher ranked
candidates are chosen over the lower ranked candidates. where $\mathcal{W}$ is
a set of committees that satisfy all constraints.

The proof of correctness easily follows from the proof of correctness of
Theorem 3. ∎

In line with the previous theorem, our reduction holds for a weaker result
such that the hardness holds even when either all diversity constraints are
set to zero ($\forall G\in\mathcal{G}$, $l_{G}^{D}=0$) or all representation
constraints are set to zero ($\forall P\in\mathcal{P}$, $l_{P}^{R}=0$).

##  5 Conclusion

We classified the complexity of finding a diverse and representative committee
using a monotone, separable positional multiwinner voting rule. In doing so,
we established the close association between DRCWD and the vertex problem
problem. This can lead to interesting future work about having an
understanding of the existence of a diverse and representative outcome and
complexity of finding one. Specifically, we can study if DRCWD under certain
realistic assumptions is PPAD-complete or not based on knowledge about the
vertex cover problem and its possible PPAD-completeness (Király and Pap 2013).
Additionally, this association can be used to find realistic settings where
the model becomes tractable and validate it by giving examples of real-world
datasets where such algorithms may work.

## Acknowledgments

I am grateful to Julia Stoyanovich for her insights. I thank Markus Brill,
Benny Kimelfeld, and Phokion G. Kolaitis for many interesting and thought-
provoking questions.

## References

  * Alimonti and Kann (1997) Alimonti, P.; and Kann, V. 1997.  Hardness of approximating problems on cubic graphs.  In _Italian Conference on Algorithms and Complexity_ , 288–298. Springer.
  * Bansal and Khot (2010) Bansal, N.; and Khot, S. 2010.  Inapproximability of hypergraph vertex cover and applications to scheduling problems.  In _International Colloquium on Automata, Languages, and Programming_ , 250–261. Springer.
  * Baumeister and Rothe (2012) Baumeister, D.; and Rothe, J. 2012.  Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules.  _Information Processing Letters_ , 112(5): 186–190.
  * Betzler and Dorn (2010) Betzler, N.; and Dorn, B. 2010.  Towards a dichotomy for the possible winner problem in elections based on scoring rules.  _Journal of Computer and System Sciences_ , 76(8): 812–836.
  * Brams (1990) Brams, S. J. 1990.  Constrained approval voting: A voting system to elect a governing board.  _Interfaces_ , 20(5): 67–80.
  * Bredereck et al. (2018) Bredereck, R.; Faliszewski, P.; Igarashi, A.; Lackner, M.; and Skowron, P. 2018\.  Multiwinner elections with diversity constraints.  In _AAAI_.
  * Celis, Huang, and Vishnoi (2018) Celis, L. E.; Huang, L.; and Vishnoi, N. K. 2018.  Multiwinner voting with fairness constraints.  _In IJCAI_.
  * Chakraborty and Kolaitis (2021) Chakraborty, V.; and Kolaitis, P. G. 2021.  Classifying the Complexity of the Possible Winner Problem on Partial Chains.  In _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems_ , 297–305.
  * Cheng et al. (2019) Cheng, Y.; Jiang, Z.; Munagala, K.; and Wang, K. 2019.  Group fairness in committee selection.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , 263–279.
  * Feige (2003) Feige, U. 2003.  Vertex cover is hardest to approximate on regular graphs.  _Technical Report MCS03–15_.
  * Garey and Johnson (1979) Garey, M. R.; and Johnson, D. S. 1979.  _Computers and intractability_ , volume 174.  Freeman San Francisco.
  * Hershkowitz et al. (2021) Hershkowitz, D. E.; Kahng, A.; Peters, D.; and Procaccia, A. D. 2021.  District-fair participatory budgeting.  _arXiv preprint arXiv:2102.06115_.
  * Kenig (2019) Kenig, B. 2019.  The complexity of the possible winner problem with partitioned preferences.  In _Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems_ , 2051–2053.
  * Király and Pap (2013) Király, T.; and Pap, J. 2013.  PPAD-completeness of polyhedral versions of Sperner’s Lemma.  _Discrete Mathematics_ , 313(15): 1594–1599.
  * Konczak and Lang (2005) Konczak, K.; and Lang, J. 2005.  Voting procedures with incomplete preferences.  In _Proc. IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling_ , volume 20. Citeseer.
  * Potthoff (1990) Potthoff, R. 1990.  Use of linear programming for constrained approval voting.  _Interfaces_ , 20(5): 79–80.
  * Relia (2022) Relia, K. 2022.  DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections.  In _IJCAI-22_.
  * Shrestha and Yang (2019) Shrestha, Y. R.; and Yang, Y. 2019.  Fairness in algorithmic decision-making: Applications in multi-winner voting, machine learning, and recommender systems.  _Algorithms_ , 12(9): 199.
  * Uckelman et al. (2009) Uckelman, J.; Chevaleyre, Y.; Endriss, U.; and Lang, J. 2009.  Representing utility functions via weighted goals.  _Mathematical Logic Quarterly_ , 55(4): 341–361.
  * Xia and Conitzer (2011) Xia, L.; and Conitzer, V. 2011.  Determining possible and necessary winners given partial orders.  _Journal of Artificial Intelligence Research_ , 41: 25–67.