11institutetext: Department of Computer Science and Engineering, University of
North Texas
11email<EMAIL_ADDRESS>22institutetext: Naveen Jindal School of
Management, University of Texas at Dallas
22email<EMAIL_ADDRESS>
# Group Fairness in Non-monotone Submodular Maximization

Jing Yuan 11 0000-0001-6407-834X Shaojie Tang 22 0000-0001-9261-5210

###### Abstract

Maximizing a submodular function has a wide range of applications in machine
learning and data mining. One such application is data summarization whose
goal is to select a small set of representative and diverse data items from a
large dataset. However, data items might have sensitive attributes such as
race or gender, in this setting, it is important to design _fairness-aware_
algorithms to mitigate potential algorithmic bias that may cause over- or
under- representation of particular groups. Motivated by that, we propose and
study the classic non-monotone submodular maximization problem subject to
novel group fairness constraints. Our goal is to select a set of items that
maximizes a non-monotone submodular function, while ensuring that the number
of selected items from each group is proportionate to its size, to the extent
specified by the decision maker. We develop the first constant-factor
approximation algorithms for this problem. We also extend the basic model to
incorporate an additional global size constraint on the total number of
selected items.

##  1 Introduction

Submodular function refers to a broad class of functions which satisfy the
natural diminishing returns property: adding an additional item to a larger
existing subset is less beneficial. A wide range of machine learning and AI
problems, including exemplar-based clustering [7], feature selection [6],
active learning [12], influence maximization in social networks [20],
recommender system [9], and diverse data summarization [19], can be formulated
as a submodular maximization problem. This problem, whose goal is to select a
set of items to maximize a submodular function, and its variants [14, 18] have
been extensively studied in the literature subject to various constraints,
including cardinality, matroid, or knapsack-type restrictions.

We notice that in practise, items or individuals are often associated with
different groups based on various attributes, such as gender, race, age,
religion, or other factors. Existing algorithms might exhibit bias if left
unchecked, for example, some of the groups might be over- or under-represented
in the final selected subset. Therefore, it becomes increasingly important to
design _fairness-aware_ algorithms to mitigate such issues. Towards this end,
we propose and study the classic non-monotone submodular maximization problem
subject to novel group fairness constraints. Our goal is to select a
_balanced_ set of items that maximizes a non-monotone submodular function,
such that the ratio of selected items from each group to its size is within a
desired range, as determined by the decision maker. Non-monotone submodular
maximization has multiple compelling applications, such as feature selection
[6], profit maximization [21], maximum cut [13] and data summarization [16].
Formally, we consider a set $V$ of items (e.g., datapoints) which are
partitioned into $m$ groups: $V_{1},V_{2},\cdots,V_{m}$ such that items from
the same group share same attributes (e.g., gender). We say that a set
$S\subseteq V$ of items is $(\alpha,\beta)$-fair if for all groups $i\in[m]$,
it holds that $\lfloor\alpha|V_{i}|\rfloor\leq|S\cap
V_{i}|\leq\lfloor\beta|V_{i}|\rfloor$. Using our model, it allows for the
decision maker to specify the desired level of fairness by setting appropriate
values of $\alpha$ and $\beta$. Specifically, setting $\alpha=\beta$ leads to
the highest level of fairness in that the number of selected items is
_strictly_ proportional to its group size; if we set $\alpha=0$ and $\beta=1$,
there are no fairness constraints. Our goal is to find such a
$(\alpha,\beta)$-fair subset of items that maximizes a submodular objective
function. Our definition of fairness, which balances solutions with respect to
sensitive attributes, has gained widespread acceptance in the academic
community, as demonstrated by its frequent use in previous studies [4, 10, 5].
There are several other notations of fairness that can be captured by our
formulation such as the $80\%$-rule [1], statistical parity [8] and
proportional representation [17].

###  1.1 Our Contributions

  * •

Our study breaks new ground by examining the classic (non-monotone) submodular
maximization problem under $(\alpha,\beta)$-fairness constraints. Our model
offers flexibility in capturing varying degrees of fairness as desired by the
decision maker, by adjusting the values of $\alpha$ and $\beta$.

  * •

We develop the first constant-factor approximation algorithm for this problem.
We observe that the parameter $\alpha$ is closely linked to the complexity of
solving the $(\alpha,\beta)$-fair non-monotone submodular maximization
problem. In particular, when $\alpha\leq 1/2$, we design a
$\frac{\gamma}{2}$-approximation algorithm and when $\alpha>1/2$, we develop a
$\frac{\gamma}{3}$-approximation algorithm, where $\gamma$ is the
approximation ratio of the current best algorithm for matroid-constrained
submodular maximization. We also extend the basic model to incorporate an
additional global size constraint on the total number of selected items. We
provide approximation algorithms that have a constant-factor approximation
ratio for this extended model.

###  1.2 Additional Related Works

In recent years, there has been a growing awareness of the importance of fair
and unbiased decision-making systems. This has led to an increased interest in
the development of fair algorithms in a wide range of applications, including
influence maximization [25], classification [26], voting [4], bandit learning
[15], and data summarization [3]. Depending on the specific context and the
type of bias that one is trying to mitigate, existing studies adopt different
metrics of fairness. This can lead to different optimization problems and
different fair algorithms that are tailored to the specific requirements of
the application. Our notation of fairness is general enough to capture many
existing notations such as the $80\%$-rule [1], statistical parity [8] and
proportional representation [17]. Unlike most of existing studies on fair
submodular maximization [4] whose objective is to maximize a monotone
submodular function, [10] develop fair algorithms in the context of streaming
non-monotone submodular maximization. Their proposed notation of fairness is
more general than ours, leading to a more challenging optimization problem
which does not admit any constant-factor approximation algorithms. [24, 23]
aim to develop randomized algorithms that satisfy average fairness
constraints. Very recently, [22] extend the studies of fair algorithms to a
more complicated adaptive setting and they propose a new metric of fairness
called group equality.

##  2 Preliminaries and Problem Statement

We consider a set $V$ of $n$ items. There is a non-negative submodular utility
function $f:2^{V}\rightarrow\mathbb{R}_{+}$. Denote by $f(e\mid S)$ the
marginal utility of $e\in V$ on top of $S\subseteq V$, i.e., $f(e\mid
S)=f(\\{e\\}\cup S)-f(S)$. We say a function
$f:2^{V}\rightarrow\mathbb{R}_{+}$ is submodular if for any two sets
$X,Y\subseteq V$ such that $X\subseteq Y$ and any item $e\in V\setminus Y$,

$f(e\mid Y)\leq f(e\mid X).$

Assume $V$ is partitioned into $m$ disjoint groups:
$V_{1},V_{2},\cdots,V_{m}$. We assume that there is a given lower and upper
bound on the fraction of items of each group that must be contained in a
feasible solution. These two bounds, namely $\alpha$ and $\beta$, represent
group fairness constraints. The problem of $(\alpha,\beta)$-fair submodular
maximization problem (labelled as P.0) can be written as follows.

P.0 $\max f(S)$
subject to:
$\lfloor\alpha|V_{i}|\rfloor\leq|S\cap
V_{i}|\leq\lfloor\beta|V_{i}|\rfloor,\forall i\in[m]$.

One can adjust the degree of group fairness in a feasible solution through
choosing appropriate values of $\alpha$ and $\beta$. I.e., strict group
fairness is achieved at $\alpha=\beta$ in which case every feasible solution
must contain the same $\alpha$ fraction of items from each group; if we set
$\alpha=0$ and $\beta=1$, then there is no group fairness constraints. We next
present the hardness result of this problem.

###### Lemma 1

Problem P.0 is NP-hard.

_Proof:_ We prove this through reduction to the classic _cardinality
constrained submodular maximization problem_ which we define below.

###### Definition 1

The input of cardinality constrained submodular maximization problem is a
group of items $U$, a submodular function $h:2^{U}\rightarrow\mathbb{R}_{+}$,
and a cardinality constraint $b$; we aim to select a group of items
$S\subseteq U$ such that $h(S)$ is maximized and $|S|\leq b$.

We next show a reduction from cardinality constrained submodular maximization
problem to P.0. Consider any given instance of cardinality constrained
submodular maximization problem, we construct a corresponding instance of P.0
as follows: Let $V=U$, $f=h$, assume there is only one group, i.e., $V=V_{1}$,
and let $\alpha=0$, $\beta=b/|U|$. It is easy to verify that these two
instances are equivalent. This finishes the proof of the reduction. $\Box$

##  3 Non-monotone Submodular Maximization with Group Fairness

##### Warm-up: Monotone Utility Function

If $f$ is monotone and submodular, we can easily confirm that P.0 can be
simplified to P.1 by removing the lower bound constraints. This is because in
this case, increasing the size of a solution by adding more items will not
decrease its utility. As a result, the lower bound constraints in P.0, which
state that $\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$ for all $i\in[m]$,
can always be met by adding sufficient items to the solution.

P.1 $\max f(S)$
subject to:
$|S\cap V_{i}|\leq\lfloor\beta|V_{i}|\rfloor,\forall i\in[m]$.

Since $f$ is a monotone submodular function, P.1 is a well-known problem of
maximizing a monotone submodular function subject to matroid constraints111A
matroid is a pair $\mathcal{M}=(V,\mathcal{I})$ where $\mathcal{I}\subseteq
2^{V}$ and 1\. $\forall Y\in\mathcal{I},X\subseteq Y\rightarrow
X\in\mathcal{I}$. 2\. $\forall X,Y\in\mathcal{I};|X|<|Y|\rightarrow\exists
e\in Y\setminus X;X\cup\\{e\\}\in\mathcal{I}$.. This problem has a
$(1-1/e)$-approximation algorithm.

We then proceed to develop approximation algorithms for non-monotone
functions. We will examine two scenarios, specifically when $\alpha\leq 1/2$
and when $\alpha>1/2$.

###  3.1 The case when $\alpha\leq 1/2$

In the scenario where $\alpha\leq 1/2$, we use the solution of P.1 as a
building block to construct our algorithm. First, it is easy to verify that
P.1 is a relaxed version of P.0 with lower bound constraints
$\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$ in P.0 being removed. Because
$f$ is a submodular function, P.1 is a classic problem of maximizing a (non-
monotone) submodular function subject to matroid constraints. There exist
effective solutions for P.1. Now we are ready to present the design of our
algorithm as below.

  1. 1.

Apply the state-of-the-art algorithm $\mathcal{A}$ for matroid constrained
submodular maximization to solve P.1 and obtain a solution $A^{P.1}$.

  2. 2.

Note that $A^{P.1}$ is not necessarily a feasible solution to P.0 because it
might violate the lower bound constraints
$\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$ for some groups. To make it
feasible, we add additional items to $A^{P.1}$. Specifically, for each group
$i\in[m]$ such that $|A^{P.1}\cap V_{i}|<\lfloor\alpha|V_{i}|\rfloor$, our
algorithm selects a backup set $B_{i}$ of size
$\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap V_{i}|$, by randomly sampling
$\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap V_{i}|$ items from $V_{i}\setminus
A^{P.1}$. Define $B_{i}=\emptyset$ if $|A^{P.1}\cap
V_{i}|\geq\lfloor\alpha|V_{i}|\rfloor$.

  3. 3.

At the end, add $\cup_{i\in[m]}B_{i}$ to $A^{P.1}$ to build the final solution
$A^{approx}$, i.e., $A^{approx}=A^{P.1}\cup(\cup_{i\in[m]}B_{i})$.

Algorithm 1 Approximation Algorithm for P.0 when $\alpha\leq 1/2$

1: Apply $\mathcal{A}$ to solve P.1 and obtain a solution $A^{P.1}$

2: for every group $i\in[m]$ do

3: if $|A^{P.1}\cap V_{i}|<\lfloor\alpha|V_{i}|\rfloor$ then

4: select a random backup set $B_{i}$ of size
$\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap V_{i}|$ from $V_{i}\setminus
A^{P.1}$

5: else

6: $B_{i}\leftarrow\emptyset$

7: $A^{approx}\leftarrow A^{P.1}\cup(\cup_{i\in[m]}B_{i})$

8: return $A^{approx}$

The pseudocode of this approximation algorithm is given as Algorithm 1.
Observe that $A^{P.1}$ is a feasible solution to P.1, hence, $A^{P.1}$
satisfies upper bound constraints of P.1 and hence P.0, i.e., $|S\cap
V_{i}|\leq\lfloor\beta|V_{i}|\rfloor,\forall i\in[m]$. According to the
construction of $B_{i}$, it is easy to verify that adding
$\cup_{i\in[m]}B_{i}$ to $A^{P.1}$ does not violate the upper bound
constraints because $\cup_{i\in[m]}B_{i}$ are only supplemented to those
groups which do not satisfy the lower bound constraints of P.0, i.e.,
$\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$. Moreover, adding
$\cup_{i\in[m]}B_{i}$ to $A^{P.1}$ makes it satisfy lower bound constraints of
P.0. Hence, $A^{approx}$ is a feasible solution to P.0.

###### Lemma 2

$A^{approx}$ is a feasible solution to P.0.

####  3.1.1 Performance Analysis

We next analyze the performance of Algorithm 1. We first introduce a useful
lemma from [2].

###### Lemma 3

If $f$ is submodular and $S$ is a random subset of $V$, such that each item in
$V$ is contained in $S$ with probability at most $p$, then
$\mathbb{E}_{S}[f(S)]\geq(1-p)f(\emptyset)$.

The next lemma states that if $A^{P.1}$ is a $\gamma$-approximate solution of
P.1, then $f(A^{P.1})$ is at least $\gamma$ fraction of the optimal solution
of P.0.

###### Lemma 4

Suppose $\mathcal{A}$ is a $\gamma$-approximate algorithm for non-monotone
submodular maximization subject to a matroid constraint. Let $OPT$ denote the
optimal solution of P.0, we have $f(A^{P.1})\geq\gamma f(OPT)$.

_Proof:_ Because $\mathcal{A}$ is a $\gamma$-approximate algorithm for non-
monotone submodular maximization subject to a matroid constraint, we have
$f(A^{P.1})\geq\gamma f(O^{P.1})$ where $O^{P.1}$ denotes the optimal solution
of P.1. Moreover, because P.1 is a relaxed version of P.0, we have
$f(O^{P.1})\geq f(OPT)$. Hence, $f(A^{P.1})\geq\gamma f(OPT)$. $\Box$

We next show that augmenting $A^{P.1}$ with items from the random set
$\cup_{i\in[m]}B_{i}$ reduces its utility by a factor of at most $1/2$ in
expectation. Here the expectation is taken over the distribution of
$\cup_{i\in[m]}B_{i}$.

###### Lemma 5

Suppose $\alpha\leq 1/2$, we have
$\mathbb{E}_{A^{approx}}[f(A^{approx})]\geq\frac{1}{2}f(A^{P.1})$ where
$A^{approx}=A^{P.1}\cup(\cup_{i\in[m]}B_{i})$.

_Proof:_ Recall that $B_{i}=\emptyset$ for all $i\in[m]$ such that
$|A^{P.1}\cap V_{i}|\geq\lfloor\alpha|V_{i}|\rfloor$, hence, adding those
$B_{i}$ to $A^{P.1}$ does not affect its utility. In the rest of the proof we
focus on those $B_{i}$ with

$\displaystyle|A^{P.1}\cap V_{i}|<\lfloor\alpha|V_{i}|\rfloor.$ (1)

Recall that for every $i\in[m]$ such that $|A^{P.1}\cap
V_{i}|<\lfloor\alpha|V_{i}|\rfloor$, $B_{i}$ is a random set of size
$\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap V_{i}|$ that is sampled from
$V_{i}\setminus A^{P.1}$. It follows that each item in $V_{i}\setminus
A^{P.1}$ is contained in $B_{i}$ with probability at most

$\displaystyle\frac{\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap
V_{i}|}{|V_{i}\setminus A^{P.1}|}.$ (2)

We next give an upper bound of (2). First,

$\displaystyle\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap
V_{i}|\leq\lfloor\alpha|V_{i}|\rfloor\leq|V_{i}|/2,$ (3)

where the second inequality is by the assumption that $\alpha\leq 1/2$.
Moreover,

$\displaystyle|V_{i}\setminus A^{P.1}|=|V_{i}|-|A^{P.1}\cap
V_{i}|=(\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap
V_{i}|)+(|V_{i}|-\lfloor\alpha|V_{i}|\rfloor)$ (4)
$\displaystyle\geq(\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap
V_{i}|)+|V_{i}|/2,$ (5)

where the inequality is by the assumption that $\alpha\leq 1/2$.

Hence,

$\displaystyle(\ref{eq:haha})\leq\frac{\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap
V_{i}|}{(\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap
V_{i}|)+|V_{i}|/2}\leq\frac{|V_{i}|/2}{|V_{i}|/2+|V_{i}|/2}=1/2,$ (6)

where the first inequality is by (5); the second inequality is by (3) and the
assumption that $\lfloor\alpha|V_{i}|\rfloor-|A^{P.1}\cap V_{i}|>0$ (listed in
(1)). That is, the probability that each item in $V_{i}\setminus A^{P.1}$ is
contained in $B_{i}$ is at most $1/2$. It follows that the probability that
each item in $V\setminus A^{P.1}$ is contained in $\cup_{i\in[m]}B_{i}$ is at
most $1/2$. Moreover, Lemma 3 states that if $f$ is submodular and $S$ is a
random subset of $V$, such that each item in $V$ appears in $S$ with
probability at most $p$, then $\mathbb{E}_{A}[f(A)]\geq(1-p)f(\emptyset)$.
With the above discussion and the observation that $f(A^{P.1}\cup\cdot)$ is
submodular, it holds that
$\mathbb{E}_{A^{approx}}[f(A^{approx})]=\mathbb{E}_{\cup_{i\in[m]}B_{i}}[f(A^{P.1}\cup(\cup_{i\in[m]}B_{i}))]\geq(1-\frac{1}{2})f(A^{P.1}\cup\emptyset)=\frac{1}{2}f(A^{P.1})$.
$\Box$

Our main theorem as below follows from Lemma 4 and Lemma 5.

###### Theorem 3.1

Suppose $\mathcal{A}$ is a $\gamma$-approximate algorithm for non-monotone
submodular maximization subject to a matroid constraint and $\alpha\leq 1/2$,
we have $\mathbb{E}_{A^{approx}}[f(A^{approx})]\geq\frac{\gamma}{2}f(OPT)$.

One option of $\mathcal{A}$ is the continuous double greedy algorithm proposed
in [11] which gives a $1/e-o(1)$-approximation solution, that is, $\gamma\geq
1/e-o(1)$. This, together with Theorem 3.1, implies that
$\mathbb{E}_{A^{approx}}[f(A^{approx})]\geq\frac{1/e-o(1)}{2}f(OPT)$.

###  3.2 The case when $\alpha>1/2$

We next consider the case when $\alpha>1/2$. We first introduce a new utility
function $g:2^{V}\rightarrow\mathbb{R}_{+}$ as below:

$\displaystyle g(\cdot)=f(V\setminus\cdot).$ (7)

We first present a well-known result, which states that submodular functions
maintain their submodularity property when taking their complement.

###### Lemma 6

If $f$ is submodular, then $g$ must be submodular.

With utility function $g$, we present a new optimization problem P.2 as below:

P.2 $\max g(S)$
subject to:
$|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap
V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor,\forall i\in[m]$.

P.2 is a flipped version of the original problem P.0 in the sense that if
there is a $\gamma$-approximate solution $A^{P.2}$ to P.2, it can be easily
verified that $V\setminus A^{P.2}$ is a $\gamma$-approximate solution to P.0.
As a result, we will focus on solving P.2 for the rest of this section.

To solve P.2, we introduce another problem (labeled as P.3) as follows:

P.3 $\max g(S)$
subject to:
$|S\cap V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor,\forall i\in[m]$.

P.3 is relaxed version of P.2 with lower bound constraints
$|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap V_{i}|$ in P.2 being removed.
Because $g$ is a submodular function, P.3 is a classic problem of maximizing a
submodular function subject to matroid constraints. Now we are ready to
present the design of our algorithm.

  1. 1.

Apply the state-of-the-art algorithm $\mathcal{A}$ for matroid constrained
submodular maximization to solve P.3 and obtain a solution $A^{P.3}$.

  2. 2.

Note that $A^{P.3}$ is not necessarily a feasible solution to P.2 because it
might violate the lower bound constraints
$|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap V_{i}|$ for some groups. We add
additional items to $A^{P.3}$ to make it feasible. Specifically, for each
group $i\in[m]$ such that $|A^{P.3}\cap
V_{i}|<|V_{i}|-\lfloor\beta|V_{i}|\rfloor$, our algorithm selects a backup set
$B_{i}$ of size $|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap V_{i}|$, by
randomly sampling $|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap V_{i}|$
items from $V_{i}\setminus A^{P.3}$. Define $B_{i}=\emptyset$ if $|A^{P.1}\cap
V_{i}|\geq|V_{i}|-\lfloor\beta|V_{i}|\rfloor$.

  3. 3.

Add $\cup_{i\in[m]}B_{i}$ to $A^{P.3}$ to build $A^{approx}$, i.e.,
$A^{approx}=A^{P.3}\cup(\cup_{i\in[m]}B_{i})$. Return $V\setminus A^{approx}$
as the final solution.

Algorithm 2 Approximation Algorithm for P.0 when $\alpha>1/2$

1: Apply $\mathcal{A}$ to solve P.3 and obtain a solution $A^{P.3}$

2: for every group $i\in[m]$ do

3: if $|A^{P.3}\cap V_{i}|<|V_{i}|-\lfloor\beta|V_{i}|\rfloor$ then

4: select a random backup set $B_{i}$ of size
$|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap V_{i}|$ from $V_{i}\setminus
A^{P.3}$

5: else

6: $B_{i}\leftarrow\emptyset$

7: $A^{approx}\leftarrow A^{P.3}\cup(\cup_{i\in[m]}B_{i})$

8: return $V\setminus A^{approx}$

The pseudocode of this approximation algorithm is given as Algorithm 2.
Observe that $A^{P.3}$ satisfies upper bound constraints of P.3 and hence P.2
because $A^{P.3}$ is a feasible solution to P.3. According to the construction
of $B_{i}$, adding $\cup_{i\in[m]}B_{i}$ to $A^{P.1}$ does not violate the
upper bound constraints because $\cup_{i\in[m]}B_{i}$ are added to meet the
lower bound constraints of P.2 if necessary. Moreover, adding
$\cup_{i\in[m]}B_{i}$ to $A^{P.3}$ makes it satisfy lower bound constraints of
P.2. Hence, $A^{approx}$ is a feasible solution to P.2.

###### Lemma 7

$A^{approx}$ is a feasible solution to P.2.

####  3.2.1 Performance Analysis

We first introduce a technical lemma which states that if $A^{P.3}$ is a
$\gamma$-approximate solution of P.3, then $f(A^{P.3})$ is at least $\gamma$
fraction of the optimal solution of P.2. This lemma follows from the
observation that P.3 is a relaxation of P.2 .

###### Lemma 8

Suppose $\mathcal{A}$ is a $\gamma$-approximate algorithm for non-monotone
submodular maximization subject to a matroid constraint. Let $O^{P.2}$ denote
the optimal solution of P.2, it holds that $g(A^{P.3})\geq\gamma g(O^{P.2})$.

We next show that augmenting $A^{P.3}$ with items from $\cup_{i\in[m]}B_{i}$
reduces its utility by a factor of at most $2/3$ in expectation.

###### Lemma 9

Suppose $\alpha>1/2$,
$\mathbb{E}_{A^{approx}}[g(A^{approx})]\geq\frac{1}{3}g(A^{P.3})$ where
$A^{approx}=A^{P.3}\cup(\cup_{i\in[m]}B_{i})$.

_Proof:_ Recall that $B_{i}=\emptyset$ for all $i\in[m]$ such that
$|A^{P.3}\cap V_{i}|\geq|V_{i}|-\lfloor\beta|V_{i}|\rfloor$, hence, adding
those $B_{i}$ to $A^{P.3}$ does not affect its utility. Therefore, we focus on
those groups $i\in[m]$ with $|A^{P.3}\cap
V_{i}|<|V_{i}|-\lfloor\beta|V_{i}|\rfloor$ in the rest of the proof. Let
$M=\\{i\mid|A^{P.3}\cap V_{i}|<|V_{i}|-\lfloor\beta|V_{i}|\rfloor\\}$ denote
the set containing the indexes of all such groups and we assume
$M\neq\emptyset$ to avoid trivial cases. We next show that it is safe to
assume $\min_{i\in M}|V_{i}|>1$ without loss of generality, i.e., the smallest
group in $M$ contains at least two items. To prove this, we consider two
cases, depending on the value of $\beta$. If $\beta=1$, then $|A^{P.3}\cap
V_{i}|<|V_{i}|-\lfloor\beta|V_{i}|\rfloor$ does not hold for any group $i$
such that $|V_{i}|=1$, that is, $\min_{i\in M}|V_{i}|>1$. If $\beta<1$, then
according to the group fairness constraints listed in P.0, we are not allowed
to select any items from those groups with $|V_{i}|=1$. Hence, removing all
groups with size one from consideration does not affect the quality of the
optimal solution.

With the assumption that $\min_{i\in M}|V_{i}|>1$, we are now in position to
prove this lemma. Recall that for every $i\in M$, $B_{i}$ is a random set of
size $|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap V_{i}|$ that is sampled
from $V_{i}\setminus A^{P.3}$. It follows that each item in $V_{i}\setminus
A^{P.3}$ appears in $B_{i}$ with probability at most

$\displaystyle\frac{|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap
V_{i}|}{|V_{i}\setminus A^{P.3}|}.$ (8)

We next give an upper bound of (8). Because we assume $\alpha>1/2$, we have
$\beta\geq\alpha>1/2$. This, together with the assumption that $\min_{i\in
M}|V_{i}|>1$, implies that for all $i\in M$,

$\displaystyle|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap
V_{i}|\leq|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq 2|V_{i}|/3.$ (9)

Moreover,

$\displaystyle|V_{i}\setminus A^{P.3}|=|V_{i}|-|A^{P.3}\cap V_{i}|$ (10)
$\displaystyle=(|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap
V_{i}|)+(|V_{i}|-(|V_{i}|-\lfloor\beta|V_{i}|\rfloor))$ (11)
$\displaystyle=(|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap
V_{i}|)+\lfloor\beta|V_{i}|\rfloor$ (12)
$\displaystyle\geq(|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap
V_{i}|)+|V_{i}|/3,$ (13)

where the inequality is by the observation that $\beta>1/2$. It follows that

$\displaystyle(\ref{eq:haha3})\leq\frac{|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap
V_{i}|}{(|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap
V_{i}|)+|V_{i}|/3}\leq\frac{2|V_{i}|/3}{2|V_{i}|/3+|V_{i}|/3}=2/3,$ (14)

where the first inequality is by (13) and the second inequality is by (9) and
the assumption that $|V_{i}|-\lfloor\beta|V_{i}|\rfloor-|A^{P.3}\cap
V_{i}|>0$. That is, each item in $V_{i}\setminus A^{P.3}$ appears in $B_{i}$
with probability at most $2/3$. Lemma 3 and the observation that
$g(A^{P.3}\cup\cdot)$ is submodular imply that
$\mathbb{E}_{A^{approx}}[g(A^{approx})]=\mathbb{E}_{\cup_{i\in[m]}B_{i}}[g(A^{P.3}\cup(\cup_{i\in[m]}B_{i}))]\geq(1-\frac{2}{3})g(A^{P.3}\cup\emptyset)=\frac{1}{3}g(A^{P.3})$.
$\Box$

Lemma 8 and Lemma 9 together imply that

$\mathbb{E}_{A^{approx}}[g(A^{approx})]\geq\frac{1}{3}g(A^{P.3})\geq\frac{\gamma}{3}g(O^{P.2}).$

By the definition of function $g$, we have

$\mathbb{E}_{A^{approx}}[f(V\setminus
A^{approx})]=\mathbb{E}_{A^{approx}}[g(A^{approx})]\geq\frac{\gamma}{3}g(O^{P.2})=\frac{\gamma}{3}f(OPT)$

where the last equality is by the observation that P.2 and P.0 share the same
value of the optimal solution. Hence, the following main theorem holds.

###### Theorem 3.2

Suppose $\mathcal{A}$ is a $\gamma$-approximate algorithm for non-monotone
submodular maximization subject to a matroid constraint and $\alpha>1/2$, we
have $\mathbb{E}_{A^{approx}}[f(V\setminus
A^{approx})]\geq\frac{\gamma}{3}f(OPT)$.

If we adopt the continuous double greedy algorithm [11] as $\mathcal{A}$ to
compute $A^{P.3}$, it gives a $1/e-o(1)$-approximation solution, that is,
$\gamma\geq 1/e-o(1)$. This, together with Theorem 3.2, implies that
$\mathbb{E}_{A^{approx}}[f(V\setminus
A^{approx})]\geq\frac{1/e-o(1)}{3}f(OPT)$.

##  4 Extension: Incorporating Global Cardinality Constraint

In this section, we extend P.0 to incorporate a global cardinality constraint.
A formal definition of this problem is listed in P.A. Our objective is to find
a best $S$ subject to a group fairness constraint $(\alpha,\beta)$ and an
additional cardinality constraint $c$.

P.A $\max f(S)$
subject to:
$\lfloor\alpha|V_{i}|\rfloor\leq|S\cap
V_{i}|\leq\lfloor\beta|V_{i}|\rfloor,\forall i\in[m]$.
$|S|\leq c$.

###  4.1 The case when $\alpha\leq 1/2$

We first consider the case when $\alpha\leq 1/2$. We introduce a new
optimization problem P.B as follows:

P.B $\max f(S)$
subject to:
$|S\cap V_{i}|\leq\lfloor\beta|V_{i}|\rfloor,\forall i\in[m]$.
$\sum_{i\in[m]}\max\\{\lfloor\alpha|V_{i}|\rfloor,|S\cap V_{i}|\\}\leq c$.

It is easy to verify that P.B is a relaxation of P.A in the sense that every
feasible solution to P.A is also a feasible solution to P.B. Hence, we have
the following lemma.

###### Lemma 10

Let $OPT$ denote the optimal solution of P.A and $O^{P.B}$ denote the optimal
solution of P.B, we have $f(O^{P.B})\geq f(OPT)$.

It has been shown that the constraints in P.B gives rise to a matroid [10].
This, together with the assumption that $f$ is a submodular function, implies
that P.B is a classic problem of maximizing a submodular function subject to
matroid constraints. Now we are ready to present the design of our algorithm.

  1. 1.

Apply the state-of-the-art algorithm $\mathcal{A}$ for matroid constrained
submodular maximization to solve P.B and obtain a solution $A^{P.B}$.

  2. 2.

Note that $A^{P.B}$ is not necessarily a feasible solution to P.A because it
might violate the lower bound constraints
$\lfloor\alpha|V_{i}|\rfloor\leq|S\cap V_{i}|$ for some groups. To make it
feasible, we add additional items to $A^{P.B}$. Specifically, for each group
$i\in[m]$ such that $|A^{P.B}\cap V_{i}|<\lfloor\alpha|V_{i}|\rfloor$, our
algorithm selects a backup set $B_{i}$ of size
$\lfloor\alpha|V_{i}|\rfloor-|A^{P.B}\cap V_{i}|$, by randomly sampling
$\lfloor\alpha|V_{i}|\rfloor-|A^{P.B}\cap V_{i}|$ items from $V_{i}\setminus
A^{P.B}$. Define $B_{i}=\emptyset$ if $|A^{P.1}\cap
V_{i}|\geq\lfloor\alpha|V_{i}|\rfloor$.

  3. 3.

At the end, add $\cup_{i\in[m]}B_{i}$ to $A^{P.B}$ to build the final solution
$A^{approx}$, i.e., $A^{approx}=A^{P.B}\cup(\cup_{i\in[m]}B_{i})$.

Algorithm 3 Approximation Algorithm for P.A when $\alpha\leq 1/2$

1: Apply $\mathcal{A}$ to solve P.B and obtain a solution $A^{P.B}$

2: for every group $i\in[m]$ do

3: if $|A^{P.B}\cap V_{i}|<\lfloor\alpha|V_{i}|\rfloor$ then

4: select a random backup set $B_{i}$ of size
$\lfloor\alpha|V_{i}|\rfloor-|A^{P.B}\cap V_{i}|$ from $V_{i}\setminus
A^{P.B}$

5: else

6: $B_{i}\leftarrow\emptyset$

7: $A^{approx}\leftarrow A^{P.B}\cup(\cup_{i\in[m]}B_{i})$

8: return $A^{approx}$

The pseudocode of this approximation algorithm is given as Algorithm 3.
Observe that $A^{P.B}$ satisfies the group-wise upper bound constraints of P.A
because $A^{P.B}$ meets the first set of constraints in P.B. According to the
construction of $B_{i}$, adding $\cup_{i\in[m]}B_{i}$ to $A^{P.B}$ does not
violate the group-wise upper bound constraints of P.A because
$\cup_{i\in[m]}B_{i}$ are added to meet the lower bound constraints of P.A if
necessary. Moreover, adding $\cup_{i\in[m]}B_{i}$ to $A^{P.B}$ does not
violate the global cardinality constraint of P.A because $A^{P.B}$ meets the
second set of constraints in P.B. At last, it is easy to verify that adding
$\cup_{i\in[m]}B_{i}$ to $A^{P.B}$ makes it satisfy the lower bound
constraints of P.A. Hence, $A^{approx}$ is a feasible solution to P.A.

###### Lemma 11

$A^{approx}$ is a feasible solution to P.A.

Following the same proof of Theorem 3.1, we have the following theorem.

###### Theorem 4.1

Suppose $\mathcal{A}$ is a $\gamma$-approximate algorithm for non-monotone
submodular maximization subject to a matroid constraint and $\alpha\leq 1/2$,
we have $\mathbb{E}_{A^{approx}}[f(A^{approx})]\geq\frac{\gamma}{2}f(OPT)$.

###  4.2 The case when $\alpha>1/2$

We next consider the case when $\alpha>1/2$. Recall that
$g(\cdot)=f(V\setminus\cdot)$. We first present a flipped formation of P.A as
below:

P.C $\max g(S)$
subject to:
$|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap
V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor,\forall i\in[m]$.
$|S|\geq n-c$.

Suppose there is a $\gamma$-approximate solution $A^{P.C}$ to P.C, it is easy
to verify that $V\setminus A^{P.C}$ is a $\gamma$-approximate solution to P.A.
We focus on solving P.C in the rest of this section. We first introduce a new
optimization problem (labeled as P.D) as follows:

P.D $\max g(S)$
subject to:
$|S\cap V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor,\forall i\in[m]$.

P.D is relaxed version of P.C with both group-wise lower bound constraints
$|V_{i}|-\lfloor\beta|V_{i}|\rfloor\leq|S\cap V_{i}|$ and global lower bound
constraints $|S|\geq n-c$ in P.C being removed. Hence, we have the following
lemma.

###### Lemma 12

Let $O^{P.C}$ denote the optimal solution of P.C and $O^{P.D}$ denote the
optimal solution of P.D, we have $g(O^{P.D})\geq g(O^{P.C})$.

Recall that if $f$ is submodular, $g$ must be submodular (by Lemma 6). Hence,
P.D is a classic problem of maximizing a submodular function subject to
matroid constraints. We next present the design of our algorithm.

  1. 1.

Apply the state-of-the-art algorithm $\mathcal{A}$ for matroid constrained
submodular maximization to solve P.D and obtain a solution $A^{P.D}$.

  2. 2.

Note that $A^{P.D}$ is not necessarily a feasible solution to P.C because it
might violate the group-wise or the global lower bound constraints of P.C. We
add additional items to $A^{P.D}$ to make it feasible. Specifically, for each
group $i\in[m]$, our algorithm selects a backup set $B_{i}$ of size
$|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap V_{i}|$, by randomly
sampling $|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap V_{i}|$ items from
$V_{i}\setminus A^{P.D}$. Define $B_{i}=\emptyset$ if
$|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap V_{i}|=0$.

  3. 3.

Add $\cup_{i\in[m]}B_{i}$ to $A^{P.D}$ to build $A^{approx}$, i.e.,
$A^{approx}=A^{P.D}\cup(\cup_{i\in[m]}B_{i})$. Return $V\setminus A^{approx}$
as the final solution.

Algorithm 4 Approximation Algorithm for P.A when $\alpha>1/2$

1: Apply $\mathcal{A}$ to solve P.D and obtain a solution $A^{P.D}$

2: for every group $i\in[m]$ do

3: if $|A^{P.D}\cap V_{i}|<|V_{i}|-\lfloor\alpha|V_{i}|\rfloor$ then

4: select a random backup set $B_{i}$ of size
$|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap V_{i}|$ from $V_{i}\setminus
A^{P.D}$

5: else

6: $B_{i}\leftarrow\emptyset$

7: $A^{approx}\leftarrow A^{P.D}\cup(\cup_{i\in[m]}B_{i})$

8: return $V\setminus A^{approx}$

The pseudocode of this approximation algorithm is given as Algorithm 4.
Observe that adding $\cup_{i\in[m]}B_{i}$ to $A^{P.D}$ ensures that each group
contributes exactly $|V_{i}|-\lfloor\alpha|V_{i}|\rfloor$ number of items to
the solution. Because
$n-c\leq\sum_{i\in[m]}(|V_{i}|-\lfloor\alpha|V_{i}|\rfloor)$ (otherwise P.C
does not have a feasible solution), $A^{P.D}\cup(\cup_{i\in[m]}B_{i})$ must
satisfy all constraints in P.C. Hence, we have the following lemma.

###### Lemma 13

$A^{approx}$ is a feasible solution to P.C.

We next analyze the performance of $A^{approx}$. The following lemma states
that adding $\cup_{i\in[m]}B_{i}$ to $A^{P.D}$ reduces its utility by a factor
of at most $2/3$ in expectation.

###### Lemma 14

Suppose $\alpha>1/2$, we have
$\mathbb{E}_{A^{approx}}[g(A^{approx})]\geq\frac{1}{3}g(A^{P.D})$.

_Proof:_ Observe that $B_{i}=\emptyset$ for all $i\in[m]$ such that
$|A^{P.D}\cap V_{i}|=|V_{i}|-\lfloor\alpha|V_{i}|\rfloor$, hence, adding those
$B_{i}$ to $A^{P.D}$ does not affect its utility. Therefore, we focus on those
groups $i\in[m]$ with $|A^{P.D}\cap
V_{i}|<|V_{i}|-\lfloor\alpha|V_{i}|\rfloor$ in the rest of the proof. Let
$Z=\\{i\in[m]\mid|A^{P.D}\cap V_{i}|<|V_{i}|-\lfloor\alpha|V_{i}|\rfloor\\}$
denote the set containing the indexes all such groups. We assume
$Z\neq\emptyset$ to avoid trivial cases. We next show that it is safe to
assume $\min_{i\in Z}|V_{i}|>1$ without loss of generality, i.e., the smallest
group in $Z$ contains at least two items. To prove this, we consider two
cases, depending on the value of $\alpha$. If $\alpha=1$, then $|A^{P.D}\cap
V_{i}|<|V_{i}|-\lfloor\alpha|V_{i}|\rfloor$ does not hold for any group $i$
such that $|V_{i}|=1$. Hence, $\min_{i\in Z}|V_{i}|>1$. If $\alpha<1$, then
according to the group fairness constraints listed in P.A, we are not allowed
to select any items from those groups with $|V_{i}|=1$. Hence, removing all
groups with size one from consideration does not affect the quality of the
optimal solution.

With the assumption that $\min_{i\in Z}|V_{i}|>1$, we are now ready to prove
this lemma. Recall that for every $i\in Z$, $B_{i}$ is a random set of size
$|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap V_{i}|$ that is sampled from
$V_{i}\setminus A^{P.D}$. It follows each item in $V_{i}\setminus A^{P.D}$
appears in $B_{i}$ with probability at most

$\displaystyle\frac{|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap
V_{i}|}{|V_{i}\setminus A^{P.D}|}.$ (15)

We next give an upper bound of (15). Because we assume $\alpha>1/2$ and
$\min_{i\in Z}|V_{i}|>1$, it holds that for all $i\in M$,

$\displaystyle|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap
V_{i}|\leq|V_{i}|-\lfloor\alpha|V_{i}|\rfloor\leq 2|V_{i}|/3.$ (16)

Moreover,

$\displaystyle|V_{i}\setminus A^{P.D}|=|V_{i}|-|A^{P.D}\cap V_{i}|$ (17)
$\displaystyle=(|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap
V_{i}|)+(|V_{i}|-(|V_{i}|-\lfloor\alpha|V_{i}|\rfloor))$ (18)
$\displaystyle=(|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap
V_{i}|)+\lfloor\alpha|V_{i}|\rfloor$ (19)
$\displaystyle\geq(|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap
V_{i}|)+|V_{i}|/3,$ (20)

where the inequality is by the assumptions that $\alpha>1/2$ and $|V_{i}|>1$.
It follows that

$\displaystyle(\ref{eq:haha31})\leq\frac{|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap
V_{i}|}{(|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap
V_{i}|)+|V_{i}|/3}\leq\frac{2|V_{i}|/3}{2|V_{i}|/3+|V_{i}|/3}=2/3,$ (21)

where the first inequality is by (20) and the second inequality is by (16) and
the assumption that $|V_{i}|-\lfloor\alpha|V_{i}|\rfloor-|A^{P.D}\cap
V_{i}|>0$. That is, each item in $V_{i}\setminus A^{P.D}$ appears in $B_{i}$
with probability at most $2/3$. Lemma 3 and the observation that
$g(A^{P.D}\cup\cdot)$ is submodular imply that
$\mathbb{E}_{A^{approx}}[g(A^{approx})]=\mathbb{E}_{\cup_{i\in[m]}B_{i}}[g(A^{P.D}\cup(\cup_{i\in[m]}B_{i}))]\geq(1-\frac{2}{3})g(A^{P.D}\cup\emptyset)=\frac{1}{3}g(A^{P.D})$.
$\Box$

Suppose $\mathcal{A}$ is a $\gamma$-approximate algorithm for non-monotone
submodular maximization subject to a matroid constraint, we have

$\mathbb{E}_{A^{approx}}[g(A^{approx})]\geq\frac{1}{3}g(A^{P.D})\geq\frac{\gamma}{3}g(O^{P.D})$

where the first inequality is by Lemma 14. This, together with $g(O^{P.D})\geq
g(O^{P.C})$ (as proved in Lemma 12), implies that
$\mathbb{E}_{A^{approx}}[g(A^{approx})]\geq\frac{\gamma}{3}g(O^{P.C})$. By the
definition of function $g$, we have

$\mathbb{E}_{A^{approx}}[f(V\setminus
A^{approx})]=\mathbb{E}_{A^{approx}}[g(A^{approx})]\geq\frac{\gamma}{3}g(O^{P.C})=\frac{\gamma}{3}f(OPT)$

where the last equality is by the observation that P.A and P.C share the same
value of the optimal solution. Hence, the following main theorem holds.

###### Theorem 4.2

Suppose $\mathcal{A}$ is a $\gamma$-approximate algorithm for non-monotone
submodular maximization subject to a matroid constraint and $\alpha>1/2$, we
have $\mathbb{E}_{A^{approx}}[f(V\setminus
A^{approx})]\geq\frac{\gamma}{3}f(OPT)$.

##  5 Conclusion

This paper presents a comprehensive investigation of the non-monotone
submodular maximization problem under group fairness constraints. Our main
contribution is the development of several constant-factor approximation
algorithms for this problem. In the future, we plan to expand our research to
explore alternative fairness metrics.

## References

  * [1] Biddle, D.: Adverse impact and test validation: A practitioner’s guide to valid and defensible employment testing. Routledge (2017)
  * [2] Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. pp. 1433–1452. SIAM (2014)
  * [3] Celis, E., Keswani, V., Straszak, D., Deshpande, A., Kathuria, T., Vishnoi, N.: Fair and diverse dpp-based data summarization. In: International Conference on Machine Learning. pp. 716–725. PMLR (2018)
  * [4] Celis, L.E., Huang, L., Vishnoi, N.K.: Multiwinner voting with fairness constraints. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. pp. 144–151 (2018)
  * [5] Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvtiskii, S.: Matroids, matchings, and fairness. In: The 22nd International Conference on Artificial Intelligence and Statistics. pp. 2212–2220. PMLR (2019)
  * [6] Das, A., Kempe, D.: Algorithms for subset selection in linear regression. In: Proceedings of the fortieth annual ACM symposium on Theory of computing. pp. 45–54 (2008)
  * [7] Dueck, D., Frey, B.J.: Non-metric affinity propagation for unsupervised image categorization. In: 2007 IEEE 11th International Conference on Computer Vision. pp. 1–8. IEEE (2007)
  * [8] Dwork, C., Hardt, M., Pitassi, T., Reingold, O., Zemel, R.: Fairness through awareness. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (2012)
  * [9] El-Arini, K., Guestrin, C.: Beyond keyword search: discovering relevant scientific literature. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 439–447 (2011)
  * [10] El Halabi, M., Mitrović, S., Norouzi-Fard, A., Tardos, J., Tarnawski, J.M.: Fairness in streaming submodular maximization: algorithms and hardness. Advances in Neural Information Processing Systems 33, 13609–13622 (2020)
  * [11] Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. pp. 570–579. IEEE (2011)
  * [12] Golovin, D., Krause, A.: Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research 42, 427–486 (2011)
  * [13] Gotovos, A., Karbasi, A., Krause, A.: Non-monotone adaptive submodular maximization. In: Twenty-Fourth International Joint Conference on Artificial Intelligence (2015)
  * [14] Gu, S., Gao, C., Wu, W.: A binary search double greedy algorithm for non-monotone dr-submodular maximization. In: Algorithmic Aspects in Information and Management: 16th International Conference, AAIM 2022, Guangzhou, China, August 13–14, 2022, Proceedings. pp. 3–14. Springer (2022)
  * [15] Joseph, M., Kearns, M., Morgenstern, J.H., Roth, A.: Fairness in learning: Classic and contextual bandits. Advances in neural information processing systems 29 (2016)
  * [16] Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A.: Fast constrained submodular maximization: Personalized data summarization. In: ICML. pp. 1358–1367 (2016)
  * [17] Monroe, B.L.: Fully proportional representation. American Political Science Review 89(4), 925–940 (1995)
  * [18] Shi, G., Gu, S., Wu, W.: k-submodular maximization with two kinds of constraints. Discrete Mathematics, Algorithms and Applications 13(04), 2150036 (2021)
  * [19] Sipos, R., Swaminathan, A., Shivaswamy, P., Joachims, T.: Temporal corpus summarization using submodular word coverage. In: Proceedings of the 21st ACM international conference on Information and knowledge management. pp. 754–763 (2012)
  * [20] Tang, S., Yuan, J.: Influence maximization with partial feedback. Operations Research Letters 48(1), 24–28 (2020)
  * [21] Tang, S., Yuan, J.: Adaptive regularized submodular maximization. In: 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2021)
  * [22] Tang, S., Yuan, J.: Group equility in adaptive submodular maximization. arXiv preprint arXiv:2207.03364 (2022)
  * [23] Tang, S., Yuan, J.: Beyond submodularity: A unified framework of fair subset selection through randomization. In: Under Review (2023)
  * [24] Tang, S., Yuan, J., Mensah-Boateng, T.: Achieving long-term fairness in submodular maximization through randomization. In: Under Review (2023)
  * [25] Tsang, A., Wilder, B., Rice, E., Tambe, M., Zick, Y.: Group-fairness in influence maximization. arXiv preprint arXiv:1903.00967 (2019)
  * [26] Zafar, M.B., Valera, I., Rogriguez, M.G., Gummadi, K.P.: Fairness constraints: Mechanisms for fair classification. In: Artificial intelligence and statistics. pp. 962–970. PMLR (2017)